Multiple Birds with One Stone: Beating $1/2$ for EFX and GMMS via Envy Cycle Elimination

Abstract

Several relaxations of envy-freeness, tailored to fair division in settings with indivisible goods, have been introduced within the last decade. Due to the lack of general existence results for most of these concepts, great attention has been paid to establishing approximation guarantees. In this work, we propose a simple algorithm that is universally fair in the sense that it returns allocations that have good approximation guarantees with respect to four such fairness notions at once. In particular, this is the first algorithm achieving a $(\varphi -1)$-approximation of envy-freeness up to any good (EFX) and a $\frac{2}{\varphi +2}$-approximation of groupwise maximin share fairness (GMMS), where $\varphi$ is the golden ratio ($\varphi \approx 1.618$). The best known approximation factor for either one of these fairness notions prior to this work was $1/2$. Moreover, the returned allocation achieves envy-freeness up to one good (EF1) and a $2/3$-approximation of pairwise maximin share fairness (PMMS). While EFX is our primary focus, we also exhibit how to fine-tune our algorithm and improve the guarantees for GMMS or PMMS. Finally, we show that GMMS -- and thus PMMS and EFX -- allocations always exist when the number of goods does not exceed the number of agents by more than two.

References in corpus (7)

• Deep Recurrent Quantization for Generating Sequential Binary Codes
• Beyond Product Quantization: Deep Progressive Quantization for Image Retrieval
• Approximation Algorithms for Computing Maximin Share Allocations
• On Truthful Mechanisms for Maximin Share Allocations
• Approximate Maximin Shares for Groups of Agents
• Greedy Algorithms for Fair Division of Mixed Manna
• An Improved Approximation Algorithm for Maximin Shares

Cited by in corpus (9)

• Fair Division of Indivisible Goods: Recent Progress and Open Questions
• Maximum Nash Welfare and Other Stories About EFX
• The Price of Fairness for Indivisible Goods
• Closing Gaps in Asymptotic Fair Division
• Fair allocation of a multiset of indivisible items
• On the Number of Almost Envy-Free Allocations
• Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness
• Fair and Efficient Allocations under Lexicographic Preferences
• Equitable Division of a Path