一、你切,我选

你和同事小周分一块蛋糕。你们都不想吃亏,也不想让对方觉得吃了亏。

最古老的办法是:一个人切,另一个人先选。 你来切,小周先挑一块,剩下的归你。

先别往下读。请你想一想:你该怎么切?为什么?

你会这样想:我不知道小周喜欢哪一块,如果我切得不平均,小周就会挑走我觉得大的那一块,我只剩小的。所以我要把蛋糕切成我自己觉得一样大的两块。这样,不管小周选哪块,我拿到的都是我心里的一半。

这个办法有两个好处:

  • 比例公平:每个人都拿到自己心里至少 1/n 的份额。你拿到的至少是你心里的一半;小周先选,选的是自己觉得更好的,一定至少是自己心里的一半。
  • 无嫉妒:每个人都不觉得别人拿到的比自己多。你对两块一样满意;小周选了自己觉得更好的那块,不会羡慕你。

这两条,是"公平"最常见的两个标准。还有第三条,叫有效率:没有办法在不让任何人更糟的情况下,让某个人更好(不浪费)。

“你切我选"满足前两条。那它是不是满足第三条?

二、口味不同时,会发生什么

我们给蛋糕加一点细节。这块蛋糕左半是巧克力,右半是香草。

  • 你觉得:整块巧克力值 8,整块香草值 2(你爱巧克力)。
  • 小周觉得:整块巧克力值 3,整块香草值 7(小周爱香草)。

两人心里的总价值都是 10,所以"心里的一半"是 5。

看三种不同的切法。

切法一:你只在巧克力里切一刀,切下巧克力的前 5/8,做成左块;剩下的是巧克力的后 3/8,加上整块香草,做成右块。

  • 你觉得:左块值 8 × 5/8 = 5;右块值 8 × 3/8 + 2 = 5。两块一样。
  • 小周觉得:左块值 3 × 5/8 = 1.875;右块值 3 × 3/8 + 7 = 8.125。小周选右块。

结果:你 5,小周 8.125。

切法二:你把每种口味都对半切,每块是"一半巧克力加一半香草”。

  • 你觉得:每块值 4 + 1 = 5。
  • 小周觉得:每块值 1.5 + 3.5 = 5。

小周随便选一块。结果:你 5,小周 5。

切法三:假设你知道小周的口味。你想:我要把蛋糕切成两块,让小周觉得一样(各 5),同时我觉得其中一块值很多。小周看巧克力便宜、香草贵,所以我把全部巧克力,再加上一点点香草(让小周觉得凑够 5)做成一块:3 + 7 × (2/7) = 5,也就是香草的 2/7。

  • 左块 = 全部巧克力 + 香草的 2/7:你觉得值 8 + 2 × 2/7 ≈ 8.57,小周觉得值 5。
  • 右块 = 剩下的香草(5/7):你觉得值 2 × 5/7 ≈ 1.43,小周觉得值 5。

小周觉得两块一样,随便选。(现实里,你会把右块切得让小周稍微更喜欢,这样小周就一定选右块,你拿左块。)结果:你约 8.57,小周 5。

你切我选:同一块蛋糕,切法不同,结果差得很远

三种切法都是比例公平的(每人至少 5),也都是无嫉妒的。可是它们的结果差得很远:

  • 切法二:5 对 5,很浪费。如果你拿全部巧克力(8),小周拿全部香草(7),两个人都比 5 好得多。
  • 切法三:你把几乎全部好处拿走了(8.57 对 5),因为你知道小周的口味。

⚠️ 这里第一次读会觉得别扭。 你会想:既然你切的两块"你觉得一样",怎么会有的切法让你 8.57、有的只给你 5?

关键在于:“你觉得一样”,只是你的保底。 你切成相等的两块,是为了不管小周怎么选,你都至少有一半。但你有很多种切出"你觉得相等"的办法,它们对小周的价值不一样。你不知道小周的口味时,切法一、二都是合理的,你只能保证 5;你知道小周的口味时,可以挑一种对你最有利的切法,把小周逼到"刚好 5"。

