引言

在生活和工作中經(jīng)常會遇到一些需要資源分配的時候，例如

1. 公司發(fā)的禮物不喜歡，想跟其他人換
2. 在線扭蛋機(jī)的交換系統(tǒng)實現(xiàn)
3. 求職offer的選擇
4. 高考投檔系統(tǒng)實現(xiàn)

其中1、2屬于單邊匹配，匹配由單邊期望決定，即“買方”決定；3、4屬于雙邊匹配問題，匹配過程需考慮“買賣雙方”的期望。

在通常情況下，我們期望獲得一個盡可能合理而穩(wěn)定的分配結(jié)果，使得最終整體收益最大化。

羅伊德-沙普利（Lloyd S. Shapley）與他人提出了一系列市場的穩(wěn)定配置機(jī)制，為博弈論和經(jīng)濟(jì)學(xué)領(lǐng)域做出了巨大的貢獻(xiàn)，最終與艾爾文-羅斯（Alvin E. Roth）一同獲得2012年獲諾貝爾經(jīng)濟(jì)學(xué)獎。

背景

之前寫過在業(yè)務(wù)中遇到了判定業(yè)務(wù)，而該判定業(yè)務(wù)實際上是一組給定對象與另一組給定對象的匹配問題：

• 集合(a, b, c, d)與集合(A, B, C, D, E)的匹配問題，最終得到的結(jié)果是多組一對一關(guān)系
• 在匹配過程中，有可能出現(xiàn)匹配錯誤導(dǎo)致的多對一匹配結(jié)果
• 為解決匹配沖突，需要對匹配結(jié)果進(jìn)行調(diào)整，做到“盡可能讓每個對象都滿意”，即達(dá)到局部最優(yōu)，資源分配合理的狀態(tài)

在調(diào)整匹配的過程為達(dá)到資源分配的穩(wěn)定性考慮了結(jié)果的優(yōu)先級排序。當(dāng)時并不清楚這樣做是否能達(dá)到最優(yōu)效果，在無意間了解到資源分配的“強(qiáng)核配置”這一概念后，發(fā)現(xiàn)自行實現(xiàn)的分配算法邏輯與博弈中的GS算法相同。確認(rèn)該方式可以做到資源分配穩(wěn)定的同時，也了解到適用于其他分配場景的實用算法，在此希望能通俗易懂地介紹給大家。

強(qiáng)核配置

強(qiáng)核配置即滿足個體合理性的同時滿足帕累托最優(yōu)狀態(tài)。
強(qiáng)核配置在匹配中不僅是存在的，而且是唯一的，具有抗策略性，即私下交易或說謊都不會使得結(jié)果變得比強(qiáng)核配置的結(jié)果更好。

帕累托最優(yōu)

帕累托最優(yōu)（Pareto Optimality），也稱為帕累托效率（Pareto Efficiency），是指資源分配的一種理想狀態(tài)，假定固有的一群人和可分配的資源，從一種分配狀態(tài)到另一種狀態(tài)的變化中，在沒有使任何人境況變壞的前提下，使得至少一個人變得更好，這就是帕累托改進(jìn)或帕累托最優(yōu)化。

帕累托最優(yōu)狀態(tài)就是不可能再有更多的帕累托改進(jìn)的余地；換句話說，帕累托改進(jìn)是達(dá)到帕累托最優(yōu)的路徑和方法。

——百度百科

算法介紹

Top Trading Cycle Algorithm

首位交易循環(huán)算法算法，在1974年提出，下稱TTC算法。

適用于“分配”或“交易”場景，即單邊匹配問題。

問題引入

一些公司在節(jié)日時給員工發(fā)不同顏色的禮品，員工在抽到獎品后對顏色不滿意，希望跟其他人交換更喜歡顏色的獎品。

對于員工而言，喜歡的顏色不盡相同，或許與其他人交換之后能獲得各方更滿意的結(jié)果。

問題定義

簡單起見，我們把問題簡化，定義一些限制條件：

1. 給定員工集合E=e1, e2, e3, e4
2. 給定員工對應(yīng)的禮物G=<e1, g1>, <e2, g2>, <e3, g3>, <e4, g4>
3. 參與的各方都滿意才能交換
4. 可以不與他人交換

TTC算法步驟

