Approximation Algorithms for Computing Maximin Share Allocations

Abstract

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.

References in corpus (2)

• On Truthful Mechanisms for Maximin Share Allocations
• Truthful Allocation Mechanisms Without Payments: Characterization and Implications on Fairness

Cited by in corpus (35)

• Fair Division of Indivisible Goods: Recent Progress and Open Questions
• Multiple Birds with One Stone: Beating $1/2$ for EFX and GMMS via Envy Cycle Elimination
• Maximum Nash Welfare and Other Stories About EFX
• Almost Envy-Free Allocations with Connected Bundles
• Fair Division of Mixed Divisible and Indivisible Goods
• Envy-freeness up to any item with high Nash welfare: The virtue of donating items
• Fair allocation of combinations of indivisible goods and chores
• An Algorithmic Framework for Approximating Maximin Share Allocation of Chores
• Closing Gaps in Asymptotic Fair Division
• Envy-Freeness in House Allocation Problems
• Fair Allocation of Indivisible Goods: Improvement and Generalization
• How to Fairly Allocate Easy and Difficult Chores
• When Do Envy-Free Allocations Exist?
• Assigning a Small Agreeable Set of Indivisible Items to Multiple Players
• Envy-free Matchings in Bipartite Graphs and their Applications to Fair Division
• Computing an Approximately Optimal Agreeable Set of Items
• Maximin Fairness with Mixed Divisible and Indivisible Goods
• Fairly Allocating Many Goods with Few Queries
• Ordinal Maximin Share Approximation for Goods
• Efficient Fair Division with Minimal Sharing
• Fair Allocation of Conflicting Items
• Fair Allocation based on Diminishing Differences
• An Improved Approximation Algorithm for Maximin Shares
• Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness
• The Fair Division of Hereditary Set Systems
• Indivisible Mixed Manna: On the Computability of MMS + PO Allocations
• The Maximin Share Dominance Relation
• Fair Allocation of Indivisible Items With Externalities
• Asymptotic Analysis of Weighted Fair Division
• Your College Dorm and Dormmates: Fair Resource Sharing with Externalities
• Fair Multi-Cake Cutting
• The Price of EF1 for Few Agents with Additive Ternary Valuations
• Fair Allocation with Interval Scheduling Constraints
• Asymptotic Fair Division: Chores Are Easier Than Goods
• Fairness Criteria for Allocating Indivisible Chores: Connections and Efficiencies