Source-linked AI summary
An Improved Approximation Algorithm for Maximin Shares
Jugal Garg, Setareh Taki
TL;DR
The paper studies approximate maximin-share allocations for indivisible items when exact MMS allocations may not exist and prior methods require costly MMS approximations. It introduces a simpler approach that yields a 3/4-MMS existence result, a strongly polynomial-time 3/4-MMS algorithm without approximating MMS values, and a stronger (3/4 + 1/(12n))-MMS existence guarantee. The paper also identifies a boundary for extending the approach toward 4/5-MMS allocations.
Problem
Exact MMS allocations need not exist, while prior approximation methods use intricate algorithms and computationally expensive approximate MMS values.
Method
The paper develops a simple approach based on greedy assignments and bag-based analysis for constructing and finding approximate MMS allocations.
Results
3/4-MMS allocations exist and can be found by a strongly polynomial-time algorithm without approximating MMS values; (3/4 + 1/(12n))-MMS allocations also always exist.
Takeaways & Limitations
The approximation guarantee improves over the previous factor, with the improvement most notable for small n.
Takeaways & Limitations
Extending the approach to a 4/5-MMS allocation is challenging because the initial greedy assignments would leave 3n high-value items and make bag initialization harder.
Abstract
from arXiv · showhide
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. We study 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). 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, a series of work 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. More recently, Ghodsi et al. [EC'2018] 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. In this paper, we develop a new approach that gives a simple algorithm for showing the existence of a 3/4-MMS allocation. Furthermore, our 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 there always exists a (3/4 + 1/(12n))-MMS allocation, improving the best previous factor. This improves the approximation guarantee, most notably for small n. We note that 3/4 was the best factor known for n> 4.
1 Introduction
The paper studies approximate maximin-share fairness for indivisible items and develops a simpler approach that improves both algorithmic efficiency and the guarantee over prior work.
- Motivation: Maximin share offers a fairness benchmark for indivisible-item allocation, but an allocation satisfying every agent’s exact MMS value need not exist.The paper therefore studies allocations guaranteeing a fraction of each agent’s MMS value.
- Prior limitations: 3/4-MMS allocations were known to exist, but prior existential techniques did not directly provide efficient algorithms and required computationally expensive MMS-value approximations.Finding an agent’s MMS value is NP-hard, although a PTAS exists.
- Algorithmic result: The approach extends to a strongly polynomial-time algorithm for finding a 3/4-MMS allocation without approximating MMS values.The extension uses tentative assignments and repeated MMS upper-bound updates, with total running time O(nm(n^4 + log m)).
- Improved guarantee: The paper also proves existence of a (3/4 + 1/(12n))-MMS allocation, improving the previous factor, especially when the number of agents is small.The same algorithm is retained, while the stronger guarantee requires a more involved analysis using dummy items.
- Approach: The paper introduces a simple greedy-and-bag-filling approach that assigns high-value items first and then completes bundles with low-value items.Greedy assignments reduce the remaining high-value items to at most 2n′, simplifying the allocation process.
2 The MMS Problem and its Properties
The paper formalizes maximin share fairness for allocating indivisible items with additive valuations and develops properties used by its approximation algorithms. It also introduces valid reductions for shrinking instances while preserving the ability to obtain an α-MMS allocation.
- MMS is the maximum value an agent can guarantee from a partition into n bundles when others choose before her.
- An α-MMS allocation gives every agent a bundle worth at least α times her MMS value.
- The paper reviews average upper bounds on MMS and a bag-filling procedure that achieves a (1−β)-MMS allocation when item values are bounded by β after normalization.
- Scaling each agent’s valuations by a positive constant preserves whether an allocation is α-MMS.
- Ordered instances assume all agents rank items in the same order, and any instance can be reduced to this form for α-MMS allocation.
- Reduction: A valid reduction removes items and one agent while ensuring an α-MMS allocation for the smaller instance extends to the original instance.
3 Existence of 3 4-MMS Allocation
The paper gives an algorithmic proof that a 3/4-MMS allocation exists, using normalization, valid reductions for high-value items, and bag filling for the reduced instance. Its reductions guarantee that assigned bundles can be removed while preserving sufficient MMS structure for the remaining agents.
- The algorithm normalizes MMS values to 1, assumes an ordered instance, and combines initial assignment with bag filling.
- Initial Assignment: 4 high-value candidate bundles are considered for initial assignment: S1={1}, S2={n,n+1}, S3={2n−1,2n,2n+1}, and S4={1,2n+1}.
- Initial Assignment: Lemma 3.1 shows that removing the lowest-index candidate bundle valued at least 3/4 by an agent is a valid reduction.
- Initial Assignment: After initial assignment, every remaining agent has MMS value at least 1, although the current MMS value may increase after reductions.
- Bag Filling: Bag filling pairs one item from each high-value group into n bags, then adds remaining items until an unassigned agent values a bag at least 3/4.
- Bag Filling: Agents are divided according to whether they value every initial bag at most 1, and the analysis bounds the extra low-value items needed to complete their bundles.
- Bag Filling: The analysis proves sufficient low-value-item supply for agents in N2 and establishes an MMS-partition bundle with more than 1 value outside the high-value set.
4 Algorithm for 3 4-MMS Allocation
The algorithm obtains a 3/4-MMS allocation in strongly polynomial time without computing agents’ exact MMS values. It uses average values as upper bounds, tentative assignments, bound updates, and bag filling.
- Overview: The algorithm targets a 3/4-MMS allocation without requiring exact MMS values, whose computation is NP-hard.A PTAS exists for MMS computation, but can be impractical for small ε.
- Normalization: The algorithm uses each agent’s average item value as an upper bound on her MMS value.Valuations are normalized so that each agent values the entire item set at n.
- Initial Assignment: Initial assignment has fixed and tentative stages that greedily allocate high-value bundles to qualifying agents.The main algorithmic components are Initial Assignment, Update Upper Bound, and Bag Filling.
- Updating MMS Upper Bound: Tentative assignments are finalized only when they do not reduce any remaining agent’s valuation excessively; otherwise, the relevant MMS upper bound is updated.Agents are classified by their values for initialized bags to identify overestimated bounds.
- Bag Filling and Running Time: The complete algorithm runs in O(n^5m) time for ordered instances and O(nm(n^4 + log m)) time for arbitrary instances.The resulting allocation guarantees 3/4-MMS.
5 Existence of (3 4 + 12n)-MMS Allocation 1
The paper extends its approach to prove a (3/4 + 1/(12n))-MMS allocation for every instance. The analysis uses the same algorithmic framework with dummy items to handle the additional approximation factor.
- Improved Guarantee: The approach proves existence of a (3/4 + 1/(12n))-MMS allocation for every instance.Here γ = 1/(12n), and the proof is algorithmic when MMS values are given.
- Algorithmic Extension: The algorithm runs the earlier procedure with α = 3/4 + γ and uses the extra 1/8 in the analysis to improve the factor.The underlying approach and analysis largely follow the earlier section.
- Dummy Items: Dummy items compensate for the additional loss caused when S4 bundles exceed value 1 for some agents.These items simplify the proof and are not assigned to agents.
- Bag Filling: The bag-filling procedure assigns each remaining agent a bundle valued at least 3/4 + γ under the established conditions.The procedure starts with initialized bags and adds unallocated items until an agent reaches the target value.
6 Conclusions
The paper presents a simple approach for 3/4-MMS allocation and extends it to a strongly polynomial-time algorithm and a stronger (3/4 + 1/(12n))-MMS existence guarantee. It also identifies challenges in extending the approach to 4/5-MMS.
- The approach gives a simple algorithm showing the existence of a 3/4-MMS allocation.
- The same approach yields a strongly polynomial-time algorithm to find a 3/4-MMS allocation.
- The approach establishes existence of a (3/4 + 1/(12n))-MMS allocation and improves the best previous factor.
- The bound 3/4 + 1/(12n) is tight, while extending the approach to 4/5-MMS remains challenging.The challenge arises because initial greedy assignments would leave 3n high-value items, complicating bag initialization and potentially making some bags too valuable.
A Missing Proofs
The proof develops bounds for MMS allocation through average and scale-invariance lemmas, ordered instances, and bundle-based arguments. Its technical analysis supports the paper’s allocation guarantees by controlling bundle values and constructing suitable partitions.
- Foundational properties: Average upper bounds MMS and scale invariance provide foundational properties for analyzing α-MMS allocations.Scaling valuations preserves the allocation guarantee after scaling MMS values by the same factor.
- Ordered instances: Ordered instances can be constructed and converted back in polynomial time while preserving MMS values and allocation guarantees.The conversion sorts item values consistently across agents, and the reverse procedure gives each agent an item at least as valuable as in the ordered allocation.
- Initial assignment and updates: The proof partitions agents by their values for initialized bags and detects when an MMS upper bound is overestimated.Agents are divided into N1, whose value for every bag is at most 1, and N2, consisting of the remaining agents.
- Partition construction: Bundle-rearrangement and greedy bag-filling arguments construct partitions with controlled item values and establish lower bounds for remaining items.The arguments repeatedly redistribute high-value items and fill bags by assigning the highest remaining item to a lowest-value bag.
- Contradiction arguments: The resulting inequalities bound the value of remaining items and rule out premature algorithm termination through contradiction.The analysis combines bounds on assigned bundles, remaining items, and agent-specific quantities such as x_a, l_a, and z.