Source-linked AI summary
Approximation Algorithms for Maximin Fair Division
Siddharth Barman, Sanath Kumar Krishnamurthy
TL;DR
The paper asks how to fairly allocate indivisible goods when exact maximin-fair allocations may not exist, especially beyond additive valuations. It develops efficient algorithms and proves a 2/3 guarantee for additive valuations and an approximately 0.21 guarantee for nonnegative, monotone, submodular valuations.
Problem
Exact maximin-fair allocations do not always exist for indivisible goods, motivating efficient multiplicative approximations, particularly for valuation classes beyond additive functions.
Method
The paper uses a simple combinatorial algorithm for additive valuations and a round-robin algorithm analyzed with multilinear extensions for submodular valuations.
Results
The algorithms achieve a 2/3-approximate maximin fair allocation for additive valuations and an approximately 0.21-approximate allocation for nonnegative, monotone, submodular valuations.
Takeaways & Limitations
Approximate maximin fairness can be efficiently obtained for additive valuations and extended to nonnegative, monotone, submodular valuations.
Takeaways & Limitations
Standard rounding techniques do not directly provide the desired guarantee when multiple submodular functions must satisfy maximin requirements simultaneously.
Abstract
from arXiv · showhide
We consider the problem of allocating indivisible goods fairly among n agents who have additive and submodular valuations for the goods. Our fairness guarantees are in terms of the maximin share, that is defined to be the maximum value that an agent can ensure for herself, if she were to partition the goods into n bundles, and then receive a minimum valued bundle. Since maximin fair allocations (i.e., allocations in which each agent gets at least her maximin share) do not always exist, prior work has focused on approximation results that aim to find allocations in which the value of the bundle allocated to each agent is (multiplicatively) as close to her maximin share as possible. In particular, Procaccia and Wang (2014) along with Amanatidis et al. (2015) have shown that under additive valuations a 2/3-approximate maximin fair allocation always exists and can be found in polynomial time. We complement these results by developing a simple and efficient algorithm that achieves the same approximation guarantee. Furthermore, we initiate the study of approximate maximin fair division under submodular valuations. Specifically, we show that when the valuations of the agents are nonnegative, monotone, and submodular, then a 0.21-approximate maximin fair allocation is guaranteed to exist. In fact, we show that such an allocation can be efficiently found by using a simple round-robin algorithm. A technical contribution of the paper is to analyze the performance of this combinatorial algorithm by employing the concept of multilinear extensions.
1 Introduction
The paper studies approximate maximin fairness for indivisible goods, extending prior additive-valuation results to submodular valuations. It provides efficient algorithms with guarantees of 2/3 for additive valuations and approximately 0.21 for nonnegative, monotone, submodular valuations.
- Maximin fairness: Maximin share is the value an agent can guarantee by partitioning goods into n bundles and receiving the least-valued bundle.It provides a fairness threshold for allocations of indivisible goods.
- Scope and motivation: The paper extends maximin fairness beyond additive valuations while addressing fair division settings where exact maximin allocations need not exist.Indivisible goods can prevent exact classical fairness guarantees, motivating multiplicative approximations.
- Additive valuations: 2/3-approximate maximin fairness is achieved in polynomial time for additive valuations using a simple combinatorial algorithm.The algorithm reduces instances to ordered valuations and uses an envy-graph procedure with majorization analysis.
- Submodular valuations: ≈0.21-approximate maximin fairness is guaranteed and efficiently computable for nonnegative, monotone, submodular valuations via a simple round-robin algorithm.The analysis uses multilinear extensions and bounds the value obtained through marginal gains across rounds.
- Chores: 4/3-approximate maximin fairness can be efficiently computed for additive valuations of negatively valued goods, improving the previously best-known 2-approximation.The analysis treats bundles with at least three chores separately from bundles containing at most two chores.
2 Notation and Preliminaries
The paper formalizes allocations of indivisible goods, agent valuations, maximin shares, and approximate maximin fairness. It distinguishes additive from nonnegative monotone submodular valuations and states the paper’s guarantees of 2/3 and 0.21, respectively.
- Additive valuations assign v_i(S) as the sum of agent i’s values for goods in S, with the paper primarily addressing nonnegative goods.
- Nonnegative, monotone, submodular valuations include normalized valuations with diminishing marginal values, and marginal functions preserve submodularity.
- An allocation is an n-partition of the goods, with bundle A_i assigned to agent i; a partial allocation may leave goods unassigned.
- An agent’s n-maximin share is the value she can guarantee by partitioning the goods into n bundles and receiving the least-valued bundle.
- Because exact maximin partitions may not exist, an α-approximate maximin fair allocation gives every agent a bundle worth at least α times her maximin share.
- The paper targets α = 2/3 for additive valuations and α = 0.21 for submodular valuations.
3 Additive Valuations
For additive valuations, the paper reduces allocation to ordered instances and gives a simple polynomial-time algorithm achieving the established maximin-share approximation guarantee.
- Main result: 2n/(3n−1)-approximate maximin fair allocations can be found in polynomial time for additive valuations.The guarantee is vi(Ai) ≥ 2n/(3n−1) µi for every agent.
- Reduction: The reduction replaces each agent’s valuation order with a common ordering while preserving threshold-feasible allocations in polynomial time.For each agent, goods are reordered by decreasing value, and ALGBL maps a feasible ordered-instance allocation back to the original instance.
- Allocation algorithm: The ordered-instance algorithm allocates goods in decreasing value order while maintaining a partial allocation and an acyclic envy graph.Cycle resolution preserves agents’ bundle values and removes envy-graph edges.
- Allocation algorithm: The resulting partial allocations satisfy envy-freeness up to the least valued good, which supports the later maximin-share analysis.The EFX property is maintained inductively throughout ALGEG.
- Analysis: The proof shows that the constructed partial allocation minimizes the sum of the largest t bundles and yields the stated maximin-share bound.The analysis concludes with v1(A1) ≥ 2n/(3n−1) µ1.
4 Submodular Valuations
For nonnegative, monotone, submodular valuations, the paper develops a polynomial-time algorithm guaranteeing each agent at least 0.21 times her maximin share.
- Main result: 0.21-approximate maximin fair allocations are guaranteed to exist and can be found in polynomial time.The result applies to nonnegative, monotone, submodular valuations with oracle access.
- ROUNDROBIN: ROUNDROBIN allocates threshold-valued goods as singleton bundles and partitions the remaining goods by taking turns.Its guarantee holds independently for each agent whose threshold does not exceed that agent’s maximin share.
- Threshold search: If ROUNDROBIN gives agent i less than 0.21τi, then τi must exceed µi, enabling threshold reduction.ALGSUB geometrically decreases failing thresholds and repeatedly invokes ROUNDROBIN.
- Analysis: The analysis uses multilinear extensions to relate random fractional allocations and round-robin marginal gains to maximin-share values.A proportionality lemma gives Vi(ui) ≥ (1−1/e)µi for the uniform fractional allocation.
- Main result: ALGSUB returns an allocation satisfying vi(Pi) ≥ 0.21µi for every agent in polynomial time.Termination follows when no agent remains in the violated set, with the thresholds comparable to the maximin shares.
5 Conclusions
The paper’s algorithms produce allocations that are approximately fair and sequenceable. The authors also identify strategic maximin fair division with submodular valuations as a direction for future work.
- The algorithms compute allocations that are both approximately fair and sequenceable.Sequenceable allocations arise from ordering agents and letting them select their most valued remaining good in sequence.
- The additive algorithm uses a reduction that explicitly provides an agent sequence for assigning goods with maximum possible marginal values.
- Strategic maximin fair division with submodular valuations remains an open direction for future work.
A Fair Division of Chores
This section studies fair division of chores, modeled as negatively valued goods, under additive valuations.
- The section studies fair division of chores under additive valuations.Chores are treated as negatively valued goods.
A.1 Notation and Preliminaries
The preliminaries define additive valuations for indivisible chores and frame fairness through approximate maximin shares. The section also states an efficient 4/3-approximation result.
- Agents have additive valuations for indivisible chores, with every chore valued nonpositively.For each agent i and chore g, vi(g) ≤ 0.
- Maximin shares provide the fairness benchmark for evaluating chore allocations.
- Approximate fairness seeks a partition in which each agent receives at least a specified multiple of her maximin share.The objective is to find such a partition efficiently, since exact maximin-fair partitions do not always exist.
- 4/3-approximate maximin fair chore allocations can be found efficiently, improving on the prior 2-approximation bound.
A.2 Approximation Guarantee for Chores
The chore result uses techniques analogous to the goods case to obtain an approximate maximin-share guarantee. Its proof reduces the problem to ordered valuations and solves that restricted setting efficiently.
- The approach proves an approximate maximin-share guarantee for chores with additive valuations using techniques similar to the goods case.
- The proof first reduces approximate maximin fair allocation to instances where all agents value chores in the same order.The reduction relies on additive valuations and does not require chores to have positive values.
- The second step develops an efficient algorithm achieving a 4/3-approximation in the restricted ordered setting.
A.3 Envy Graph Algorithm for Chores
The algorithm addresses chores ordered identically by all agents. It allocates chores incrementally using an envy graph and restores acyclicity while preserving agents’ bundle values.
- Chores are indexed so every agent agrees on their nonincreasing disutility order.
- The algorithm maintains a partial allocation while assigning chores in increasing index order.
- The envy graph has one node per agent and an edge i→j exactly when agent i values j’s bundle more than her own.
- Lemma 5 transforms any partial allocation into one whose agents’ bundle values do not decrease and whose envy graph is acyclic.
A.4 Proof of Theorem 4
ALGCHORES orders chores by common disutility, allocates them to sink agents, and uses envy-graph updates to preserve acyclicity. The proof establishes the stated maximin guarantee by bounding the last chore assigned to an agent and analyzing the resulting bundle structure.
- Proof strategy: The proof focuses on agent 1’s last assigned chore gr and compares her post-assignment bundle with a maximin-share partition.The bundle containing gr may later change when Lemma 5 swaps bundles.
- Algorithm: ALGCHORES orders chores by nonincreasing disutility, initializes empty bundles, and repeatedly assigns chores while maintaining an acyclic envy graph.A sink vertex is always available because every finite acyclic directed graph has one.
- Algorithm: Lemma 5 updates the allocation without decreasing agents’ values and restores an acyclic envy graph after allocation steps.
- Proof strategy: If agent 1’s last chore satisfies |v1(gr)| > 1/3|µ1|, then a pigeonhole argument rules out assigning her three or more chores before gr.Three sufficiently early chores would form a bundle valued below µ1 in any partition, contradicting the definition of the maximin share.
- Proof strategy: Lemma 6 shows that when at most 2n chores remain and the largest disutility exceeds 1/3|µ|, a specified paired partition achieves the maximin share.
- Conclusion: The final case analysis proves that if |v1(gr)| > 1/3|µ1|, the returned allocation is maximin fair for agent 1.The argument handles bundles containing one or two chores and concludes v1(A1) ≥ |µ1|.
B.1 EF1 does not imply Maximin Fair
An EF1 allocation need not provide any constant-factor maximin guarantee. A constructed instance has an EF1 allocation giving one agent value 1, although the maximin share is at least n.
- Therefore, EF1 does not imply a constant-factor maximin guarantee.
- An instance with n agents and 2n−1 goods admits an EF1 allocation that gives agent 1 only the singleton bundle {1}.The remaining agents receive one unit-valued good together with one n-valued good.
- The same instance has a partition whose minimum bundle value is n, so its maximin share is at least n.
B.2 Nonexistence of Maximin Fair Allocation
For submodular valuations, a maximin fair allocation need not exist. A two-agent, four-good construction gives each agent maximin share 2 but makes their required maximin bundles incompatible.
- Agent 1 has a unique maximin partition pairing the two a-goods and the two b-goods, with maximin share 2.
- Agent 2 has a different unique maximin partition pairing each a-good with a b-good, also with maximin share 2.
- No allocation gives both agents bundles valued at least 2, because agent 1’s threshold-2 bundle forces agent 2’s value to be at most 1.5.
- Thus, unlike the additive two-agent case, submodular valuations do not guarantee existence of a maximin fair allocation.