论文标题
在树上的离散且有限的本地无嫉妒的蛋糕切割方案
A Discrete and Bounded Locally Envy-Free Cake Cutting Protocol on Trees
论文作者
论文摘要
我们研究了\ emph {相当}的经典问题，将异质和可分裂的资源分开 - 模型为线段$ [0,1] $，通常称为\ emph {cake} - 在$ n $代理中。这项工作考虑了该问题的有趣变体，其中代理嵌入了图。图形约束需要每个代理商对她的邻居份额进行评估她的分配份额。鉴于图，目标是有效地找到\ emph {本地嫉妒的}分配，其中每个代理都重视她的蛋糕所占的份额至少与邻居的任何份额一样多。 这项工作的最重要贡献是一个有界协议，该协议在树图上使用$ n^{o（n）} $ Queries在标准Robertson-Webb（RW）查询模型下的$ n^{o（n）} $查询中找到了本地无嫉妒的分配。我们提出的协议的查询复杂性虽然指数级，但显着改善了目前最著名的Aziz和Mackenzie [AM16]的高指数查询复杂性结合了完整的图表。特别是，我们还表明，如果下面的树图最多具有两个深度，则可以找到一个本地嫉妒的分配，并带有$ O（n^4 \ log n）$ rw查询。这是针对非平凡图结构的第一个也是唯一具有多项式查询复杂性的本地嫉妒的切割方案。 有趣的是，我们的离散协议简单易懂，而不是[AM16]的高度参与的协议。这种简单性可以归因于它们的递归性质以及将单个代理作为指定的\ emph {cutter}的使用。我们认为，这些结果将有助于我们通过发现其查询复杂性中的瓶颈及其与基础图形结构的关系，从而提高对嫉妒无蛋糕切割的具有挑战性问题的算法理解。
We study the classic problem of \emph{fairly} dividing a heterogeneous and divisible resource -- modeled as a line segment $[0,1]$ and typically called as a \emph{cake} -- among $n$ agents. This work considers an interesting variant of the problem where agents are embedded on a graph. The graphical constraint entails that each agent evaluates her allocated share only against her neighbors' share. Given a graph, the goal is to efficiently find a \emph{locally envy-free} allocation where every agent values her share of the cake to be at least as much as that of any of her neighbors' share. The most significant contribution of this work is a bounded protocol that finds a locally envy-free allocation among $n$ agents on a tree graph using $n^{O(n)}$ queries under the standard Robertson-Webb (RW) query model. The query complexity of our proposed protocol, though exponential, significantly improves the currently best known hyper-exponential query complexity bound of Aziz and Mackenzie [AM16] for complete graphs. In particular, we also show that if the underlying tree graph has a depth of at most two, one can find a locally envy-free allocation with $O(n^4 \log n)$ RW queries. This is the first and the only known locally envy-free cake cutting protocol with polynomial query complexity for a non-trivial graph structure. Interestingly, our discrete protocols are simple and easy to understand, as opposed to highly involved protocol of [AM16]. This simplicity can be attributed to their recursive nature and the use of a single agent as a designated \emph{cutter}. We believe that these results will help us improve our algorithmic understanding of the arguably challenging problem of envy-free cake-cutting by uncovering the bottlenecks in its query complexity and its relation to the underlying graph structures.
