假設你組織了一次相親會，男女人數相同。參會者在相親會上互相認識后，每個人心目中都對全體異性相親對象有了一個偏好順序。每個男性對每個女性都有了一個喜好的排序，所有女性也對男性有了這樣一個排名。

作為組織者，搜集到所有人的排名信息后，你會如何考慮將男女配對，讓他們后續發展？有沒有一種最佳的配對方法？

當然，這里必須對“最佳”定個標準。在本問題中，“最佳”的首要標準是產生“穩定婚姻。“穩定婚姻”是這樣定義的：

首先我們要定義的是“不穩定婚姻”。“不穩定婚姻”的定義是：如果有這樣兩對夫婦，其中一對的丈夫認為另一對夫婦中的妻子比自己的妻子好；同時另一對夫婦中的妻子認為當前的老公也不如另一個老公好。這里的“好”和“壞”就是按之前個人的喜好排名決定。如果存在這種情況，那就意味著有兩對婚姻里有一男一女，同時存在離開現任配偶，與對方重組婚姻的意愿，那么這兩對婚姻就是“不穩定婚姻”。

穩定婚姻和不穩定婚姻的例子，假設以下3男3女，有如下偏好關系，左邊的為最喜歡：

男1：女1，女2，女3；

男2：女1，女3，女2；

男3：女2，女3，女1；

女1：男3，男1，男2；

女2：男1，男2，男3；

女3：男3，男2，男1；

則： 男1女1；男2女3；男3女2；是一組穩定婚姻。

男1女2；男2女1；男3女3；是一組不穩定婚姻。因為男1覺得男2的妻子女1，比現任妻子女2好；女1覺得女2的丈夫男1，比現任丈夫男2好。

“穩定婚姻”的定義就是一組婚姻中，不存在不穩定婚姻。那么對任何一組偏好列表，是否總可以進行合理的匹配，使得最終配對的結構都是“穩定婚姻”？這就是“穩定婚姻問題”（Stable Marriage Problem）。

答案：確實有這樣的一個算法，可以確定地找到一種穩定婚姻方案。算法也挺有意思，其實跟生活中的行為是很有相似度的。這個算法有兩個鏡像版本：“男性主動”或是“女性主動”的版本。就以“男性主動”版本為例：

男性循環向女性求婚（其實男性求婚順序無關緊要，最終結果是一樣的）。任何時刻，沒有婚約的男性都向自己偏好列表中的排名最高的（且從未求婚過的女性）求婚。而女性第一次接到求婚請求時，暫時接受婚約。第二次接受求婚時，她顯然會比較一下這個男性與現有現訂婚的男性的排名，如果更高則接受，并且放棄之前的婚約；否則直接拒絕當前的求婚。

每次求婚之后，總有部分男性被拒了，則繼續按照自己的偏好列表繼續求婚，但只向自己未求婚過的女性求婚了。而所有女性策略還是相同，如果新的求婚排名高則接受，并且拒掉之前婚約，否則直接拒絕。

每次求婚之后，總有一些原先有婚約的男性不幸被拒，重新加入相親軍團。

那么如此循環，直到所有人都結婚，則算法結束，問題解決。

仍按之前三男三女為例，執行以上求婚算法，偏好列表是：

男1：女1，女2，女3；

男2：女1，女3，女2；

男3：女2，女3，女1；

女1：男3，男1，男2；

女2：男1，男2，男3；

女3：男3，男2，男1；

則一種可能的求婚過程是：

男1向女1求婚，女1接受；

男2向女1求婚，因女1對男1比男2更偏好，則女1拒絕；

男3向女2求婚，女2接受；

男2向女3求婚，女3接受。

此時，所有人都有婚約；結果如下：

男1女1；男2女3，男3女2。可以驗證，結果為穩定婚姻。

可以看出，此結果中，男性較為滿意，但女性不太滿意，特別是女2。

對此算法，你肯定會有若干疑問：

第一個問題是，怎么證明算法可以在有限時間內結束？

因為每名男性只可能向特定的女性求婚一次。所以，總的求婚次數最多是n2，n就是男性或女性人數。這個數字是有限的，所以算法必然在有限時間內結束。

第二個問題是，怎么確定算法結束時，每個人都結婚了？

可以用反證法，如果有這種情況，那么存在一個女人，她從來未被求過婚，并且有從未向這個女人求過婚的男人。但這是不可能的，因為如果只剩下這個男人和這個女人沒有結婚，那么根據算法，不管這個女人在這個男人的喜好列表里的排名有多低，他還是得向這個女人求婚。所以，算法結束時，所有人都結婚了。

