Complete EFX allocation of indivisible goods with additive values
Let $N = \{1, \dots, n\}$ be a finite set of agents, $n \ge 1$, and $M$ a finite set of indivisible goods. Agent $i$ values each good $g$ at $v_{ig} \ge 0$ and each bundle $S \subseteq M$ additively, at $v_i(S) = \sum_{g \in S} v_{ig}$. A complete allocation is a partition $(A_1, \dots, A_n)$ of $M$, with empty bundles allowed.
Caragiannis, Kurokawa, Moulin, Procaccia, Shah and Wang introduced envy-freeness up to any good (EFX), requiring the inequality below only for goods $g$ with $v_{ig} > 0$. By a perturbation argument of Chaudhury, Garg and Mehlhorn, complete allocations of the one kind exist for every additive valuation profile if and only if complete allocations of the other kind do. Complete EFX allocations exist for two agents (Plaut and Roughgarden), for three agents (Chaudhury, Garg and Mehlhorn), and whenever the agents have at most three distinct valuation functions (Prakash HV, Ghosal, Nimbhorkar and Varma).
Problem. Does every such valuation profile admit a complete allocation with $$v_i(A_i) \ge v_i(A_j \setminus \{g\}) \qquad \text{for all } i, j \in N \text{ and every } g \in A_j,$$ including goods $g$ that agent $i$ values at zero?
Source: Caragiannis, Kurokawa, Moulin, Procaccia, Shah and Wang (2016), the open question after Definition 4.4, with envy tested only after removing positively valued goods. Stated with every good (EFX₀) by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Secondary
- OC
- Keywords
- AIM Open Applied Problems, envy-free allocations, fair division
References
@inproceedings{caragiannis2016,
author = {Caragiannis, Ioannis and Kurokawa, David and Moulin, Herv{\'e} and Procaccia, Ariel D. and Shah, Nisarg and Wang, Junxing},
title = {The unreasonable fairness of maximum {N}ash welfare},
booktitle = {Proceedings of the 2016 ACM Conference on Economics and Computation (EC '16)},
publisher = {ACM},
address = {New York},
year = {2016},
pages = {305--322},
doi = {10.1145/2940716.2940726},
}
@article{chaudhury2024,
author = {Chaudhury, Bhaskar Ray and Garg, Jugal and Mehlhorn, Kurt},
title = {{EFX} exists for three agents},
journal = {J. ACM},
volume = {71},
number = {1},
year = {2024},
pages = {Art. 4, 1--27},
doi = {10.1145/3616009},
}
@article{plaut2020,
author = {Plaut, Benjamin and Roughgarden, Tim},
title = {Almost envy-freeness with general valuations},
journal = {SIAM J. Discrete Math.},
volume = {34},
number = {2},
year = {2020},
pages = {1039--1068},
doi = {10.1137/19M124397X},
}
@inproceedings{prakash2025,
author = {Prakash HV, Vishwa and Ghosal, Pratik and Nimbhorkar, Prajakta and Varma, Nithin},
title = {{EFX} exists for three types of agents},
booktitle = {Proceedings of the 26th ACM Conference on Economics and Computation (EC '25)},
publisher = {ACM},
address = {New York},
year = {2025},
pages = {101--128},
doi = {10.1145/3736252.3742509},
eprint = {2410.13580},
archivePrefix = {arXiv},
}
@misc{aim-efx-additive-goods,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Complete EFX allocation of indivisible goods with additive values}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/313-efx-additive-goods.md},
note = {Entry 313 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00428, "Complete EFX allocation of indivisible goods with additive values", clopen.solutions.