和朋友出游分房间差点友尽，“我都行”这个究极难题原来可以这么解？

来源：滚动播报

（来源：科普中国）

房怎么分？“我都行”先挑，不羡慕别人的公平怎么达成？

约朋友出去玩，最容易达成一致的，可能只有“出去玩”这三个字。

去哪儿、吃什么、几点出发，都还能慢慢商量。真正让气氛微妙起来的，是晚上的民宿分房：一间带阳台，晚上能坐着赏月；一间朝院子，安静好睡；还有一间普普通通，唯一的优点是离客厅近，大家分月饼时不会漏掉你。

订房时，大家看的是同一组照片；到入住时才发现，照片里的美好，需要分配。

图丨AI 生成情景图

“房费一人三分之一？”

话音刚落，有人开始研究阳台，有人开始研究账单，还有一位坐下玩起了手机，只留下一句——“我都行，你们定。”

一起出游，谁都不想显得斤斤计较。但同样的钱，有人推窗见月，有人推窗见墙，心里难免有一点小小的不平衡。

抽签？倒是干脆。抽完以后，总有人想再抽一次。

有没有一种分法，既不用劝谁“大度一点”，也不用争出那扇阳台究竟值多少钱，就能让大家都不想换成别人的那一份？

数学家还更进了一步：先不问其中一个人的喜好，把价格定好，让他第一个挑。在相应条件下，剩下的人也都能拿到自己最满意的选项。

我这间挺划算，

但你那间好像更划算

在请数学家出场之前，我们自己就能想到一个看着不错的办法：

让每个人给三间房估价，合计都凑成 900 元，再取每间房估值的平均数作为房费。假设这次恰好三人最看重的房间各不相同，分完以后，每人付的钱还都低于自己的心理价。

图丨三个人对各间房心理估值的一种情况

这么一看，岂不是人人都觉得自己捡了便宜？

于是，小 A 住阳台房，付 330 元；小 B 住安静房，付 270 元；小 C 住普通房，付 300 元。账刚好对上。

小 A 尤其满意：阳台房在他心里值 450 元，现在只花 330 元，相当于“赚”了 120 元。

本来已经准备去阳台赏月了，偏偏又看了一眼小B的账单。安静房在小 A 心里值 400 元，小 B 却只要付 270 元。按同样的算法，这份差了 130 元。

他没有觉得自己的房间不值这个价。他只是发现，别人的那份更划算。（ps：这里的“赚”，是用“心里的估值，减去实际要付的钱”来估算。）

原来，“我觉得自己赚了”和“我不想跟你换”，是两码事。 别笑，就连刚才这种人人都觉得买到了便宜的情况，也过不了这第二关。

Envy-Free 分配法

公平分配研究给这种要求起了个名字——无嫉妒（Envy-Free）：按我自己的判断，把别人的房间连同他的账单一起换给我，我也不会觉得更好。

注意，房间和账单得一起换。只拿走阳台、把账单留给朋友，那叫愿望，不叫方案。

这个标准允许大家付不同的钱，也允许大家有不同的喜好。有人愿意为赏月多花一点，有人宁可省下钱去买盒月饼。

那么问题来了：喜好长在别人脑子里，怎么调价格，才能让大家都不惦记别人的那份？

公平之前，

有时需要把选择变多

至于怎样调出这样的价格，先从两个人试起。

“你分我选”最古老的用武之地，中秋当晚就摆在饭桌上：一块莲蓉双黄，两个人分。一人切，另一人先挑。切的人不敢切偏——偏的那块多半落到自己手里；先挑的人也无话可说。互不相欠，皆大欢喜。

可是三个人呢？

1940 年代，躲避纳粹的波兰数学家施坦豪斯在战时琢磨起了这个问题。他和巴拿赫、克纳斯特一起研究了多人分蛋糕的办法：每个人至少拿到自己眼中 1/n 的份额[4]——没想到吧，切个蛋糕能切出一整个学科。

不过，“我这份够了”，不代表“不想瞄一眼别人的盘子”。三人的无嫉妒切法，直到 1960 年代才由塞尔弗里奇和康威各自提出；适用于任意有限人数的有限步无嫉妒方案，则要等到 1995 年的布拉姆斯与泰勒[5]。

为了分好一块蛋糕，他们是认真的

而我们在小长假遇到的问题则更难办，总不能沿着阳台切一刀，一人带走半间。

好在房间旁边还跟着一张账单。价格在这里就像那把切月饼的刀：房间切不开，费用却能调一调，让不同的房间变得同样合意。

回到民宿的走廊上。假设另一次出游，只有两个人、两间房，总价也是 900 元。小 A 想了想，给出一组价格：阳台房 550 元，普通房 350 元。这两个“房间加价格”的组合，在他眼里正好一样满意。

那就让朋友先挑。

网络图

