Cutsets and EF1 Fair Division of Graphs

Abstract

A connected graph G = (V, E) provides a natural context for importing the connectivity requirement of fair division from the continuous world into the discrete one. Each of n agents is allocated a share of G's vertex set V. These n shares partition V, with each required to induce a connected subgraph. Agents use their own valuation functions to determine the non-negative numerical values of the shares, which then determine whether the allocation is fair in some specified sense. Applications include the problem of dividing cities connected by a road network when each party wishes to drive among its allocated cities without leaving its territory. We introduce graph cutsets - forbidden substructures which block allocations that are fair in the EF1 (envy-free up to one item) sense. Two parameters - gap and valence - determine blocked values of n. If G contains a cutset of gap k ≥ 2 and valence in the interval [n - k + 1, n - 1], then allocations that are CEF1 (connected EF1) fail to exist for n agents with certain CM (common monotone) valuations; an elementary cutset yields such a failure even for CA (common additive) valuations. Additionally, we provide an example (Graph GIII in Figure 1) which excludes both cutsets of gap at least two and CEF1 divisions for three agents even with CA valuations. We show that it is NP-complete to determine whether cutsets exist. Finally, for some graphs G we can, in combination with some new positive results, pin down G's spectrum - the list of exactly which values of n do/do not guarantee CEF1 allocations. Examples suggest a conjectured common spectral pattern for all graphs.