Approximation Algorithms for Computing Maximin Share Allocations
From MaRDI portal
Publication:4554942
DOI10.1145/3147173zbMath1407.68540arXiv1503.00941OpenAlexW1542025417MaRDI QIDQ4554942
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
Combinatorial aspects of matroids and geometric lattices (05B35) Approximation algorithms (68W25) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)
Related Items (26)
Allocating indivisible goods to strategic agents: pure Nash equilibria and fairness ⋮ A tight negative example for MMS fair allocations ⋮ Maximum Nash welfare and other stories about EFX ⋮ Fair multi-cake cutting ⋮ Fair allocation of indivisible goods: beyond additive valuations ⋮ Ordinal Maximin Share Approximation for Goods ⋮ Approximate competitive equilibrium with generic budget ⋮ Efficient Fair Division with Minimal Sharing ⋮ 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 ⋮ Multiple birds with one stone: beating 1/2 for EFX and GMMS via envy cycle elimination ⋮ Fair allocation of indivisible items with conflict graphs ⋮ When Do Envy-Free Allocations Exist? ⋮ Fair division of mixed divisible and indivisible goods ⋮ An improved approximation algorithm for 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 ⋮ Computing a small agreeable set of indivisible items ⋮ Almost envy-free allocations with connected bundles ⋮ Envy-freeness in house allocation problems
This page was built for publication: Approximation Algorithms for Computing Maximin Share Allocations