最后一個問題：怎么證明所有婚姻是穩定的？還是用反證法，如果存在這樣兩對不穩定夫妻，且不穩定因素是Bob和Alice。那么因為Alice在Bob心目中的排名比其現任妻子高，則Bob必然在現任妻子之前向Alice求婚過。而Alice心目中，Bob的排名比現任丈夫高，則不管其現任丈夫在Bob之前或之后求婚，留下的必然是Bob。所以不可能出現不穩定婚姻。

這個算法是1960年代，由科學家戴維·蓋爾（Gale）和勞艾徳·沙普利（Shapley）提出來的，現在該算法用他們的姓氏首字母命名，稱為“GS算法”。有意思的是“GS算法”在被正式提出之前，就已經在一些場合下被使用了。但不是用在相親，而是用在一些地方的醫學院接受實習醫生的配對選擇流程。

(上圖：一定人數下，可能產生的穩定婚姻組合數量。橫軸為男性或女性人數，縱軸為穩定婚姻組合數。虛線為計算機采樣結果，實線為Pittle的理論公式預測。一般認為，穩定婚姻組合數的增長與N*lnN同級。圖片來源：Michael Dzierzawa, Marie-José Oméro, Statistics of stable marriages, Physica A 287 (1–2) (2000) 321–333.)

GS算法流程是清楚了，但你肯定還有不少的疑問和思考，那以下我就講講這個問題的若干變種和對它們的一些分析。

第一個變種是，雖然GS算法給出的結果都是穩定的婚姻，但是同樣是穩定，穩定的程度是不同的。可以想到有這樣一種現成的對婚姻穩定度的度量：每一對夫婦，其配偶在自己的喜好列表上的名次。名次越高，名次的數值越小，表示對配偶越滿意，婚姻也越穩定。

這一度量取值范圍是1到n，n為男性或女性人數。對這個度量，我稱其為“穩定成本”，因為它表達了婚姻的穩定度，并且越低，越穩定，所以是“成本”。

有了“穩定成本”這樣一種度量，我們一下子可以考慮很多有意思的問題。比如對之前男方主動求婚的GS算法，其給出配對結果，男方與女方的穩定成本比較，哪一方的穩定成本比較低，哪一方對婚姻更滿意呢？答案有點出人意料：男方滿意度較高，女方較低。

實際上可以證明，在男方主動求婚的情況下，最后配對的結果，在所有可能的穩定配對結果中，男性總是可以與可能的最高順位的女性配對，而女性則是所有可能結果中，與順位最低的男性結婚。

（上圖：男性主動情況下的GS算法中，男女穩定成本的圖例。橫軸為人數，帶○線為男性穩定成本，帶黑點的實線為女性穩定成本。可以看出，在男性主動情況下，男性比女性對配偶更滿意。圖片來源同前。）

那么當然，如果算法改成女性主動求婚的話，那么結果總是女性的滿意度最高，而男性的滿意度最低。總之，可以學到的一點是，在找配偶的問題上，主動出擊有時是很重要的。

仍按之前三男三女為例，以女性主動方式，執行以上求婚算法，偏好列表是：

男1：女1，女2，女3；

男2：女1，女3，女2；

男3：女2，女3，女1；

女1：男3，男1，男2；

女2：男1，男2，男3；

女3：男3，男2，男1；

則一種可能的求婚過程是：

女1向男3求婚，男3接受；

女2向男1求婚，男1接受；

女3向男3求婚，男3接受，女1被毀約；

女1向男1求婚，男1接受，女2被毀約；

女2向男2求婚，男2接受。

配對結果為：

女1男1，女2男2，女3男3。這種女性主動下的配對結果，女性會比較滿意。

那么，會出現另一個問題，如果要求男女滿意度差不多，該怎么辦？這個想法又會引出很多問題。

先考慮這樣一個問題：如果我們要求配對的結果是總體上穩定成本最小，即所有人的穩定成本之和最小，這種條件下，是否總是產生穩定婚姻？

很可惜，答案是否定的。也就是總體上最穩定的婚姻組合，局部很可能產生不穩定婚姻。比如之前的例子，全局最小穩定成本配對結果是：

