三人合租的房租公平分配方案
今天在读《数学也荒唐》时读到分蛋糕问题，想起之前写过一篇 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
2->3需要将难度退化
Posted by: Anonymous | (10) October 13, 2018 02:59 PM
建议移除情感因素这个条件，只考虑性价比，这样解法一就是完美解。
不然会变得无法讨论，如解法一中会出现A、C都满意而B对其中两间房价格不满意，最后一间房房型不满意的情况。解法二则会出现B、C对同一间房有同样期望价格，而致使C不能满意的情况。
Posted by: la | (9) September 13, 2018 09:02 PM
呵呵，累不累还计算！
Posted by: EXPASSET | (8) September 4, 2018 09:53 AM
三室一厅的一个月只要2400吗。。。
Posted by: 杨光 | (7) August 13, 2018 08:52 AM
也可以三人共同定价，然后抓阄选房。
然后可以根据个人喜好，私下协商调换。
Posted by: davy chen | (6) July 31, 2018 10:42 AM
我实际的方法是三个不同房间根据大小扥规格给定3个不同的定价，3人确认该价格方案后，进行抽签排选择顺序，依次选择。
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
我想到一个简单的方案是:
每个人自己根据总价分成自己认为合理的3个房间价格, 然后3个人同时摊牌, 以9个价格中最高的确定该房间的所属和价格, 然后剩下2个人用同样的方法竞标, 最后1个人的房间和价格没有选择权了.
虽然看起来不太公平, 但也是比较简单合理的.
PS: 出现最高价格相同的情况还需额外处理,如继续竞拍; 另外还有可能最后1个房间价格为0或负的情况, 虽然会让另外2人不满,但规则本身是公平的.
Posted by: dwing | (2) July 25, 2018 09:26 PM
人往往是贪婪的
Posted by: fangxin | (1) July 25, 2018 05:45 PM