郭鳴宇 刁旭 沈陽(yáng)城市學(xué)院

關(guān)鍵字：GS算法 穩(wěn)定匹配 師生互選

1 引言

當(dāng)前高速發(fā)展的經(jīng)濟(jì)現(xiàn)狀衍生了很多研究成果，穩(wěn)定匹配問(wèn)題就是其中之一。2012年，美國(guó)學(xué)者羅斯和沙普利在“穩(wěn)定匹配理論和市場(chǎng)設(shè)計(jì)實(shí)踐”領(lǐng)域做出了突出貢獻(xiàn)并因此獲得諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。1962 年，美國(guó)數(shù)學(xué)家 David Gale 和 Lloyd Shapley 發(fā)明了一種尋找穩(wěn)定婚姻的策略。不管男女各有多少人，不管他們各自的偏好如何，應(yīng)用這種策略后總能得到一個(gè)穩(wěn)定的婚姻搭配。

本文主要是針對(duì)解決穩(wěn)定匹配問(wèn)的GS算法。首先簡(jiǎn)要介紹了穩(wěn)定匹配的含義以及在實(shí)踐過(guò)程中發(fā)現(xiàn)的穩(wěn)定匹配當(dāng)前存在的問(wèn)題。然后針對(duì)這一問(wèn)題對(duì)穩(wěn)定算法進(jìn)行了優(yōu)化，并應(yīng)用到學(xué)校的畢業(yè)師生互選系統(tǒng)中。

2 穩(wěn)定匹配

2.1 穩(wěn)定匹配問(wèn)題內(nèi)容描述

穩(wěn)定匹配問(wèn)題(stable matching)是一個(gè)生活中經(jīng)常能夠遇到的問(wèn)題，GS算法是解決穩(wěn)定匹配問(wèn)題的一個(gè)算法。所謂穩(wěn)定匹配難題，是指：有n個(gè)男人，還有n個(gè)女人，男人心目中有自己的心上人列表，從最喜歡的女神一直排列下去，而女人心中也有相同的列表。很明顯的，某男性喜歡的女人，她可能根本看不上他。而多個(gè)女人喜歡的男人，也不可能同時(shí)娶這些女人。所以要找出一個(gè)讓所有人都能結(jié)婚，且大家都滿意的方案是很難的。

有n個(gè)男人和n個(gè)女人(n＞=2)，每個(gè)男人對(duì)所有女人有一個(gè)好感度排名，每個(gè)女人對(duì)所有男人也有一個(gè)好感度排名。將男女兩兩配對(duì)，得到n對(duì)男女，稱之為一個(gè)完美匹配。如果有一組男女A和B，他們?cè)谄ヅ渲袥](méi)有被配對(duì)，且對(duì)對(duì)方的好感度均大于對(duì)現(xiàn)有配偶的好感度（男人A覺(jué)得女人B好過(guò)現(xiàn)在的妻子C，女人B覺(jué)得A好過(guò)現(xiàn)在的丈夫D），則稱之為一個(gè)不穩(wěn)定配對(duì)。如果一個(gè)完美匹配中沒(méi)有不穩(wěn)定配對(duì)，則稱改匹配為一個(gè)穩(wěn)定匹配。

算法邏輯如下：如果存在男人m是自由的且還沒(méi)對(duì)每個(gè)女人都求過(guò)婚則選擇這個(gè)男人m，令w是m的優(yōu)先表中還沒(méi)求過(guò)婚的最高排名的女人。然后判斷w是自由的情況下m，w變成約會(huì)狀態(tài)。如果w隨后又與m1約會(huì)并且w更偏愛(ài)m1而不愛(ài)m，那么m恢復(fù)自由。當(dāng)然如果w更偏愛(ài)m而不愛(ài)m1，則m1仍自由。

2.2 穩(wěn)定匹配的不足

被動(dòng)方會(huì)越來(lái)越好，主動(dòng)方會(huì)越來(lái)越差。如某單身女性w從第一次跟別人組隊(duì)之后，如果另一個(gè)男性m繼續(xù)向她表示滿意，而且m剛好在w的排序表上的排名比w的現(xiàn)任更高，那么w會(huì)甩了現(xiàn)任然后與m結(jié)合。如果m在w的排序表上的排名比w的現(xiàn)任低，那么w不接受m，繼續(xù)和現(xiàn)任在一起。這個(gè)規(guī)律可以看出，w自從第一個(gè)跟別人組隊(duì)之后，她如果后面還有與其他人組合，那么跟她后面組合的人只會(huì)”越來(lái)越好”，即越來(lái)越符合她的排序表，也就是說(shuō)，她得到的伴侶質(zhì)量會(huì)越來(lái)越好。若某男性向他排序表上的女性示愛(ài)，如果第一個(gè)示愛(ài)失敗之后只能再去找第二個(gè)，再失敗再找第三個(gè)，以此類推。于是這在他脫單之前，他能選擇的女性只會(huì)越來(lái)越不符合他的排序表，也就是說(shuō)，他能選擇的異性質(zhì)量會(huì)越來(lái)越差。如果男性的排名表完全協(xié)調(diào)(他們?nèi)剂谐霾煌宰鳛樗麄兊牡谝贿x擇)，那么在GS算法的所有運(yùn)行中所有男人最終都與他們的第一選擇匹配，而與女人的排序表無(wú)關(guān)。假設(shè)男m1最喜歡女w1，m2最喜歡w2，…，mn最喜歡wn。那么所有男性單身者在選擇時(shí)都會(huì)進(jìn)入前面說(shuō)到的這種情況，也就是直接和最喜歡的女性脫單了。這個(gè)時(shí)候女性就變成沒(méi)有選擇權(quán)了，如果這時(shí)候單身女性的排序表剛好跟單身男性完全沖突的話，也就是說(shuō)，w1最不喜歡m1，w2最不喜歡m2，以此類推。那么這種情境下的匹配結(jié)果雖然是穩(wěn)定的，但卻也往往也不是最情投意合的，因?yàn)槟行远嫉玫搅俗钕矏?ài)的女性，而女性卻都得到了最不喜愛(ài)的男性。

