EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number
- 1 March 2025
- journal article
- research article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 73 (2) , 738-751
Abstract
A Simpler Approach to the EFX Problem Envy-freeness up to any item (EFX) has emerged as a compelling fairness notion in discrete fair division. However, its existence remains one of the biggest open problems in the field. In a breakthrough, Chaudhury et al. (2020) establish the existence of EFX allocations for three agents with additive valuations through intricate case analysis. The paper “EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number” by Akrami, Alon, Chaudhury, Garg, Mehlhorn, and Mehta offers a simpler approach for improving the EFX guarantee. They demonstrate the existence of EFX allocations for three agents when at least one has additive valuations (whereas the other two have general monotone valuations). Additionally, they nearly resolve a conjecture regarding the rainbow cycle number, leading to an (almost) tight bound for the existence of approximate EFX allocations with few unallocated items achievable through this approach.Keywords
This publication has 15 references indexed in Scilit:
- Zero sum cycles in complete digraphsEuropean Journal of Combinatorics, 2021
- An improved approximation algorithm for maximin sharesArtificial Intelligence, 2021
- Divisible subdivisionsJournal of Graph Theory, 2021
- Fair Division with Binary Valuations: One Rule to Rule Them All2020
- Multiple birds with one stone: Beating 1/2 for EFX and GMMS via envy cycle eliminationTheoretical Computer Science, 2020
- Maximin Envy-Free Division of Indivisible ItemsGroup Decision and Negotiation, 2016
- Fair assignment of indivisible objects under ordinal preferencesArtificial Intelligence, 2015
- Characterizing conflicts in fair division of indivisible goods using a scale of criteriaAutonomous Agents and Multi-Agent Systems, 2015
- The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal IncomesJournal of Political Economy, 2011
- Fair Division1996