蛋糕切割图：离散和有界比例协议

作者：Xiaohui Bei,Xiaoming Sun,Hao Wu,Jialin Zhang,Zhijie Zhang,Wei Zi

摘要：经典的蛋糕切割问题研究如何在多个代理之间找到异构和可分割资源的公平分配。蛋糕切割中最常被研究的两个公平概念是比例性和羡慕性。众所周知，通过简单的协议可以有效地找到试剂之间的比例分配[16]。对于嫉妒，在最近的一次突破中，Aziz和Mackenzie [5]为任意数量的玩家提出了一个独立且有限的无嫉妒协议。然而，该协议遭受高多指数查询复杂性的困扰，并且仍然可以找到更简单和更有效的无羡慕协议。

在本文中，我们通过假设边缘描述其熟人关系的代理的基础图来考虑蛋糕切割问题的变化，并且代理相对于其邻居的那些评估他们的份额。如果每个代理人认为她至少获得了邻居的平均价值，则分配称为本地比例。局部比例性概括了比例性，并且在比例性和嫉妒之间处于一个有趣的中间地带：它的存在由无嫉妒的分配保证，但是没有简单的协议可以为一般图形产生这样的局部比例分配。以前的工作显示了特殊类图的局部比例协议，它在[1]和[8]中列出，作为一个开放性问题，为更一般的图类设计简单的局部比例协议。在本文中，我们通过为任何给定图形呈现离散且有界的局部比例协议来完全解决这个开放式问题。我们的协议的查询复杂度只有单个指数，这明显小于[5]中给出的无嫉妒协议的六个塔的复杂度。

原文标题：Cake Cutting on Graphs: A Discrete and Bounded Proportional Protocol

原文摘要：The classical cake cutting problem studies how to find fair allocations of a heterogeneous and divisible resource among multiple agents. Two of the most commonly studied fairness concepts in cake cutting are proportionality and envy-freeness. It is well known that a proportional allocation amongnagents can be found efficiently via simple protocols [16]. For envy-freeness, in a recent breakthrough, Aziz and Mackenzie [5] proposed a discrete and bounded envy-free protocol for any number of players. However, the protocol suffers from high multiple-exponential query complexity and it remains open to find simpler and more efficient envy-free protocols.

In this paper we consider a variation of the cake cutting problem by assuming an underlying graph over the agents whose edges describe their acquaintance relationships, and agents evaluate their shares relatively to those of their neighbors. An allocation is called locally proportional if each agent thinks she receives at least the average value over her neighbors. Local proportionality generalizes proportionality and is in an interesting middle ground between proportionality and envy-freeness: its existence is guaranteed by that of an envy-free allocation, but no simple protocol is known to produce such a locally proportional allocation for general graphs. Previous works showed locally proportional protocols for special classes of graphs, and it is listed in both [1] and [8] as an open question to design simple locally proportional protocols for more general classes of graphs. In this paper we completely resolved this open question by presenting a discrete and bounded locally proportional protocol for any given graphs. Our protocol has a query complexity of only single exponential, which is significantly smaller than the six towers ofnquery complexity of the envy-free protocol given in [5].

地址：https://arxiv.org/abs/1907.05083