切個(gè)蛋糕也燒腦

石無魚

如何分一塊蛋糕？你可能會(huì)認(rèn)為答案非常簡(jiǎn)單。根據(jù)人數(shù)，把蛋糕切成相應(yīng)的分?jǐn)?shù)，只要大小差不多，不就可以了？

其實(shí)，這個(gè)問題非常復(fù)雜。例如，分糕的本意是讓大家都吃得開心，但總有一些意外情況會(huì)讓有些人不歡而散，比如，有的人非常討厭草莓，但你按照上述分糕方法，很有可能恰恰給他們分了有草莓的那一塊，還有的人可能會(huì)覺得自己手中分到的蛋糕小，感覺很不公平。說到這里，也許現(xiàn)在你已經(jīng)明白了，我們不只是在談?wù)摰案?，而是在談?wù)摴椒峙涞膯栴}。

在生活的許多方面，都涉及到“分糕”，比如如果在學(xué)校住宿，你會(huì)遇到分配宿舍床位的問題。在家里，家務(wù)也需要分配，再大一點(diǎn)，在法律政治領(lǐng)域，法官該如何判刑，稅收該收多少，高考政策該如何向貧困地區(qū)傾斜，這些也可以簡(jiǎn)化為一個(gè)“分糕”問題。當(dāng)我們弄懂了一個(gè)蛋糕該如何分配，這些問題其實(shí)都可以解決。然而，到底該怎么分配呢？為了簡(jiǎn)化，我們不妨先從如何科學(xué)地分一塊蛋糕或者一個(gè)宿舍開始。

我分，你選擇

現(xiàn)在我們假想一個(gè)簡(jiǎn)單的情形，假如兩個(gè)孩子都要吃一塊蛋糕，蛋糕只有一塊，媽媽該如何分配，讓這兩個(gè)孩子都不覺得自己拿得太少？

聰明的你可能很快想到答案，只需使用一種“我分，你選擇”的方法就可以解決。這種情況下，媽媽可以讓一個(gè)孩子分糕，另一個(gè)孩子挑。切糕的人知道選擇的人會(huì)挑兩半中的最好的一半，所以他會(huì)盡可能均勻地切割蛋糕。雙方都能得到一塊他們認(rèn)為是至少和別人一樣好的蛋糕。

該方法非常巧妙，不僅在于它的操作性很強(qiáng)，而且它產(chǎn)生的結(jié)果至少在某些情況下是直觀公平的。因此，經(jīng)濟(jì)學(xué)家和數(shù)學(xué)家們將這種分割模式稱為“無嫉妒”模式。

“我分，你選擇”的方法在實(shí)際生活中應(yīng)用得非常廣泛，比如家務(wù)也可以公平地分配，只要一個(gè)人列出家務(wù)清單，另一個(gè)人選擇自己的那一份。

在商業(yè)領(lǐng)域，這種方法也應(yīng)用于企業(yè)并購。如果一個(gè)企業(yè)要并購另外一個(gè)企業(yè)，往往是強(qiáng)勢(shì)一點(diǎn)的企業(yè)提出收購價(jià)格，而另一個(gè)企業(yè)考慮是不是采納。類似的，跟終止關(guān)系有關(guān)的離婚協(xié)議或者公司之間的合同終止也利用了這種方法。

《國際海事法》甚至也運(yùn)用了這種方法。在20世紀(jì)70年代，各國開始考慮到，海底開采將成為一大產(chǎn)業(yè)，發(fā)展中國家擔(dān)心在自己有能力建立科學(xué)的測(cè)量方法之前，技術(shù)先進(jìn)的發(fā)達(dá)國家的企業(yè)將買走最有價(jià)值的海底所有權(quán)?！逗Ｑ蠓üs》解決了這個(gè)問題。現(xiàn)在，如果一家公司希望在海底開采，他們必須首先將開采區(qū)域劃分成兩部分，由主權(quán)國選擇一個(gè)。

N塊蛋糕的切分模式

然而，這些只是兩個(gè)人之間的分割模式，假如蛋糕現(xiàn)在是三個(gè)人一起吃，又該如何分配呢？

20世紀(jì)40年代，一個(gè)名為胡果·斯坦豪斯的教授是第一個(gè)用數(shù)學(xué)的嚴(yán)謹(jǐn)性來解決這些問題的。他思考的是是否在三個(gè)或三個(gè)以上的人之間，可以運(yùn)用“我分，你選擇”的方法，他最終想出了現(xiàn)在所謂的“孤分法”。

