Fair division of graphs and of tangled cakes
share
A tangle is a connected topological space constructed by gluing several copies of the unit interval [0, 1]. We explore which tangles guarantee envy-free allocations of connected shares for n agents, meaning that such allocations exist no matter which monotonic and continuous functions represent agents' valuations. Each single tangle 𝒯 corresponds in a natural way to an infinite topological class 𝒢(𝒯) of multigraphs, many of which are graphs. This correspondence links EF fair division of tangles to EFk_outer fair division of graphs. We know from Bilò et al that all Hamiltonian graphs guarantee EF1_outer allocations when the number of agents is 2, 3, 4 and guarantee EF2_outer allocations for arbitrarily many agents. We show that exactly six tangles are stringable; these guarantee EF connected allocations for any number of agents, and their associated topological classes contain only Hamiltonian graphs. Any non-stringable tangle has a finite upper bound r on the number of agents for which EF allocations of connected shares are guaranteed. Most graphs in the associated non-stringable topological class are not Hamiltonian, and a negative transfer theorem shows that for each k ≥ 1 most of these graphs fail to guarantee EFk_outer allocations of vertices for r + 1 or more agents. This answers a question posed in Bilò et al, and explains why a focus on Hamiltonian graphs was necessary. With bounds on the number of agents, however, we obtain positive results for some non-stringable classes. An elaboration of Stromquist's moving knife procedure shows that the non-stringable lips tangle guarantees envy-free allocations of connected shares for three agents. We then modify the discrete version of Stromquist's procedure in Bilò et al to show that all graphs in the topological class guarantee EF1_outer allocations for three agents.
READ FULL TEXT