朋友选阳台，小 A 省下 200 元；朋友选普通房，小 A 花自己认可的价钱住阳台。进退皆是赢家，小 A 和朋友都拿到了住房的“大结果”。

注意，房间还是那两间，价格却让小 A 多了一个最佳选项。

1999 年，数学家弗朗西斯·苏（Francis E. Su）证明：在相应的偏好条件下，多人分房也能找到 Envy-Free 的安排。他用的两样工具，一个是研究“搭配与排列”的组合数学，一个是研究“连续变形而不撕裂”的拓扑学——分个房，居然动用了这等家伙什。[1]

两个人的道理到这里就通了。但第三个人一加入，事情就没那么简单。

回到三人出游：小 A 、小 B 都到了，小 C 还在路上。群里那句“我都行”，并没有告诉大家他究竟喜欢什么。现实里，小 C 也未必是在路上：他可能只是不想当众报出自己的心理价。

此时，怎么才敢让小 C 先挑？

他随便挑，

我们真都行

假设另一次三人分房，分配好价格后：

小 A 觉得，阳台房和安静房，并列第一。小 B 觉得，安静房和普通房，并列第一。这里的“第一”，都算上了相应的房费，恰好有两个选项打成平手。

这时，小 C 拖着行李箱进门了。

他走向阳台房——行，小 A 住安静房，小 B 住普通房。

他看中了安静房——也行，小 A 去阳台房，小 B 还是普通房。

他偏偏就喜欢离客厅近的普通房——没问题，小 A 去阳台房，小 B 住安静房。

图 | 三行代表小 C 的三种选择，小 A 和小 B 拿到的都是自己的并列最佳选项

小 C 无论挑走哪一间，另外两人都拿到了自己并列最喜欢的一份。只要小 C 自己诚实地按照喜好挑，三人就都不想换。价格从头到尾不变，也没有人等他选完再扫兴地浇上一桶冷水：“你这间得加钱”。

现在，那个一开始听起来偏心的安排，有点意思了：小 C 可以先选，因为小 A 和小 B 已经有了足够的好选择。

不过刚才，我们是假设已经找到了这样的价格，才让小 C 放心先挑。剩下的问题是：换一套房、换几个朋友，这样的价格还找得到吗？

要研究这件事，先把所有可能的价目表放在一起看。三间房总价 900 元，每间价格都不低于 0 ；这种价格组合，恰好能在一个三角形里表示。

分个房，

怎么还画上三角形了？

在这张图上，三个角分别代表（900，0，0）、（0，900，0）、（0，0，900）；正中心代表（300，300，300）。边上至少有一间房免费，内部三间房都收费。

图 | 价目表与三角形的对应关系，三角形上每一个点都是一种价格分配

这下，调房价就变成了在图上挪动一个点。

挪到这里，小 A 觉得阳台值得；挪到那里，阳台太贵，安静房开始显得可爱。我们要找的，是让两个人都拥有足够选择余地的位置。

价目表有无穷多张，总不能挨个报价，把赏月聊成看日出。

数学家请出的帮手，是一种涂色游戏。

把大三角形分成许多小三角形。大三角形的三个角各涂一种颜色；边上的点，只能用这条边两端的颜色；内部的点，三种颜色随便选。

规则就这些。

神奇的是，只要遵守这些规则，至少有一个小三角形，三个顶点会集齐三种颜色。

图 | 阴影小三角形的三个顶点集齐三种颜色| wiki

这就是二维的 Sperner 引理。[1]

它给出了一个判词般的结论：只需要把边界涂好，中间怎么涂都行，一个“三色齐全”的小三角迟早会出现——数学不会因为你不配合而失效。

把两人的选房偏好按特定规则记到价格图上，就能借助这个涂色结论，证明我们要找的安排确实存在：在相应条件下，可以找到同一组价格，让小 A 和小 B 各有至少两个最佳选项，两人的最佳选项合起来又覆盖三间房。[2]

这样，小 C 挑走任何一间，剩下两人仍能各住一间自己最满意的房间。具体怎样编码、怎样从附近的价格得到同一组价格，放在文末彩蛋里展开。

到这里，可以正式亮出这条定理了。Su 把它命名为“和谐租房定理”（Rental Harmony），它只要求三个条件：

1.任何一张价目表摆出来，每个人都至少接受一个房间；

2.面对免费房和收费房，谁都选免费的；

3.偏好是“闭合”的：如果一个人在一串越来越接近的价格下都选同一间房，那么在这串价格的极限处，他依然选它。

这些条件不能省。比如，普通房免费你都不愿住，就不能直接套用这个版本；免费还加上闭合条件，还意味着几间房同时免费时，人们对它们同样合意。前面把价格逼近到同一处，靠的也是闭合条件。在这个问题上，数学家比收房租的房东还较真。

来者不拒

多多益善

偏偏小 D 也想加入这趟旅行。

换成四个人、四间房，还能让一个没表态的人先选吗？在相应条件下，可以。论文讨论的，正是任意人数的这个问题。[2]