想象一下，現(xiàn)在一塊蛋糕由三個(gè)人分。其中一個(gè)被隨機(jī)抽為切糕者，他的任務(wù)是將蛋糕切成三塊。此時(shí)，切糕者不知道他會(huì)得到哪一塊，所以他試圖切出三個(gè)同樣大小的蛋糕塊。剩下的兩個(gè)人，會(huì)選擇哪塊蛋糕他們?cè)敢饨邮?，然后他們?huì)做比較，如果兩個(gè)選擇的人都宣稱自己愿意接受不同的蛋糕，游戲結(jié)束，這兩塊蛋糕由他們拿走，切糕的人拿到第三塊。

然而，如果兩個(gè)選擇者都想要同一塊，切糕者拿走沒有人搶的兩塊中的一塊，剩下的兩塊蛋糕可以重新制作成一塊蛋糕，然后兩個(gè)饑餓的競(jìng)爭(zhēng)對(duì)手來重新進(jìn)行“我分，你選擇”的游戲。

胡果的“孤分法”很簡(jiǎn)單，可擴(kuò)展到三個(gè)以上的玩家，但它不能保證結(jié)果是高效率的。如果要高效率地分配，我們需要更復(fù)雜的數(shù)學(xué)。

三角形蛋糕

20世紀(jì)90年代后期，弗朗西斯·蘇在哈佛大學(xué)獲得了他的數(shù)學(xué)博士學(xué)位，一天，他在劍橋大學(xué)上學(xué)的朋友布拉德·曼找上了他，告訴了他一個(gè)關(guān)于住宿問題的煩惱。像在劍橋上學(xué)的大多數(shù)學(xué)生一樣，曼將與一些室友共用一個(gè)小的套間。當(dāng)涉及到誰該住什么房間，又該花費(fèi)多少時(shí)，大家的意見不統(tǒng)一，曼想知道如何打破僵局。

雖然我們大多數(shù)人會(huì)用一個(gè)簡(jiǎn)單的經(jīng)驗(yàn)方法回應(yīng)，比如采用抽簽或者直接平分房租等的方法，但蘇（現(xiàn)在是美國數(shù)學(xué)協(xié)會(huì)的主席）和我們不一樣，他告訴曼這是一個(gè)數(shù)學(xué)問題，而且還是一個(gè)有關(guān)公平分配的問題。作為一個(gè)“古老切蛋糕的問題”的實(shí)際應(yīng)用，特別啟發(fā)蘇的是20世紀(jì)20年代一個(gè)不起眼的數(shù)學(xué)論證——斯波納引理。這個(gè)定理其最基本的版本，無關(guān)房間或蛋糕分配，相反，它與三角形有關(guān)。這個(gè)引理是這樣的，有一個(gè)大三角形，其頂點(diǎn)分別用紅、綠、黃著色，大三角形里有奇數(shù)個(gè)小三角形，每個(gè)小三角形的三個(gè)頂點(diǎn)也隨機(jī)用紅、綠、黃三種不同的顏色著色，不管你怎么隨機(jī)選擇顏色，最終會(huì)至少得到一個(gè)小三角形，它的三個(gè)頂點(diǎn)是分別用紅、綠、黃來著色。

那么，這與租金有什么關(guān)系呢？

蘇將這個(gè)三角形的頂點(diǎn)重新定位為房間價(jià)格分配模式。例如，蘇將從三角形外面的一個(gè)頂點(diǎn)開始，并問其所有者以下問題：“如果租金是按照這個(gè)定價(jià)方案分配，你會(huì)選擇哪個(gè)房間？”取決于這些人的回答，這一點(diǎn)將會(huì)標(biāo)上一個(gè)字母（A、B或C，這些字母代表著這個(gè)人愿意支付的價(jià)格，以及選擇的房間）。然后，同樣的問題會(huì)被提出，三個(gè)人的回答將組成一個(gè)三角形，該方法將不斷重復(fù)下去，直到一個(gè)房間定價(jià)機(jī)制被發(fā)現(xiàn)，其中每一個(gè)人愿意支付不同的價(jià)格。根據(jù)計(jì)算，這樣的三角形是一定存在的，這個(gè)時(shí)候在租金方面實(shí)現(xiàn)了“無嫉妒，無爭(zhēng)吵”。

撇開數(shù)學(xué)論證細(xì)節(jié)不談，該方法在實(shí)際應(yīng)用中取得了巨大成功。2014年，紐約時(shí)報(bào)用這種方法成功地計(jì)算了三個(gè)人租用一個(gè)3000美元的房間時(shí)該如何分配。

