Reconfiguration in Fair Division Revisited

Abstract

We revisit reconfiguration in the fair allocation of indivisible goods, where the goal is to transform one fair allocation into another through a sequence of exchanges while preserving fairness at every step. Our focus is on the hierarchy of envy-freeness up to $k$ goods (EF$k$). We show that for any fixed $k$, two EF1 allocations with the same size vector need not admit a reconfiguration path whose intermediate allocations satisfy EF$k$. This impossibility persists even when the two allocations arise from standard EF1 approaches: the envy cycle elimination algorithm or the maximum Nash welfare solution. In contrast, we prove that allocations with the same size vector produced by recursively balanced picking sequences, including round-robin, are always connected via a path that maintains EF2. We also show that deciding whether an EF1 reconfiguration path exists is NP-hard for any fixed number of agents. Furthermore, we complement these exchange-based results by studying a more permissive model that also allows transfers, establishing additional connectivity guarantees.