>>>  技術話題—商業文明的嶄新時代  >>>

簡體     傳統

　　什么是算法？每當有人問作者這樣的問題時，他總會引用這個例子：假如你是一個媒人，有若干個單身男子登門求助，還有同樣多的單身女子也前來征婚。如果你已經知道這些女孩兒在每個男孩兒心目中的排名，以及男孩兒們在每個女孩兒心中的排名，你應該怎樣為他們牽線配對呢？

　　最好的配對方案當然是，每個人的另一半正好都是自己的“第一選擇”。這雖然很完美，但絕大多數情況下都不可能實現。比方說，男 1 號最喜歡的是女 1 號，而女 1 號的最愛不是男 1 號，這兩個人的最佳選擇就不可能被同時滿足。如果好幾個男孩兒最喜歡的都是同一個女孩兒，這幾個男孩兒的首選也不會同時得到滿足。當這種最為理想的配對方案無法實現時，怎樣的配對方案才能令人滿意呢？

　　其實，找的對象太完美不見得是好事兒，和諧才是婚姻的關鍵。如果男 1 號和女 1 號各有各的對象，但男 1 號覺得，比起自己現在的，女 1 號更好一些；女 1 號也發現，在自己心目中，男 1 號的排名比現男友更靠前。這樣一來，這兩人就可能拋棄各自現在的對象——如果出現了這種情況，我們就說婚姻搭配是不穩定的。作為一個紅娘，你深知，對象介紹得不好沒關系，就怕婚姻關系不穩定。給客戶牽線配對時，雖然不能讓每個人都得到最滿意的，但搭配必須得穩定。換句話說，對于每一個人，在他心目中比他當前伴侶更好的異性，都不會認為他也是一個更好的選擇。現在，我們的問題是：穩定的婚姻搭配總是存在嗎？應該怎樣尋找？

　　一次失敗的嘗試

　　為了便于分析，我們下面做一些約定。我們用字母A、B、C對男性進行編號，用數字1、2、3對女性進行編號。我們把所有男性從上到下列在左側，括號里的數字表示每個人心目中對所有女性的排名；再把所有女性列在右側，用括號里的字母表示她們對男性的偏好。圖 1 所示的就是 2 男 2 女的一種情形，每個男的都更喜歡女 1 號，但女 1 號更喜歡男B，女 2 號更喜歡男A。若按A-1、B-2進行搭配，則男B和女 1 都更喜歡對方一些，這樣的婚姻搭配就是不穩定的。但若換一種搭配方案（如圖2），這樣的搭配就是穩定的了。

圖 1 一個不穩定的婚姻搭配圖

　　可能很多人會立即想到一種尋找穩定婚姻搭配的策略：不斷修補當前搭配方案。如果兩個人互相都覺得對方比自己當前的伴侶更好，就讓這兩個人成為一對，剩下被甩的那兩個人組成一對。

圖 2 一個穩定的婚姻搭配

　　如果還有想要私奔的男女對，就繼續按照他們的愿望對換情侶，直到最終消除所有的不穩定組合。容易看出，應用這種“修補策略”所得到的最終結果一定滿足穩定性，但這種策略的問題在于，它不一定存在“最終結果”。事實上，按照上述方法反復調整搭配方案，最終可能會陷入一個死循環，因此該策略甚至不能保證得出一個確定的方案來，如圖 3 所示。

圖 3 應用“修補策略”可能會產生死循環

　　Gale-Shapley 算法

　　1962年，美國數學家 David Gale 和 Lloyd Shapley 發明了一種尋找穩定婚姻的策略。不管男女各有多少人，也不管他們的偏好如何，應用這種策略后總能得到一個穩定的搭配。換句話說，他們證明了穩定的婚姻搭配總是存在的。有趣的是，這種策略反映了現實生活中的很多真實情況。

　　在這種策略中，男孩兒將一輪一輪地去追求他中意的女子，女子可以選擇接受或者拒絕他的追求者。第一輪，每個男孩兒都選擇自己名單上排在首位的女孩兒，并向她表白。此時，一個女孩兒可能面對的情況有三種：沒有人跟她表白，只有一個人跟她表白，有不止一個人跟她表白。在第一種情況下，這個女孩兒什么都不用做，只需要繼續等待；在第二種情況下，接受那個人的表白，答應暫時和他做情侶；在第三種情況下，從所有追求者中選擇自己最中意的那一位，答應和他暫時做情侶，并拒絕所有其他追求者。

　　第一輪結束后，有些男孩兒已經有女朋友了，有些男孩兒仍然是單身。在第二輪追女行動中，每個單身男孩兒都從所有還沒拒絕過他的女孩兒中選出自己最中意的那一個，并向她表白，不管她現在是否是單身。和第一輪一樣，女孩兒們需要從表白者中選擇最中意的一位，拒絕其他追求者。注意，如果這個女孩兒已經有男朋友了，當她遇到了更好的追求者時，她必須拒絕掉現在的男友，投向新的追求者的懷抱。這樣，一些單身男孩兒將會得到女友，那些已經有了女友的人也可能重新變成光棍。在以后的每一輪中，單身男孩兒繼續追求列表中的下一個女孩兒，女孩兒則從包括現男友在內的所有追求者中選擇最好的一個，并對其他人說不。這樣一輪一輪地進行下去，直到某個時候所有人都不再單身，下一輪將不會有任何新的表白發生，整個過程自動結束。此時的婚姻搭配就一定是穩定的了。

