0%
不要我的我不要之數學演算法

不要我的我不要之數學演算法

作者:小庄
沒得選擇的案例不勝枚舉。來自西方的著名代表有維特,他與綠蒂女士那番驚天地泣鬼神的「恨不相逢未嫁時」最後以一枚子彈悲壯地了結;東方的代表更是真實存在的人物,金岳霖遇見的林徽因當時已經是梁夫人,雖說他立刻撇下了美國女友苦苦追求,奈何林徽因沒有腦子進水去迎合,於是偷雞不成蝕把米,最後鬱鬱而終。
在以上原則下,維特金岳霖們即便被拒也得心甘情願地接受,因為綠蒂林徽因絕對不是因為禮教之類狗屁原因不要你,她不要你,僅僅是因為她選擇了自己更喜歡的,而唐璜們也要牢牢記住自己到底最愛哪一個,第二愛哪一個,不是姐姐妹妹們都一樣心肝寶貝的。
人生若能活出此等意境,該是多麼清爽通透。
讓我們回過頭去看看1962年沙普利教授和合作者蓋爾(David Gale)發表在九九藏書《美國數學月刊》(American Mathematical Monthly)上的著名論文《大學錄取和婚姻穩定》(College Admissions and the Stability of Marriage)是如何描述的吧。
這個上世紀五六十年代即被發現的機制叫做Gale-Shapley演算法,雖說受各種客觀條件所限,還沒真正用到男女搭配中去(除了少部分娛樂相親節目),但在一些西方地區的公立學校招生錄取中卻已然發揮了極大威力,沙普利他們能獲獎便因這一點。不知道隨著未來世界信息透明度增高,是不是能切實有效地大放異彩,改變人類已混亂得一塌糊塗的婚姻市場。
少女也好,夫人也好,更別提寡婦,
已不能象昔日似地令我痴迷—九九藏書
總之,我過去的生命已不能重複。
從母系氏族向父系氏族轉換的過程當中,人類逐漸形成了一種獨特的現象,那就是出現了婚姻市場。無論從什麼角度來說,它都堪稱一個弔詭的市場——在這裏做買賣的所謂智人們,浮沉無度,雨打飄零,無非逃不脫兩大煩惱:沒得選擇的煩惱和無從選擇的煩惱。
無從選擇的案例則是唐璜、卡薩瓦諾和阿爾菲之流。雖說世間流傳的故事多麼旖旎香艷,我卻是在少年時代就從拜倫的長詩《唐璜》里讀出過苦楚。公主王妃孤女強盜女……一雙雙香掌中輪轉徘徊,這名浪子活得也很辛苦好不好!末了只落得吟出一段厭世的感慨:
接下來進入第二輪求婚,那些沒有被接受的男人集體向次喜歡的女人求婚,先不用擔心她有沒有未婚夫了,因為即便她第一輪已經答應了一個男人,但九九藏書只要第二輪求婚的人當中有她更喜歡的,就可以更換。
2012年10月,新一屆諾貝爾獎開盤,15日揭曉的經濟學獎授予了美國人勞埃德·沙普利(Lloyd Shapley)和埃爾文·羅斯(Alvin Roth),獲獎理由是他們將數學中的「匹配機制」引入到了現實問題的解決當中。這項工作最早可以追溯到上世紀50年代至60年代,沙普利教授對市場如何進行最優化的組織做出了理論角度的研究,而羅斯教授則在近些年將前者得到的方法加以應用,拿來對付兩性婚配、醫學生擇校和腎臟移植配對等現實中非常突出的需求矛盾。
如此循環往複,男人們按照喜歡程度的遞減依次求婚,女人們始終選擇那一輪求婚者中自己最喜歡的一個。沒有人求的壁花也不要絕望,因為男女人數相等,怎麼著還是會輪到九_九_藏_書的。則若干輪下來,最後達到的匹配一定是這樣的:男人在沒有拒絕過自己的女人中找到了最喜歡的,女人在選擇了自己的男人中找到了最喜歡的。皆大歡喜。
如何做到?其實並不難。
論文把婚姻市場簡化為n對n的相親局,也就是在n個適齡男性和n個適齡女性之間做搭配。對於這麼個局來說,其最優的配對結果是要讓每對牽手的男女都選到了對自己來說是可選對象中最好的那一個。這句話如何解釋呢,換而言之,就是除婚配對象之外的其他異性要麼就是「我愛ta但ta不(夠)愛我」,要麼就是「ta愛我但我不(夠)愛ta」。那麼可想而知,倘若這個局裡的人都有一定道德和理性,就不會出現出軌偷腥現象了。雖說聽上去有點too simple了,但邏輯上沒問題……
數學家們提出方案如下:讓男人們在心目中為這九*九*藏*書些女人打分,從最喜歡、次喜歡、次次喜歡一直到最不喜歡。然後他們集體去做第一輪求婚,顯然,都是直奔最喜歡的女人。收到求婚的女人可以選擇求婚對象中自己最喜歡的男人,答應下來,暫時成為伴侶。注意,只是暫時。
以上,在文學家的筆下被詮釋為迷人的錯亂和未解之謎,然而換到數學家看來,可一併歸入沒有選擇正確演算法所引發的系統崩潰。對於婚姻市場來說,穩定的秩序很重要,一切有可能導致失穩出現的因素都需要想辦法避免和調解,不管維特還是唐璜,倘若有機會讓懂數學的人給上上課,結果一定會好許多。「穩定婚姻問題」(Stable Marriage Problem 或Stable Matching Problem,簡稱SMP)一直是博弈論高手們琢磨的重大課題。
我談情的日子完了。無論多迷人: