Fair division of graphs and of tangled cakes

DOI10.1007/S10107-023-01945-5arXiv2102.08560OpenAlexW3129431470MaRDI QIDQ6120940FDOQ6120940

Authors: Ayumi Igarashi, William S. Zwicker 

Publication date: 21 February 2024

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Abstract: 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 $mathcalT$ corresponds in a natural way to an infinite topological class $mathcalG(mathcalT)$ 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`o 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 $kgeq1$ 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`o 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`o et al to show that all graphs in the topological class guarantee EF1${}_{outer}$ allocations for three agents.

Full work available at URL: https://arxiv.org/abs/2102.08560

Recommendations

• Almost envy-free allocations with connected bundles
• Approximate envy-freeness in graphical cake cutting
• Dividing a graphical cake
• Almost envy-free allocations with connected bundles
• The price of connectivity in fair division

zbMATH Keywords

graphstanglesfair divisioncake cuttingenvy-freeness

Mathematics Subject Classification ID

Applications of graph theory (05C90) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Cites Work

• Graph theory
• Rental Harmony: Sperner's Lemma in Fair Division
• How to Cut a Cake Fairly
• Dividing a cake fairly
• A moving-knife solution to the four-person envy-free cake-division problem
• Cake division with minimal cuts: envy-free procedures for three persons, four persons, and beyond
• Non-Separable and Planar Graphs
• Almost envy-free allocations with connected bundles
• Maximin share allocations on cycles
• The price of connectivity in fair division

Cited In (3)

• Approximate envy-freeness in graphical cake cutting
• Dividing a graphical cake
• Almost envy-free allocations with connected bundles

This page was built for publication: Fair division of graphs and of tangled cakes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6120940)