公平的划分

给一个蛋糕，一群人怎样才能把蛋糕分配给他们自己，使每个人都能满意地得到自己的那份呢?货物的分割问题有着悠久而丰富的历史。本页探讨了数学上的结果公平的划分自从20世纪40年代以来，雨果·施泰因豪斯开始对这个问题进行严格的数学研究。公平分割涉及到许多不同的主题，并且与科学领域有着惊人的联系组合，数学归纳法，图论，算法,拓扑结构．

我们首先考虑两个人公平分配的情况:给一个蛋糕，两个人如何分配蛋糕，使两个人都对他们的那份感到满意?两个人都对自己的份额感到满意意味着什么?我们将通过分析一个著名的方法来研究这些问题，这个方法被称为切割-选择法。

2人员选拔方法:一个人把蛋糕分成两份，另一个人从中选择一份。

为了理解这是否会导致每个人都满意的划分，我们必须首先考虑玩家的偏好。一般来说，人们可能有不同的喜好，蛋糕的不同部分可能有不同的价值。例如，一个人可能更喜欢蛋糕中间有草莓装饰的那块，而另一个人可能喜欢巧克力糖霜，想要蛋糕角落里糖霜最多的那块。

除了不同的偏好，还有几种解释公平的方式。蛋糕的一份 $2$人民是一个成比例的如果每个人都相信她或他至少收到了，就分 $\压裂{1}{2}$蛋糕。蛋糕的一份 $2$人民是一个envy-free如果每个人都认为她或他得到了价值最大的一块，则进行分割(如果平分，则从其中一块中获得价值最大的一块)。

如果Alice和Bob采用2人切割选择法，得到的除法是比例除法吗?这是一个没有嫉妒的部门吗?

---

解决方案:假设Alice是切割者，Bob是选择者。从爱丽丝的角度来看，她知道鲍勃可以从她的两份蛋糕中任意选择，所以她的最佳策略是把蛋糕切成她认为价值相等的两份。那么无论她最后得到哪件作品，她都相信这件作品是有价值的 $\压裂{1}{2}$对另一块蛋糕没有更强烈的偏好。从Bob的角度来看，他被允许选择他更喜欢的作品，所以最后，他不会对Alice的作品有更强烈的偏好，他得到了他认为至少是 $\压裂{1}{2}$蛋糕。这表明，结果既成比例，又没有嫉妒的分割蛋糕。

我们可以把上面的定义归纳为蛋糕的分割 $n$人民是一个成比例的如果每个人都相信她或他至少收到了，就分 $\压裂{1}{n}$蛋糕，是一个envy-free如果每个人都认为她或他得到了价值最大的那一块，就进行分割。另一种思考没有嫉妒的划分的方式是，没有人对其他人的蛋糕有严格的更强的偏好。

移刀步骤

既然我们已经考虑了将蛋糕分给两个人的问题，那么我们如何将蛋糕分给爱丽丝、鲍勃和卡罗尔这三个人呢?我们从比例分配的问题开始:我们如何把蛋糕分成三份，使三个人都满意他们至少得到了一块 $\压裂{1}{3}$蛋糕之路?的移刀程序工作原理如下。一个人用刀在蛋糕上慢慢移动，这样刀左边的蛋糕量就会从0不断增加到整个蛋糕。只要爱丽丝，鲍勃或卡罗尔相信刀左边的蛋糕等于 $\压裂{1}{3}$切蛋糕的时候，这个人喊道:“切!”第一个喊出的人可以得到刀左边的棋子(如果多人同时喊出，那么他们中的任何一个人都可以被随机选中接受这把棋子)。然后得到一块蛋糕的人去给蛋糕倒一杯牛奶，剩下的两个人和剩下的那部分蛋糕继续动刀。

tinypic

我们可以这样分析这个过程:

• 在第一和第二阶段，喊“切!”的两个人都会得到他们认为是正确的蛋糕 $\压裂{1}{3}$蛋糕的一部分
• 对于在这个过程中没有大喊大叫的人来说，这个人认为在第一和第二阶段要从蛋糕上切下的部分都小于 $\压裂{1}{3}$蛋糕。那么这个人得到的至少是 $1 - \frac{1}{3} - \frac{1}{3} = \frac{1}{3}$蛋糕。

