Fair division of graphs and of tangled cakes

DOI10.1007/S10107-023-01945-5MaRDI QIDQ6120940zbMATH OpenOpenAlexFDO

Authors Ayumi Igarashi, William S. Zwicker

Publication date 21 February 2024

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

Copyright license Creative Commons Attribution 4.0 International

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

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)

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.

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

Cites work

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