Title: Fair Division of Graphs and of Tangled Cakes
Presented By: William Zwicker

Abstract:
Recent work by Bilò et al [1] concerns allocating graph vertices (treated as indivisible objects) so that each share forms a connected subgraph, and so that no agent x envies another’s share “up to one good” – there is always some vertex in agent y’s share such that any envy x may have for y’s share would be erased if x pretended y had not received that vertex. Their methods are adapted from the cake-cutting literature, wherein the unit interval [0,1] serves as a model for the continuous “cake.” But the discrete analogue of [0,1] is the topological class of all path graphs, so most of their results apply only to path graphs (and Hamiltonian graphs, which add edges to a path graph). How about non-Hamiltonian graphs? Here, the continuous analogue is more complicated than [0,1]; several copies of [0,1] are glued at their endpoints to form the letter Y, or the figure 8, or something more complex . . . a “tangle.” We give some positive and negative results for envy free division of tangles, and discuss implications for the original problem of graph division. These implications are negative for results that apply – for any number of agents – to all graphs in a non-Hamiltonian topological class, but we conjecture some positive implications when one bounds the number of agents.