这说明动刀法给出了一个比例除法 $3.$人。如果Alice, Bob和Carol想邀请他们的朋友来参加聚会，移刀程序是否也给每个人一个比例划分?假设 $N \geq 4$人们用刀在蛋糕上连续移动来分蛋糕，只要有人相信刀左边的蛋糕等于 $\压裂{1}{n}$切蛋糕时，他/她会大喊“切!”现在，第一个人接受他们相信的东西 $\压裂{1}{n}$每个人都认为剩下的那块至少是 $1 - \frac{1}{n} = \frac{n-1}{n}$蛋糕。现在,通过数学归纳法，问题简化为除法 $\压裂{n} {n}$蛋糕中 $n - 1$根据归纳假设，移动刀的过程会给剩下的每个人至少 $\压裂{1}{n}$剩下的蛋糕，所以每个人都得到她/他认为至少是 $\frac{1}{n-1} \times \frac{n-1}{n} = \frac{1}{n}$原来的蛋糕。这就得到了一个比例的除法 $n$人。

移动刀的做法能让所有人都不嫉妒地分蛋糕吗 $n$人呢?换句话说，如果手术进行到最后，所有的棋子都被放在桌子上，每个人会在移刀过程中选择他们收到的棋子吗?

---

解决方案:我们证明了动刀法给出的除法是成比例的，但不一定是无嫉妒的。假设爱丽丝、鲍勃和卡罗尔正在分一块蛋糕，爱丽丝第一个喊“切!”然后她拿起刀左边的那块，她认为那块有价值 $\压裂{1}{3}$蛋糕。现在，当移动刀的过程继续在剩下的蛋糕上进行时，在某个点上，爱丽丝相信刀子已经移到另一个蛋糕上了 $\压裂{1}{3}$她就会喊"切!"(除了按照程序，她现在已经离开房间去喝一杯牛奶，不再参与移动刀的过程)。但是，假设鲍勃和卡罗尔都认为移动的刀还没有移动过 $\压裂{1}{3}$价值标记，所以他们都没有喊着让刀停下来。最后，爱丽丝认为第二块蛋糕比第一块大，所以她没有得到她认为最大的那一块。这说明移动刀的过程并不一定是没有嫉妒的。

注意移动刀的过程不是离散的(因为假设刀在蛋糕上连续移动，以便在任何位置切割)，也不一定会导致没有嫉妒的分割。这就引出了以下问题:是否存在一种无嫉妒的除法程序 $n$人呢?是否存在离散的过程，只需要有限数量的切割?

1960年，北伊利诺伊大学的约翰·塞尔弗里奇和剑桥大学的约翰·霍顿·康威首次解决了使用离散方法的无嫉妒除法。需要切割最少的方法是Selfridge-Conway离散方法，它最多使用5个切割。

对于一般 $n$1995年，布拉姆斯和泰勒提出了第一个针对4名或4名以上选手的无嫉妒除法。其他的方法是由罗伯逊和韦伯，以及布拉姆斯和基尔古尔提出的。Brams和Kilgour的方法被称为间隙程序，它使用了拍卖的概念，让每个参与者对拟议划分中的物品出价。然后，该过程根据参与者的出价找到项目的分配。不过，这些算法适用于一般情况 $n$拥有这样的属性，即所需的切割数量是无限的，并且需要任意多的步骤才能找到除法，这取决于玩家的喜好。一个长期悬而未决的问题是，是否有一个程序有限的蛋糕分割的步骤数 $n$人。

开放的问题:是否存在一个不受嫉妒的公平划分程序 $n$拥有有限的步骤数?

公平分配问题也有一个对应的问题，在这个问题中，一个不受欢迎的商品被分配 $n$人，例如在分担家务或分摊租金。马丁·加德纳提出了将一组杂务(不可分割的，不受欢迎的项目)分配给多人的问题。在租金分配问题中，一群室友必须为可能有不同特征的房间决定一个公平的租金分配:爱丽丝可能喜欢窗户，鲍勃可能喜欢硬木地板，目标是根据他们的偏好找到一种方法来决定如何最好地分配租金。

