
房怎么分?"我都行"先挑股票在线配资靠谱吗,不羡慕别人的公平怎么达成?
约朋友出去玩,最容易达成一致的,可能只有"出去玩"这三个字。
去哪儿、吃什么、几点出发,都还能慢慢商量。真正让气氛微妙起来的,是晚上的民宿分房:一间带阳台,晚上能坐着赏月;一间朝院子,安静好睡;还有一间普普通通,唯一的优点是离客厅近,大家分月饼时不会漏掉你。
订房时,大家看的是同一组照片;到入住时才发现,照片里的美好,需要分配。

图丨 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 觉得阳台值得;挪到那里,阳台太贵,安静房开始显得可爱。我们要找的,是让两个人都拥有足够选择余地的位置。
价目表有无穷多张,总不能挨个报价,把赏月聊成看日出。
数学家请出的帮手,是一种涂色游戏。
把大三角形分成许多小三角形。大三角形的三个角各涂一种颜色;边上的点,只能用这条边两端的颜色;内部的点,三种颜色随便选。
规则就这些。
神奇的是,只要遵守这些规则,至少有一个小三角形,三个顶点会集齐三种颜色。
元股证券:ygzq.hk
图 | 阴影小三角形的三个顶点集齐三种颜色 | 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.
策划制作
来源丨中科院物理所(id:cas-iop)股票在线配资靠谱吗
河南配资网提示:本文来自互联网,不代表本网站观点。