Connectedness in weighted consensus division of graphical cakes between two agents
Josef Hanke, Ana Rita Pires · Mathematical Social Sciences · 2025
Austin’s moving knife procedure was originally introduced to find a consensus division of an interval/circular cake between two agents, each of whom believes that they receive exactly half of the cake. We generalise this in two ways: we consider cakes modelled by graphs, and let the two agents have unequal, arbitrary entitlements. In this setting, we seek a weighted consensus division – one where each agent believes they received exactly the share they are entitled to – which also minimises the number of connected components that each agent receives. First, we review the weighted consensus division of a circular cake, which gives exactly one connected piece to each agent. Next, by judiciously mapping a circle to a graph, we produce a weighted consensus division of a star graph cake that gives at most two connected pieces to each agent — and show that this bound on the number of connected pieces is tight. For a tree, each agent receives at most h + 1 connected pieces, where h is the minimal height of the tree. For a connected graphical cake, each agent receives r + 2 connected pieces, where r is the radius of the graph. Finally, for a graphical cake with s connected components, the division involves at most s + 2 r + 4 connected pieces, where r is the maximum radius among all connected components. • We investigate fair division of a cake between two agents with unequal entitlements. • We obtain a consensus division: both agents agree that each got their entitlement. • The cake is shaped like a graph, generalising the usual interval or circle models. • A graphical cake can better model road networks, power grids, or rivers. • We give bounds on the number of connected components received by each agent.