还有一些问题需要其他公平的概念。想象一个一半草莓一半巧克力的蛋糕。假设Alice只喜欢巧克力，Bob只喜欢草莓，他们采用了两人切割选择法。如果爱丽丝是切蛋糕的人，她不知道鲍勃的喜好，那么她就会把蛋糕分成每一块一半巧克力，一半草莓。但之后，两个玩家都只收到了他们想要的一半。另一方面，如果爱丽丝知道鲍勃的喜好，那么她会把蛋糕分成巧克力一块和草莓一块，所以他们都得到了自己的喜好。这是一个概念帕累托效率；第一个Alice不知道Bob偏好的解是帕累托效率低下因为有可能找到另一种除法让一个人过得更好而不让另一个人过得更糟。

除了这些问题之外，公平划分在拍卖、经济学、社会选择理论和博弈论中也有许多应用。公平分配算法可以考虑到所有人的偏好，用来解决货物分割的纠纷。

我们现在进入组合拓扑的世界，并展示如何应用拓扑中的不动点定理来解决无嫉妒的公平除法问题。我们首先给出以下定义。的 $n$-维单纯形是集合

$\ Delta_n = \ {(x_0, x_1、x_2 \ ldots x_n)在\ \ mathbb {R} ^ {n + 1}: 0 \ leq x_i, \ x_i之和= 1 \}。$

让 $e_i \in \mathbb{R}^{n+1}$用 $我$这个坐标等于1其他的坐标都等于0。然后 $e_i$的顶点 $\ Delta_n$．直观地说，单形上的每一点都可以看作是蛋糕的一部分 $n + 1$分段，坐标 $我$蛋糕的分量是一块一块的吗 $我$．顶点 $e_i$的 $\ Delta_n$那么分割的蛋糕在哪一块呢 $我$整个蛋糕和其他所有的蛋糕都有大小吗 $0$．的简化式 $n = 0, 1,$而且 $2$可以从几何上可视化如下所示:

我们将专注于这个案子 $n = 2,$这是一个三角形。把这个三角形的顶点标为 $1、2、3$考虑把这个三角形分解成更小的三角形，其中最小的三角形被称为细胞．假设沿着这条边的顶点相连 $1$而且 $2$要么贴上标签 $1$或 $2$，顶点沿边连接 $2$而且 $3.$要么贴上标签 $2$或 $3.$，顶点沿边连接 $1$而且 $3.$要么贴上标签 $1$或 $3.$，内部的顶点用任意一个标记 $1、2、$或 $3.$．满足这些条件的标签称为Sperner标签：

我们首先展示了图论的以下结果。

在图表中 $G$,学位顶点的 $v$邻边的个数是多少 $v$．任何图中奇次顶点的个数必须是偶数。

---

解决方案:考虑图中所有顶点的度数之和。因为每条边都有两个端点，所以所有顶点的度数之和等于边数的两倍。因为度数的和是偶的，而偶度数的顶点的度数和是偶的，所以奇数度数的顶点的度数和一定是偶的。这说明一定有奇数次的偶数个顶点。

我们给出了斯珀纳引理的一个陈述和证明 $n = 2,$它对应一个三角形;高维简式的证明也遵循同样的推理，只是做了一些修改。

Sperner引理:如果一个三角形被分解成单元格，并且所有顶点都用Sperner标签进行标记，那么所有不同标签的单元格数量都是奇数。

---

证明:通过为三角剖分的每个单元格引入一个顶点和一个特殊顶点来创建辅助图 $v ^ *$对于三角形的外面。现在，用一条边连接任意两个顶点，如果它们边界的交点是一个单元格的边，其端点标记为 $1$而且 $2$．与顶点相邻的顶点 $v ^ *$边界上端点有标签的单元格吗 $1$而且 $2$，如下例所示:

