# Understanding EFX Allocations: Counting and Variants

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 56 references that are in the map.
- First posted on arXiv 4 Apr 2025.

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

- [Almost Envy-Freeness with General Valuations](https://mlsanity.com/paper/1707.04769/) (2017)
- [Online Fair Division: analysing a Food Bank problem](https://mlsanity.com/paper/1502.07571/) (2015)
- [Best of Both Worlds: Ex-Ante and Ex-Post Fairness in Resource Allocation](https://mlsanity.com/paper/2005.14122/) (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)
- [Envy-freeness up to any item with high Nash welfare: The virtue of donating items](https://mlsanity.com/paper/1902.04319/) (2019)
- [Almost Envy-Freeness in Group Resource Allocation](https://mlsanity.com/paper/1901.08463/) (2019)
- [Equitable Allocations of Indivisible Goods](https://mlsanity.com/paper/1905.10656/) (2019)
- [Multiple Birds with One Stone: Beating 1/2 for EFX and GMMS via Envy Cycle Elimination](https://mlsanity.com/paper/1909.07650/) (2019)
- [Weighted Envy-Freeness in Indivisible Item Allocation](https://mlsanity.com/paper/1909.10502/) (2019)
- [Groupwise Maximin Fair Allocation of Indivisible Goods](https://mlsanity.com/paper/1711.07621/) (2017)
- [A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation](https://mlsanity.com/paper/1909.00740/) (2019)
- [Simultaneously Achieving Ex-ante and Ex-post Fairness](https://mlsanity.com/paper/2004.02554/) (2020)
- [On Maximum Weighted Nash Welfare for Binary Valuations](https://mlsanity.com/paper/2204.03803/) (2022)
- [Uniform Welfare Guarantees Under Identical Subadditive Valuations](https://mlsanity.com/paper/2005.00504/) (2020)
- [For One and All: Individual and Group Fairness in the Allocation of Indivisible Goods](https://mlsanity.com/paper/2302.06958/) (2023)
- [Existence and Computation of Maximin Fair Allocations Under Matroid-Rank Valuations](https://mlsanity.com/paper/2012.12710/) (2020)
- [Fair-Share Allocations for Agents with Arbitrary Entitlements](https://mlsanity.com/paper/2103.04304/) (2021)
- [On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources](https://mlsanity.com/paper/2012.06788/) (2020)
- [Extension of Additive Valuations to General Valuations on the Existence of EFX](https://mlsanity.com/paper/2107.09901/) (2021)
- [Approximately EFX Allocations for Indivisible Chores](https://mlsanity.com/paper/2109.07313/) (2021)
- [Generalized binary utility functions and fair allocations](https://mlsanity.com/paper/2109.08461/) (2021)
- [An EF2X Allocation Protocol for Restricted Additive Valuations](https://mlsanity.com/paper/2202.13676/) (2022)
- [Weighted Envy-Freeness for Submodular Valuations](https://mlsanity.com/paper/2209.06437/) (2022)
- [Fair Division of Chores with Budget Constraints](https://mlsanity.com/paper/2410.23979/) (2024)
- [On the Number of Almost Envy-Free Allocations](https://mlsanity.com/paper/2006.00178/) (2020)
- [Almost Envy-freeness, Envy-rank, and Nash Social Welfare Matchings](https://mlsanity.com/paper/2007.07027/) (2020)
- [Best of Both Worlds: Agents with Entitlements](https://mlsanity.com/paper/2209.03908/) (2022)

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

- [Online Fair Division with Additional Information](https://mlsanity.com/paper/2505.24503/) (2025)
- [The Cost of EFX: Generalized-Mean Welfare and Complexity Dichotomies with Few Surplus Items](https://mlsanity.com/paper/2601.12849/) (2026)
- [Online Fair Division with Budget Constraints](https://mlsanity.com/paper/2607.23310/) (2026)

## Abstract (arXiv)

Envy-freeness up to any good (EFX) is a popular and important fairness property in the fair allocation of indivisible goods, of which its existence in general is still an open question. In this work, we investigate the problem of determining the minimum number of EFX allocations for a given instance, arguing that this approach may yield valuable insights into the existence and computation of EFX allocations. We focus on restricted instances where the number of goods slightly exceeds the number of agents, and extend our analysis to weighted EFX (WEFX) and a novel variant of EFX for general monotone valuations, termed EFX+. In doing so, we identify the transition threshold for the existence of allocations satisfying these fairness notions. Notably, we resolve open problems regarding WEFX by proving polynomial-time computability under binary additive valuations, and establishing the first constant-factor approximation for two agents.