Source-linked AI summary
Approximation Algorithms for Computing Maximin Share Allocations
Georgios Amanatidis, Evangelos Markakis, Afshin Nikzad, Amin Saberi
TL;DR
The paper asks how to compute fair maximin share allocations when indivisible goods make exact allocations unavailable. It redesigns approximation algorithms and analyzes special cases and random instances, obtaining a polynomial-time 2/3 approximation, stronger special-case guarantees, and high-probability existence results.
Problem
Indivisible goods do not always admit maximin share allocations, while the best achievable approximation remains difficult to characterize.
Method
The paper redesigns an existing approximation algorithm, studies three-agent and {0,1,2}-valued special cases, and applies probabilistic analysis to random instances.
Results
The paper gives a polynomial-time 2/3-ε approximation for any number of agents, a 7/8 approximation for three agents, an exact algorithm for {0,1,2} values, and high-probability existence in random instances.
Takeaways & Limitations
The results provide stronger approximate or exact guarantees in general, special-case, and randomly generated maximin share settings.
Takeaways & Limitations
Improving beyond the 2/3 approximation appears to require drastically new ideas, and the authors identify it as an open problem.
Abstract
from arXiv · showhide
We study the problem of computing maximin share guarantees, a recently introduced fairness notion. Given a set of $n$ agents and a set of goods, the maximin share of a single agent is the best that she can guarantee to herself, if she would be allowed to partition the goods in any way she prefers, into $n$ bundles, and then receive her least desirable bundle. The objective then in our problem is to find a partition, so that each agent is guaranteed her maximin share. In settings with indivisible goods, such allocations are not guaranteed to exist, so we resort to approximation algorithms. Our main result is a $2/3$-approximation, that runs in polynomial time for any number of agents. This improves upon the algorithm of Procaccia and Wang, which also produces a $2/3$-approximation but runs in polynomial time only for a constant number of agents. To achieve this, we redesign certain parts of their algorithm. Furthermore, motivated by the apparent difficulty, both theoretically and experimentally, in finding lower bounds on the existence of approximate solutions, we undertake a probabilistic analysis. We prove that in randomly generated instances, with high probability there exists a maximin share allocation. This can be seen as a justification of the experimental evidence reported in relevant works. Finally, we provide further positive results for two special cases that arise from previous works. The first one is the intriguing case of $3$ agents, for which it is already known that exact maximin share allocations do not always exist (contrary to the case of $2$ agents). We provide a $7/8$-approximation algorithm, improving the previously known result of $3/4$. The second case is when all item values belong to $\{0, 1, 2\}$, extending the $\{0, 1\}$ setting studied in Bouveret and Lemaître. We obtain an exact algorithm for any number of agents in this case.
1 Introduction
The paper studies approximate maximin share allocations for indivisible goods, where exact guarantees may not exist. It gives polynomial-time approximation algorithms, positive results for special cases, and a probabilistic existence analysis.
- Indivisible goods may prevent fair allocations from existing, and deciding existence can be NP-hard.
- The maximin share is the value an agent can guarantee by partitioning goods into n bundles and receiving the least valuable bundle.
- (2/3 −ε)-approximation runs in polynomial time for any number of agents and goods, improving the prior algorithm’s constant-agent restriction.
- 7/8-approximation improves the previously known 3/4 ratio for three agents.
- Exact maximin share allocations always exist when item values belong to {0,1,2}, for any number of agents.
- Randomly generated instances contain maximin share allocations with high probability, supporting reported experimental evidence.
2 Definitions and Notation
This section formalizes maximin share fairness for additive valuations over indivisible goods. It defines the individual guarantee, the corresponding allocation, and illustrative examples.
- Agents have additive valuations, so each bundle’s value equals the sum of its item values.
- An agent’s n-maximin share is the highest minimum bundle value she can obtain over partitions into n bundles.
- The guarantee is independent of other agents’ valuation functions and does not decrease when one good is removed while reducing the number of bundles.
- An MMS allocation gives every agent a bundle worth at least her maximin share µi(n,M).
- For the three-agent example, the maximin shares are µ1(3,M)=1/2, µ2(3,M)=1/4, and µ3(3,M)=1.
- Maximin share allocations need not always exist, motivating allocations that guarantee a fraction ρ of each agent’s maximin share.
3 Warmup: Some Useful Properties and a Polynomial Time 1/2-approximation
The warmup develops properties of maximin shares and presents a simple polynomial-time 1/2-approximation. Its approach combines preliminary allocation of valuable goods with Greedy Round-Robin.
- A maximin share is bounded above by an agent’s total value divided by the number of agents.
- Greedy Round-Robin achieves an additive approximation with error bounded by the maximum item value vmax.
- The algorithm fixes an agent order and lets agents repeatedly choose their most desirable remaining item.
- The resulting allocation limits each agent’s envy of another bundle to at most vmax.
- The monotonicity property states that allocating one good and reducing the number of bundles does not decrease the remaining agent’s maximin share.
- Algorithm 2 first allocates sufficiently valuable goods, then runs Greedy Round-Robin on the remaining instance to obtain a 1/2-approximation.
4 A Polynomial Time
The section develops a polynomial-time algorithm achieving a 2/3-approximation for maximin share allocations with any number of agents, by redesigning the difficult parts of Procaccia and Wang’s approach. Its recursive matching framework efficiently identifies which agents can be satisfied now and preserves the conditions needed for later calls.
- Main result: 2/3-approximation is achieved in polynomial time for any number of agents and goods.The resulting allocation gives every agent a bundle worth at least 2/3−ε of her maximin share, for any constant ε > 0.
- Main result: The algorithm addresses the exponential dependence on the number of agents in Procaccia and Wang’s earlier 2/3-approximation.The paper identifies the source of exponentiality and changes selected parts of the earlier algorithm.
- Algorithm: APX-MMS first approximates each agent’s maximin value with Woeginger’s PTAS, then invokes the recursive algorithm REC-MMS on the remaining instance.REC-MMS uses approximate values ξ and recursively partitions the unallocated goods among the currently unsatisfied agents.
- Algorithm: REC-MMS uses a bipartite matching to allocate bundles to some agents while reserving the remaining agents and goods for recursive calls.The set X + contains agents not matched in the current call; the other active agents are matched immediately, while X + is handled recursively.
- Matching lemma: The crucial set X + can be found efficiently and supports both the current matching and preservation of the recursive invariant.Lemma 4.5 guarantees an efficiently computable set, a perfect matching for the complementary agents, and preservation of inequality (1) after allocation.
- Limitations: The approximation analysis is tight relative to the known analysis of the density-balance parameter ρn, leaving improvement beyond 2/3 as an open problem.The paper notes that existing lower-bound constructions do not rule out a PTAS.
5 Two Special Cases
The paper improves maximin-share guarantees in two special cases: three agents and valuations in {0,1,2}. It gives a 7/8-approximation for three agents and an exact polynomial-time algorithm for bounded valuations.
- The Case of n = 3 Agents: 7/8−ε is achieved in polynomial time for three agents, improving the previous 3/4 guarantee.The algorithm combines ideas from earlier procedures and examines allowed matchings more deeply.
- The Case of n = 3 Agents: When no large item exists, the first agent partitions the goods and the remaining agents receive bundles through carefully selected matchings and two-agent partitions.The procedure tries the relevant perfect matchings and uses approximate 2-maximin partitions before assigning the remaining bundles.
- The Case of n = 3 Agents: The three-agent algorithm first gives a sufficiently valuable item to one agent when such an item exists, then uses cut-and-choose for the other two.The selected item has value at least 7/8 of the agent’s approximate maximin-share estimate.
- The Case of n = 3 Agents: The three-agent proof establishes that the resulting allocation gives every agent at least a (7/8−ε)-approximation of her maximin share.The analysis covers both the direct allocation branch and the branch using the constructed partitions.
- Values in {0,1,2}: Exact maximin-share allocations can be found in O(nm logm) time when every item value belongs to {0,1,2}.This extends the earlier {0,1} setting without approximation loss.
- Values in {0,1,2}: For bounded valuations, the algorithm starts from initial buckets, identifies agents needing adjustment, and reverses selected rows using a graph-coloring argument.Agents not initially satisfied have specific 1/0 and 2/1 rows; reversing one or both can make them satisfied or right-satisfied.
6 A Probabilistic Analysis
The probabilistic analysis studies random valuation instances and shows that simple round-robin algorithms achieve maximin-share-level guarantees with high probability. The bounds are asymptotically strong but their constants vary substantially across item-to-agent ratios.
- Proof strategy: The probability analysis combines Hoeffding and Chebyshev inequalities with separate estimates for ranges such as 2n ≤ m < 3n and m ≥ 3n.The proof explicitly treats the boundary regime m < 3n more carefully.
- Random instances: The same guarantee is stronger than each agent’s maximin share for m ≥ 2n, by the paper’s comparison between average value and maximin share.The theorem’s value guarantee therefore implies a maximin-share guarantee in this regime.
- Random instances: With probability 1−o(1), Greedy Round-Robin gives every agent at least 1/n of her total value when valuations are i.i.d. uniform on [0,1] and m ≥ 2n.The failure term is O(1/n) for m > 2n and O(logn/n) when m = 2n.
- Random instances: Modified Greedy Round-Robin allocates every agent a bundle worth at least her maximin share with probability 1−o(1) for any m and sufficiently large n.Its failure term is O(1/n) when m > 2n and O(logn/n) when m ≤ 2n.
- Proof strategy: For m < 2n, the analysis uses induction over phase 1 and a high-probability phase-2 guarantee when the remaining instance has exactly twice as many goods as agents.The argument preserves the maximin-share lower bound as agents and goods are removed.
- Bounds and limitations: The bounds are weaker near m = 4n because the general treatment loses constants, although subdividing item-count intervals can improve them.For example, the reported error term is less than 130/n for m = 4n and n > 450, versus less than 8/n for m = 13n when n ≥ 59.
7 Conclusions
The conclusions identify improving the general 2/3-approximation as the main open problem and point to special cases, practical implementation, and truthful mechanisms as further directions.
- Open problems: Improving on the 2/3-approximation remains the paper’s main open question.The authors suggest that surpassing 2/3 may require a substantially different approach.
- Open problems: Better ratios for special cases could provide new insights, including for the two-value setting related to the Santa Claus problem.The cited setting uses additive valuations in which each good has value 0 or v_j.
- Future directions: The paper leaves practical algorithmic evaluation and truthfulness or mechanism-design issues for future work.The conclusions specifically mention practical exploration and truthful mechanisms for more than two agents.