# Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 61 references that are in the map.
- First posted on arXiv 17 Sep 2021.

## Builds on (most cited first, 22 of 22)

- [Almost Envy-Freeness with General Valuations](https://mlsanity.com/paper/1707.04769/) (2017)
- [EFX Exists for Three Agents](https://mlsanity.com/paper/2002.05119/) (2020)
- [Maximum Nash Welfare and Other Stories About EFX](https://mlsanity.com/paper/2001.09838/) (2020)
- [Fair and Truthful Mechanisms for Dichotomous Valuations](https://mlsanity.com/paper/2002.10704/) (2020)
- [A Little Charity Guarantees Almost Envy-Freeness](https://mlsanity.com/paper/1907.04596/) (2019)
- [Fair Division with Binary Valuations: One Rule to Rule Them All](https://mlsanity.com/paper/2007.06073/) (2020)
- [Fair Allocation of Indivisible Goods: Improvement and Generalization](https://mlsanity.com/paper/1704.00222/) (2017)
- [Envy-freeness up to any item with high Nash welfare: The virtue of donating items](https://mlsanity.com/paper/1902.04319/) (2019)
- [Approximation Algorithms for Computing Maximin Share Allocations](https://mlsanity.com/paper/1503.00941/) (2015)
- [Nash Social Welfare Approximation for Strategic Agents](https://mlsanity.com/paper/1607.01569/) (2016)
- [An Improved Approximation Algorithm for Maximin Shares](https://mlsanity.com/paper/1903.00029/) (2019)
- [Multiple Birds with One Stone: Beating 1/2 for EFX and GMMS via Envy Cycle Elimination](https://mlsanity.com/paper/1909.07650/) (2019)
- [Comparing Approximate Relaxations of Envy-Freeness](https://mlsanity.com/paper/1806.03114/) (2018)
- [On Truthful Mechanisms for Maximin Share Allocations](https://mlsanity.com/paper/1605.04026/) (2016)
- [Groupwise Maximin Fair Allocation of Indivisible Goods](https://mlsanity.com/paper/1711.07621/) (2017)
- [Improving EFX Guarantees through Rainbow Cycle Number](https://mlsanity.com/paper/2103.01628/) (2021)
- [Truthful Allocation Mechanisms Without Payments: Characterization and Implications on Fairness](https://mlsanity.com/paper/1705.10706/) (2017)
- [Complexity of Manipulating Sequential Allocation](https://mlsanity.com/paper/1602.06940/) (2016)
- [Equilibria in Sequential Allocation](https://mlsanity.com/paper/1705.09444/) (2017)
- [Existence of EFX for Two Additive Valuations](https://mlsanity.com/paper/2008.08798/) (2020)
- [Algorithms for Manipulating Sequential Allocation](https://mlsanity.com/paper/1909.06747/) (2019)
- [(Almost Full) EFX Exists for Four Agents (and Beyond)](https://mlsanity.com/paper/2102.10654/) (2021)

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

- [Fair Shares: Feasibility, Domination and Incentives](https://mlsanity.com/paper/2205.07519/) (2022)
- [Fair Allocation in Dynamic Mechanism Design](https://mlsanity.com/paper/2406.00147/) (2024)
- [Distributed course allocation with asymmetric friendships](https://mlsanity.com/paper/2309.09684/) (2023)

## Abstract (arXiv)

We consider the problem of fairly allocating a set of indivisible goods to a set of strategic agents with additive valuation functions. We assume no monetary transfers and, therefore, a mechanism in our setting is an algorithm that takes as input the reported -- rather than the true -- values of the agents. Our main goal is to explore whether there exist mechanisms that have pure Nash equilibria for every instance and, at the same time, provide fairness guarantees for the allocations that correspond to these equilibria. We focus on two relaxations of envy-freeness, namely envy-freeness up to one good (EF1), and envy-freeness up to any good (EFX), and we positively answer the above question. In particular, we study two algorithms that are known to produce such allocations in the non-strategic setting: Round-Robin (EF1 allocations for any number of agents) and a cut-and-choose algorithm of Plaut and Roughgarden [SIAM Journal of Discrete Mathematics, 2020] (EFX allocations for two agents). For Round-Robin we show that all of its pure Nash equilibria induce allocations that are EF1 with respect to the underlying true values, while for the algorithm of Plaut and Roughgarden we show that the corresponding allocations not only are EFX but also satisfy maximin share fairness, something that is not true for this algorithm in the non-strategic setting! Further, we show that a weaker version of the latter result holds for any mechanism for two agents that always has pure Nash equilibria which all induce EFX allocations.