# Fairly Allocating Many Goods with Few Queries

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jul 2018.

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

- [PROPm Allocations of Indivisible Goods to Multiple Agents](https://mlsanity.com/paper/2105.11348/) (2021)
- [Envy-Free Allocation of Indivisible Goods via Noisy Queries](https://mlsanity.com/paper/2602.06361/) (2026)

## Abstract (arXiv)

We investigate the query complexity of the fair allocation of indivisible goods. For two agents with arbitrary monotonic utilities, we design an algorithm that computes an allocation satisfying envy-freeness up to one good (EF1), a relaxation of envy-freeness, using a logarithmic number of queries. We show that the logarithmic query complexity bound also holds for three agents with additive utilities, and that a polylogarithmic bound holds for three agents with monotonic utilities. These results suggest that it is possible to fairly allocate goods in practice even when the number of goods is extremely large. By contrast, we prove that computing an allocation satisfying envy-freeness and another of its relaxations, envy-freeness up to any good (EFX), requires a linear number of queries even when there are only two agents with identical additive utilities.