房怎么分？
「我都行」先挑
不羡慕别人的公平怎么达成？
约朋友出去玩，最容易达成一致的，
可能只有“出去玩”这三个字。
去哪儿、吃什么、几点出发，都还能慢慢商量。
真正让气氛微妙起来的，是晚上的民宿分房：
一间带阳台，晚上能坐着赏月；一间朝院子，安静好睡；还有一间普普通通，唯一的优点是离客厅近，大家分月饼时不会漏掉你。
订房时，大家看的是同一组照片；到入住时才发现，照片里的美好，需要分配。
图：AI生成情景图
"房费一人三分之一？"
话音刚落，有人开始研究阳台，有人开始研究账单，还有一位坐下玩起了手机，只留下一句——"我都行，你们定。"
一起出游，谁都不想显得斤斤计较。但同样的钱，有人推窗见月，有人推窗见墙，心里难免有一点小小的不平衡。
抽签？倒是干脆。抽完以后，总有人想再抽一次。
有没有一种分法，既不用劝谁“大度一点”，也不用争出那扇阳台究竟值多少钱，就能让大家都不想换成别人的那一份？
数学家还更进了一步：先不问其中一个人的喜好，把价格定好，让他第一个挑。在相应条件下，剩下的人也都能拿到自己最满意的选项。
part.01
我这间挺划算，
但你那间好像更划算
在请数学家出场之前，我们自己就能想到一个看着不错的办法：
让每个人给三间房估价，合计都凑成900元，再取每间房估值的平均数作为房费。假设这次恰好三人最看重的房间各不相同，分完以后，每人付的钱还都低于自己的心理价。
图：三个人对各间房心理估值的一种情况
这么一看，岂不是人人都觉得自己捡了便宜？
于是，小A住阳台房，付330元；小B住安静房，付270元；小C住普通房，付300元。账刚好对上。
小A尤其满意：阳台房在他心里值450元，现在只花330元，相当于“赚”了120元。
本来已经准备去阳台赏月了，偏偏又看了一眼小B的账单。安静房在小A心里值400元，小B却只要付270元。按同样的算法，这份差了130元。
他没有觉得自己的房间不值这个价。他只是发现，别人的那份更划算。（ps：这里的“赚”，是用”心里的估值，减去实际要付的钱“来估算。）
原来，“我觉得自己赚了”和“我不想跟你换”，是两码事。 别笑，就连刚才这种人人都觉得买到了便宜的情况，也过不了这第二关。
Envy-Free分配法
公平分配研究给这种要求起了个名字——无嫉妒（Envy-Free）：按我自己的判断，把别人的房间连同他的账单一起换给我，我也不会觉得更好。
注意，房间和账单得一起换。只拿走阳台、把账单留给朋友，那叫愿望，不叫方案。
这个标准允许大家付不同的钱，也允许大家有不同的喜好。有人愿意为赏月多花一点，有人宁可省下钱去买盒月饼。
那么问题来了：喜好长在别人脑子里，怎么调价格，才能让大家都不惦记别人的那份？
part.02
公平之前，
有时需要把选择变多
至于怎样调出这样的价格，先从两个人试起。
"你分我选"最古老的用武之地，中秋当晚就摆在饭桌上：一块莲蓉双黄，两个人分。一人切，另一人先挑。切的人不敢切偏——偏的那块多半落到自己手里；先挑的人也无话可说。互不相欠，皆大欢喜。
可是三个人呢？
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先挑？
part.03
他随便挑，
我们真都行
假设另一次三人分房，分配好价格后：
小A觉得，阳台房和安静房，并列第一。小B觉得，安静房和普通房，并列第一。这里的“第一”，都算上了相应的房费，恰好有两个选项打成平手。
这时，小C拖着行李箱进门了。
他走向阳台房——行，小A住安静房，小B住普通房。
他看中了安静房——也行，小A去阳台房，小B还是普通房。
他偏偏就喜欢离客厅近的普通房——没问题，小A去阳台房，小B住安静房。
图：三行代表小C的三种选择，小A和小B拿到的都是自己的并列最佳选项
小C无论挑走哪一间，另外两人都拿到了自己并列最喜欢的一份。只要小C自己诚实地按照喜好挑，三人就都不想换。价格从头到尾不变，也没有人等他选完再扫兴地浇上一桶冷水：“你这间得加钱”。
现在，那个一开始听起来偏心的安排，有点意思了：小C可以先选，因为小A和小B已经有了足够的好选择。
不过刚才，我们是假设已经找到了这样的价格，才让小C放心先挑。剩下的问题是：换一套房、换几个朋友，这样的价格还找得到吗？
要研究这件事，先把所有可能的价目表放在一起看。三间房总价900元，每间价格都不低于0；这种价格组合，恰好能在一个三角形里表示。
part.04
分个房，
怎么还画上三角形了？
在这张图上，三个角分别代表（900，0，0）、（0，900，0）、（0，0，900）；正中心代表（300，300，300）。边上至少有一间房免费，内部三间房都收费。
图：价目表与三角形的对应关系，三角形上每一个点都是一种价格分配
这下，调房价就变成了在图上挪动一个点。
挪到这里，小A觉得阳台值得；挪到那里，阳台太贵，安静房开始显得可爱。我们要找的，是让两个人都拥有足够选择余地的位置。
价目表有无穷多张，总不能挨个报价，把赏月聊成看日出。
数学家请出的帮手，是一种涂色游戏。
把大三角形分成许多小三角形。大三角形的三个角各涂一种颜色；边上的点，只能用这条边两端的颜色；内部的点，三种颜色随便选。
规则就这些。
神奇的是，只要遵守这些规则，至少有一个小三角形，三个顶点会集齐三种颜色。
图：阴影小三角形的三个顶点集齐三种颜色（图源wiki）
这就是二维的 Sperner 引理。[1]
它给出了一个判词般的结论：只需要把边界涂好，中间怎么涂都行，一个"三色齐全"的小三角迟早会出现——数学不会因为你不配合而失效。
把两人的选房偏好按特定规则记到价格图上，就能借助这个涂色结论，证明我们要找的安排确实存在：在相应条件下，可以找到同一组价格，让小A和小B各有至少两个最佳选项，两人的最佳选项合起来又覆盖三间房。[2]
这样，小C挑走任何一间，剩下两人仍能各住一间自己最满意的房间。具体怎样编码、怎样从附近的价格得到同一组价格，放在文末彩蛋里展开。
到这里，可以正式亮出这条定理了。Su 把它命名为"和谐租房定理"（Rental Harmony），它只要求三个条件：
Rental Harmony
任何一张价目表摆出来，每个人都至少接受一个房间；
面对免费房和收费房，谁都选免费的；
偏好是"闭合"的：如果一个人在一串越来越接近的价格下都选同一间房，那么在这串价格的极限处，他依然选它。
这些条件不能省。比如，普通房免费你都不愿住，就不能直接套用这个版本；免费还加上闭合条件，还意味着几间房同时免费时，人们对它们同样合意。前面把价格逼近到同一处，靠的也是闭合条件。在这个问题上，数学家比收房租的房东还较真。
part.05
来者不拒
多多益善
偏偏小D也想加入这趟旅行。
换成四个人、四间房，还能让一个没表态的人先选吗？在相应条件下，可以。论文讨论的，正是任意人数的这个问题。[2]
但“每个人都有两个选项”，这回不够用了。
假如前面三个人都只认同1号和2号房，人人都有备选，合起来却只有两间。三个人盯着两把钥匙，谁说“我都行”也没用。
所以，除了看每个人，还得看每一小群人：在已经询问过偏好的那些人中，任取一群，他们合起来最喜欢的房间，至少要比人数多一间。最后那位先拿走一间，剩下的才仍然够分。这样的条件能保证配得上，这背后藏着的是Hall匹配定理。[2]
数学家没有读心术，猜不到最后一个人的心思，却为他的选择留好了余地。这才是整件事最惊喜的地方。
part.06
月亮只有一个，
喜欢什么各有各的
这套模型当然不止于小长假里的民宿分房，在更漫长日常的生活里，它也有不小的用武之地。
合伙人分办公室？邻居分车位？经营者分摊位？——只要每人恰好需要一个位置，而且允许用费用调整来补偿差异，就可以考虑类似的分配模型。
而对准备出去玩的我们来说，倒不必先在群里发一份拓扑学讲义。
把房间和价格放在一起讨论，已经比只问一句“谁住哪间”多了一条协商的路。你愿意为阳台多花一点，他乐意省下钱吃夜宵，两个人未必非得争出谁的喜好更合理。
中秋一起出去玩，月亮只有一个，大家想要的却未必一样。
公平未必需要把这些愿望磨成同一个样子。
至于群里那个说“我都行”的朋友，下次可以认真问一句：“那价格先说好，你先挑？”
当然，说得这么热闹，真到了中秋，我们多半还是靠抽签草草了事。只是往后每次抽签，大概都会想起：这世上，还藏着一个专门解决"没人想换"的三角形。
道理我都懂，但还是抽签吧
文末互动
来看你的选择
还有别的好主意？欢迎在评论区分享给为此烦恼的小伙伴！
顺便，把这篇转进那个总有人说"我都行"的群里——趁中秋之前，把价目表说清楚。
彩蛋①：
为什么三色三角形一定会出现
把颜色换成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.
编辑：辣条
↓ 点击标题即可查看 ↓
3. 做磁共振检查，忘了摘“999足金”的金镯子，万万没想到……
4. 耗资3000万美元的救援任务彻底失败，雨燕天文台正在坠向地球
6. 一滴雨水，电压竟能超过1000伏？它甚至可能把金属“电坏”
7. 体长11600光年，碳总量是全人类的6倍，这类隐秘的生物用了四亿多年，生长成了自然界的地基
10. 俗话说，“响屁不臭，臭屁不响”，有科学道理吗？ | No. 526