论文标题
注意差距：分离蛋糕切割
Mind the Gap: Cake Cutting With Separation
论文作者
论文摘要
我们研究了相当分配可分配的资源（也称为蛋糕切割的问题）的问题，并要求将不同代理人收到的股票彼此足够分开。例如，这捕获了社会疏远准则引起的限制。虽然有时不可能根据分离要求分配成比例的份额，但我们表明，始终可以达到众所周知的Maximin共享标准。然后，我们在这种情况下提供了最大值共享性的算法分析 - 例如，代理的最大值共享不能通过任何有限算法准确地计算出来，但是可以使用任意小的误差来近似。此外，我们考虑了馅饼的分裂（即圆形蛋糕），并表明可以实现最大值共享的顺序放松。我们还证明，分离存在最大资源的最大资源数量。
We study the problem of fairly allocating a divisible resource, also known as cake cutting, with an additional requirement that the shares that different agents receive should be sufficiently separated from one another. This captures, for example, constraints arising from social distancing guidelines. While it is sometimes impossible to allocate a proportional share to every agent under the separation requirement, we show that the well-known criterion of maximin share fairness can always be attained. We then provide algorithmic analysis of maximin share fairness in this setting -- for instance, the maximin share of an agent cannot be computed exactly by any finite algorithm, but can be approximated with an arbitrarily small error. In addition, we consider the division of a pie (i.e., a circular cake) and show that an ordinal relaxation of maximin share fairness can be achieved. We also prove that an envy-free or equitable allocation that allocates the maximum amount of resource exists under separation.
