WorksComputer Science
On the Complexity of Envy Cycle Elimination
Abstract
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 time for agents and goods, and establish the tightness of this bound.