穩(wěn)定匹配問題中的納什均衡

王 燁，李雨生

（同濟(jì)大學(xué) 數(shù)學(xué)系，上海 200092）

1 穩(wěn)定婚配問題和納什均衡

1.1 婚配問題

婚配問題最早是由Gale等［1］于1962年提出，這個問題和圖論有關(guān)（求完全二部圖的穩(wěn)定完備匹配，這是一個NP問題）.

婚配問題是組合數(shù)學(xué)的一個重要問題，在一些關(guān)于組合數(shù)學(xué)的書籍中都有介紹［2-3］.婚配問題是要為n名男子與n名女子安排融洽的婚配關(guān)系.如果每名男子恰好適合與n名女子中的任意一個婚配，且每名女子恰好適合與n名男子中的任意一個婚配，則必定存在一個完美婚配.現(xiàn)在假設(shè)每個男子都有一個由與他合適婚配女子構(gòu)成的集合，該集合中的元素是按照該男子對與他合適婚配女子的喜愛程度進(jìn)行的有序排列，此排列稱為該男子的喜好列表；同時每個女子也都有一個由與她合適婚配男子構(gòu)成的集合，該集合的元素也是按照該女子對與她合適婚配男子的喜愛程度進(jìn)行的有序排列，此排列稱為該女子的喜好列表.

1.2 穩(wěn)定匹配

假設(shè)二部圖G＝G（n，n），V1＝｛a，b，…｝是男子的集合，V2＝｛A，B，…｝是女子的集合，其中｜V1｜＝｜V2｜＝n.在已知每個人喜好列表的前提下，定義二部圖G的穩(wěn)定匹配是一個獨(dú)立邊集合M，若aB∈E（G）-M，則存在W∈V2，使得aW∈M（a喜歡W勝于喜歡B），或存在m∈V1，使得mB∈M（B喜歡m勝于喜歡a）.

因此，由定義可知，若a沒有和B結(jié)婚，則a與一個喜愛程度勝于B的人結(jié)婚，或B與一個喜愛程度勝于a的人結(jié)婚，否則a最終會和B結(jié)婚.

由上述分析可知，穩(wěn)定匹配的結(jié)果不是唯一的，且不一定是完全匹配.但它是一個極大匹配，即此匹配不能再通過添加邊使其變大.假設(shè)M∪｛aB｝是G中的一個匹配，且aB∈E（G）-M，若a，B都是獨(dú)身主義者，則他們不會與心儀的對象結(jié)婚，在這種情況下，穩(wěn)定匹配M是極大匹配，卻非完全匹配.本文假設(shè)婚配中不存在獨(dú)身主義者，所得的穩(wěn)定匹配是一個完全匹配.

假設(shè)二部圖G＝G（n，n），V1是男子的集合，V2是女子的集合，其中｜V1｜＝｜V2｜＝n，μ是圖G 的一組匹配.匹配μ的中斷對mW（其中m∈V1，W∈V2），是指mW?μ，且m和W 都是喜歡對方勝于喜歡在μ中匹配的對象.因此，二部圖G的匹配M 是穩(wěn)定匹配，當(dāng)且僅當(dāng)M不存在中斷對.

1.3 GS算法及復(fù)雜度分析

Gale等提出了穩(wěn)定婚配問題后，也提出了著名的GS算法［1］（也稱延遲認(rèn)可算法），此算法可尋求到一組穩(wěn)定匹配.

算法1（GS算法）

已知所有人的喜好列表，且不存在獨(dú)身主義者.在第一輪選擇過程中，讓這些男子去向他們最心儀（喜好列表中排序第一）的女子求婚.等所有男子求婚完畢后，所有收到求婚的女子都從自己的求婚者中（根據(jù)個人的喜好列表）選擇自己最喜歡的人并且接受他為未婚夫，沒人求婚的女子只能暫時等一等.以上過程稱為一輪，之后的每一輪都按照類似的方式進(jìn)行.

在第一輪結(jié)束后，還處于單身狀態(tài)的男子中的每個人再次向還沒有對其求婚過的女子中自己最喜歡的人求婚（無論女子是否已經(jīng)有了未婚夫），然后，等所有單身男子求婚完畢后，所有收到求婚的女子都從自己的求婚對象中選擇自己最喜歡的人接受為未婚夫.原來有未婚夫而求婚者中有自己更喜歡對象的女子會換掉自己的未婚夫.等到這一輪完畢之后，再開始如上所述的新一輪的求婚.依此類推，當(dāng)所有女子（男子）都已訂婚時，算法結(jié)束.

為了計(jì)算GS算法的復(fù)雜度，在每一輪，接到求婚的女子有三種可能的情形，第一種是接受求婚者，第二種是拒絕這一輪的求婚者，第三種是解除婚約并接受這一輪的一個求婚者.對于第一種情形，她正好做一次選擇，而對于后兩種情形，她最多做（n-1）次選擇，因此，對每名女子這種算法有O （n）步驟，因此總共有O n（2）步驟.

