Networked Fairness in Cake Cutting

Networked Fairness in Cake Cutting

Xiaohui Bei, Youming Qiao, Shengyu Zhang

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 3632-3638. https://doi.org/10.24963/ijcai.2017/508

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.
Keywords:
Multidisciplinary Topics and Applications: AI and Social Sciences
Knowledge Representation, Reasoning, and Logic: Game Theory
Agent-based and Multi-agent Systems: Coordination and cooperation
Agent-based and Multi-agent Systems: Social Choice Theory