Title: Fair Division of Indivisibles: On the Computability of Maximin Share (MMS) Allocations
Abstract: 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 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 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 (Kurokawa et al. 2016), a series of remarkable works provided approximation algorithms for a 2/3-MMS allocation in which each agent receives a bundle worth at least 2/3 times her maximin share. Later, Ghodsi et al. 2021 showed the existence of a 3/4-MMS allocation and a PTAS to find a (3/4 - ε)-MMS allocation for an ε > 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 2/3-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 2/3-MMS algorithm, we develop a new approach that gives a simple algorithm for showing the existence of a 3/4-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 3/4-MMS allocation, where we do not need to approximate the MMS values at all. Second, we show that a (3/4+1/12n)-MMS allocation always exists. This considerably improves the approximation guarantee, most notably for small n. We note that 3/4 was the best factor known for n>4. To this day, this is the stat of the art approximation factor for the MMS problem.
Next, the proof of existence for 3/4-MMS allocation is simplified further, which results in improving the approximation factor and giving at least half of the agents a bundle which they value at least 4/5 times their MMS value and the rest will receive 3/4 times their MMS value. This result raises the hope of obtaining an approximate MMS allocation beyond 3/4+1/12n.
Besides the classic setting of MMS, this thesis also covers results in 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 4/7-GMMS allocation after donating at most n items.
Another generalization to the MMS problem is to study the MMS problem is mixed manna where 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 good (and chore) manna and plays a substantial role in obtaining approximate MMS allocation in several works. In contrast to good (and chore) manna, for the mixed manna, a recent result by Kulkarni et al. 2020 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. This thesis complements the hardness result by considering two restricted settings and obtaining a PTAS for each setting. The first restricted setting is when the two following conditions hold: (i) the number of agents is a constant, and (ii) for every agent, her absolute value for all the items is at least a constant factor of her total (absolute) value for all the goods or all the chores. The second restricted setting is when the absolute value of MMS is at least 1/ρ times either the total value of all the goods or the total cost of all the chores for some constant ρ ≥ 1.
