{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/116235"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/116235","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Fair division of indivisibles: on the computability of maximin share (MMS) allocations","abstract":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-11-15 without embargo terms","abstract_html":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-11-15 without embargo terms","abstract_has_math":false,"creators":["Taki, Setareh"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Industrial Engineering","degree_department":null,"school":null,"contributors":["Garg, Jugal","Chekuri, Chandra","Nagi, Rakesh","Chandrasekaran, Karthekeyan","Mehta, Ruta"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2022,"date_issued":"2022-08","date_published":"2022-08","updated_at":"2026-07-22T22:24:55Z","subjects":["Maximin Share","Fair Division","Algorithmic Game Theory","Approximation Algorithms"],"languages":["en","eng"],"rights":["Copyright 2022 Setareh Taki"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/116235","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Garg, Jugal","Chekuri, Chandra","Nagi, Rakesh","Chandrasekaran, Karthekeyan","Mehta, Ruta"]},{"key":"dc:creator","label":"Author","values":["Taki, Setareh"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2022-08","2022-07-14"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Industrial Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Maximin Share","Fair Division","Algorithmic Game Theory","Approximation Algorithms"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2022 Setareh Taki"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/116235"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-11-15 without embargo terms","The student, Setareh Taki, accepted the attached license on 2022-07-13 at 19:17.","The student, Setareh Taki, submitted this Dissertation for approval on 2022-07-13 at 21:26.","This Dissertation was approved for publication on 2022-07-14 at 16:39.","DSpace SAF Submission Ingestion Package generated from Vireo submission #18294 on 2022-11-15 at 18:20:58","Fair division is a fundamental problem in various multi-agent settings, where the goal is to divide a set of resources among agents in a \\emph{fair} manner. This thesis studies the case where $m$ indivisible items need to be divided among $n$ agents with additive valuations using the popular fairness notion of \\emph{maximin share} (MMS). The maximin value of an agent is the largest value she can guarantee herself if she is allowed to choose a partition of the items into $n$ bundles (one for each agent), on the condition that she receives her least preferred bundle. An MMS allocation provides each agent a bundle worth at least her maximin share. While it is known that such an allocation need not exist~\\cite{procaccia2014fair,kurokawa2016can}, a series of remarkable works~\\cite{procaccia2014fair,KurokawaPW18,amanatidis2017approximation,barman2017approximation, ourpaper} provided approximation algorithms for a $\\tfrac{2}{3}$-MMS allocation in which each agent receives a bundle worth at least $\\tfrac{2}{3}$ times her maximin share. Later, Ghodsi et al.~\\cite{ghodsi2017fair} showed the existence of a $\\tf34$-MMS allocation and a PTAS to find a ($\\tf34-\\epsilon$)-MMS allocation for an $\\epsilon > 0$. Most of the previous works utilize intricate algorithms and require agents' approximate MMS values, which are computationally expensive to obtain. The focus of this thesis is the classic setting of the MMS problem where all items are assumed to be goods (positively valued). The first result in this setting is an alternative $\\tf23$-MMS allocation that offers a simple algorithm and straightforward analysis. In contrast to other algorithms, the approach allows for a simple and intuitive understanding of why it works. Using the intuition built by the simple $\\tf23$-MMS algorithm, we develop a new approach that gives a simple algorithm for showing the existence of a $\\tf34$-MMS allocation. Furthermore, the approach is powerful enough to be easily extended in two directions: First, we get a strongly polynomial time algorithm to find a $\\tf34$-MMS allocation, where we do not need to approximate the MMS values at all. Second, we show that a $(\\tf34+\\tfrac{1}{12n})$-MMS allocation always exists. This considerably improves the approximation guarantee, most notably for small $n$. We note that $\\tf34$ was the best factor known for $n> 4$. To this day, this is the state of the art approximation factor for the MMS problem. Besides the classic setting of MMS, this thesis also covers results on the generalization of the MMS problem. The first aspect is studying the Groupwise MMS (GMMS) problem, which is a stronger notion than MMS. An allocation is GMMS if every sub-allocation is also an MMS allocation. We show an algorithm that obtains $\\tf47$-GMMS allocation after donating at most $n$ items (that were intended to be allocated). Another approach to generalize the MMS problem is to study the MMS problem as mixed manna. In mixed manna, an item can be a good for some agents and a chore (that causes disutility) for others. Specifically, a PTAS to obtain MMS value is investigated. Such PTAS is known for goods (and chores) manna and plays a substantial role in obtaining approximate MMS allocation in several works. In contrast to goods (and chores) manna, for the mixed manna, a recent result by \\cite{Kulkarni2020} showed that finding even an approximate MMS value of an agent up to any approximation factor in $(0,1]$ is NP-hard for general instances. In this thesis, the hardness result is complemented by considering two restricted settings and obtaining a PTAS for each setting. The first restricted setting is when the following conditions hold: $(i)$ the number of agents is a constant, and $(ii)$ for every agent, her absolute value for all items is at least a constant factor of her total (absolute) value for all goods {\\em or} all chores. The second restricted setting is when the absolute value of MMS is at least $1/\\rho$ times either the total value of all goods or the total cost of all chores, for some constant $\\rho \\ge 1$."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Fair division of indivisibles: on the computability of maximin share (MMS) allocations"]}]}],"canonical_facts":{"dc:contributor":["Garg, Jugal","Chekuri, Chandra","Nagi, Rakesh","Chandrasekaran, Karthekeyan","Mehta, Ruta"],"dc:creator":["Taki, Setareh"],"dc:date":["2022-08","2022-07-14"],"dc:description":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-11-15 without embargo terms","The student, Setareh Taki, accepted the attached license on 2022-07-13 at 19:17.","The student, Setareh Taki, submitted this Dissertation for approval on 2022-07-13 at 21:26.","This Dissertation was approved for publication on 2022-07-14 at 16:39.","DSpace SAF Submission Ingestion Package generated from Vireo submission #18294 on 2022-11-15 at 18:20:58","Fair division is a fundamental problem in various multi-agent settings, where the goal is to divide a set of resources among agents in a \\emph{fair} manner. This thesis studies the case where $m$ indivisible items need to be divided among $n$ agents with additive valuations using the popular fairness notion of \\emph{maximin share} (MMS). The maximin value of an agent is the largest value she can guarantee herself if she is allowed to choose a partition of the items into $n$ bundles (one for each agent), on the condition that she receives her least preferred bundle. An MMS allocation provides each agent a bundle worth at least her maximin share. While it is known that such an allocation need not exist~\\cite{procaccia2014fair,kurokawa2016can}, a series of remarkable works~\\cite{procaccia2014fair,KurokawaPW18,amanatidis2017approximation,barman2017approximation, ourpaper} provided approximation algorithms for a $\\tfrac{2}{3}$-MMS allocation in which each agent receives a bundle worth at least $\\tfrac{2}{3}$ times her maximin share. Later, Ghodsi et al.~\\cite{ghodsi2017fair} showed the existence of a $\\tf34$-MMS allocation and a PTAS to find a ($\\tf34-\\epsilon$)-MMS allocation for an $\\epsilon > 0$. Most of the previous works utilize intricate algorithms and require agents' approximate MMS values, which are computationally expensive to obtain. The focus of this thesis is the classic setting of the MMS problem where all items are assumed to be goods (positively valued). The first result in this setting is an alternative $\\tf23$-MMS allocation that offers a simple algorithm and straightforward analysis. In contrast to other algorithms, the approach allows for a simple and intuitive understanding of why it works. Using the intuition built by the simple $\\tf23$-MMS algorithm, we develop a new approach that gives a simple algorithm for showing the existence of a $\\tf34$-MMS allocation. Furthermore, the approach is powerful enough to be easily extended in two directions: First, we get a strongly polynomial time algorithm to find a $\\tf34$-MMS allocation, where we do not need to approximate the MMS values at all. Second, we show that a $(\\tf34+\\tfrac{1}{12n})$-MMS allocation always exists. This considerably improves the approximation guarantee, most notably for small $n$. We note that $\\tf34$ was the best factor known for $n> 4$. To this day, this is the state of the art approximation factor for the MMS problem. Besides the classic setting of MMS, this thesis also covers results on the generalization of the MMS problem. The first aspect is studying the Groupwise MMS (GMMS) problem, which is a stronger notion than MMS. An allocation is GMMS if every sub-allocation is also an MMS allocation. We show an algorithm that obtains $\\tf47$-GMMS allocation after donating at most $n$ items (that were intended to be allocated). Another approach to generalize the MMS problem is to study the MMS problem as mixed manna. In mixed manna, an item can be a good for some agents and a chore (that causes disutility) for others. Specifically, a PTAS to obtain MMS value is investigated. Such PTAS is known for goods (and chores) manna and plays a substantial role in obtaining approximate MMS allocation in several works. In contrast to goods (and chores) manna, for the mixed manna, a recent result by \\cite{Kulkarni2020} showed that finding even an approximate MMS value of an agent up to any approximation factor in $(0,1]$ is NP-hard for general instances. In this thesis, the hardness result is complemented by considering two restricted settings and obtaining a PTAS for each setting. The first restricted setting is when the following conditions hold: $(i)$ the number of agents is a constant, and $(ii)$ for every agent, her absolute value for all items is at least a constant factor of her total (absolute) value for all goods {\\em or} all chores. The second restricted setting is when the absolute value of MMS is at least $1/\\rho$ times either the total value of all goods or the total cost of all chores, for some constant $\\rho \\ge 1$."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/116235"],"dc:language":["en","eng"],"dc:rights":["Copyright 2022 Setareh Taki"],"dc:subject":["Maximin Share","Fair Division","Algorithmic Game Theory","Approximation Algorithms"],"dc:title":["Fair division of indivisibles: on the computability of maximin share (MMS) allocations"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Industrial Engineering"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:55Z"}