When Do Envy-Free Allocations Exist?

DOI10.1137/19M1279125zbMath1452.91172arXiv1811.01630MaRDI QIDQ5130903

Warut Suksompong, Pasin Manurangsi

Publication date: 29 October 2020

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1811.01630

zbMATH Keywords

phase transitionasymptotic analysisfair divisionenvy-freeness

Mathematics Subject Classification ID

Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Related Items

Fixing knockout tournaments with seeds ⋮ Fair division of indivisible goods: recent progress and open questions ⋮ The price of fairness for indivisible goods ⋮ Closing Gaps in Asymptotic Fair Division ⋮ The Price of Connectivity in Fair Division

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Asymptotic existence of proportionally fair allocations
• Asymptotic existence of fair divisions for groups
• Approximate maximin shares for groups of agents
• Almost envy-freeness in group resource allocation
• Democratic fair allocation of indivisible goods
• Fair cake-cutting among families
• Local resilience of graphs
• How to Cut a Cake Fairly
• Approximation Algorithms for Computing Maximin Share Allocations