三人合租的房租公平分配方案
今天在读《数学也荒唐》时读到分蛋糕问题，想起之前写过一篇 blog 谈房租分配，其实是同一个问题：
当多个人要切分资源时，如何让每个人都满意。
因为每个人对价值判断是不一样的，就租房来说，有人追求性价比；有人追求舒适，对价格不敏感；按某种固定的方案定价就不太公平。
如果是两人合租，最简单的公平方案就是你定价，我来选。A 来提一个自己认为公平的定价方案：例如大房间 1000 ，小房间 800 ；B 来选择住大房间还是小房间。如果 A B 都是理性的，这就是让双方都满意的方案。
但是三人或更多人分配就没有这么简洁的策略。我在前篇 blog 中讨论了这个问题，在回复中，也有同学给了知乎上分蛋糕问题的链接。
过了这些年，今天读书时又看到，感觉有趣，那么再写一次。
当三人合租时，可以先由 A 先提一个自认为公平的定价方案：例如主卧 1000 ，朝南的次卧 800 ，朝北的次卧 600 。
然后 B 对这个定价方案做出判断，他有两个选择：
如果 B 认为至少有两个房间的定价是可以接受的，那么他可以选择按 C B A 的次序来选择。因为有两个房间可以接受，他是第 2 个选，那么总可以选到满意的房间。
如果 B 认为有两个房间的定价不合理，那么他可以把心目中不合理的两个房间标记为差，然后交给 C 处理。
之后 C 也有两个选择：
如果他觉得定价方案没那么差（两个房间都不合理），那么他可以选择按 B C A 的次序来选择。这样，B 是第一个选，一定能选到他认为最好的房间。（B 认为两间房不合理，那么第三间一定是占了便宜）
如果 C 也认为有两个房间定价不合理，他也把心目中不合理的房间标记为差。
最后，A 必须选择 B C 都不喜欢的房间（如果 B C 观点一致，那么 A 在两间不合理的房间中挑一间）。
A 选走一间房后，问题就退化成两人分配两间房的问题了。
简单说就是，作为定价方 A ，肯定是最后选的，那么他会保证定价均衡。而 B 只有在保证自己可以获得可以接受的选择时，才会让给 C 先选。如果他选择标记出不喜欢的，那么他要么拿到最满意的，要么获得重新分配的方案，而不会在不喜欢的两项中被迫选其一。
只要每个人都理性行事，最终每个人都可以满意。
还有一个方案：
由 A 提出一个方案，还是按上面的例子，例如主卧 1000 ，朝南的次卧 800 ，朝北的次卧 600 。
B 这个时候做出判断，看看是否基本满意，如果对分配方案认可，就直接轮到 C ，按 C B A 的次序从 A 提出的方案中挑选即可。
如果 B 特别中意其中一间，可以对这间加价：例如，他可以说，主卧 1100 ，然后问 C 要不要这间。C 可以选择加价后的主卧，如果 C 不要，B 必须选择这间。
这样 B 和 C 中一定会有人选走这间加过价的房间；之后，剩下的一人对剩下的两间提一个方案，交给 A 优先选择。
按照这个方案，在从三人问题化简到两人问题的过程中，首先选定的人有机会充分考虑价格和喜好因素，所以三人都不会有怨言。
这个问题叫做 Fair Division ，在 wikipedia 上可以找到详细的证明。
Comments
Posted by: hl4 | (11) January 25, 2019 02:37 PM
Posted by: Anonymous | (10) October 13, 2018 02:59 PM
Posted by: la | (9) September 13, 2018 09:02 PM
Posted by: EXPASSET | (8) September 4, 2018 09:53 AM
Posted by: 杨光 | (7) August 13, 2018 08:52 AM
Posted by: davy chen | (6) July 31, 2018 10:42 AM
Posted by: 温玉 | (5) July 30, 2018 03:37 PM
Posted by: icicle | (4) July 28, 2018 10:24 AM
Posted by: dwing | (3) July 25, 2018 09:30 PM
Posted by: dwing | (2) July 25, 2018 09:26 PM
Posted by: fangxin | (1) July 25, 2018 05:45 PM