所以:公平(比例、无嫉妒)和效率是两回事。 “你切我选"保证了前者,不保证后者;它给了切的人一点信息上的优势。

三、三个人:移动刀

人多了怎么办?有一个办法,叫移动刀:

一把刀,从蛋糕的最左边慢慢往右移。每个人心里都在算:刀左边这一块,对我值多少?第一个觉得"够 1/3 了"的人喊"停”,拿走这一块。剩下的蛋糕,由剩下的人重复这个过程。最后两个人,用"你切我选"。

我们来走一遍。蛋糕是一条线段,长度 1。

  • 你:觉得每个地方都一样好吃(值 1 每单位长度)。刀左边的长度 x,对你值 x。你在 x = 1/3 喊停。
  • 小周:偏爱左边。左半(0 到 0.5)每单位长度值 1.5,右半每单位值 0.5(总共 1.5 × 0.5 + 0.5 × 0.5 = 1)。刀左边在左半时对小周值 1.5x,等于 1/3 时 x = 2/9 ≈ 0.222。
  • 小林:和你一样,觉得每处一样好吃,在 x = 1/3 喊停。

刀往右移,小周最先喊停(0.222 最小)。小周拿走 [0, 0.222],对小周值 1/3。

剩下的 [0.222, 1],长度 7/9,由你和小林用"你切我选"分:你们俩都觉得每处一样,各得 7/18 ≈ 0.389。0.389 大于 1/3。

每个人都拿到了自己心里至少 1/3(你 0.389,小周 0.333,小林 0.389)。这就是比例公平。

这个办法保证比例,但不一定无嫉妒。想要三个人都无嫉妒,有更复杂的办法:Selfridge 和 Conway 在 1960 年代各自发现了一个三人的办法,据转述最多切 5 刀。再后来,Brams 和 Taylor 1995 年给出了任意多人的无嫉妒办法,但是步数没有上限;Aziz 和 Mackenzie 2016 年给出了任意多人、步数有上限的无嫉妒办法。(这些我据二手转述。)

四、不能切开的东西:分房租

蛋糕可以切,房间不能切。三个人合租一套房子,三个房间(大、中、小),总房租 1200。怎么分房间、怎么摊房租,才没有人羡慕别人?

每个人心里对每个房间有一个"愿意付多少":

大房 中房 小房
你 600 400 300
小周 500 450 350
小林 450 400 400

先试试平摊:每人付 400(三个人各付 400,不管住哪个房间)。你住大房,小周住中房,小林住小房(这是让"大家愿意付的钱的总和"最大的分法,总共 600 + 450 + 400 = 1450)。

  • 小周住中房:愿意付 450,付 400,剩 +50。可是如果住大房:愿意付 500,付 400,剩 +100。小周羡慕你。

所以平摊会有人羡慕。办法是:不平摊,给房间定价,让大房贵一些、小房便宜一些。

我们试价格 大房 500,中房 380,小房 320(总和 1200)。每个人的"愿意付的钱 − 要付的钱":

分房租:找到一组价格,谁也不羡慕别人的房间

  • 你:大房 +100,中房 +20,小房 −20。住大房最好。
  • 小周:大房 +0,中房 +70,小房 +30。住中房最好。
  • 小林:大房 −50,中房 +20,小房 +80。住小房最好。

每个人住在自己的房间里,都是自己这一行最大的数,没有人想换。 这就是无嫉妒的分房租。(我用程序对所有整十元的价格都检验过:在这个房间分配下,满足无嫉妒的价格有 58 组,上面只是其中一组;比如 550、370、280 也行。)