男1女2，男2女1，男3女3。男性總穩定成本為：2+1+2=5，女性總穩定成本為：3+1+1=5，總成本為10。可以驗證，這是一種達到最小總成本的配對方案，然而這個方案是不穩定的，不穩定因素來自男1和女1。這也是社會學領域經常遇到的情況，即因為個體的“自私”，導致社會總成本上升，這種情況非常常見。

另一個問題是，怎么尋找這種總體上的最優解？算法復雜度如何？之前的GS算法是比較好的算法那，它的復雜度是n2，n是男人或女人的人數。而尋找總體最優解，如果用蠻力搜索，枚舉所有組合，那么需要n!次搜索，顯然不太優越。你也可以想象，如果是需要找到精確最優解的話，那它是一個指數復雜度的問題和一個NP問題。甚至還是一個“NP-困難”的問題，因為給出一個組合，驗證這個組合是否是全局最優，都沒有一個多項式算法。

但這個情況下，有個有意思的計算，就是全局最優情況下，每個人匹配到配偶的排名期望值是多少？數學家給算出來了，這個值是1.617√N（黃金分割比？），N是男性或女性人數。也即是說，如果是100個男性和女性，如果按全局最配對，那么平均每個人能匹配到的配偶的排名是1.617√100，約等于16名。 這個結果還不錯，就是每個人的配偶是自己心目中，在100個人里排名第16名左右。但這是不考慮婚姻是否穩定的，其中有可能存在不穩定婚姻的情況。

那么下一個問題是，要求穩定婚姻的情況下，最低總穩定成本的情況如何？這里有一個意外的情況是，這種條件下，有了多項式時間的匹配算法。而之前，在不要求穩定婚姻情況下，反而沒有多項式時間的算法。增加了約束條件后，卻有了更快的算法。這是非常有意思的，問題的要求更多，計算反而更快了。原因是可以猜到的：因為在要求穩定婚姻的情況下，有很多組合不用考慮了，反而能加速了。

這個具體算法略復雜，，現在的算法復雜度是N3，比GS算法的N2要復雜點，但仍然是多項式時間的算法。那么這時候平均每個人的穩定成本或配偶排名是多少呢？數學家也算出來了，答案是2√(N)，也就是100對夫妻的話，平均每個人的配偶排名大概是第20名。比之前的16名要差一些，但總體上還是挺靠前的。

所以，如果你要搞相親會的話，也許這種穩定婚姻情況下的全局最優算法，是一種比較好的匹配算法。

但目前為止，我們還沒有討論過男女平等的問題。那么我們來看看怎么能做到男女平等，但我們需要先定義一個男女平等的標準。高德納（Donald Knuth）和波利亞（George Polya）等人曾提出過這么三種標準：

第一種：平等主義下的最低穩定成本（minimization of egalitarian cost）。它的意思是把全體男性看各自妻子的名次累加得到一個數值，然后把全體女性看各自丈夫的名次累加得到一個數值，兩個數值

得到一個總成本值，并尋找其最小值。其實這個標準與之前的全局最低是一摸一樣的，之所以叫它“平等主義”就是不區分性別了，男女混在一起算，這可能也算一種男女平等，是現在比較流行的一種平等概念。

第二種：最小后悔成本（minimization of regret cost)。這種情況下，規定這樣一種“后悔成本”：一對夫妻中，夫婦看對方的名次中，比較大的那個數值，就稱為這對夫妻的“后悔成本”。比如說，丈夫看妻子是排名第1，妻子看丈夫則是排名第10， 則這對夫妻的后悔成本是10。現在我們要尋找這樣一種使得全體夫妻的后悔成本總和最小的配對，這種配對方案被稱為“最小后悔成本”。對這種問題，現在已經找到一種算法，復雜度與GS算法是一樣的N2，說明這個問題現在已經很好得被解決。

第三種男女平等標準：“性別平等下的最小成本”（minimization of sex-equalness cost），它應該是大家心目中最常見的男女平等，即全體男性的穩定成本之和，與全體女性的穩定成本之和，兩者比較差值的絕對值，希望越小越好。不像第一種，第一種是比較男女成本的和值，這個是比較差值，這大概是大家心目中典型的男女平等。這種條件下的穩定婚姻問題，也被稱為“平衡穩定婚姻問題”（Equitable Stable Marriage Problem）。對這類問題，又有一個意外情況就是，它沒有多項式算法了。如同尋找全局最優問題一樣，它又變成一個NP-困難問題，雖然這種男女平等是大家很希望的一個結果。

