Fair division of graphs and of tangled cakes

Abstract

Fair division has been studied in both continuous and discrete contexts. One strand of the continuous literature seeks to award each agent with a single connected piece-a subinterval. The analogue for the discrete case corresponds to the fair division of a graph, where allocations must be contiguous so that each bundle of vertices is required to induce a connected subgraph. With envy-freeness up to one item (EF1) as the fairness criterion, however, positive results for three or more agents havemostly been limited to traceable graphs. We introduce tangles as a new context for fair division. A tangle is a more complicated cake-a connected topological space constructed by gluing together several copies of the unit interval [0, 1]-and each single tangle T corresponds in a natural way to an infinite topological class G(T) of graphs, linking envy-free fair division of tangles to EFk fair division of graphs. In addition to the unit interval itself, we show that only five other stringable tangles guarantee the existence of envyfree and connected allocations for arbitrarily many agents, with the corresponding topological classes containing only traceable graphs. Any other tangle T has a bound r on the number of agents for which such allocations necessarily exist, and our Negative Transfer Principle then applies to the graphs in T 's class; for any integer k >= 1, almost all graphs in this class are non-traceable and fail to guarantee EFk contiguous allocations for r + 1 or more agents, even when very strict requirements are placed on the valuation functions for the agents. 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 L guarantees envy-free allocations of connected shares for three agents. We then modify the discrete version of Stromquist's procedure in Bilo et al. (Games Econ Behav 131:197-221, 2022) to show that all graphs in the topological class G(L) (most of which are non-traceable) guarantee EF1 allocations for three agents.