但“每个人都有两个选项”，这回不够用了。

假如前面三个人都只认同 1 号和 2 号房，人人都有备选，合起来却只有两间。三个人盯着两把钥匙，谁说“我都行”也没用。

所以，除了看每个人，还得看每一小群人：在已经询问过偏好的那些人中，任取一群，他们合起来最喜欢的房间，至少要比人数多一间。最后那位先拿走一间，剩下的才仍然够分。这样的条件能保证配得上，这背后藏着的是 Hall 匹配定理。[2]

数学家没有读心术，猜不到最后一个人的心思，却为他的选择留好了余地。这才是整件事最惊喜的地方。

月亮只有一个，

喜欢什么各有各的

这套模型当然不止于小长假里的民宿分房，在更漫长日常的生活里，它也有不小的用武之地。

合伙人分办公室？邻居分车位？经营者分摊位？——只要每人恰好需要一个位置，而且允许用费用调整来补偿差异，就可以考虑类似的分配模型。

而对准备出去玩的我们来说，倒不必先在群里发一份拓扑学讲义。

把房间和价格放在一起讨论，已经比只问一句“谁住哪间”多了一条协商的路。你愿意为阳台多花一点，他乐意省下钱吃夜宵，两个人未必非得争出谁的喜好更合理。

中秋一起出去玩，月亮只有一个，大家想要的却未必一样。

公平未必需要把这些愿望磨成同一个样子。

至于群里那个说“我都行”的朋友，下次可以认真问一句：“那价格先说好，你先挑？”

当然，说得这么热闹，真到了中秋，我们多半还是靠抽签草草了事。只是往后每次抽签，大概都会想起：这世上，还藏着一个专门解决“没人想换”的三角形。

彩蛋①：

为什么三色三角形一定会出现

把颜色换成 1、2、3。我们把端点分别是 1 和 2 的小边当作“门”，小三角形当作房间。

图 | 把颜色换成编号 1、2、3，仍是同一个涂色问题 | wiki

一间房有几扇门？顶点同时有 1 和 2、却没有 3 时，有两扇；集齐 1、2、3 时，恰好一扇；其余情况没有门。

再看大三角形的外墙：门只会出现在连接1号角和2号角的那条边上。从 1 走到 2，编号切换的次数一定是奇数，所以外门有奇数扇。

从一扇外门进去，有另一扇门就继续走，不走回头路。如果从另一扇外门出来，这两扇外门就配成一对。外门有奇数扇，不可能全部两两配对，因此至少有一条路会停在里面——那间只有一扇门的房间，正是三色小三角。

图 | 这是 Sperner 引理证明中的“走门”示意：沿特定标签的边进入小三角形，寻找三色齐全的终点。| PBS Infinite Series

Sperner 引理在论文第 2 节[2]给出了完整证明。

彩蛋②：

三色齐了，为什么就能分房？

把价格三角形切成小网格，在每个网格点问小 A 和小 B ：这张价目表下，你最想住哪间？ 再把两人的回答按特定规则编成三种颜色。

这套编码有个巧妙之处：只要小 A 或小 B 始终只选同一间房，或者两人的选择合起来漏了一间，三种颜色就凑不齐。

在正文的条件下，编码满足 Sperner 引理的边界规则，因此一定能找到一个三色小三角。它意味着：在这几个相近的价格下，两人各自都选过不止一间房，合起来又覆盖了三间房。

但还差一步：价格相近，不等于价格相同。 不断细分网格，再选取收敛的价格序列，借助偏好的“闭合”条件，就能把这些最佳选项保留到同一张价目表上。

这时，两人各有至少两个最佳选项，合起来覆盖三间房。小 C 随便挑走哪间，剩下两人仍能各拿一间自己最满意的。

图源 | PBS Infinite Series

具体编码与完整证明，见这篇论文的第 3 节[2]。也可以看 PBS Infinite Series《Splitting Rent with Triangles》，这里有很形象的动画解说。

参考文献

[1] Francis E. Su. Rental Harmony: Sperner's Lemma in Fair Division. The American Mathematical Monthly, 106(10), 930–942, 1999. ：https://math.hmc.edu/su/wp-content/uploads/sites/10/2019/06/Rental-harmony.pdf

[2] Florian Frick, Kelsey Houston-Edwards, Frédéric Meunier. Achieving Rental Harmony with a Secretive Roommate. The American Mathematical Monthly, 2019：https://arxiv.org/html/1702.07325

[3] PBS Infinite Series. Splitting Rent with Triangles, 2017.https://www.pbs.org/video/splitting-rent-with-triangles-ekutju/

[4] H. Steinhaus. The Problem of Fair Division. Econometrica, 16(1), 101–104, 1948.

[5] S. J. Brams, A. D. Taylor. An Envy-Free Cake Division Protocol. The American Mathematical Monthly, 102(1), 9–18, 1995.