Multiple birds with one stone: beating 1/2 for EFX and GMMS via envy cycle elimination

DOI10.1016/j.tcs.2020.07.006zbMath1458.91107arXiv1909.07650OpenAlexW3042417763MaRDI QIDQ2202022

Apostolos Ntokos, Georgios Amanatidis, Evangelos Markakis

Publication date: 17 September 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

fair divisionenvy-cycle eliminationenvy-freeness up to any goodgroupwise maximin share fairness

Mathematics Subject Classification ID

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

Related Items (9)

Computing envy-freeable allocations with limited subsidies ⋮ Maximum Nash welfare and other stories about EFX ⋮ Exact and approximation algorithms for PMMS under identical constraints ⋮ Fair division of indivisible goods: recent progress and open questions ⋮ Approximately EFX allocations for indivisible chores ⋮ The existence and efficiency of PMMS allocations ⋮ The price of fairness for indivisible goods ⋮ A Little Charity Guarantees Almost Envy-Freeness ⋮ Closing Gaps in Asymptotic Fair Division

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Welfare bounds in the fair division problem
• Approximate maximin shares for groups of agents
• Coverage, Matching, and Beyond: New Results on Budgeted Mechanism Design
• Approximation Algorithms for Computing Maximin Share Allocations
• Fair Enough
• Improving Nash Social Welfare Approximations
• A Little Charity Guarantees Almost Envy-Freeness
• Handbook of Computational Social Choice

This page was built for publication: Multiple birds with one stone: beating 1/2 for EFX and GMMS via envy cycle elimination