2026/08/05 by Max Dupré la Tour, Ayumi Igarashi
Computer Science · #cs.GT
arxiv created 2026/08/05 · arxiv updated 2026/08/06
We give an existential transfer framework for converting continuous fair division theorems into guarantees for indivisible items arranged on a path. This allows continuous envy-freeness and consensus results to translate directly into EFk-type guarantees for indivisible allocations. Combining this method with connected cake-cutting theorems, we obtain connected allocations satisfying envy-freeness up to one good and one chore for identical valuations and for arbitrary valuations when the number of agents is a prime power. Combining this method with the equicardinal necklace-splitting theorem of Jojić et al., we show that, for any prime-power number r of bundles and n arbitrary valuation functions, there exists an allocation in which every bundle is the union of at most n intervals, and the bundles satisfy consensus up to n goods and n chores. This result is the first EFk-type guarantee for consensus fair division with non-additive valuations beyond the halving case. Envy-freeness constraints can be imposed simultaneously at the cost of one additional interval and one additional item in each guarantee. As a consequence, when the number of agents is a prime power, every instance with monotone valuations admits an EF2 allocation whose bundle sizes differ by at most two.