论文标题
嫉妒的蛋糕切成图形约束
Envy-Free Cake Cutting with Graph Constraints
论文作者
论文摘要
我们研究了$ n $ n $代理商在蛋糕中相当划分的异质和可分裂资源的经典问题 - 以蛋糕为代表，$ [0,1] $。这项工作考虑了该问题的有趣变体，其中代理嵌入了图。图形约束需要每个代理商对她的邻居份额进行评估她的分配份额。鉴于图表，目标是有效地找到一个本地嫉妒的分配，每个代理商对她的份额的份额至少与邻居的份额一样多。 最著名的算法（由Aziz和Mackenzie）找到了嫉妒的蛋糕划分具有超指数的查询复杂性。这项工作的关键技术贡献之一是在$ n $ n $ agents上确定一个非平凡的图形结构 - 深度为最深度为2（depth2tree）的树图，该$ n $ n $代理承认有效的有效的蛋糕切割协议（在Robertson-Webb查询模型下）。特别是，我们开发了一个离散协议，该协议在$ o（n^3 \ log（n））$ cuts cains of cake上找到了$ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $的无本地分配。对于Depth2tree的特殊情况，每个非根源代理都连接到最重要的两个代理（2星），我们表明$ O（n^2）$ Queries就足够了。我们通过建立$ω（n^2）$（评估）查询的算法结果来补充我们的算法结果，以在1星形图上找到$ n $ n $ apent的本地无嫉妒的分配（在假设根代理将蛋糕分配到$ n $ n $ connectectection的情况下）。
We study the classic problem of fairly dividing a heterogeneous and divisible resource -- represented by a cake, $[0,1]$ -- 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 neighbor's share. Given a graph, the goal is to efficiently find a locally envy-free allocation where every agent values her share to be at least as much as any of her neighbor's share. The best known algorithm (by Aziz and Mackenzie) for finding envy-free cake divisions has a hyper-exponential query complexity. One of the key technical contributions of this work is to identify a non-trivial graph structure -- tree graphs with depth at-most two (Depth2Tree) -- on $n$ agents that admits a query efficient cake-cutting protocol (under the Robertson-Webb query model). In particular, we develop a discrete protocol that finds a locally envy-free allocation among $n$ agents on depth-two trees with at-most $O(n^3 \log(n))$ cuts on the cake. For the special case of Depth2Tree where every non-root agent is connected to at-most two agents (2-Star), we show that $O(n^2)$ queries suffice. We complement our algorithmic results with establishing a lower bound of $Ω(n^2)$ (evaluation) queries for finding a locally envy-free allocation among $n$ agents on a 1-Star graph (under the assumption that the root agent partitions the cake into $n$ connected pieces).
