Papers for

resource allocation software engineers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Fair allocation exchanges may fail to stay fair in every step

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.

Mon 14 SeptComputer Science and Game TheoryDiscrete Mathematics
The gist
This paper looks at how to change one fair way of splitting things to another fair way by swapping items fairly at each step. It finds that even when starting with good fair setups, it isn't always possible to keep fairness in every exchange step unless you relax fairness a bit. They also show deciding if such a fully fair swapping path exists is very hard to compute. However, some simple picking methods guarantee you can get from one fair split to another by slightly relaxing fairness. Lastly, they explore how allowing transfers makes it easier to keep fairness throughout the process.
Open 2609.15358v1