A Discrete and Bounded Locally Envy-Free Cake Cutting Protocol on Trees

EasyChair Preprint 11034

Abstract

We 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 envy-free cake division, but with a huge query complexity consisting of six towers of exponent in the number of agents, $n$. However, the best-known 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 envy-free 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 non-trivial graph structure, namely a tree having depth at most $2$, that admits a query efficient protocol to find locally envy-free allocations using $O(n^4 \log n)$ queries under the standard Robertson-Webb (RW) query model. To the best of our knowledge, this is the first such non-trivial graph structure. In our second result, we develop a novel cake-division protocol that finds a locally envy-free 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 best-known query complexity of six-towers-of-$n$ for complete graphs.

Keyphrases: envy-freeness, fair division, graph constraints

@booklet{EasyChair:11034,
  author    = {Ganesh Ghalme and Xin Huang and Yuka Machino and Nidhi Rathi},
  title     = {A Discrete and Bounded Locally Envy-Free Cake  Cutting Protocol on Trees},
  howpublished = {EasyChair Preprint 11034},
  year      = {EasyChair, 2023}}