Approximation Algorithms for Computing Maximin Share Allocations

DOI10.1145/3147173MaRDI QIDQ4554942zbMATH OpenOpenAlexFDO

Authors Georgios Amanatidis, Evangelos Markakis, Afshin Nikzad, Amin Saberi

Publication date 12 November 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.00941, http://repository.essex.ac.uk/27279/1/journal-mms_acm_alt.pdf

zbMATH Keywords

fair divisionmaximin share

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Approximation algorithms (68W25) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

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^itre. We obtain an exact algorithm for any number of agents in this case.

Recommendations

• Approximation algorithms for computing maximin share allocations
• An improved approximation algorithm for maximin shares
• Approximating the Maximum Sharing Problem
• An Efficient Approximation Algorithm for Maximum Simple Sharing Problem
• On Approximating the Maximum Simple Sharing Problem
• Approximate maximin share allocations in matroids
• Approximation Algorithms for Min-Max and Max-Min Resource Sharing Problems, and Applications
• An approximation algorithm for the general max-min resource sharing problem
• Approximation Algorithms for the Max-Min Allocation Problem
• Algorithm Theory - SWAT 2004

Cited in

(51)

• On maximin share allocations in matroids
• Approximate maximin shares for groups of agents
• Sharing-group allocation problems
• Almost envy-free allocations with connected bundles
• Allocating indivisible goods to strategic agents: pure Nash equilibria and fairness
• A tight negative example for MMS fair allocations
• Multiple birds with one stone: beating 1/2 for EFX and GMMS via envy cycle elimination
• Fair division of mixed divisible and indivisible goods
• An improved approximation algorithm for maximin shares
• Maximin share guarantee for goods with positive externalities
• Finding maxmin allocations in cooperative and competitive fair division
• Computing a small agreeable set of indivisible items
• Envy-freeness in house allocation problems
• Maximum Nash welfare and other stories about EFX
• Fair multi-cake cutting
• Fair allocation of indivisible goods: beyond additive valuations
• Approximate competitive equilibrium with generic budget
• Fair allocation of indivisible items with conflict graphs
• An Efficient Approximation Algorithm for Maximum Simple Sharing Problem
• Approximation algorithms for computing maximin share allocations
• scientific article; zbMATH DE number 4160481 (Why is no real title available?)
• Fair enough: guaranteeing approximate maximin shares
• A Little Charity Guarantees Almost Envy-Freeness
• Fair allocation of indivisible goods: improvement
• Closing gaps in asymptotic fair division
• Fairly allocating many goods with few queries
• Ordinal Maximin Share Approximation for Goods
• Efficient Fair Division with Minimal Sharing
• Maximin share allocations on cycles
• When do envy-free allocations exist?
• On allocating goods to maximize fairness
• Approximate maximin share allocations in matroids
• Faster min-max resource sharing in theory and practice
• Existence of EFX for two additive valuations
• Approximate and strategyproof maximin share allocation of chores with ordinal preferences
• Fair division of indivisible goods: recent progress and open questions
• Improved maximin guarantees for subadditive and fractionally subadditive fair allocation problem
• Envy-free matchings in bipartite graphs and their applications to fair division
• On best-of-both-worlds fair-share allocations
• Maximin fair allocation of indivisible items under cost utilities
• Approximating maximin share allocations
• On the price of fairness of allocating contiguous blocks
• The price of EF1 for few agents with additive ternary valuations
• Asymptotic analysis of weighted fair division
• Restricted existence and approximation algorithms for PMMS
• Approximate maximin share allocation for indivisible goods under a knapsack constraint
• The budgeted maximin share allocation problem
• Fair and truthful allocations under leveled valuations
• Maximin share allocation under knapsack constraints
• EFX exists for three agents
• Title not available (Why is no real title available?)

This page was built for publication: Approximation Algorithms for Computing Maximin Share Allocations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4554942)