1. 每位員工對每個禮物的滿意程度排序
2. 員工提出當(dāng)前最滿意的禮物，將員工與期望禮物間建立一條邊，同時將禮物與其主人間建立一條邊
3. 尋找建立的邊是否形成了循環(huán)，允許自循環(huán)，可能有多個循環(huán)
4. 循環(huán)中的員工交換禮物，停止參與交換
5. 剩余員工將循環(huán)中的名單從表中去除，繼續(xù)提出當(dāng)前最滿意的禮物，迭代尋找循環(huán)
6. 交換全部完成，結(jié)束

案例演示

根據(jù)滿意程度組成的表格，按滿意度從高（左）到低（右）排序，以及建立的有向圖

<e1, g3>與<e3, g1>形成了循環(huán)，達(dá)成交易并離場

<e2, g4>與<e4, g2>形成了循環(huán)，達(dá)成交易并離場，所有交易都已完成

算法的核心思想：根據(jù)當(dāng)前優(yōu)先級順序形成交換循環(huán)，意見達(dá)成一致的員工與禮物優(yōu)先交換并離場，剩下的員工從滿意度表中去除已離場禮物后繼續(xù)嘗試形成交換循環(huán)。

問題解決

TTC有一些特點：

1. 每次迭代一定存在循環(huán)，即使是自循環(huán)
2. 多個循環(huán)之間一定不會出現(xiàn)相交，因為每個節(jié)點只有一條出邊
3. 能換到的禮物一定不比已有的差，因為最差情況下會形成自循環(huán)而離場

盡管我們平常交換公司禮物的方式也是使用TTC算法，但通常來說卻少足夠的候選交易池和一定的規(guī)則，最終的結(jié)果不一定能達(dá)到最優(yōu)。

補(bǔ)充

TTC算法可以獲得強(qiáng)核配置，強(qiáng)核配置具有抗策略性，說謊或私下交易都不會讓結(jié)果變得更好。

做個不嚴(yán)謹(jǐn)?shù)暮唵巫C明：

1. 第一輪交易成功的員工們，說謊或私下交易只會讓結(jié)果更壞，畢竟已獲得最滿意結(jié)果了
2. 第二輪交易成功的員工，無論自身的滿意度排序如何也無法改變一輪交易成功的循環(huán)，因此不可能變得更好；私下交易也會損害全局利益
3. 類推第三輪等

Gale-Shaply Algorithm

蓋爾-沙普利算法，又稱Deffered Acceptance Algorithm，延遲接受算法，在1962年提出，下稱GS算法或延遲接受算法。

適用于“配對”場景（并非必須一對一），即雙邊匹配問題。

問題引入

求職是一個雙向選擇的過程，需要公司認(rèn)可求職者并下發(fā)offer之后，求職者基于手中的offer對比，并做出接受或拒絕的判斷。
對于求職者而言，offer明顯需要基于多重考量后選取最優(yōu)的結(jié)果；對于公司而言，職位是有限的，因此招到的員工在公司能力評估排序中越靠前越好。
雙方都希望從這個匹配中達(dá)到最大化收益，那么怎樣的發(fā)/接offer策略會達(dá)到整體收益最大化即帕累托最優(yōu)呢？

問題定義

同樣簡單起見，定義一些限制條件：

1. 給定公司集合C=c1, c2, c3, c4
2. 給定求職者集合E=e1, e2, e3, e4，對C中每個公司都提出求職申請
3. 每個公司只錄取一名求職者，每個求職者只接受一個offer

GS算法步驟

1. 每個公司為每名求職者進(jìn)行滿意度排序，求職者對每個公司的offer進(jìn)行滿意度排序
2. 每家公司優(yōu)先給排序靠前的求職者發(fā)offer，如果被拒絕則繼續(xù)給下一位發(fā)offer
3. 求職者在收到offer后并不馬上決定，而是等待收到其他offer后進(jìn)行對比，僅保留最滿意的offer，回絕其他offer
4. 計算過程為：C方發(fā)一輪offer->E方?jīng)Q策->C方發(fā)一輪offer->E方?jīng)Q策......
5. 當(dāng)所有決定不再變動時，分配結(jié)束，求職者接受手中offer

案例演示

