Networked fairness in cake cutting

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