1.4 納什均衡

Nash在1951年提出了納什均衡的概念［4］.納什均衡是參與博弈的每一個局中人在給定其他局中人策略的條件下選擇上策（即：不管其他局中人采取什么策略，每個局中人都選擇對自己最有利的策略）所構(gòu)成的一種策略組合.

納什均衡理論奠定了現(xiàn)代主流博弈理論和經(jīng)濟(jì)理論的根本基礎(chǔ)，對經(jīng)濟(jì)和其他相關(guān)學(xué)科有著深遠(yuǎn)影響.

2 穩(wěn)定匹配中的納什均衡

本節(jié)研究納什均衡與穩(wěn)定匹配的內(nèi)在聯(lián)系.

命題1 穩(wěn)定匹配是納什均衡.

證明：假設(shè)圖G的穩(wěn)定匹配為M，則M不存在中斷對.由穩(wěn)定匹配的定義可知，若a沒有和B結(jié)婚，則a與一個喜愛程度勝于B的人結(jié)婚，或B與一個喜愛程度勝于a的人結(jié)婚，否則a最終會和B結(jié)婚，即：對于?aB∈M，a，B不能同時存在更優(yōu)的匹配對象.而納什均衡是指參與博弈的每一個局中人在給定其他局中人策略的條件下選擇對自己最有利的策略所構(gòu)成的一種策略組合，即：在給定別人策略的情況下，沒有人有足夠理由打破這種均衡.在穩(wěn)定匹配M中，情況也是如此，任何一組匹配對中的點(diǎn)都不存在更優(yōu)的匹配對象，因而沒有足夠的理由打破這種匹配，這正是納什均衡的思想.

此外，如果對方的策略是確定已知的，那么自己的策略是最優(yōu)的，而如果對方的策略是不確定未知的，那么自己的策略就很難是最優(yōu)的.這與穩(wěn)定匹配的思想一致，在GS算法中可以更為直觀地理解這個問題，如果同一部集里其他人的選擇是確定的（已知其他人的喜好列表），那么自己會有一個最優(yōu)的選擇，但如果其他人的選擇是不確定的（其他人的喜好列表未知），那么自己的喜好列表順序?qū)ψ约旱倪x擇結(jié)果有著很大的影響，因而自己的選擇很難達(dá)到最優(yōu).

3 GS算法編程

3.1 GS算法流程圖

在Gale等提出GS算法后，一些人對GS算法進(jìn)行了研究和改進(jìn)［5-6］，其中Gusfield等針對穩(wěn)定婚配問題的結(jié)構(gòu)和算法進(jìn)行了較為詳細(xì)的研究［7］.而目前GS算法編程普遍采用的C語言，以輸入?yún)⑴c婚配者的喜好列表方式進(jìn)行編程運(yùn)算.本文引入置換矩陣的表示方式，采用Matlab進(jìn)行編程，表示形式更為直觀.

對GS算法做一些改進(jìn).在GS算法中，Gale等規(guī)定每一輪中，還處于單身狀態(tài)的男子中的每個人向還沒有對其求婚過的女子中自己最喜歡的人求婚，等所有單身男子求婚完畢后，所有收到求婚的女子都從自己的求婚對象中選擇自己最喜歡的人接受為未婚夫.現(xiàn)在，規(guī)定在每一輪中，還處于單身狀態(tài)的男子中的每個人向還沒有對其求婚過的女子中自己最喜歡的人求婚，不必等到所有男子求婚完畢后，女子就可以依次對男子向自己的求婚做出決定（接受或者拒絕），具體的GS算法流程見圖1.這種每輪女子依次對男子的求婚做出決定的算法所得到的結(jié)果仍是一組穩(wěn)定匹配.

圖1 GS算法流程圖Fig.1 The flow chart of GS algorithm

3.2 GS的矩陣算法

假設(shè)二部圖G＝G（n，n），V1＝｛a，b，…｝是男子的集合，V2＝｛a′，b′，…｝是女子的集合，且｜V1｜＝｜V2｜＝n.將男子a，b，…分別標(biāo)號記為男子1，2，…，n；將女子分別標(biāo)號記為女子1，2，…，n.設(shè)矩陣An×n中元素aij表示男子i的喜好列表中女子j的排列名次.矩陣Bn×n中元素bij表示女子i的喜好列表中男子j的排列名次，其中1≤i≤n，1≤j≤n.根據(jù)圖1的GS算法流程圖，做出了GS迭代算法，其中輸出矩陣Cn×n是（0，1）矩陣，它表示一組穩(wěn)定匹配，其中cij＝1表示男子i與女子j配對，cij＝0表示男子i與女子j沒有配對.由于在穩(wěn)定婚配中每名男子與一名女子結(jié)婚，同樣每名女子與一名男子結(jié)婚，因而矩陣C不僅是（0，1）矩陣，而且還是每行每列恰有一個1的（0，1）矩陣，即矩陣C是置換矩陣.矩陣D1×n中元素di＝ni＋1，其中ni表示男子i已求婚的次數(shù).

