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 have mostly 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 $$\mathcal {T}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>T</mml:mi> </mml:math> corresponds in a natural way to an infinite topological class $$\mathcal {G}(\mathcal {T})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>G</mml:mi> <mml:mo>(</mml:mo> <mml:mi>T</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> of graphs, linking envy-free fair division of tangles to EF k fair division of graphs. In addition to the unit interval itself, we show that only five other stringable tangles guarantee the existence of envy-free and connected allocations for arbitrarily many agents, with the corresponding topological classes containing only traceable graphs. Any other tangle $$\mathcal {T}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>T</mml:mi> </mml:math> 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 $$\mathcal {T}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>T</mml:mi> </mml:math> ’s class; for any integer $$k \ge 1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> , almost all graphs in this class are non-traceable and fail to guarantee EF k contiguous allocations for $$r + 1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>r</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> 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 $$\mathcal {L}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>L</mml:mi> </mml:math> guarantees envy-free allocations of connected shares for three agents. We then modify the discrete version of Stromquist’s procedure in Bilò et al. (Games Econ Behav 131:197–221, 2022) to show that all graphs in the topological class $$\mathcal {G}(\mathcal {L})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>G</mml:mi> <mml:mo>(</mml:mo> <mml:mi>L</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> (most of which are non-traceable) guarantee EF1 allocations for three agents.