Download PDFOpen PDF in browserA Discrete and Bounded Locally EnvyFree Cake Cutting Protocol on TreesEasyChair Preprint no. 1103418 pages•Date: October 6, 2023AbstractWe study the classic problem of fairly allocating a divisible resource modeled as a line segment $[0,1]$ and referred to as a cake. In a landmark result, Aziz and Mackenzie [FOCS'16] gave the first discrete and bounded protocol for computing an envyfree cake division, but with a huge query complexity consisting of six towers of exponent in the number of agents, $n$. However, the bestknown lower bound for the same is $\Omega(n^2)$, leaving a massive gap in our understanding of the complexity of the problem. In this work, we study an important variant of the problem where agents are embedded on a graph, whose edges determine agent relations. Given a graph, the goal is to find a locally envyfree allocation where every agent values her share of the cake at least as much as that of any of her neighbors' share. We identify a nontrivial graph structure, namely a tree having depth at most $2$, that admits a query efficient protocol to find locally envyfree allocations using $O(n^4 \log n)$ queries under the standard RobertsonWebb (RW) query model. To the best of our knowledge, this is the first such nontrivial graph structure. In our second result, we develop a novel cakedivision protocol that finds a locally envyfree allocation among $n$ agents on any tree graph using $O(n^{2n})$ RW queries. Though exponential, our protocol for tree graphs achieves a significant improvement over the bestknown query complexity of sixtowersof$n$ for complete graphs. Keyphrases: envyfreeness, fair division, graph constraints