下面給出GS的矩陣算法：

參數(shù)：初始矩陣C＝0n×n（零陣），D＝I1×n（全1向量），矩陣An×n和Bn×n.

目標(biāo)：輸出矩陣Cn×n.

步驟1 輸入初始矩陣C＝0n×n，D＝I1×n，以及矩陣An×n和Bn×n.

步驟2 若Cn×n的行列式為零，則尋找Cn×n矩陣的第i行為零，指派男子i向喜好列表中第di個女子求婚，該女子為j，即aij＝di.指定Cn×n矩陣中cij＝1.與此同時，di＝di＋1.若Cn×n的行列式不為零，轉(zhuǎn)至步驟5.

步驟3 若Cn×n中存在第k列的計(jì)數(shù)（即第k列上所有元素之和）大于1，則搜索第k列中不為零的元素所處的行為k1，k2，…，取Bn×n中bk，k1，bk，k2，…的最小值的元素bk，ki.令cki，k＝1，Cn×n第k 列的其他元素為零.若Cn×n中每列的計(jì)數(shù)小于等于1，轉(zhuǎn)至步驟4.

步驟4 若Cn×n的行列式為零，轉(zhuǎn)至步驟2；若Cn×n的行列式不為零，轉(zhuǎn)至步驟5.

步驟5 輸出置換矩陣Cn×n.

4 算例

下面來具體解決一個婚配問題.考慮男子a，b，c和女子a′，b′，c′進(jìn)行婚配，表1和表2分別是男子和女子的喜好列表，試圖求解一組穩(wěn)定婚姻匹配.

表1 男子的喜好列表Tab.1 The preference list of men

表2 女子的喜好列表Tab.2 The preference list of women

根據(jù)表1和表2以及上述A，B矩陣的定義，可知

與傳統(tǒng)的GS算法迭代運(yùn)算相比較，此編程算法簡潔明了，調(diào)用方便快捷.用矩陣的方法定義喜好列表，進(jìn)而輸出置換矩陣來表示穩(wěn)定匹配，使繁瑣的喜好列表順序簡單化，而且輸入A，B矩陣之后即可調(diào)用函數(shù)，方法簡單.但與傳統(tǒng)的C語言程序相比，因?yàn)檠h(huán)次數(shù)較多，Matlab程序運(yùn)行時間會較長.此外，Matlab程序的運(yùn)行結(jié)果只是其中一組的穩(wěn)定匹配，并不是所有的穩(wěn)定匹配輸出結(jié)果，因而此編程還可以繼續(xù)擴(kuò)展.

5 圖論中的納什均衡思想

在圖論中，除了穩(wěn)定匹配問題外，很多問題也都蘊(yùn)含著納什均衡思想，這些思想對圖論問題的理解和求解都有著很大的幫助.

（1）著色問題.最優(yōu)著色問題是尋求一個k色圖的真k著色.一旦此k著色確定，改變其中一條邊的著色，此圖的色數(shù)不會減少，因而沒有達(dá)到優(yōu)化的效果，即改變?nèi)我庖贿叺念伾疾粫蛊鋬?yōu)化，此圖的著色也就趨向于均衡.

（2）最短路徑問題.最短路徑問題是圖論研究中的一個經(jīng)典算法問題，旨在尋找圖（由節(jié)點(diǎn)和路徑組成）中兩節(jié)點(diǎn)之間的最短路徑.每一條邊都有兩種選擇，走此條邊和不走此條邊.最短路徑一旦確定，其中任意一條邊改變自己的選擇，都不能使自己收益，路徑也不會優(yōu)化，因而最短路徑的選擇也趨向于均衡.

納什均衡存在于生活中的每一個細(xì)微之處，在圖論的很多方面都可以運(yùn)用納什均衡理論加以解釋，對于解決圖論問題也有著非常大的益處.

［1］Gale D，Shapley L S.College admissions and the stability of marriage［J］.The American Mathematical Monthly，1962，69（1）：9.

［2］Bollobas B.Modern graph theory［M］.New York：Springer，2003.

［3］Brualdi R A.Introductory combinatorics［M］.Upper Saddle River：Prentice Hall，2004.

［4］Nash J.Non-cooperative games［J］.Annals of Mathematics，1951，54：286.

［5］Dubins L E，F(xiàn)reedman D A.Machiavelli and the Gale-Shapley algorithm［J］.The American Mathematical Monthly，1981，88（7）：485.

［6］Huang C C.Cheating by men in the Gale-Shapley stable matching algorithm［J］.Lecture Notes in Computer Science，2006，4168：418.

［7］Gusfield D，Irving R W.The stable marriage problem：structure and algorithm［M］.Boston：MIT Press，1989.