A Little Charity Guarantees Almost Envy-Freeness

3^rd 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

• https://arxiv.org/pdf/1907.04596.pdf