公平分配

给一个蛋糕，一群人如何分配蛋糕，使每个人都高兴地分享?商品分割问题有着悠久而丰富的历史。这一页探讨的数学结果公平的划分从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}$蛋糕的路？这动刀的过程工作原理如下。一个人移动的刀慢慢地在蛋糕，使蛋糕的左侧连续从零刀上升到整个蛋糕的金额。一旦任一翘，鲍勃，或卡罗尔认为，一块蛋糕向左刀的等于 $\压裂{1}{3}$切蛋糕的时候，这个人会大喊“切!”第一个喊出声音的人得到刀子左边的那块(如果多人同时喊出声音，那么他们中的任何一个人都可以随机选择得到这块刀)。然后，拿了一块蛋糕的那个人去拿一杯牛奶，剩下的两个人和蛋糕的剩余部分继续移动刀子的过程。

tinypic

我们可以用下面分析一下这个过程：

• 在第一和第二阶段两个，两个人谁喊“切！”收到蛋糕的作品，他们认为是准确 $\压裂{1}{3}$的蛋糕
• 对于在制作过程中没有大声喊出来的人来说，这个人认为在第一和第二阶段从蛋糕上切下来的那一块都少于 $\压裂{1}{3}$的蛋糕。那么这个人收到的部分至少是 $1 - frac{1}{3} - frac{1}{3} = frac{1}{3}$的蛋糕。

