EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number

• 成果类型: Article
• 署名作者: Akrami, Hannaneh; Alon, Noga; Chaudhury, Bhaskar Ray; Garg, Jugal; Mehlhorn, Kurt; Mehta, Ruta
• 署名单位: Max Planck Society; Saarland University; Princeton University; University of Illinois System; University of Illinois Urbana-Champaign
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2023.0433
• 发表日期: 2025
• 关键词: fair division; assignment

摘要

The existence of envy-freeness up to any good (EFX) allocations is a fundamental open problem in discrete fair division. The goal is to determine the existence of an allocation of a set of indivisible goods among n agents for which no agent envies another, following the removal of any single good from the other agent's bundle. Because the general problem has been elusive, progress is made on two fronts: (i) proving existence when n is small and (ii) proving the existence of relaxations of EFX. In this paper, we improve and simplify the state-of-the-art results on both fronts with new techniques. For the case of three agents, the existence of EFX was first shown with additive valuations and then extended to nice-cancelable valuations. As our first main result, we simplify and improve this result by showing the existence of EFX allocations when two of the agents have general monotone valuations and one has a maximin share (MMS)-feasible valuation (a strict generalization of nice-cancelable valuation functions). Our approach is significantly simpler than the previous ones, and it also avoids using the standard concepts of envy graph and champion graph and may find use in other fair-division problems. Second, we consider approximate EFX allocations with few unallocated goods (charity). Through a promising new method using a problem in extremal combinatorics called rainbow cycle number (RCN), the existence of ( 1 - epsilon )-EFX allocation with O((n/epsilon)45) charity was established. This is done by upper bounding the RCN by O(d4) in d-dimension. They conjecture RCN to be O( d ) . We almost settle this conjecture by improving the upper bound to O( d log d ) and thereby get (almost) optimal charity of O(( n / epsilon ) 12 ) that is possible through this method. Our technique is much simpler than the previous ones and is based on the probabilistic method.