Optimizing the Envy Cycle Elimination Algorithm
2026-06-01 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors study a method called envy cycle elimination (ECE) that fairly divides items so no one envies another's share too much. While ECE always finds a fair allocation, it allows different choices about who gets which item and when. They show that if these choices are made by picking the combination that increases overall happiness the most, the total happiness is better than with random or simpler choices. However, improving choice in only one part (item or person) doesn’t help as much. They also tested their ideas with experiments to support their findings.
fair allocationindivisible goodsenvy-freeness up to one good (EF1)envy cycle elimination (ECE)utilitarian welfareheuristicsallocation algorithmswelfare guarantees
Authors
Karen Frilya Celine, Warut Suksompong
Abstract
In the fair allocation of indivisible goods, a widely used notion of fairness is envy-freeness up to one good (EF1). A classical way to compute an EF1 allocation is the envy cycle elimination (ECE) algorithm, which iteratively assigns a good to an unenvied agent and, after each assignment, resolves any resulting envy cycle. Although the ECE algorithm always produces an EF1 allocation, it leaves considerable freedom in choosing both the next good to allocate and the agent to receive it. We investigate natural heuristics that exploit this flexibility to improve welfare guarantees. For example, we show that if the heuristic jointly selects the good and the receiving agent maximizing the utility, the worst-case utilitarian welfare loss is significantly lower than that of the vanilla algorithm. By contrast, restricting the heuristic to select only one of these two dimensions does not yield comparable improvements. We also complement our theoretical results with empirical average-case analysis.