TY - GEN

T1 - A little charity guarantees almost envy-freeness

AU - Chaudhury, Bhaskar Ray

AU - Kavitha, Telikepalli

AU - Mehlhorn, Kurt

AU - Sgouritsa, Alkmini

N1 - Publisher Copyright:
Copyright © 2020 by SIAM

PY - 2020

Y1 - 2020

N2 - Fair division of indivisible goods is a very well-studied problem. The goal of this problem is to distribute m goods to n agents in a “fair” manner, where every agent has a valuation for each subset of goods. We assume general valuations. Envy-freeness is the most extensively studied notion of fairness. However, envy-free allocations do not always exist when goods are indivisible. The notion of fairness we consider here is “envy-freeness up to any good” (EFX) where no agent envies another agent after the removal of any single good from the other agent's bundle. It is not known if such an allocation always exists even when n = 3. We show there is always a partition of the set of goods into n + 1 subsets (X1, . . ., Xn, P) where for i ∈ [n], Xi is the bundle allocated to agent i and the set P is unallocated (or donated to charity) such that we have: (1) envy-freeness up to any good, (2) no agent values P higher than her own bundle, and (3) fewer than n goods go to charity, i.e., |P| < n (typically m ≫ n). Our proof is constructive. When agents have additive valuations and |P| is large (i.e., when |P| is close to n), our allocation also has a good maximin share (MMS) guarantee. Moreover, a minor variant of our algorithm also shows the existence of an allocation which is 4/7 groupwise maximin share (GMMS): this is a notion of fairness stronger than MMS. This improves upon the current best bound of 1/2 known for an approximate GMMS allocation.

AB - Fair division of indivisible goods is a very well-studied problem. The goal of this problem is to distribute m goods to n agents in a “fair” manner, where every agent has a valuation for each subset of goods. We assume general valuations. Envy-freeness is the most extensively studied notion of fairness. However, envy-free allocations do not always exist when goods are indivisible. The notion of fairness we consider here is “envy-freeness up to any good” (EFX) where no agent envies another agent after the removal of any single good from the other agent's bundle. It is not known if such an allocation always exists even when n = 3. We show there is always a partition of the set of goods into n + 1 subsets (X1, . . ., Xn, P) where for i ∈ [n], Xi is the bundle allocated to agent i and the set P is unallocated (or donated to charity) such that we have: (1) envy-freeness up to any good, (2) no agent values P higher than her own bundle, and (3) fewer than n goods go to charity, i.e., |P| < n (typically m ≫ n). Our proof is constructive. When agents have additive valuations and |P| is large (i.e., when |P| is close to n), our allocation also has a good maximin share (MMS) guarantee. Moreover, a minor variant of our algorithm also shows the existence of an allocation which is 4/7 groupwise maximin share (GMMS): this is a notion of fairness stronger than MMS. This improves upon the current best bound of 1/2 known for an approximate GMMS allocation.

UR - http://www.scopus.com/inward/record.url?scp=85084092294&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85084092294&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85084092294

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 2658

EP - 2672

BT - 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020

A2 - Chawla, Shuchi

PB - Association for Computing Machinery

T2 - 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020

Y2 - 5 January 2020 through 8 January 2020

ER -