On the Complexity of Envy Cycle Elimination
The envy cycle elimination (ECE) algorithm is a fundamental algorithm for the fair allocation of indivisible goods, guaranteeing an allocation that is envy-free up to one good under arbitrary monotone utilities. We show that the ECE algorithm can be implemented in $O(nm)$ time for $n$ agents and $m$ goods, and establish the tightness of this bound.
Authors
- Warut Suksompong (ORCID: https://orcid.org/0000-0001-8973-2539)
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-11-18
- DOI
- https://doi.org/10.48550/arxiv.2611.24167
- Primary Topic
- Game Theory and Voting Systems
- Type
- preprint