C方與E方滿意度排序組成的表格以及第一輪offer發(fā)放情況，其中 n, m 表示公司對求職者的排位（左）及求職者對公司的排位（右）

e1獲得了2個offer并通過比較拒絕了c2的offer

c2給下一候選人e4發(fā)offer，e4通過比較拒絕了c4的offer

c4給下一候選人e2發(fā)offer，e2通過比較拒絕了c3的offer

c3給下一候選人e1發(fā)offer，e1通過比較拒絕了c1的offer

c1給下一候選人e2發(fā)offer，e2通過比較拒絕了c1的offer

c1給下一候選人e3發(fā)offer，此時匹配達(dá)到穩(wěn)定狀態(tài)

達(dá)到穩(wěn)定狀態(tài)后，資源得到最大化利用。

算法的核心思想：主動方（C方）按照優(yōu)先級申請匹配，而被動方（E方）根據(jù)優(yōu)先級進(jìn)行比較，只保留最合適的匹配申請最后統(tǒng)一決定，最終達(dá)到穩(wěn)定匹配，因此被稱為“延遲接受”。

問題解決

GS算法被證明不會無限循環(huán)執(zhí)行，最終狀態(tài)會達(dá)到穩(wěn)定的匹配狀態(tài)。這一點比較好理解，畢竟任何公司發(fā)offer的對象不會重復(fù)且在排序表上越來越靠后，最差情況下需執(zhí)行n^2次，其他一些證明在參考文獻(xiàn)中有提到。

當(dāng)然，實際情況下受到崗位數(shù)量、offer期限、發(fā)offer時間等的影響問題會變得復(fù)雜很多，但核心還是保持不變的。

仔細(xì)想想，我們在實際發(fā)/接offer時不也幾乎都是這樣決策的嗎？這說明在長期的勞資雙方博弈下延遲接受算法確實是一種實現(xiàn)各方利益最大化的良好選擇，也經(jīng)受住了市場的考驗。

在最理想的狀態(tài)下，所有C方統(tǒng)一發(fā)offer，E方統(tǒng)一接受/拒絕，可以達(dá)到整體利益的最大化。但對于競爭力弱的主動方公司來說，自身需求可能得不到較好的滿足，因此出現(xiàn)offer決策時間短（不允許延遲決策的情況可以參考秘書問題）、提前發(fā)offer搶人等操作，導(dǎo)致整體資源分配不穩(wěn)定不合理，甚至產(chǎn)生惡性競爭。

補(bǔ)充

有趣的是，對于上文給出的案例數(shù)據(jù)，會發(fā)現(xiàn)各位求職者拿到的都不是最滿意的那個offer，各公司招到的員工也不是最滿意的那個，比如最優(yōu)秀的e1求職者和c4公司。這也沒辦法，誰讓你在最心儀的公司/員工面前表現(xiàn)那么差（末位）呢？這說明也許匹配的過程中雙方看對眼或許比自身條件還重要。（同樣適用于找對象場景）

在如下場景中，由C方主動發(fā)起匹配和由E方主動發(fā)起匹配最終GS算法的結(jié)果是不一樣的。由C發(fā)起的穩(wěn)定匹配對于C而言結(jié)果更好；而由E發(fā)起的則完全相反。所以，盡量在這樣的匹配場景中掌握主動權(quán)，或許會給自己帶來更好的結(jié)果。（這條在找對象場景也適用，hhh）

image

GS算法對于主動方具有抗策略性。

總結(jié)

穩(wěn)定匹配理論在不增減資源的前提下，僅僅對現(xiàn)有資源進(jìn)行重新排列組合，就能使各方都達(dá)到相對滿意狀態(tài)，整體達(dá)到最優(yōu)。在升學(xué)志愿、學(xué)校分配、捐獻(xiàn)器官交換、崗位分配等領(lǐng)域，這些理論思想都有得到廣泛應(yīng)用，在匹配問題也比較常見的計算機(jī)領(lǐng)域應(yīng)該也有不少應(yīng)用場景。

參考資料

SF2972: Game theory - www.kth.se

蓋爾-沙普利算法 - 百度百科

雙邊匹配理論及其應(yīng)用研究新進(jìn)展[張衛(wèi)東，黃春華]pdf下載

Stable Matching-穩(wěn)定匹配問題 - 橡膠大口吃のBlog