Economics and Computation Series
A Little Charity Guarantees Almost Envy-Freeness
3rd February 2021, 13:00
Alkmini Sgouritsa
University of Liverpool
Abstract
The goal of this work is to distribute m goods to n agents in a “fair” manner, where every agent has a valuation for each subset of goods. "Envy-freeness up to any good" (EFX) is currently the most promising relaxation of envy freeness for the case of indivisible goods. An allocation satisfies EFX when no agent envies another agent after the removal of any single good from the latter’s bundle. It is not known if such an allocation always exists for more than 3 agents.
We show that there is always a partition of the set of goods into n+1 subsets (X1,...,Xn,P) where Xi is the bundle allocated to agent i and the set P is unallocated (or donated to charity) such that:
- EFX is satisfied among agents,
- no agent envies P and
- fewer than n goods go to charity.
Our proof is constructive and leads to a pseudo-polynomial time algorithm to find such an allocation.
Joint work with Bhaskar Ray Chaudhury, Telikepalli Kavitha and Kurt Mehlhorn.
Additional Materials
Maintained by Nicos Protopapas