Networked Fairness in Cake Cutting

Xiaohui Bei, Youming Qiao, Shengyu Zhang

Abstract

We introduce a graphical framework for fair division in cake cutting, where comparisons between agents are limited by an underlying network structure. We generalize the classical fairness notions of envy-freeness and proportionality in this graphical setting. An allocation is called envy-free on a graph if no agent envies any of her neighbor's share, and is called proportional on a graph if every agent values her own share no less than the average among her neighbors, with respect to her own measure. These generalizations enable new research directions in developing simple and efficient algorithms that can produce fair allocations under specific graph structures. On the algorithmic frontier, we first propose a moving-knife algorithm that outputs an envy-free allocation on trees. Next, we give a discrete and bounded algorithm for computing a proportional allocation on transitive closure of trees, a class of graphs formed by taking a rooted tree and connecting all its ancestor-descendant pairs.

Introduction

The "cake cutting" problem is a fundamental challenge in multi-agent systems: how to divide a divisible resource fairly among $n$ agents with different preferences. Traditionally, fairness is viewed globally. Envy-freeness requires that no agent prefers another's slice, while proportionality ensures everyone receives at least $1/n$ of the total value. However, global envy-freeness is computationally intensive, and in large-scale systems, agents often only compare themselves to a local neighborhood.

This paper proposes a networked approach where fairness is defined relative to a graph $G$. By relaxing global requirements to local ones, we can design significantly more efficient and simpler algorithms for specific network topologies like trees and hierarchical descendant graphs.

Graphical Fairness Framework

In this framework, an allocation is envy-free on $G$ if agent $i$ does not envy any neighbor $j$ in the graph. Similarly, an allocation is proportional on $G$ if agent $i$ values their own share at least as much as the average value of the shares held by their neighbors (including themselves).

A key theoretical finding is that while envy-freeness is "downward closed" (a globally envy-free allocation is locally envy-free on any subgraph), proportionality is not. Removing an edge changes the local average, meaning a globally proportional allocation might fail to be locally proportional on a sparse graph. This necessitates specialized algorithms for networked proportionality.

Algorithms for Trees and Hierarchies

Envy-Freeness on Trees

For tree structures, we propose a moving-knife procedure that operates top-down from the root. The root divides the cake into equal pieces (using the Austin procedure), and children select the best pieces for their subtrees. This ALLOCATIONTREE algorithm achieves envy-freeness on any $n$-node tree using only $O(n^2)$ cuts—a massive reduction from the complexity required for complete graphs.

Proportionality on Descendant Graphs

We target "descendant graphs," which are formed by taking a rooted tree and connecting all ancestor-descendant pairs. This structure effectively models organizational hierarchies where priority or seniority exists.

Comparison of a rooted tree (a) and its corresponding descendant graph (b).

To solve proportionality on these graphs, we introduce a "collect-cut-distribute" algorithm. Nodes calculate a function $f(v)$ to determine how many slices to create from pieces inherited from ancestors before distributing them to descendants.

The execution of the proportional allocation algorithm, showing f-values and the distribution process.

Key Results and Complexity

The proposed algorithms offer significant complexity gains over general-purpose protocols:

  • Trees: Envy-free allocations are found in $O(n^2)$ cuts.
  • Descendant Graphs: The ALGDESCENDANTGRAPH ensures proportionality with "singly exponential" complexity ($n^2 \cdot d!$ cuts, where $d$ is depth), which is a significant improvement over the astronomical complexity of general envy-free algorithms for complete graphs.
  • Existence Proof: The paper formally proves that for any graph $G$, an envy-free allocation always exists, but a proportional one requires specific algorithmic care due to the lack of monotonicity.

Conclusion

By shifting the focus from global to networked fairness, we uncover more efficient pathways for resource division. While trees and descendant graphs provide a strong foundation, future work should explore more diverse topologies, such as social network power-laws or grid graphs, to further bridge the gap between local and global fairness.

Summary updated

Abstract

We introduce a graphical framework for fair division in cake cutting, where comparisons between agents are limited by an underlying network structure. We generalize the classical fairness notions of envy-freeness and proportionality in this graphical setting. An allocation is called envy-free on a graph if no agent envies any of her neighbor's share, and is called proportional on a graph if every agent values her own share no less than the average among her neighbors, with respect to her own measure. These generalizations enable new research directions in developing simple and efficient algorithms that can produce fair allocations under specific graph structures. On the algorithmic frontier, we first propose a moving-knife algorithm that outputs an envy-free allocation on trees. The algorithm is significantly simpler than the discrete and bounded envy-free algorithm introduced in [Aziz and Mackenzie, 2016] for compete graphs. Next, we give a discrete and bounded algorithm for computing a proportional allocation on transitive closure of trees, a class of graphs by taking a rooted tree and connecting all its ancestor-descendant pairs.
BibTeX
@inproceedings{bei2017networked,
  author = {Xiaohui Bei and Youming Qiao and Shengyu Zhang},
  title = {{Networked Fairness in Cake Cutting}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  url = {https://openreview.net/forum?id=r1Z-WBfObH},
}
Figure