引言
在生活和工作中經(jīng)常會(huì)遇到一些需要資源分配的時(shí)候，例如
- 公司發(fā)的禮物不喜歡崔列，想跟其他人換
- 在線扭蛋機(jī)的交換系統(tǒng)實(shí)現(xiàn)
- 求職offer的選擇
- 高考投檔系統(tǒng)實(shí)現(xiàn)
其中1腊满、2屬于單邊匹配钢拧，匹配由單邊期望決定，即“買方”決定最蕾；3依溯、4屬于雙邊匹配問題，匹配過程需考慮“買賣雙方”的期望瘟则。
在通常情況下黎炉，我們期望獲得一個(gè)盡可能合理而穩(wěn)定的分配結(jié)果，使得最終整體收益最大化醋拧。
羅伊德-沙普利（Lloyd S. Shapley）與他人提出了一系列市場(chǎng)的穩(wěn)定配置機(jī)制慷嗜，為博弈論和經(jīng)濟(jì)學(xué)領(lǐng)域做出了巨大的貢獻(xiàn)淀弹，最終與艾爾文-羅斯（Alvin E. Roth）一同獲得2012年獲諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。
背景
之前寫過在業(yè)務(wù)中遇到了判定業(yè)務(wù)庆械，而該判定業(yè)務(wù)實(shí)際上是一組給定對(duì)象與另一組給定對(duì)象的匹配問題：
- 集合
(a, b, c, d)與集合(A, B, C, D, E)的匹配問題薇溃，最終得到的結(jié)果是多組一對(duì)一關(guān)系 - 在匹配過程中，有可能出現(xiàn)匹配錯(cuò)誤導(dǎo)致的多對(duì)一匹配結(jié)果
- 為解決匹配沖突缭乘，需要對(duì)匹配結(jié)果進(jìn)行調(diào)整沐序，做到“盡可能讓每個(gè)對(duì)象都滿意”，即達(dá)到局部最優(yōu)堕绩，資源分配合理的狀態(tài)
在調(diào)整匹配的過程為達(dá)到資源分配的穩(wěn)定性考慮了結(jié)果的優(yōu)先級(jí)排序策幼。當(dāng)時(shí)并不清楚這樣做是否能達(dá)到最優(yōu)效果，在無意間了解到資源分配的“強(qiáng)核配置”這一概念后逛尚，發(fā)現(xiàn)自行實(shí)現(xiàn)的分配算法邏輯與博弈中的GS算法相同垄惧。確認(rèn)該方式可以做到資源分配穩(wěn)定的同時(shí)刁愿，也了解到適用于其他分配場(chǎng)景的實(shí)用算法绰寞，在此希望能通俗易懂地介紹給大家。
強(qiáng)核配置
強(qiáng)核配置即滿足個(gè)體合理性的同時(shí)滿足帕累托最優(yōu)狀態(tài)铣口。
強(qiáng)核配置在匹配中不僅是存在的滤钱，而且是唯一的，具有抗策略性脑题，即私下交易或說謊都不會(huì)使得結(jié)果變得比強(qiáng)核配置的結(jié)果更好件缸。
帕累托最優(yōu)
帕累托最優(yōu)（Pareto Optimality），也稱為帕累托效率（Pareto Efficiency）叔遂，是指資源分配的一種理想狀態(tài)他炊，假定固有的一群人和可分配的資源，從一種分配狀態(tài)到另一種狀態(tài)的變化中已艰，在沒有使任何人境況變壞的前提下痊末，使得至少一個(gè)人變得更好，這就是帕累托改進(jìn)或帕累托最優(yōu)化哩掺。
帕累托最優(yōu)狀態(tài)就是不可能再有更多的帕累托改進(jìn)的余地凿叠；換句話說，帕累托改進(jìn)是達(dá)到帕累托最優(yōu)的路徑和方法嚼吞。
——百度百科
算法介紹
Top Trading Cycle Algorithm
首位交易循環(huán)算法算法盒件，在1974年提出，下稱TTC算法舱禽。
適用于“分配”或“交易”場(chǎng)景炒刁，即單邊匹配問題。
問題引入
一些公司在節(jié)日時(shí)給員工發(fā)不同顏色的禮品誊稚，員工在抽到獎(jiǎng)品后對(duì)顏色不滿意翔始，希望跟其他人交換更喜歡顏色的獎(jiǎng)品飒筑。
對(duì)于員工而言，喜歡的顏色不盡相同绽昏，或許與其他人交換之后能獲得各方更滿意的結(jié)果协屡。
問題定義
簡(jiǎn)單起見，我們把問題簡(jiǎn)化全谤，定義一些限制條件：
- 給定員工集合E=e1, e2, e3, e4
- 給定員工對(duì)應(yīng)的禮物G=<e1, g1>, <e2, g2>, <e3, g3>, <e4, g4>
- 參與的各方都滿意才能交換
- 可以不與他人交換
TTC算法步驟
- 每位員工對(duì)每個(gè)禮物的滿意程度排序
- 員工提出當(dāng)前最滿意的禮物肤晓，將員工與期望禮物間建立一條邊，同時(shí)將禮物與其主人間建立一條邊
- 尋找建立的邊是否形成了循環(huán)认然，允許自循環(huán)补憾，可能有多個(gè)循環(huán)
- 循環(huán)中的員工交換禮物，停止參與交換
- 剩余員工將循環(huán)中的名單從表中去除卷员，繼續(xù)提出當(dāng)前最滿意的禮物盈匾，迭代尋找循環(huán)
- 交換全部完成，結(jié)束
案例演示
算法的核心思想：根據(jù)當(dāng)前優(yōu)先級(jí)順序形成交換循環(huán)，意見達(dá)成一致的員工與禮物優(yōu)先交換并離場(chǎng)叙凡，剩下的員工從滿意度表中去除已離場(chǎng)禮物后繼續(xù)嘗試形成交換循環(huán)劈伴。
問題解決
TTC有一些特點(diǎn)：
- 每次迭代一定存在循環(huán)，即使是自循環(huán)
- 多個(gè)循環(huán)之間一定不會(huì)出現(xiàn)相交握爷，因?yàn)槊總€(gè)節(jié)點(diǎn)只有一條出邊
- 能換到的禮物一定不比已有的差跛璧，因?yàn)樽畈钋闆r下會(huì)形成自循環(huán)而離場(chǎng)
盡管我們平常交換公司禮物的方式也是使用TTC算法，但通常來說卻少足夠的候選交易池和一定的規(guī)則新啼，最終的結(jié)果不一定能達(dá)到最優(yōu)追城。
補(bǔ)充
TTC算法可以獲得強(qiáng)核配置，強(qiáng)核配置具有抗策略性师抄，說謊或私下交易都不會(huì)讓結(jié)果變得更好漓柑。
做個(gè)不嚴(yán)謹(jǐn)?shù)暮?jiǎn)單證明：
- 第一輪交易成功的員工們，說謊或私下交易只會(huì)讓結(jié)果更壞叨吮，畢竟已獲得最滿意結(jié)果了
- 第二輪交易成功的員工辆布，無論自身的滿意度排序如何也無法改變一輪交易成功的循環(huán)，因此不可能變得更好茶鉴；私下交易也會(huì)損害全局利益
- 類推第三輪等
Gale-Shaply Algorithm
蓋爾-沙普利算法锋玲，又稱Deffered Acceptance Algorithm，延遲接受算法涵叮，在1962年提出惭蹂，下稱GS算法或延遲接受算法伞插。
適用于“配對(duì)”場(chǎng)景（并非必須一對(duì)一），即雙邊匹配問題盾碗。
問題引入
求職是一個(gè)雙向選擇的過程媚污，需要公司認(rèn)可求職者并下發(fā)offer之后，求職者基于手中的offer對(duì)比廷雅，并做出接受或拒絕的判斷耗美。
對(duì)于求職者而言，offer明顯需要基于多重考量后選取最優(yōu)的結(jié)果航缀；對(duì)于公司而言商架，職位是有限的，因此招到的員工在公司能力評(píng)估排序中越靠前越好芥玉。
雙方都希望從這個(gè)匹配中達(dá)到最大化收益蛇摸，那么怎樣的發(fā)/接offer策略會(huì)達(dá)到整體收益最大化即帕累托最優(yōu)呢？
問題定義
同樣簡(jiǎn)單起見灿巧，定義一些限制條件：
- 給定公司集合C=c1, c2, c3, c4
- 給定求職者集合E=e1, e2, e3, e4赶袄，對(duì)C中每個(gè)公司都提出求職申請(qǐng)
- 每個(gè)公司只錄取一名求職者，每個(gè)求職者只接受一個(gè)offer
GS算法步驟
- 每個(gè)公司為每名求職者進(jìn)行滿意度排序砸烦，求職者對(duì)每個(gè)公司的offer進(jìn)行滿意度排序
- 每家公司優(yōu)先給排序靠前的求職者發(fā)offer弃鸦，如果被拒絕則繼續(xù)給下一位發(fā)offer
- 求職者在收到offer后并不馬上決定绞吁，而是等待收到其他offer后進(jìn)行對(duì)比幢痘，僅保留最滿意的offer，回絕其他offer
- 計(jì)算過程為：C方發(fā)一輪offer->E方?jīng)Q策->C方發(fā)一輪offer->E方?jīng)Q策......
- 當(dāng)所有決定不再變動(dòng)時(shí)家破，分配結(jié)束颜说，求職者接受手中offer
案例演示
達(dá)到穩(wěn)定狀態(tài)后，資源得到最大化利用髓梅。
算法的核心思想：主動(dòng)方（C方）按照優(yōu)先級(jí)申請(qǐng)匹配拟蜻，而被動(dòng)方（E方）根據(jù)優(yōu)先級(jí)進(jìn)行比較，只保留最合適的匹配申請(qǐng)最后統(tǒng)一決定枯饿，最終達(dá)到穩(wěn)定匹配酝锅，因此被稱為“延遲接受”。
問題解決
GS算法被證明不會(huì)無限循環(huán)執(zhí)行奢方，最終狀態(tài)會(huì)達(dá)到穩(wěn)定的匹配狀態(tài)搔扁。這一點(diǎn)比較好理解爸舒，畢竟任何公司發(fā)offer的對(duì)象不會(huì)重復(fù)且在排序表上越來越靠后，最差情況下需執(zhí)行n^2次稿蹲，其他一些證明在參考文獻(xiàn)中有提到扭勉。
當(dāng)然，實(shí)際情況下受到崗位數(shù)量苛聘、offer期限剖效、發(fā)offer時(shí)間等的影響問題會(huì)變得復(fù)雜很多，但核心還是保持不變的焰盗。
仔細(xì)想想璧尸，我們?cè)趯?shí)際發(fā)/接offer時(shí)不也幾乎都是這樣決策的嗎？這說明在長(zhǎng)期的勞資雙方博弈下延遲接受算法確實(shí)是一種實(shí)現(xiàn)各方利益最大化的良好選擇熬拒，也經(jīng)受住了市場(chǎng)的考驗(yàn)爷光。
在最理想的狀態(tài)下，所有C方統(tǒng)一發(fā)offer澎粟，E方統(tǒng)一接受/拒絕蛀序，可以達(dá)到整體利益的最大化。但對(duì)于競(jìng)爭(zhēng)力弱的主動(dòng)方公司來說活烙，自身需求可能得不到較好的滿足徐裸，因此出現(xiàn)offer決策時(shí)間短（不允許延遲決策的情況可以參考秘書問題）、提前發(fā)offer搶人等操作啸盏，導(dǎo)致整體資源分配不穩(wěn)定不合理重贺，甚至產(chǎn)生惡性競(jìng)爭(zhēng)。
補(bǔ)充
有趣的是回懦，對(duì)于上文給出的案例數(shù)據(jù)气笙，會(huì)發(fā)現(xiàn)各位求職者拿到的都不是最滿意的那個(gè)offer，各公司招到的員工也不是最滿意的那個(gè)怯晕，比如最優(yōu)秀的e1求職者和c4公司潜圃。這也沒辦法，誰讓你在最心儀的公司/員工面前表現(xiàn)那么差（末位）呢舟茶？這說明也許匹配的過程中雙方看對(duì)眼或許比自身?xiàng)l件還重要谭期。（同樣適用于找對(duì)象場(chǎng)景）
在如下場(chǎng)景中，由C方主動(dòng)發(fā)起匹配和由E方主動(dòng)發(fā)起匹配最終GS算法的結(jié)果是不一樣的吧凉。由C發(fā)起的穩(wěn)定匹配對(duì)于C而言結(jié)果更好隧出；而由E發(fā)起的則完全相反。所以客燕，盡量在這樣的匹配場(chǎng)景中掌握主動(dòng)權(quán)鸳劳，或許會(huì)給自己帶來更好的結(jié)果。（這條在找對(duì)象場(chǎng)景也適用也搓，hhh）
GS算法對(duì)于主動(dòng)方具有抗策略性赏廓。
總結(jié)
穩(wěn)定匹配理論在不增減資源的前提下涵紊，僅僅對(duì)現(xiàn)有資源進(jìn)行重新排列組合，就能使各方都達(dá)到相對(duì)滿意狀態(tài)幔摸，整體達(dá)到最優(yōu)摸柄。在升學(xué)志愿、學(xué)校分配既忆、捐獻(xiàn)器官交換驱负、崗位分配等領(lǐng)域，這些理論思想都有得到廣泛應(yīng)用患雇，在匹配問題也比較常見的計(jì)算機(jī)領(lǐng)域應(yīng)該也有不少應(yīng)用場(chǎng)景跃脊。
參考資料
SF2972: Game theory - www.kth.se