　　這個策略會不會像之前的修補法一樣，出現永遠也無法終止的情況呢？不會。下面我們將說明，隨著輪數的增加，總有一個時候所有人都能配對。由于在每一輪中，至少會有一個男孩兒向某個女孩兒告白，因此總的告白次數將隨著輪數的增加而增加。倘若整個流程一直沒有因所有人都配上對了而結束，最終必然會出現某個男孩兒追遍了所有女孩兒的情況。而一個女孩兒只要被人追過一次，以后就不可能再單身了。既然所有女孩兒都被這個男孩兒追過，就說明所有女孩兒現在都不是單身，也就是說此時所有人都已配對。

圖 4 應用上述策略，三輪之后將得出穩定的婚姻搭配

　　接下來，我們還需要證明，這樣得出的配對方案確實是穩定的。首先注意到，隨著輪數的增加，一個男孩兒追求的對象總是越來越糟，而一個女孩兒的男友只可能變得越來越好。假設男A和女 1 各自有各自的對象，但比起現在的對象，男A更喜歡女1。因此，男A之前肯定已經跟女 1 表白過。既然女 1 最后沒有跟男A在一起，說明女 1 拒絕了男A，也就是說她有了比男A更好的男孩兒。這就證明了，兩個人雖然不是一對，但都覺得對方比自己現在的伴侶好，這樣的情況絕不可能發生。

　　我們把用來解決某種問題的一個策略，或者說一個方案，或者說一個處理過程，或者說一系列操作規則，或者更貼切地說，一套計算方法，叫做“算法”。上面這個用來尋找穩定婚姻的策略就叫做“Gale-Shapley 算法”，有些人也管它叫“延遲認可算法”。

　　Gale-Shapley 算法的意義和應用

　　每個算法都有它的實際意義，能給我們帶來很多啟發。Gale-Shapley 算法最大的意義就在于，作為一個為這些男女牽線的媒人，你并不需要親自計算穩定婚姻匹配，甚至根本不需要了解每個人的偏好，只需要按照這個算法組織一個男女配對活動就可以了。你需要做的僅僅是把算法流程當作游戲規則告訴大家，游戲結束后會自動得到一個大家都滿意的婚姻匹配。整個算法可以簡單地描述為：每個人都去做自己想做的事情。對于男性來說，從最喜歡的女孩兒開始追起是順理成章的事；對于女性來說，不斷選擇最好的男孩兒也正好符合她的利益。因此，大家會自動遵守游戲規則，不用担心有人虛報自己的偏好。

　　歷史上，這樣的“配對游戲”還真有過實際應用，并且更有意思的是，這個算法的應用居然比算法本身的提出還早 10 年。早在 1952 年，美國就開始用這種辦法給醫學院的學生安排工作，這被稱之為“全國住院醫師配對項目”。配對的基本流程就是，各醫院從尚未拒絕這一職位的醫學院學生中選出最佳人選并發送聘用通知，當學生收到來自各醫院的聘用通知后，系統會根據他所填寫的意愿表自動將其分配到意愿最高的職位，并拒絕掉其他的職位。如此反復，直到每個學生都分配到了工作。那時人們并不知道這樣的流程可以保證工作分配的穩定性，只是憑直覺認為這是很合理的。直到 10 年之后，Gale 和 Shapley 才系統地研究了這個流程，提出了穩定婚姻問題，并證明了這個算法的正確性。

　　這個算法還有很多有趣的性質。比如說，大家可能會想，這種男追女女拒男的方案對男性更有利還是對女性更有利呢？答案是，這種方案對男性更有利。事實上，穩定婚姻搭配往往不止一種，然而上述算法的結果可以保證，每一位男性得到的伴侶都是所有可能的穩定婚姻搭配方案中最理想的，同時每一位女性得到的伴侶都是所有可能的穩定婚姻搭配方案中最差的。受篇幅限制，我們略去證明的過程。

　　這個算法會有一些潛在的問題。剛才我們已經說了，對于每位女性來說，得到的結果都是所有可能的穩定搭配中最差的一種。此時，倘若有某位女性知道所有其他人的偏好列表，經過精心計算，她有可能發現，故意拒絕掉本不該拒絕的人（暫時保留一個較差的人在身邊），或許有機會等來更好的結果。因而，在實際生活中應用這種算法，不得不考慮一些可能的欺詐與博弈。

　　這個算法還有一些局限。例如，它無法處理 2n 個人不分男女的穩定搭配問題。一個簡單的應用場景便是宿舍分配問題：假設每個宿舍住兩個人，已知 2n 個學生中每一個學生對其余 2n-1個學生的偏好評價，如何尋找一個穩定的宿舍分配？此時，Gale-Shapley 算法就不再有用武之地了。而事實上，宿舍分配問題中很可能根本就不存在穩定的搭配。例如，有A、B、C、D四個人，其中A把B排在第一，B把C排在第一，C把A排在第一，而且他們三人都把D排在最后。容易看出，此時一定不存在穩定的宿舍分配方案。倘若A、D同宿舍，B、C同宿舍，那么C會認為A是更好的室友（因為C把A排在了第一），同時A會認為C是更好的室友（因為他把D排在了最后）。同理，B、D同宿舍或者C、D同宿舍也都是不行的，因而穩定的宿舍分配是不存在的。此時，重新定義宿舍分配的優劣性便是一個更為基本的問題。

　　穩定婚姻問題還有很多其他的變種，有些問題甚至是 NP 完全問題，至今仍然沒有（也不大可能有）一種有效的算法。在圖論、算法和博弈論中，這都是非常有趣的話題。

　　作者顧森，網名 Matrix67，北京大學中文系應用語言學專業學生，數學愛好者。2005年開辦數學博客，至今已積累上千篇文章，已有上萬人訂閱。

顧森 2013-02-22 15:04:49