A Little Charity Guarantees Almost Envy-Freeness

DOI10.1137/20M1359134MaRDI QIDQ4957912

Telikepalli Kavitha, Kurt Mehlhorn, Bhaskar Chaudhury, Alkmini Sgouritsa

Publication date: 10 September 2021

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

fair divisionEFX allocationsMMS allocations

Mathematics Subject Classification ID

Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Algorithms in computer science (68W99)

Related Items (4)

Computing envy-freeable allocations with limited subsidies ⋮ On the existence of EFX allocations ⋮ EFX under budget constraint ⋮ Fair division of indivisible goods: recent progress and open questions

Cites Work

• Unnamed Item
• Unnamed Item
• Multiple birds with one stone: beating 1/2 for EFX and GMMS via envy cycle elimination
• Approximation Algorithms for Computing Maximin Share Allocations
• Fair Enough
• Approximating the Nash Social Welfare with Indivisible Items
• Nash Social Welfare for Indivisible Items under Separable, Piecewise-Linear Concave Utilities
• Fair Allocation of Indivisible Goods to Asymmetric Agents
• Nash Social Welfare, Matrix Permanent, and Stable Polynomials
• On fair division for indivisible items
• Almost Envy-Freeness with General Valuations
• A Little Charity Guarantees Almost Envy-Freeness

This page was built for publication: A Little Charity Guarantees Almost Envy-Freeness