这表明移动刀程序给出了一个比例的分割 $3.$人。如果爱丽丝，鲍勃和卡罗尔想邀请他们的朋友参加聚会，移动刀程序是否也给每个人一个比例划分?假设 $n \组4$人们用刀分蛋糕，刀在蛋糕上不断地移动，一旦有人相信刀左边的那块蛋糕等于 $\压裂{1} {N}$蛋糕，他/她呼喊“切！”现在，第一人接收他们认为是什么 $\压裂{1} {N}$每个人都相信剩下的那块蛋糕至少是 $1 - \压裂{1} {N} = \压裂{N-1} {N}$的蛋糕。现在，数学归纳法，问题就归结为分裂 $\压裂{N-1} {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年，北伊利诺伊大学的约翰·塞尔弗里奇(John Selfridge)和剑桥大学的约翰·霍顿·康威(John Horton Conway)首次用离散方法解决了3人博弈的无嫉妒除法。需要最少切割的方法是Selfridge-Conway离散程序，它最多使用5次切割。

对于一般 $n$在1995年，布拉姆斯和泰勒首次提出了四名或四名以上球员的无嫉妒分区法。其他方法则是由罗伯逊和韦伯以及布拉姆斯和基尔格提出的。布拉姆斯和基尔戈的方法被称为间隔程序，它采用了一种拍卖的概念，即每个参与者都对拟议分区中的物品进行投标。然后，该程序根据参与者的出价找到项目的分配。不过，这些算法适用于一般情况 $n$具有这样的性质，需要削减的数量是无限的，并可能需要一个任意大数量的步骤，找到分工，根据玩家的喜好。一个长期未解决的问题是，是否有一个过程有限的步骤数为免嫉妒的蛋糕划分之间 $n$人。

开放式问题：是否存在无嫉妒的公平划分程序 $n$玩家用有限的步数？

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

还有一些问题需要其他的公平观念。考虑一个一半草莓一半巧克力的蛋糕。假设爱丽丝只喜欢巧克力，鲍勃只喜欢草莓，他们采用了二人选择的方法。如果爱丽丝是切蛋糕的人，她不知道鲍勃的偏好，那么她会将蛋糕分成两份，每一份包含一半巧克力，一半草莓。但随后，两名玩家得到的棋子只包含他们想要的一半。另一方面，如果爱丽丝知道鲍勃的偏好，她会把蛋糕分成巧克力块和草莓块，这样他们都能得到自己的偏好。这就是帕累托效率;第一个解决方案中，翘不知道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 \中\ 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.$．满足这些条件的标记称为ASperner标签：

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

在图 $G$,学位顶点的 $v$邻近边缘的数量 $v$．奇度顶点的任意图形数必须是偶数。

---

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

我们给出Sperner引理的声明和证明 $n = 2,$它对应一个三角形;高维单元的证明遵循同样的推理，只是稍加修改。

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

---

证明:通过为三角剖分的每个单元引入一个顶点和一个特殊顶点来创建辅助图 $v ^ *$为三角形的外部。现在，通过边缘连接任何两个顶点，如果它们的边界的交叉点是一个细胞与由标记的端点的边缘 $1$和 $2$．相邻顶点的顶点 $v ^ *$边界上的单元格端点是否有标签 $1$和 $2$，如下例所示:

现在，当从顶点沿边界移动 $1$和 $2$在大三角形中，带有标签的边的数目是奇数 $1$和 $2$，因为我们从标顶点开始 $1$并以标记为的顶点结束 $2$．这意味着程度 $v ^ *$奇数(在上图中，的度 $v ^ *$等于三）。通过以上的结果，该图表具有偶数个 $k$奇数次顶点的集合 $v ^ *$有奇数度，有吗 $K-1$奇数度的顶点留在三角形内部。三角形内部的顶点可以是一阶，二阶，或者三阶，所以内部顶点唯一可能的奇数阶是一阶。如果一个顶点的度数是1，那么它对应于一个单元格 $c$这样 $c$具有由标记的边缘 $1，2$和其他的边 $c$不能用 $1，2$．这意味着另一边缘 $c$必须有标签 $(1、3)$和 $(2、3)$， 所以 $c$与标签细胞 $1，2，3$．这表明 $K-1$细胞标记 $1、2、3,$这是一个奇数，证明了斯伯纳引理。

(在上面的图中，第一级的五个内部顶点都对应有标签的单元格 $1、2、$和 $3.$．）

对于一般 $n$，斯珀纳引理通过归纳进行 $n$．

特别是，Sperner引理表明存在最后一个三角形标签 $1，2，3$在任何Sperner标签中。我们现在证明了三个人的无嫉妒公平分割定理(一般情况的证明也可以用同样的方式得到，只需要做一些修改)。

三个人的无嫉妒公平分割定理(Simmons):对于三个人来说，存在一个蛋糕的分割，这样每个玩家都能得到她/他认为价值最大的一块蛋糕。

---

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

现在，按照下面的方法构造三角剖分的第二个标记。为每个顶点 $x$，考虑三角测量给出的标签 $l$然后问对应于这个标签的人，如果把蛋糕分成几部分，他们更喜欢哪一块 $X = (x1, x_2, x_3)$对应于这个点在单纯形中的坐标。将顶点标记为 $1$如果该人的意愿件 $1$， $2$如果该人的意愿件 $2$, $3.$如果该人的意愿件 $3.$．其结果是一个Sperner标记，因为沿着各边界 $（e_i，e_j）$,只有部分 $我$和 $j$为非空，因此只有它们才是首选。根据斯伯纳引理，存在一个细胞，标记为 $1、2、3$，对应于每个玩家选择蛋糕的不同部分的单元格。现在，我们在这个单元格上递归，以获得顶点越来越近的单元格序列( $\小量$趋向于0)，使得相应的单元格有非空的交集，并且每个玩家每次都选择相同的部分作为单元格的标签。在极限情况下，交集点是一个分割点，在这个分割点上，每个玩家都喜欢分到不同的一块蛋糕。

请注意，这个证明给出了寻找固定点和公平分配博弈的近似算法。对于将租金或分裂琐事的问题，弗朗西斯·萨开发了一种算法，反复查询依次在每个室友在哪个房间，他或她宁愿如果总租金是在某些方面的房间之间划分（或琐事分布在某些方面）。然后根据Sperner引理的程序来确定房间的租金后，每个室友轮到建议。这些方法已经在一些在线工具已经实现：

公平划分计算器

公平分配租金

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

Sperner引理也意味着被称为布劳威尔的不动点定理组合拓扑结构的著名理论。

这定点定理:任何连续映射 $f$从单一到本身有一个固定的点 $x$， IE。， $F（X）= X$．

从组合拓扑中的其他结果同样适用于公平分配的问题。例如，火腿三明治定理显示, $n$人们可能有不同的喜好，总是有一个单一的蛋糕，使所有 $n$人们相信蛋糕的双方都有同等价值。

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

参考文献

S. Brams，A·泰勒，“羡慕的对象，免费蛋糕师协议”。美国数学月刊102（1）：9-18（1995）。

m·加德纳:“啊哈!Insight”，W.F. Freeman and Co.，纽约(1978)。

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

f .苏公平分配页。