# Existence of EFX for Two Additive Valuations

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Aug 2020.

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

- [Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness](https://mlsanity.com/paper/2109.08644/) (2021)
- [The Cost of EFX: Generalized-Mean Welfare and Complexity Dichotomies with Few Surplus Items](https://mlsanity.com/paper/2601.12849/) (2026)
- [Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division](https://mlsanity.com/paper/2507.14957/) (2025)

## Abstract (arXiv)

Fair division of indivisible items is a well-studied topic in Economics and Computer Science. The objective is to allocate items to agents in a fair manner, where each agent has a valuation for each subset of items. Envy-freeness is one of the most widely studied notions of fairness. Since complete envy-free allocations do not always exist when items are indivisible, several relaxations have been considered. Among them, possibly the most compelling one is envy-freeness up to any item (EFX), where no agent envies another agent after the removal of any single item from the other agent's bundle. However, despite significant efforts by many researchers for several years, it is known that a complete EFX allocation always exists only in limited cases. In this paper, we show that a complete EFX allocation always exists when each agent is of one of two given types, where agents of the same type have identical additive valuations. This is the first such existence result for non-identical valuations when there are any number of agents and items and no limit on the number of distinct values an agent can have for individual items. We give a constructive proof, in which we iteratively obtain a Pareto dominating (partial) EFX allocation from an existing partial EFX allocation.