Beyond Cake Cutting: Allocating Homogeneous Divisible Goods
Beyond Cake Cutting: Allocating Homogeneous Divisible Goods
复制标题
DOI：
10.5555/3535850.3535875
复制
发表时间：
2022-01
期刊：
影响因子：
--
通讯作者：
I. Caragiannis;Vasilis Gkatzelis;Alexandros Psomas;Daniel Schoepflin
中科院分区：
文献类型：
--
作者：
I. Caragiannis;Vasilis Gkatzelis;Alexandros Psomas;Daniel Schoepflin
被称为“切蛋糕”的公平分配问题一直是跨越几十年的多篇论文的焦点。在这方面的工作中最突出的问题是限制了Robertson-Webb查询模型中计算无嫉妒结果的查询复杂性。然而，这个问题的复杂性的根源是人为的：代理人的价值被假设为在“蛋糕”的不同部分上是可加性的，但在每一部分中是无限复杂的。在大多数激励性的例子中，这是不现实的，因为蛋糕代表了同质商品的有限集合。我们通过引入一个更准确地捕捉这些应用的公平分配模型来解决这个问题：代理人从给定商品中获得的价值仅取决于他们收到的商品数量，但它可以是该数量的任意函数，允许代理人表达超出标准蛋糕切割的偏好。在这个模型中，我们研究的查询复杂度计算分配，不仅是免费的，但也近似帕累托最优之间的所有免费的分配。使用一种新的基于流的方法，我们表明，我们可以通过多项式数量的约束编码的随机分配的事后可行性，这减少了我们的问题，解决一个线性规划。
The problem of fair division known as"cake cutting"has been the focus of multiple papers spanning several decades. The most prominent problem in this line of work has been to bound the query complexity of computing an envy-free outcome in the Robertson-Webb query model. However, the root of this problem's complexity is somewhat artificial: the agents' values are assumed to be additive across different pieces of the"cake"but infinitely complicated within each piece. This is unrealistic in most of the motivating examples, where the cake represents a finite collection of homogeneous goods. We address this issue by introducing a fair division model that more accurately captures these applications: the value that an agent gains from a given good depends only on the amount of the good they receive, yet it can be an arbitrary function of this amount, allowing the agents to express preferences that go beyond standard cake cutting. In this model, we study the query complexity of computing allocations that are not just envy-free, but also approximately Pareto optimal among all envy-free allocations. Using a novel flow-based approach, we show that we can encode the ex-post feasibility of randomized allocations via a polynomial number of constraints, which reduces our problem to solving a linear program.