# Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 62 of its 82 references that are in the map.
- First posted on arXiv 20 Jul 2025.

## Builds on (most cited first, 30 of 62)

- [Almost Envy-Freeness with General Valuations](https://mlsanity.com/paper/1707.04769/) (2017)
- [Fair Division of Indivisible Goods: Recent Progress and Open Questions](https://mlsanity.com/paper/2208.08782/) (2022)
- [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)
- [An Improved Approximation Algorithm for Maximin Shares](https://mlsanity.com/paper/1903.00029/) (2019)
- [Approximation Algorithms for Maximin Fair Division](https://mlsanity.com/paper/1703.01851/) (2017)
- [The Price of Fairness for Indivisible Goods](https://mlsanity.com/paper/1905.04910/) (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)
- [Breaking the 3/4 Barrier for Approximate Maximin Share](https://mlsanity.com/paper/2307.07304/) (2023)
- [Fair Division with Allocator's Preference](https://mlsanity.com/paper/2310.03475/) (2023)
- [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)
- [Finding Fair and Efficient Allocations When Valuations Don't Add Up](https://mlsanity.com/paper/2003.07060/) (2020)
- [A tight negative example for MMS fair allocations](https://mlsanity.com/paper/2104.04977/) (2021)
- [Maximizing Nash Social Welfare in 2-Value Instances](https://mlsanity.com/paper/2107.08965/) (2021)
- [Existence and Computation of Maximin Fair Allocations Under Matroid-Rank Valuations](https://mlsanity.com/paper/2012.12710/) (2020)
- [Approximability Landscape of Welfare Maximization within Fair Allocations](https://mlsanity.com/paper/2205.14296/) (2022)
- [Fair Allocation of Two Types of Chores](https://mlsanity.com/paper/2211.00879/) (2022)
- [Pushing the Frontier on Approximate EFX Allocations](https://mlsanity.com/paper/2406.12413/) (2024)
- [Existence of EFX for Two Additive Valuations](https://mlsanity.com/paper/2008.08798/) (2020)
- [Approximately EFX Allocations for Indivisible Chores](https://mlsanity.com/paper/2109.07313/) (2021)
- [How to Fairly Allocate Easy and Difficult Chores](https://mlsanity.com/paper/2110.11285/) (2021)
- [New Fairness Concepts for Allocating Indivisible Items](https://mlsanity.com/paper/2206.01710/) (2022)

## Abstract (arXiv)

We study the fair division of indivisible items and provide new insights into the EFX problem, which is widely regarded as the central open question in fair division, and the PMMS problem, a strictly stronger variant of EFX. Our first result constructs a three-agent instance with two monotone valuations and one additive valuation in which no PMMS allocation exists. Since EFX allocations are known to exist under these assumptions, this establishes a formal separation between EFX and PMMS. We prove existence of fair allocations for three important special cases. We show that EFX allocations exist for personalized bivalued valuations, where for each agent i there exist values ai > bi such that agent i assigns value vi(g) ∈ ai, bi to each good g. We establish an analogous existence result for PMMS allocations when ai is divisible by bi. We also prove that PMMS allocations exist for binary-valued MMS-feasible valuations, where each bundle S has value vi(S) ∈ 0, 1. Notably, this result holds even without assuming monotonicity of valuations and thus applies to the fair division of chores and mixed manna. Finally, we study a class of valuations called pair-demand valuations, which extend the well-studied unit-demand valuations to the case where each agent derives value from at most two items, and we show that PMMS allocations exist in this setting. Our proofs are constructive, and we provide polynomial-time algorithms for all three existence results.