A LITTLE CHARITY GUARANTEES ALMOST ENVY-FREENESS

Sgouritsa, Alkmini, RAY CHAUDHURY, BHASKAR, TELIKEPALLI, KAVITHA and MEHLHORN, KURT (2021) A LITTLE CHARITY GUARANTEES ALMOST ENVY-FREENESS. SIAM Journal on Computing, 50 (4). pp. 1336-1358.

Text sicomp21EFX.pdf - Author Accepted Manuscript Download (442kB) | Preview

Abstract

The 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 monotone 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. 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 and leads to a pseudopolynomial time algorithm to find such an allocation. 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 that 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.

Item Type:	Article
Uncontrolled Keywords:	fair division, EFX allocations, MMS allocations
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	12 May 2021 08:05
Last Modified:	29 Nov 2023 04:18
DOI:	10.1137/20M1359134
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3122364