Best-of-Both-Worlds Fairness of the Envy-Cycle-Elimination Algorithm
This work addresses the challenge of combining ex-post and ex-ante fairness in indivisible goods allocation, but the results are largely negative for three or more agents, indicating limitations of the ECE approach.
The paper investigates whether the Envy-Cycle-Elimination (ECE) algorithm can be randomized to achieve ex-ante proportionality in addition to its known fairness guarantees. For two agents, a randomized variant achieves ex-post EFX and ex-ante envy-free in near-linear time, but for three agents, natural randomization methods fail to ensure ex-ante proportionality.
We consider the problem of fairly dividing indivisible goods among agents with additive valuations. It is known that an Epistemic EFX and $2/3$-MMS allocation can be obtained using the Envy-Cycle-Elimination (ECE) algorithm. In this work, we explore whether this algorithm can be randomized to also ensure ex-ante proportionality. For two agents, we show that a randomized variant of ECE can compute an ex-post EFX and ex-ante envy-free allocation in near-linear time. However, for three agents, we show that several natural randomization methods for ECE fail to achieve ex-ante proportionality.