# One Dollar Each Eliminates Envy

arXiv: https://arxiv.org/abs/1912.02797 · HTML: https://mlsanity.com/paper/1912.02797/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Dec 2019.

## Built on by (most cited first, 2 of 2)

- [Fast Online Value-Maximizing Prediction Sets with Conformal Cost Control](https://mlsanity.com/paper/2302.00839/) (2023)
- [Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division](https://mlsanity.com/paper/2507.14957/) (2025)

## Abstract (arXiv)

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.