Campus Event Calendar

Event Entry

What and Who

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

Hannaneh Akrami
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1  
AG Audience

Date, Time and Location

Tuesday, 4 July 2023
30 Minutes
E1 4


The existence of EFX allocations is a fundamental open problem in discrete fair division. Given a set of agents and indivisible goods, the goal is to determine the existence of an allocation where no agent envies another, following removal of any single good from the other agent’s bundle. Since the general problem has been elusive, progress is made on two fronts: (i) proving existence when the number of agents 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 the state-of-the-art by showing the existence of EFX allocations when two of the agents have general monotone valuations and one has additive or more generally MMS-feasible valuation (a strict generalization of nice-cancelable valuation functions). In contrast to the previous works, our new algorithm moves in the space of complete allocations, improving a potential, as long as the allocation is not EFX.

Secondly, we consider relaxations of EFX allocations, namely, approximate-EFX allocations and EFX allocations with few unallocated goods (charity). Through a promising new method using a problem in extremal combinatorics called Rainbow Cycle Number (RCN), Chaudhury et al. managed to show the existence of (1-epsilon)-EFX allocation with sub-linear charity, namely O((n/epsilon)^(4/5)) charity, where n is the number of agents. This is done by upper bounding the RCN by O(d^4) in d-dimension. They conjectured this number to be O(d) and gave a matching lower bound. We almost settle this conjecture by improving the upper bound to O(d log(d)) and thereby get (almost) optimal charity of \tilde{O}((n/ epsilon)^(1/2)) that is possible through this method. Our technique is based on probabilistic method. We also derandomize the approach to construct such an allocation in deterministic polynomial time.


Roohani Sharma
+49 681 9325 1116
--email hidden

Virtual Meeting Details

527 278 8807
passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

If you wish to attend the talk online but do not have the zoom password, contact Roohani Sharma at

Roohani Sharma, 06/21/2023 02:40 -- Created document.