这是 Su 1999 年的"租金和谐"的想法:只要能用钱(价格)调节,无嫉妒的分配总是存在的(据摘要的说法)。后来有人把这样的算法做成了网站,叫 Spliddit,让人们可以免费分房租、分财物、分功劳(Goldman 和 Procaccia,据摘要)。

要小心一点:这里的"愿意付多少"是各人私下的真实估价。如果有人谎报(比如把大房的估价说得很低,想让价格便宜一点),结果就会变。所以在使用这类办法时,需要考虑怎么让大家说真话。

五、三条标准的关系

  • 比例公平:每人至少得到自己心里的 1/n。
  • 无嫉妒:没有人觉得别人的比自己的好。(当大家对东西的评价是可以相加的时候,无嫉妒比比例公平更强:无嫉妒的分法一定是比例公平的,反过来对三个人以上不成立。)
  • 有效率:没有浪费。

这三条不是一回事,也不是总能同时满足。“你切我选"满足前两条,但可能浪费;一个有效率的分法,可能让某个人嫉妒。

六、证据:现实里在用

理论预测。 两人"你切我选"保证比例和无嫉妒;三人以上需要更复杂的办法;有价格可以调节时,无嫉妒的分配总存在。

证据。

  • 三人以上的办法。 Selfridge–Conway(1960 年代,据转述最多 5 刀);Brams 和 Taylor 1995 年(据转述发表在《美国数学月刊》,没有核对卷页);Aziz 和 Mackenzie 2016 年的 FOCS 论文(有上限的任意多人办法)。移动刀等办法,通常追溯到 Steinhaus 等波兰数学家 1940 年代的工作(这一条我没有核对到出处,请当作通行的说法)。
  • 分房租。 Su 1999 年的《租金和谐:公平分割中的 Sperner 引理》(《美国数学月刊》,我没有核对到卷页)。
  • 应用。 Spliddit 网站(Goldman 和 Procaccia,ACM SIGecom Exchanges,据目录约 2015 年),提供房租、财物、功劳的分配。
  • 行为实验。 我没有核对到可靠的、系统的实验证据,说明人们在现实里怎样使用或偏离这些办法,所以这里不下结论。

局限。 这些办法有很强的前提:每个人的估价是能相加的(几块加起来的价值,等于各块价值之和),每个人愿意说真话,而且大家相信这个办法。现实里,东西之间会互补或替代,分配也常常要考虑需要、贡献、历史等。

分歧。 什么才算"公平”,是价值判断:同样一块蛋糕,有人认为"每人心里一半"就公平,有人认为"每人实际吃到的一样多"才公平,还有人认为"按需要分"。模型只告诉你每种标准下会得到什么,不替你选标准。

七、常见的误用

  • “你切我选一定最好。” 不对。它公平,但可能浪费;切的人如果知道对方的口味,还能占便宜。
  • “公平就是每人一样多。” 不对。比例公平是"每人心里至少 1/n",每人拿到的实际东西可以很不一样(你拿巧克力,小周拿香草)。
  • “无嫉妒就一定有效率。” 不对。切法二是无嫉妒的,但很浪费。
  • “不能切的东西没法公平分。” 不对。用价格补差,可以做到无嫉妒。
  • “平摊房租最公平。” 不一定。大房小房住的人享受不同,平摊时会有人羡慕别人。

八、小结

  • 三条标准:比例(每人至少 1/n)、无嫉妒(不羡慕别人)、有效率(没有浪费)。
  • 你切我选:你切成自己觉得相等的两块,对方先选。比例公平、无嫉妒;口味相同时不浪费,口味不同时可能浪费(5 对 5,而 8 对 7 是可能的)。
  • 信息的优势:切的人若知道对方口味,能拿到更多(8.57 对 5)。
  • 移动刀:三人以上,谁先觉得够了谁喊停;保证比例公平。无嫉妒的办法更复杂(Selfridge–Conway、Brams–Taylor、Aziz–Mackenzie)。
  • 分房租:定价让大房贵、小房便宜,可以做到没人羡慕别人(500、380、320 的例子)。
  • 证据:算法已被做成网站;行为证据我没有核对到。