（上圖：穩定婚姻情況下，男女穩定成本對比，橫軸為女性，縱軸為男性。圖片是在200人的情況下，產生若干隨機偏好列表列表，尋找其中所有穩定婚姻組合，分別計算男性和女性穩定成本。圖片來源：Physics Reports 917 (2021) 1–79）

以上就是科學家提出過的三種“男女平等思想下”的度量。但我自己又考慮了下，其實還可以有其他的男女平等度量。比如基于“方差”的度量，因為人喜歡與其他人比較穩定成本，雖然這種心理不太好。

但是這樣，就可以另外定義三種類似的度量：

“平等主義下的最小穩定方差：就是看所有人的穩定成本的方差，越小越好。

“性別平等下的最小成本方差”，顧名思義，就是那女分開來看，分別計算全體男性的穩定成本方差和全體女性的穩定成本方差，越小越好。

第三種，可能是“三觀”最不正的，可以叫“最小夫妻嫌棄指數”：就是夫妻間，互相看對方的穩定成本，也就是排名的差值，希望越小越好。比如夫妻互看，都是第一名，那當然是最好；如果丈夫嫌棄妻子，妻子看丈夫也是哪都不行，雖然可能家庭不太和諧，但也算平等了吧。但如果一方看另一方排名很高，而另一方反過來排名很低，落差很大，那么男女就不太平等了。GS算法產生的結果往往就是這種情況，有時我們需要避免那種情況。那么就可以定義夫妻間“嫌棄指數”：雙方看彼此的排名的差值的絕對值。那我們如果尋找所有夫妻的“嫌棄指數”的最小值，那么也是一種可以研究的問題。

以上三種度量可能是因為“三觀不正”，目前我沒有看到有人研究過算法，有興趣的聽眾可以自己研究下。

那好了，以上對穩定婚姻問題的基本形態和目前的一些結果介紹完了，講講它的若干種擴展。擴展有兩大類，一種是擴展配對的數量。

比如有這樣一種家庭組合問題：有若干男女和待收養的小孩，所有男女和小孩都對其他集合的對象有一個偏好列表，問如何將一男一女和一個小孩組合在一起，成立家庭最為合理。問題內容挺奇葩的，但確實是一個很好的算法問題。

還有一種擴展，就更常見了，就是配對對象本身不分類型，希望被劃分到若干組。比如一群人去吃飯，人數很多，需要分桌。每個人都有一些希望一起吃飯和希望不一起吃飯的人，那么怎樣分桌可以使大家最滿意，這就是一個“分桌問題”（Seating Problem）。有時它也被稱為“穩定室友問題”(Stable Roommate Problem）。

(上圖：室友關系好壞對學生是一個很重要的問題)

聽上去“穩定婚姻”問題都是處理一些不太正經的問題，但其實它有很多非常正經的應用場合。除了之前的分配學生去醫院實習的問題，其實大學錄取過程，就有點像“穩定婚姻問題”。對美國的大學錄取，就更為典型。比如，美國大學的基本錄取流程就是，學生可以向若干大學同時發出申請，如果其中有若干大學同意錄取，那么學生就可以選擇自己最想去的大學。如果全部被拒了，那么學社還有幾會繼續發申請給其他大學。這個流程有點像前面“GS算法”，因為學生主動申請，結果會對學生比較理想，學生總是可以進入其可能進入的最好大學。當然，學校也會意識到這個問題，所以有時大學會主動邀請他們特別想錄取的學生入學。

還有一種應用場合則更加性命攸關了，就是器官捐獻和匹配。如果現在有三個可供移植的相同器官和三個等待移植的病人。把哪個器官分配給誰，如何做到公平合理，移植效果又最大化，這就是需要諸多權衡和考慮的問題。

最后，穩定婚姻問題在物理學中也有它的意義。我們可以把穩定成本想象成一個物體的能量或者能級。一般來說，一個系統中的物體總是傾向于從能級高到能級最低的狀態演變。很多學術論文里，會直接把“穩定婚姻”問題里的“穩定成本”稱為“能量”，那么尋找最小總成本的問題，就相當于尋找這個系統最穩定狀態的問題，這就是“穩定婚姻問題”在物理學中的意義。

參考鏈接：

https://www.sciencedirect.com/science/article/pii/S0370157321000843

https://hal.archives-ouvertes.fr/jpa-00247483/document

DOI: 10.1051/jphyslet:019850046017077100