From Cake-Cutting and Necklace-Splitting to Fair Division of Indivisible Items

Abstract

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 EF$k$-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 EF$k$-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 EF$2$ allocation whose bundle sizes differ by at most two.