论文标题
与连接的碎片的嫉妒无蛋糕部的近似算法
Approximation Algorithms for Envy-Free Cake Division with Connected Pieces
论文作者
论文摘要
蛋糕切割是一个经典的模型，用于研究具有个人喜好的代理商中异质，可分裂的资源的公平划分。在典型的要求下，每个代理必须收到连接的蛋糕，我们开发了近似算法，以寻找无嫉妒的（公平）蛋糕部门。特别是，这项工作改善了针对此基本问题的最新添加近似。我们的结果适用于代理商估值满足基本假设并进行标准化的一般蛋糕部实例（蛋糕的价值1美元）。此外，在标准的Robertson-Webb查询模型下，开发的算法在多项式时间内执行。 先前的工作表明，可以有效地计算蛋糕部（带有连接的零件），其中任何代理商的添加剂最多为$ 1/3 $。有效的算法也以发现（几乎）$ 1/2 $ - 多态度嫉妒的连接蛋糕部门而闻名。改善添加近似保证并维护乘法性的保证，我们开发了一种多项式时间算法，该算法计算一个连接的蛋糕部门，两者均为$ \ weft（\ frac {1} {4} {4} +o（o（1）\ right）$ - 添加性 - 添加性嫉妒和$ \ weft（我们的算法基于间隔生长和嫉妒循环灭绝的思想。 此外，我们研究了蛋糕部的实例，其中跨代理的不同估值的数量在参数上是界限的。我们表明，这种蛋糕部实例接受了连接的无嫉妒蛋糕部门的完全多项式时间近似方案。
Cake cutting is a classic model for studying fair division of a heterogeneous, divisible resource among agents with individual preferences. Addressing cake division under a typical requirement that each agent must receive a connected piece of the cake, we develop approximation algorithms for finding envy-free (fair) cake divisions. In particular, this work improves the state-of-the-art additive approximation bound for this fundamental problem. Our results hold for general cake division instances in which the agents' valuations satisfy basic assumptions and are normalized (to have value $1$ for the cake). Furthermore, the developed algorithms execute in polynomial time under the standard Robertson-Webb query model. Prior work has shown that one can efficiently compute a cake division (with connected pieces) in which the additive envy of any agent is at most $1/3$. An efficient algorithm is also known for finding connected cake divisions that are (almost) $1/2$-multiplicatively envy-free. Improving the additive approximation guarantee and maintaining the multiplicative one, we develop a polynomial-time algorithm that computes a connected cake division that is both $\left(\frac{1}{4} +o(1) \right)$-additively envy-free and $\left(\frac{1}{2} - o(1) \right)$-multiplicatively envy-free. Our algorithm is based on the ideas of interval growing and envy-cycle-elimination. In addition, we study cake division instances in which the number of distinct valuations across the agents is parametrically bounded. We show that such cake division instances admit a fully polynomial-time approximation scheme for connected envy-free cake division.
