当玩家迟到时，蛋糕切割

Question

通常的陈述 公平的蛋糕切割问题 假设所有$ n $玩家都同时获得他们的股份。但是，在许多情况下，玩家逐步到达。例如，我们可能会将蛋糕划分为$ n $球员，但随后有一个新玩家到达并想要分享。

通常，公平的蛋糕部门需要大量的努力（例如，需要玩家回答许多查询），尤其是当玩家数量很大时。

是否可以在$ n $玩家的情况下使用蛋糕的现有部门，以创建蛋糕的新部门至$ n+1美元的玩家，而额外的努力最少（即重新分配蛋糕的努力要少得多从头开始）？

Answer 1

我会说我无法为您的问题提供一个很好的答案（我认为您可能会从中获得研究论文），但是我认为我可以通过正式定义问题并说明某些问题来提供帮助困难的谎言。

背景. 。让我清楚地说明蛋糕切割的模型。我们希望将间隔$ [0,1] $分配给$ n $播放器。每个播放器$ i $都具有蛋糕的子集$ s $ s $ v_i（s）$的估值功能。我们将假设此功能是概率度量。它是非负和添加剂的（对于分离$ a，b subseteq [0,1] $，$ v_i（a cup b）= v_i（a） + v_i（b）$）和$ v_i（[0,1] ）= 1 $。解决这个问题的方法是 协议 或查询玩家并分配间隔的一部分的算法。请注意，玩家可能会误报/谎言回答查询。

一些论文将有更具体的限制； 例如, ，估值功能是连续的，分段线性的或分段恒定的。

让分配给玩家的碎片为$ {s_1， dots，s_n } $。我们通常希望协议的以下属性：

• 相称性: ：每个播放器$ i $都有一种策略，可以保证他/他的价值至少为$（1/n）v_i（[0,1]）$。 （从$ i $的角度来看，他/他获得了蛋糕总价值的$ 1/n $。）
• 嫉妒: ：每个玩家都有一个策略，可以保证$ v_i（s_i） geq v_i（s_j）$ for其他玩家$ j $。 （每个玩家都喜欢他/她自己的作品，而不是其他玩家的作品。）

请注意，嫉妒意味着比例。

我们也可能想要一些“操作”属性，例如切成几片，多项式运行时间（或实际上是可计算性/构造性 - 我们不想使用选择的公理来选择蛋糕的子集！ ）， 等等。

---

要问的具体问题. 。两个笔记。首先，您问题的任何答案都将解决总体问题：首先将整个蛋糕交给玩家$ 1 $，然后让其他玩家在线到达并迭代应用此协议。因此，我们应该期望这个问题要比我们应用的标准蛋糕切割设置要困难。

其次，我们总是可以通过将所有蛋糕从所有人那里取回并使用已知算法从头开始将其重新分配来解决您的问题。因此，问题只是有一种更优雅的方式来做到这一点。我认为，量化这一点的好方法是“重新分配何时需要比从头开始的时间更少或更少的时间；和/或玩家何时可以保留其当前切片的很大一部分？”

1. 假设我们对$ n $播放器有无嫉妒的分配。我们如何重新分配以在$ n+1 $的玩家之间产生嫉妒的分配？

我怀疑这非常困难。原因是找到无嫉妒，有效的分配已经是一个困难的问题。据我所知，已知的协议可能需要无限的切割蛋糕，并且非常复杂。 （请参阅Brams和Taylor， 嫉妒的无蛋糕部协议, ，1995年。）因此，没有什么比将所有人从所有人带回并使用Brams-Taylor重新分配给$ n+1 $ $的代理人更好的了。

1. 假设我们有$ n $的比例分配；我们如何重新分配以获得$ n+1 $的比例分配？

我认为这仍然很困难（尽管更可行）。考虑每个玩家均匀重视蛋糕，每个玩家都有$ 1/n $尺寸的切片的情况。那么，无论新玩家所做的一切都需要在每个人之间进行改组。这是另一个不好的情况：假设玩家$ 1 $的估值正好为$ 1/n $，但值$ 2 $ $ 2 $的切片为$（n-1）/n $。假设玩家$ 2 $值她自己的切片恰好$ 1/n $，但值$ 3 $ $ 3 $ s $（n-1）/n $，依此类推，播放器$ n $估价自己的切片，以$ 1//$ n $ and player $ 1 $的slice s $（n-1）/n $。现在新玩家到达。无论新播放器想要什么，您的协议最终都将不得不将某些东西从玩家$ 2 $到玩家$ 1 $，从玩家$ 3 $到玩家$ 2 $，等等。

---

一个参考可能是 沃尔什， 在线蛋糕切割, ，在2011年算法决策理论中 （PDF链接）。但是我认为纸张假设我们事先知道到达的代理数量，并且假设当玩家离开时必须精确分配一件作品（这是在协议结束之前），因此确实不适合您的问题。

---

重新分配维持比例的比例分配的一种方法是如下。让每个$ n $ n $播放器中的每一个将他的分配的蛋糕切成$ n+1 $ $ $，他本人同样价值。根据他的说法，播放器$ n+1 $现在将从$ n $ player的削减中选择最好的作品。很容易证明所产生的分配也是成比例的。

Answer 2

假设蛋糕/区域是圆圈$ c $，带有半径$ r $。然后，我们可以通过切割蛋糕切割来创建$ n $ fief零件，从而为每个玩家分配一个$ frac { pi r^2} {n} $的区域。然后，我们可以分配$（n+1）$ th中心周围的一个小圆圈，然后随后在那个圈（吞咽内圈的部分）上响起新玩家，依此类推。这样，每个玩家都会获得一个连续的作品/情节，以单调的方式缩小了第一个$ n+1 $的播放器，并朝着中心移动，以供以后加入的人。

计算数字很简单；对于第一个新玩家，只需解决

$ qquad pi r_1^2 = frac { pi r^2} {n+1} $

为了获得他的阴谋的半径。第二，解决

美元^2} {n+2} end {align} $

为两个新玩家获得（外部）半径，依此类推。看来播放器$ n + i $ get ofter radius $ r_i = frac {r sqrt {i}}} { sqrt {n + k}} $在$ k $ $ k $之后，其他玩家已加入，但我没有证明这一点。

这就是您获得的$ n = 6 $和$ k = 0,1,2,3 $：

^[资源]

同样的想法适用于$ n $侧的常规多边形。如果您假设矩形作为基本形式，则可以通过分配第一个$ n $均等的列和以下播放器行（从一侧开始）来做类似的事情。