如何用數學方法合理分配房租/房間？
中英混雜預警：對某些人群可能產生頭痛等不適癥狀，此類人群請在心理醫生指導下謹慎閱讀。
6.6 更新：減少了不必要的英文使用，採取了拗口的中文翻譯(with English in parentheses)。根據評論中的關鍵困惑點，對原文進行了完善。
-----------------------------------------------------------------------------------
我和室友們租到了一個非常好的新公寓。但是第一棘手的問題是，如何合理的分配房間？我們有一個房間非常大，朝西，下午陽光很好；有一個房間稍小，但是房間周正，面街朝東，陽光充足；最後一個房間，面積居中，但是陽光稍有不足。很明顯，大家都想要最大的房間。對於另外兩個房間，每個人的偏好不一定相同。
作為三個書獃子的（nerdy）經濟學家（in training），我們第一反應當然是讓價格決定。但是拍賣有個嚴重的問題就是，總價無法保證正好等於房租。如果只拍賣其中兩個房子，又很難保證無嫉妒（envy-free）。因為第三個房子與另外兩個房子並沒有差很多，但是拍賣結果很有可能讓它變得非常便宜，或者非常貴，這時候一定會有人心理不平衡。舉個例子，也許A先生覺得第一間房能帶來的效用（utility）是$2000,第三間房的效用是$500。那麼拍賣第一間房時，他是願意出價到$2000的，然後他拿到這間房。但是等到第二間房也拍賣完以後，大家發現第三間房子只需要支付$100就可以住了。這時候A先生會後悔，因為他若是住第三間房可以有$400剩餘效用，而住第一間只有$0的效用。
後來我們發現，哈佛的書獃子的（nerdy）數學家們已經想過並解決了相同的問題。解決的方法非常優雅（elegant），並且對個人偏好（preference）只需要三個簡單合理的假設便可以證出均衡的存在。
簡單概括全文。談起分配房租，正常人的第一反應是所有人坐下來一起討論，討論出一個所有人都認為合理的房租支付方案。此過程分兩步，確定房間，確定房租。但是複雜之處在於，不確定房間難以確定房租，不確定房租難以確定房間。因此此文章介紹的方法旨在將這個討論的過程數學化，定理化，從而實現更高效更準確的分配。紐約時報通過本文介紹這種演算法開發了一個分房的app。有興趣的知友可以去試一試，從而可以更好的理解本文介紹的原理。用兩句話概括分房的思路：通過演算法產生一個房租分配方式（每一個房間制定一個房價），然後讓每一個租客在給定的房價下選擇一個最想住的房間。如果有兩個人選擇了同一個房間，說明該房租分配不合理，換一個分配方式，重複以上步驟，直到找到某一個分配方式使得所有人選擇不同的房間。紐約時報的簡單介紹（英文）。 下文將簡要介紹的和諧租房定理證明了，在滿足一定條件下，這樣的和諧分配方式一定存在。通過對存在性證明的簡要介紹，希望讀者能大致理解分房演算法，以及感受數學的魅力。實際操作可以直接使用NYT的APP，不需要完全理解本文。
和諧租房定理【Rental Harmony Theorem (Su 1999)】. n個室友想分配n個房間。假設以下三個條件成立：
- 在任何房租分配方式下，每一個人都會接受至少一個房間
- 面對一個免費的房間和不免費的房間，每一個人都會選擇免費的房間
- 【偏好集的閉合性（Closed Preference Sets）】 如果一個人面對一序列的價格（a sequence of prices），都選擇同一個房間，那麼面對序列的極限價格(the limiting price)，他還會選擇同一個房間。
那麼， 一定存在一種房租分配方式使得每個人都選擇不同的房間。
這個結論是挺令人震撼的。我們不需要知道房間的任何情況，也不需要知道每個人具體的偏好便可以達到理想的無嫉妒（envy-free）的均衡。每個人都很滿意，因為他或者支付便宜的房租，或者住上了喜歡的房子。定理的前兩個假設較實際，我覺得沒有太大的爭議。1.畢竟整個房子簽下來說明每個人都是想住的。如果有一個人只愛上一個房間，並且非它不住，那麼不妨就把那個房間定個合理的價錢給他，然後其他人分配剩下的房間。2.免費的幹嘛不住。這實際上是對房子的一個要求，保證沒有質量差得離譜的房間（比如沒有暖氣沒有窗戶的小冰窖）。這個條件可以放鬆。3.閉合性要求，保證人們對房租沒有奇怪的偏好。下面簡單講解一下證明的過程。我們不妨只討論最簡單的三個人情況。我們希望先找到一個分蛋糕問題的解，然後把這個解套用到房租問題上。
事實上，分房問題其實和切蛋糕問題是一樣的。 蛋糕問題這裡見更多：三個極度自私的人分一個蛋糕，採用什麼策略，能讓三人都覺得公平？
假設有一個長方形的蛋糕，上面不均勻的分布著不同的糕點上的裝飾配料（toppings），比方說草莓，獼猴桃，櫻桃，etc。 每個人在選擇的時候既考慮蛋糕的大小，也考慮裝飾配料。有的人也許很喜歡草莓，所以如果有分到草莓，蛋糕小一點也無所謂。那麼這種情況下，如果有三個人，應該怎麼分最合理呢？
Simmons (1980) 提出一個蛋糕問題的解決方案，利用了Sperner引理（ Sperner"s lemma）。
************ Sperner 引理介紹 **********
我們只考慮三個人的情況。取一個大三角形，把大三角形的頂點分別標成1,2,3。然後它再細分成很多小三角形（elementary triangles） ，如下圖所示。之後再給每個小三角形的頂點隨機標號。標號遵循一個原則，在大三角形邊上的頂點只能出現與該邊相連的頂點上的那兩個數字。比如，下圖中的底邊上不能出現3，但是標1或2是隨機選擇的。三角形內部的標號完全隨機。
*************引理結束***********
現在運用到分蛋糕問題中去。假設我們有三個吃貨，A,B,C。 要切三塊蛋糕，分別編號1,2,3 分給他們。先畫一個如下圖所示的大三角形。博弈論中管這個叫做單純形（Simplex），是所有可能的蛋糕分配方式的集合。三角形中任一點代表著一種分配方式，並且任何點的x,y,z坐標相加的和都為1。比如，某一個點在三角形內，坐標為（1/2,1/4,1/4）， 它意味著編號為1的蛋糕體積為整個的1/2，編號2的體積為1/4，編號3體積為1/4。又比如，左下頂點坐標為（1,0,0），意味著1號蛋糕分走全部。然後，把每個小三角形的頂點按如圖所示方法都標上人名，A，B，C，使得每個小三角形的頂點標號都是ABC。
於是通過Sperner引理我們知道一定有至少一個小三角形有著三個標號不同的頂點，如圖中紫色區域。但是紫色區域依然是一個集合，並不是一個具體的分配方式。如果我們想分的粗糙一點，隨便在某一個紫色三角形內選一點 （比如某紫色三角形幾何中心）便找到了近似合理的分配方式，然後按三角形頂點的標號分配蛋糕。例如，如果用最下方的紫三角，那麼A得到2號蛋糕，B得到3號，C得到1號。1,2,3號蛋糕大小由紫三角形內某一點坐標決定。（注意：這個點只是一個估測值，並不能保證三個人在這一點一定會主動選擇方案指定的蛋糕，所以說近似合理）
如果希望更精確，可以給定一個誤差，然後選擇一個紫色三角形繼續細分，並重複之前步驟，最終可以找到一個點（分配方式）使得每個人選擇不同的蛋糕，（此處用到了定理的第三個條件）。對於出現多個紫三角的情況，所有這些三角在理論上都是等價的，可以隨機選擇一個。
蛋糕分完了，我們可以用同樣的方式分房。一個小問題是，大家都希望房租越少越好。所以我們要用負數（房租補貼）才能直接運用分蛋糕的方法。用一個具體例子來說，假設房租一個月3000刀，那麼我們可以先要求每人都交一個較高的房租（只要足夠高都可以，比如$1200），然後將多出部分作為補貼像蛋糕一樣分配（我的例子里$600的補貼）。於是我們就花了一下午的時間愉快的分出了房間。。
推薦閱讀：