存在的問題

蘇的算法有效，不過只達(dá)到了“無嫉妒”效果，并不一定是最公平的。想象一個(gè)極端的例子，一個(gè)有三間臥室的套間月租金共為3000美元，第一個(gè)室友只想住在第一個(gè)臥室，第二個(gè)室友僅對(duì)第二個(gè)感興趣，第三個(gè)室友也只喜歡第三個(gè)臥室。每個(gè)室友都愿意為他或她喜歡的房間支付全部的3000美元。

用蘇的方法，一個(gè)可能的分配方案將是把每一個(gè)室友放在他們選擇的房間，第一個(gè)房間的人承擔(dān)全部租金。第二和第三個(gè)房間的人不用交任何費(fèi)用，第一個(gè)房間的人也沒有理由反對(duì)。他支付的3000美元完全和他愿意支付的房間的價(jià)格一樣多，他也對(duì)其他房間沒興趣。這雖然是一個(gè)“無嫉妒”的解決方案，但它顯然是不公平的，公平的方案應(yīng)該是給大家分配到他們想要的房間，并且讓每個(gè)人支付相應(yīng)的租金。

在“我分，你選擇”模式中，也存在這樣的弊端。再來回顧下蛋糕的例子。想象一下，如果蛋糕是一塊水果蛋糕，比方說蛋糕的中間有幾個(gè)草莓，兩個(gè)小孩有不同的食物偏好，有一個(gè)非常喜歡吃草莓，另外一個(gè)并不喜歡。如果草莓迷主持切糕，他可能會(huì)將蛋糕平均分割，在任何一邊，都會(huì)留下相同數(shù)量的草莓，這會(huì)保證在另外一個(gè)小孩選擇任何一塊蛋糕時(shí)，他的那一塊都有一定數(shù)量的草莓。

這次分配結(jié)果再次達(dá)到了“無嫉妒”模式。這樣的結(jié)果是有效的，雙方都沒有任何理由要交換自己的那一塊，從理論上講，這兩個(gè)人也沒有什么好嫉妒的，但不喜歡草莓的小孩對(duì)結(jié)果很不滿意。草莓愛好者其實(shí)可以給那個(gè)不想要草莓的人分一塊沒有草莓的、更大的蛋糕，而自己得到所有的草莓，這時(shí)大家可以雙贏。

然而，上述解決方案可能在數(shù)學(xué)意義上達(dá)到了“無嫉妒”模式，但它并不符合我們的基本公平感。草莓愛好者為了幾顆草莓，只能吃到一小塊，而蛋糕愛好者拿到了一大塊，這公平嗎？

一個(gè)更公平的算法

來自卡內(nèi)基梅隆大學(xué)的研究者們想解決這種問題，讓分配的結(jié)果不僅符合“無嫉妒模式”，還要讓每個(gè)人都能感覺到公平，他們發(fā)明了Spliddit算法。首先，這個(gè)算法會(huì)最大化每個(gè)室友愿意為那個(gè)房間支付的房租，以及他最終支付的錢的差異。這種方法可以衡量每一個(gè)交易者獲利多少，保證每個(gè)室友的獲利比他在其他房間里的獲利高。這滿足了“無嫉妒”的條件，沒有人愿意交換房間。隨后，研究者還試圖找到一個(gè)“直覺公平”的解決方案，計(jì)算器會(huì)最小化每個(gè)室友實(shí)際獲利的差異，然后根據(jù)計(jì)算的價(jià)格分配房間。

簡(jiǎn)單地說，算法將保證每個(gè)人都得到一個(gè)很好的交易，但沒有一個(gè)人比起其他室友得到更好的交易。Spliddit算法自發(fā)布以來，已經(jīng)應(yīng)用于租車費(fèi)用計(jì)算、工作信用分配、任務(wù)分配等等。

然而，雖然數(shù)學(xué)家們的公平算法已經(jīng)越來越進(jìn)步，但具體地運(yùn)用到現(xiàn)實(shí)社會(huì)時(shí)，情形又會(huì)變得復(fù)雜許多。例如，一個(gè)兄弟分割父母財(cái)產(chǎn)時(shí)，也許算法可以為他們找到一個(gè)很平等的分割方案，但其中一個(gè)子女在父母患病期間付出最多，是不是應(yīng)該分得更多呢？這類問題，Spliddit算法也沒法解決。

看來，關(guān)于如何“切糕”讓每個(gè)人覺得公平，這一個(gè)復(fù)雜的問題還會(huì)像幽靈一樣，與學(xué)者們糾纏不清。