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

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

當(dāng)然，這里必須對“最佳”定個標(biāo)準(zhǔn)。在本問題中，“最佳”的首要標(biāo)準(zhǔn)是產(chǎn)生“穩(wěn)定婚姻。“穩(wěn)定婚姻”是這樣定義的：

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

穩(wěn)定婚姻和不穩(wěn)定婚姻的例子，假設(shè)以下3男3女，有如下偏好關(guān)系，左邊的為最喜歡：

男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；是一組穩(wěn)定婚姻。

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

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

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

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

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

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

那么如此循環(huán)，直到所有人都結(jié)婚，則算法結(jié)束，問題解決。

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

男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接受。

此時，所有人都有婚約；結(jié)果如下：

男1女1；男2女3，男3女2。可以驗證，結(jié)果為穩(wěn)定婚姻。

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

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

第一個問題是，怎么證明算法可以在有限時間內(nèi)結(jié)束？

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

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

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

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

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

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

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

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

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

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

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

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

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

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

男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接受。

配對結(jié)果為：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

第三種，可能是“三觀”最不正的，可以叫“最小夫妻嫌棄指數(shù)”：就是夫妻間，互相看對方的穩(wěn)定成本，也就是排名的差值，希望越小越好。比如夫妻互看，都是第一名，那當(dāng)然是最好；如果丈夫嫌棄妻子，妻子看丈夫也是哪都不行，雖然可能家庭不太和諧，但也算平等了吧。但如果一方看另一方排名很高，而另一方反過來排名很低，落差很大，那么男女就不太平等了。GS算法產(chǎn)生的結(jié)果往往就是這種情況，有時我們需要避免那種情況。那么就可以定義夫妻間“嫌棄指數(shù)”：雙方看彼此的排名的差值的絕對值。那我們?nèi)绻麑ふ宜蟹蚱薜摹跋訔壷笖?shù)”的最小值，那么也是一種可以研究的問題。

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

那好了，以上對穩(wěn)定婚姻問題的基本形態(tài)和目前的一些結(jié)果介紹完了，講講它的若干種擴(kuò)展。擴(kuò)展有兩大類，一種是擴(kuò)展配對的數(shù)量。

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

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

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

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

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

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

參考鏈接：

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

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

DOI: 10.1051/jphyslet:019850046017077100