回到那块蛋糕。下次你要和别人分一件东西,请想一想:你们心里对每一部分的估价一样吗?你用的是哪一条"公平"?有没有办法让两个人拿到的都比"每人一半"更好?

思考题

  1. 蛋糕例子里(你:巧克力 8、香草 2;小周:巧克力 3、香草 7),把你的切法改成:左块是巧克力的前 3/4,右块是剩下的巧克力和全部香草。算出两块在你和小周心里各值多少。这样切,你的两块相等吗?
  2. 如果你和小周的口味完全一样,“你切我选"会不会浪费?为什么?
  3. 你的口味:巧克力 6、香草 4;小周的口味:巧克力 2、香草 8。如果你知道小周的口味,设计一个切法:左块 = 全部巧克力 + 香草的一部分,让小周觉得两块一样。你能拿到多少?
  4. 移动刀,你觉得每处一样好吃,小林也是;小周偏爱左边,左半每单位值 1.8,右半每单位值 0.2(总共 1)。谁先喊停?此时喊停的人拿走多长的一块?剩下的两人用"你切我选"分,每人至少拿到多少?
  5. 分房租的例子,检验价格(大房 550,中房 370,小房 280)是不是无嫉妒(住房安排不变:你大房,小周中房,小林小房)。总和是多少?
  6. 想一个生活里"公平分"的例子(分家务、分遗产、分团队奖金、合租分房租……),说说你会用哪一条"公平"标准,对方会不会有不同的想法。

思考题提示

  1. 你:左块值 8 × 3/4 = 6;右块值 8 × 1/4 + 2 = 4。不相等(6 和 4)。小周:左块值 3 × 3/4 = 2.25,右块值 3 × 1/4 + 7 = 7.75,小周会选右块,你拿左块(6)。这一次你运气好:小周爱香草,恰好选走了你不太想要的那块。但你并不能事先指望这一点:如果小周的口味和你一样爱巧克力,就会选走左块(6),你只剩 4,比保底的 5 还少。所以在不知道对方口味时,稳妥的切法是切成你自己觉得相等的两块。
  2. 不会浪费。 口味完全一样,两块在两人心里一样值,不管怎么选,两人的价值都一样,不存在"换一换,大家都更好"的空间。
  3. 小周觉得:全部巧克力值 2,要凑到 5,还差 3,香草每份(整块)值 8,所以需要香草的 3/8。左块 = 全部巧克力 + 香草的 3/8。你觉得左块值 6 + 4 × 3/8 = 6 + 1.5 = 7.5;小周觉得左块值 5,右块(香草的 5/8)值 8 × 5/8 = 5。小周觉得一样。你拿左块得 7.5,小周得 5。(而切成"每块各一半巧克力一半香草”,你们都只得到 5 左右。)
  4. 你和小林在 x = 1/3 喊停。小周:1.8x = 1/3,x = 1/5.4 ≈ 0.185,最先喊停。小周拿走 [0, 0.185]。剩下长度 0.815,你和小林觉得每处一样,用"你切我选",每人至少 0.815 ÷ 2 ≈ 0.407,大于 1/3。
  5. 你:大房 600 − 550 = +50,中房 400 − 370 = +30,小房 300 − 280 = +20,大房最好。小周:大房 500 − 550 = −50,中房 450 − 370 = +80,小房 350 − 280 = +70,中房最好。小林:大房 450 − 550 = −100,中房 400 − 370 = +30,小房 400 − 280 = +120,小房最好。每个人住在自己最好的房间,无嫉妒。总和 550 + 370 + 280 = 1200。
  6. 开放题。例:分遗产。有人用"每人一样多",有人用"谁更需要多分",有人用"谁照顾得多多分"。每种标准都是一种"公平",没有统一的答案。