3 互選算法

3.1 互選算法的優(yōu)化

鑒于GS算法只能做到n對(duì)n相同數(shù)量的兩隊(duì)人員進(jìn)行穩(wěn)定匹配，并且應(yīng)用于相親場(chǎng)景時(shí)還會(huì)有主動(dòng)方越來(lái)越好，被動(dòng)方越來(lái)越差這一不足，我設(shè)想了一個(gè)優(yōu)化后的算法，可以實(shí)現(xiàn)任意數(shù)量被動(dòng)方對(duì)任意數(shù)量主動(dòng)方的穩(wěn)定匹配。并將這一算法應(yīng)用到不需要高要求“情投意合”的使用場(chǎng)景中，可以將該算法得到有效利用。如師生互選系統(tǒng)、就業(yè)系統(tǒng)、選拔系統(tǒng)等。最終結(jié)果會(huì)使每個(gè)互選雙方都有相互人選或者匹配的崗位，且數(shù)量差距小于等于一，滿足師生互選、就業(yè)或者選拔系統(tǒng)資源均衡的要求。

3.2 互選算法的實(shí)現(xiàn)

假設(shè)數(shù)量多的一方為主動(dòng)方Zn，數(shù)量少的一方為被動(dòng)方Bm。則首先選出第一批主動(dòng)方，數(shù)量為m，去主動(dòng)與被動(dòng)方進(jìn)行穩(wěn)定匹配。匹配方式與傳統(tǒng)穩(wěn)定匹配算法相同，穩(wěn)定匹配后，換后面m個(gè)主動(dòng)方與被動(dòng)方進(jìn)行穩(wěn)定匹配。以此類推，直到最后一批主動(dòng)方與被動(dòng)方匹配結(jié)束。此時(shí)，所有的主動(dòng)方都已匹配到了對(duì)應(yīng)的人員。由穩(wěn)定匹配的原理可知，每一輪匹配結(jié)束后，所有人全部都已經(jīng)匹配到了一位滿意對(duì)象。任意兩名被動(dòng)方所匹配到的主動(dòng)方只差都在小于等與一范圍內(nèi)。因?yàn)樽詈笠慌暗拿恳慌闹鲃?dòng)方和被動(dòng)方都會(huì)形成穩(wěn)定匹配，只有最后一次可能會(huì)有人沒(méi)有被匹配，所以能夠保證數(shù)量之差最大為一。

4 互選算法的應(yīng)用

互選算法優(yōu)化了主動(dòng)方與被動(dòng)方數(shù)量可以不一致的問(wèn)題，并且可以使每個(gè)被動(dòng)方所匹配的主動(dòng)方人數(shù)之差不超過(guò)一。這一特性可以應(yīng)用于更多的場(chǎng)景之中，不只局促在“相親”這一場(chǎng)景下。因此，我將它應(yīng)用于比較貼近當(dāng)前情況的場(chǎng)景中——畢業(yè)系統(tǒng)師生互選。該算法可以很好的完成導(dǎo)師、學(xué)生的互選。老師的數(shù)量多于學(xué)生，則可將學(xué)生看作主動(dòng)方，學(xué)生看做被動(dòng)方。我們將學(xué)生按照每一批的數(shù)量等于老師的數(shù)量去進(jìn)行穩(wěn)定匹配，直到最后一輪結(jié)束，即可完成老師與學(xué)生的互選。最終得到的結(jié)果可以保證任兩位導(dǎo)師名下匹配的學(xué)生數(shù)之差不會(huì)大于一。解決了平時(shí)導(dǎo)師、學(xué)生互選時(shí)數(shù)量不均衡的問(wèn)題。

5 結(jié)論

通過(guò)對(duì)GS算法的研究，以及使用“相親”的場(chǎng)景模擬了穩(wěn)定匹配問(wèn)題，更加深刻地了解了GS算法的原理。并通過(guò)實(shí)踐驗(yàn)證，得出GS算法可以有效解決穩(wěn)定匹配的問(wèn)題。但是通過(guò)一步步觀察發(fā)現(xiàn)，GS算法得出的結(jié)果會(huì)有被動(dòng)方所匹配的人會(huì)越來(lái)越好，而主動(dòng)方匹配的卻是越來(lái)越不符合心意的弊端。基于這一發(fā)現(xiàn)，我將互選算法進(jìn)行了優(yōu)化，使被動(dòng)方與主動(dòng)方數(shù)量可以不一定一致，通過(guò)分批次進(jìn)行穩(wěn)定匹配，最后可以得到多對(duì)多的穩(wěn)定匹配，且任意被動(dòng)方所匹配的主動(dòng)方之差小于等于一。這一結(jié)果可以應(yīng)用于畢業(yè)師生互選系統(tǒng)之中。解決了之前師生互選資源的不均衡問(wèn)題。通過(guò)這次課題，提高了對(duì)算法優(yōu)化以及對(duì)問(wèn)題剖析的能力。