• Friday, May 21 st, 2021 : William Zwicker (Union College)

https://zoom.univ-paris1.fr/j/92167705411?pwd=dDVOT1lyZmZ1N0ZlV2FzSk5KNTZSZz09

pwd: 369238

meeting number: 921 6770 5411

Title : Fair division of graphs and of tangled cakes

Summary: Fair Division is studied in both the continuous context (a single divisible “cake” is modeled by the [0, 1] interval) and the discrete (a pile of indivisible objects will be divided into sub-piles). One strand of the continuous literature seeks to award a single connected piece (a subinterval) as each agent’s share; what is the analogue for the discrete case? In fair division of a graph, the indivisible graph vertices are allocated to the agents, with each share of vertices required to induce a connected subgraph. When the envy freeness fairness criterion is adjusted to handle indivisible objects and applied to graphs, however, positive results for three or more agents have been limited – until recently ­– to Hamiltonian graphs (graphs with a path visiting each vertex exactly once). QUESTION: Is this limitation fundamental?

We introduce tangles – a new context for fair division. A tangle is a connected topological space constructed by gluing together several copies of the unit interval [0, 1]. We explore which tangles guarantee envy-free allocations of connected shares for n agents. Each single tangle T corresponds in a natural way to an infinite topological class G(T) of graphs. This correspondence links fair division of tangles to EFkouter fair division of graphs, in a way that yields partial answers to our question. Loosely speaking, the answers are “No, if three agents are sharing the graph,” but “Yes, if arbitrarily many agents".