Combinatorial Optimization Reading Group - Vishnu V. Narayan

Title: One Dollar Each Eliminates Envy

Abstract:

We study the fair division of a collection of $m$ indivisible goods amongst a set of $n$ agents. Whilst envy-free allocations typically do not exist in the indivisible goods setting, envy-freeness can be achieved if some amount of a divisible good (money) is introduced. Specifically, Halpern and Shah (SAGT 2019, pp.374-389) showed that, given additive valuation functions where the marginal value of each item is at most one dollar for each agent, there always exists an envy-free allocation requiring a subsidy of at most $(n−1)m$ dollars. The authors also conjectured that a subsidy of $n−1$ dollars is sufficient for additive valuations. We prove this conjecture. In fact, a subsidy of at most one dollar per agent is sufficient to guarantee the existence of an envy-free allocation. Further, we prove that for general monotonic valuation functions an envy-free allocation always exists with a subsidy of at most $2(n−1)$ dollars per agent. In particular, the total subsidy required for monotonic valuations is independent of the number of items.

Joint work with Johannes Brustle, Jack Dippel, Mashbat Suzuki, and Adrian Vetta.