Cutsets and EF1 Fair Division of Graphs

A connected graph 𝐺 = (𝑉 , 𝐸) provides a natural context for importing the connectivity requirement of fair division from the continuous world into the discrete one. Each of 𝑛 agents is allocated a share of 𝐺's vertex set 𝑉. These 𝑛 shares partition 𝑉 , 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 𝑛. If 𝐺 contains a cutset of gap 𝑘 ≥ 2 and valence in the interval [𝑛-𝑘 + 1, 𝑛-1], then allocations that are CEF1 (connected EF1) fail to exist for 𝑛 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 𝐺 𝐼 𝐼 𝐼 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 𝐺 we can, in combination with some new positive results, pin down 𝐺's spectrum-the list of exactly which values of 𝑛 do/ do not guarantee CEF1 allocations. Examples suggest a conjectured common spectral pattern for all graphs.