现在，当从顶点沿着边界移动时 $1$而且 $2$在大三角形中，有奇数条带标签的边 $1$而且 $2$，因为我们从标记为 $1$在一个顶点处结束 $2$．这意味着程度 $v ^ *$是奇数(在上图中，度 $v ^ *$等于3)。由上面的结果，这个图是偶数 $k$奇次顶点，自 $v ^ *$有奇数度，有吗 $k - 1$奇数度顶点保留在三角形内部。现在，三角形内部的顶点可以有1次，2次，或3次，所以内部顶点唯一可能的奇数次是1次。如果一个顶点的度数为1，那么它对应一个单元格 $c$这样 $c$是否有一条边用 $1、2$其他的边 $c$不能用 $1、2$．这意味着其他的边 $c$必须有标签 $(1、3)$而且 $(2、3)$,所以 $c$细胞有标签吗 $1、2、3$．这表明 $k - 1$标记的细胞 $1、2、3,$这是一个奇数，证明了斯珀纳引理。

(检查上图中，度数为1的五个内顶点每一个都对应一个带标签的单元格 $1、2、$而且 $3.$．）

对于一般 $n$，斯珀纳引理通过归纳法继续 $n$．

特别地，斯珀纳引理证明了它的存在至少一个带有标签的三角形 $1、2、3$在任何Sperner标签中。我们现在证明三个人的无嫉妒公平分割定理(一般情况的证明可以通过同样的方式进行一些修改)。

三人无嫉妒公平划分定理(Simmons):对于三个人来说，会有一个蛋糕的分配，每个人都会得到一块她/他认为价值最大的蛋糕。

---

证明:鉴于 $\epsilon > 0，$构造单一形的三角剖分，使单元格顶点之间的距离最大 $\ε,$考虑一下标签 $l$使每个单元格都有标签 $A、B$而且 $C$．

现在，按照下面的方法构造第二个三角剖分标记。对于每个顶点 $x$，考虑三角测量给出的标签 $l$然后问这个标签对应的人，如果蛋糕被分成几部分，他们更喜欢哪一块 $X = (x_1, x_2, x_3)$对应于这个点在单形上的坐标。用 $1$如果这个人喜欢一块 $1$， $2$如果这个人喜欢一块 $2$, $3.$如果这个人喜欢一块 $3.$．结果就是斯珀纳标记，因为沿着每个边界 $(e_i e_j)$，只有碎片 $我$而且 $j$是非空的，因此只有它们是首选的。然后根据斯珀纳引理，存在一个标记为 $1 2 3$，对应一个单元格，每个玩家选择不同的蛋糕。现在，我们在这个单元格上递归以获得顶点越来越接近的单元格序列( $\ε$趋于0)，这样对应的单元格有非空交集，每个玩家每次选择相同的棋子，他的名字出现在一个单元格的标签。在极限情况下，交点上的一个点就是一个分，每个参与人都喜欢分得蛋糕的不同一块。

注意，这个证明给出了寻找不动点和公平分割的近似算法。对于分摊租金或分担家务的问题，弗朗西斯·苏(Francis Su)开发了一种算法，可以反复询问每一位房客，如果房租以某种方式在房间之间分配(或家务以某种方式分配)，她或他会喜欢哪个房间。然后基于斯珀纳引理的程序确定房间租金，在每个室友的回合后求婚。这些方法已经在一些在线工具中实现了:

公平除法计算器

公平分配房租

Spliddit:共享租金，分配货物，分配信用的在线计算器

斯珀纳引理还包含了组合拓扑中一个著名的理论，即布鲁厄不动点定理。

Brouwer不动点定理:任意连续映射 $f$从单纯形到自身有一个固定点 $x$,也就是说, $F (x) = x$．

组合拓扑的其他结果也适用于公平分割问题。例如，火腿三明治定理说明对于 $n$人们可能有不同的喜好，总有一块蛋糕让所有人 $n$人们认为蛋糕的两面价值相等。

正如我们所展示的，切蛋糕问题涉及许多不同的领域，从组合学和图论到算法和拓扑学。它在经济学、博弈论和决策理论中也有很多应用，在过去几十年里，对这个问题进行了大量的数学研究。也许还有许多悬而未决的问题你会有人想出新办法来解决这些问题!

参考文献

S. Brams, A. Taylor，《无嫉妒的蛋糕分割协议》。美国数学月刊102(1):9-18(1995)。

加德纳先生:“啊哈!《洞察力》，W.F. Freeman and Co.，纽约(1978)。

苏峰，“租值和谐:公平分割的Sperner引理”，《美国数学月刊》第106期，第930-942页(1999年12月)。

f .苏公平分割页面。