# PROPm Allocations of Indivisible Goods to Multiple Agents

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 14 references that are in the map.
- First posted on arXiv 24 May 2021.

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

- [Almost Envy-Freeness with General Valuations](https://mlsanity.com/paper/1707.04769/) (2017)
- [Fair Public Decision Making](https://mlsanity.com/paper/1611.04034/) (2016)
- [EFX Exists for Three Agents](https://mlsanity.com/paper/2002.05119/) (2020)
- [A Little Charity Guarantees Almost Envy-Freeness](https://mlsanity.com/paper/1907.04596/) (2019)
- [Finding Fair and Efficient Allocations](https://mlsanity.com/paper/1707.04731/) (2017)
- [Multiple Birds with One Stone: Beating 1/2 for EFX and GMMS via Envy Cycle Elimination](https://mlsanity.com/paper/1909.07650/) (2019)
- [A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation](https://mlsanity.com/paper/1909.00740/) (2019)
- [APX-Hardness of Maximizing Nash Social Welfare with Indivisible Items](https://mlsanity.com/paper/1507.01159/) (2015)
- [Fairly Allocating Many Goods with Few Queries](https://mlsanity.com/paper/1807.11367/) (2018)
- [Achieving Proportionality up to the Maximin Item with Indivisible Goods](https://mlsanity.com/paper/2009.09508/) (2020)

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

- [(Almost) Envy-Free, Proportional and Efficient Allocations of an Indivisible Mixed Manna](https://mlsanity.com/paper/2202.02672/) (2022)

## Abstract (arXiv)

We study the classic problem of fairly allocating a set of indivisible goods among a group of agents, and focus on the notion of approximate proportionality known as PROPm. Prior work showed that there exists an allocation that satisfies this notion of fairness for instances involving up to five agents, but fell short of proving that this is true in general. We extend this result to show that a PROPm allocation is guaranteed to exist for all instances, independent of the number of agents or goods. Our proof is constructive, providing an algorithm that computes such an allocation and, unlike prior work, the running time of this algorithm is polynomial in both the number of agents and the number of goods.