匹配市場(chǎng)算法

匹配，是人們社會(huì)生活中許多問題的一種抽象。例如高考錄取，是考生與大學(xué)之間的匹配;學(xué)生畢業(yè)了找工作，是畢業(yè)生和用人單位之間的匹配;男女婚戀，自然也是一種匹配。這些匹配的形成過程，常常會(huì)在某種制度（包括法律法規(guī)、約定俗成的做法等）下進(jìn)行。顯然，這些匹配的結(jié)果如何（與制度很有關(guān)系），具有重大的社會(huì)意義。于是，匹配的制度設(shè)計(jì)就成為一個(gè)很有價(jià)值的問題。2012年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)，就頒發(fā)給了兩位在這方面作出突出貢獻(xiàn)的學(xué)者。

匹配市場(chǎng)模型

上面這些例子的共性，一是有雙方，每一方有多個(gè)對(duì)象，二是互選，事情不能一廂情愿，糾結(jié)就發(fā)生在這里。其實(shí)，即便不是互選，由于資源有限，常常也會(huì)很難搞定。想一想那些熱門的大學(xué)吧，就算大學(xué)不挑學(xué)生，但宿舍床位有限，食堂空間有限，不可能容納所有希望去的學(xué)生，最后總有一個(gè)怎么安排的問題。

下面我們來討論一種相對(duì)單純點(diǎn)的匹配問題，看看算法思想如何在其中發(fā)揮作用。設(shè)想有這樣一個(gè)情境：你有A、B、C、D有一定價(jià)值的4件舊物品希望送出去，現(xiàn)在有4個(gè)人W、X、Y、Z有興趣要。當(dāng)然，一人分得一件是比較合適的，也就是說要在物品和人之間形成一個(gè)匹配?？晌锲肥遣灰粯拥?，某兩個(gè)人可能最想得到某同一件物品，該如何安排呢？

按照經(jīng)濟(jì)學(xué)的語言，這意味著需求和供給之間有沖突。盡管你只是想把物品送出去，并沒有想賺錢，但我們不妨從市場(chǎng)的觀點(diǎn)來探討一種解決方案。你告訴他們，每人對(duì)每件物品給出一個(gè)以金額表達(dá)的價(jià)值，對(duì)應(yīng)他愿意支付的最大數(shù)額以得到相應(yīng)的東西，但超過了就不值了。這樣，所表達(dá)的價(jià)值就反映了人們對(duì)不同物品的喜愛程度。假設(shè)他們告訴你了，于是你就面對(duì)如圖1（a）所示的一個(gè)局面。

圖1中的4×4數(shù)據(jù)矩陣就是W、X、Y、Z對(duì)A、B、C、D的估值。每一行對(duì)應(yīng)一個(gè)人，每一列對(duì)應(yīng)一件物品。從中我們看到W最喜歡的是B，因?yàn)樗o出的估值是9，在第一行中最大。而X和Z最喜歡的都是A，因?yàn)槎冀o出了最大估值，于是有沖突了。圖1（b）與（a）含義是一樣的，只是另外一種圖示，便于后面的算法討論。

怎么辦呢？人們參照市場(chǎng)經(jīng)濟(jì)的一種基本精神——物以稀為貴——設(shè)計(jì)了一個(gè)算法。該算法要通過為物品確定一組價(jià)格，來達(dá)成某種最優(yōu)意義下的物品分配。下面先就圖1的例子，通過圖2中的三個(gè)圖來解釋這個(gè)算法的步驟，接著再討論它的一些性質(zhì)。

先看圖2（a），它和圖1不同的是左邊添加了4個(gè)0，用以表示A、B、C、D的初始嘗試價(jià)格。同時(shí)我們也注意到，在原先的物品（A、B、C、D）和人（W、X、Y、Z）之間添加了一些邊（線），形成了一個(gè)二部圖，也就是節(jié)點(diǎn)可以分成左右兩邊，邊只是跨兩邊節(jié)點(diǎn)的圖。在這個(gè)算法中，那些邊的含義很關(guān)鍵，表示“最大差價(jià)”。例如，W和B之間的邊，意味著9-0=9是W目前看到的最合適的物品，于是表達(dá)了“W最希望得到B”的含義。此時(shí)，初始價(jià)格為0，最大差價(jià)也就對(duì)應(yīng)最大價(jià)值了。若價(jià)格變了，最大差價(jià)自當(dāng)改變，于是二部圖中的邊也就要相應(yīng)調(diào)整了。

下面來重點(diǎn)了。我們看到圖2（a）中表現(xiàn)出了一些沖突。例如，從W、X、Z沿著邊向左看過去，只能看見A和B。也就是說三個(gè)人表達(dá)的最愛集中在兩個(gè)物品上，因此沒法都照顧到！怎么辦？物以稀為貴，讓那些供不應(yīng)求的物品加點(diǎn)價(jià)！于是我們看到了圖2（b），其中A和B的價(jià)格提升到了1。這里的算法規(guī)則是讓二部圖中的邊總是對(duì)應(yīng)最大差價(jià)。不過，就這個(gè)例子的當(dāng)前數(shù)據(jù)而言，邊還是那些，因此二部圖的樣子沒有變。

下面是另一個(gè)要點(diǎn)?？梢钥吹綀D2（b）中依然有W、X、Z三個(gè)“爭(zhēng)搶”A和B兩個(gè)的現(xiàn)象。我們可以繼續(xù)給A、B加價(jià)。不過，還可以看到X和Z要的都是A，也是一種“供不應(yīng)求”現(xiàn)象，于是也可以就單給A加價(jià)。這里是想說，加價(jià)的方式不唯一，只要是針對(duì)“供不應(yīng)求”現(xiàn)象都可以。不同的選擇不會(huì)影響最后結(jié)果的性質(zhì)（可能對(duì)效率有些影響，但不是本文重點(diǎn)）。假設(shè)我們現(xiàn)在就選擇只給A加價(jià)。

現(xiàn)在看圖2（c），A的價(jià)格提升到了2。我們看到，按照“最大差價(jià)”原則確定的物品和人之間的邊，二部圖發(fā)生了一個(gè)關(guān)鍵性變化——X現(xiàn)在認(rèn)為也可以要D了，A和D對(duì)他來說差價(jià)都是6。于是，就浮現(xiàn)出一種無沖突安排，也叫完美匹配：A—Z，B—W，C—Y，D—X。

這樣一種安排意義重大。首先，每個(gè)人得到的都是對(duì)他而言差價(jià)最大的物品，也就是說他不可能通過要求換一個(gè)物品來獲得更大的差價(jià)。再者，如果我們看4件物品對(duì)于它們的獲得者的價(jià)值，對(duì)應(yīng)圖2（c）右邊估值矩陣上圈出來的4個(gè)數(shù)字，滿足一個(gè)令人興奮的性質(zhì)：它們的和是該矩陣上不同行不同列元素之和的最大值。這意味著，盡管并不是每個(gè)人都得到了最初最想要的物品（如X沒有得到A），但這種分配實(shí)現(xiàn)了一種總體價(jià)值最優(yōu)，稱為達(dá)到了社會(huì)最優(yōu)。

匹配市場(chǎng)算法

上面的例子，讓我們看到了借助市場(chǎng)“無形之手”——通過價(jià)格調(diào)整供需關(guān)系——得到的一種匹配的算法。一般地，給定任何非負(fù)整數(shù)估值矩陣，圖3所示即為這個(gè)算法的框圖。

一共有四個(gè)框，其中“初始價(jià)格”框沒什么說的。

“完美匹配”是判斷在二部圖上是否出現(xiàn)了無沖突的匹配關(guān)系。圖論告訴我們，如果沒有完美匹配，就意味著存在那種供不應(yīng)求的沖突情況，也稱為存在受限組，即二部圖一邊的節(jié)點(diǎn)子集，大于鄰居節(jié)點(diǎn)集。

如果發(fā)現(xiàn)了在“人”一邊存在一個(gè)受限組和它對(duì)應(yīng)的“物品”集合，“調(diào)整價(jià)格”就是很簡(jiǎn)單的事情，即給那些物品的價(jià)格+1。在前面的例子中已經(jīng)提到，在任何受限組基礎(chǔ)上做這種價(jià)格調(diào)整都會(huì)得到一致的結(jié)果。

而基于當(dāng)前價(jià)格按照最大差價(jià)原則重新“構(gòu)造二部圖”，確定該有哪些邊，也是直截了當(dāng)?shù)?，即后面討論中?huì)看到的。其中，取得max的k（可能多個(gè)）就指示“人”節(jié)點(diǎn)i就和“物”節(jié)點(diǎn)k之間有一條邊。

難點(diǎn)在哪里？在于如何判斷一個(gè)二部圖中是否存在一個(gè)完美匹配。對(duì)于圖2所示的例子，規(guī)模很小，我們憑目測(cè)就可以斷定（a）和（b）中沒有完美匹配，（c）就有了。但一般來說這是不容易的。體會(huì)一下這個(gè)難度，請(qǐng)看圖4。其中展示了四個(gè)二部圖，你能看出哪些有完美匹配嗎？如果沒有，能指出一個(gè)受限組嗎？

也許，你目測(cè)能力很強(qiáng)，看到（a）中不存在完美匹配，因?yàn)橛惺芟藿M{a，b，c，e}，它們對(duì)應(yīng)到左邊只有{1，3，6};還能看到（c）中存在完美匹配a—4，b—1，c—3，d—2，e—6和f—5。但你肯定感到了這是一個(gè)相當(dāng)困難的任務(wù)，需要用計(jì)算機(jī)來解決。的確，為了使圖3所示的框架性算法能夠?qū)崿F(xiàn)，在“完美匹配”判斷框要啟用一個(gè)子算法，相當(dāng)于調(diào)用子程序。

有多種不同的方法來判斷一個(gè)二部圖是否存在完美匹配。其中之一，就是利用本欄目在2020年8月刊上介紹的求網(wǎng)絡(luò)最大流的算法。下面，就來看網(wǎng)絡(luò)流問題和這里的匹配問題是怎么聯(lián)系起來的。

回顧網(wǎng)絡(luò)最大流問題。它針對(duì)一個(gè)有源節(jié)點(diǎn)（s）和目標(biāo)節(jié)點(diǎn)（t）的加權(quán)有向圖，確定從源到目標(biāo)能夠?qū)崿F(xiàn)的最大流量。下面我們會(huì)看到，有一種相當(dāng)直接的方式，將判斷兩邊都有n個(gè)節(jié)點(diǎn)二部圖是否存在完美匹配的問題實(shí)例轉(zhuǎn)換為一個(gè)網(wǎng)絡(luò)最大流問題的實(shí)例，以至于后者的最大流量達(dá)到n，當(dāng)且僅當(dāng)前者存在一個(gè)完美匹配。

我們用如上頁圖5中的例子來解釋這個(gè)對(duì)應(yīng)關(guān)系。（a）是要判斷是否存在完美匹配的二部圖，（b）是一個(gè)網(wǎng)絡(luò)最大流問題的實(shí)例。它基于（a），添加了兩個(gè)節(jié)點(diǎn)s和t，s連到右邊所有節(jié)點(diǎn)，t連到左邊所有節(jié)點(diǎn);給所有邊賦予從右向左的方向，且令每條邊的權(quán)值均為1。

不難看到，如果圖5（b）中s到t的最大流量達(dá)到了n，注意到每條邊的權(quán)重均為1，就意味著從s到t有n條中間節(jié)點(diǎn)無重用的路徑，也就是（a）中有完美匹配，對(duì)應(yīng)那些從s到t路徑中的中間邊。反之，如果（b）中s到t的最大流量小于n，意味著（a）中不存在n條端節(jié)點(diǎn)無沖突的邊跨接在左右兩邊，也就是沒有完美匹配了。此時(shí)，記L和R為二部圖中實(shí)現(xiàn)最大流的左、右兩邊的節(jié)點(diǎn)集合，受限組就是R加上右邊任一其他節(jié)點(diǎn)，在匹配市場(chǎng)算法中需要加價(jià)的就是L中的節(jié)點(diǎn)。以圖5（b）為例，能發(fā)現(xiàn)從s到t的最大流量是5，具體實(shí)現(xiàn)為s→a→1→t，s→b→3→t，s→c→6→t，s→d→2→t，s→f→4→t，小于節(jié)點(diǎn)數(shù)6，因而二部圖5（a）中不存在完美匹配，需要給節(jié)點(diǎn)1，2，3，4，6加價(jià)。

上述這一段討論有特別意義。當(dāng)算法學(xué)習(xí)積累到一定程度，面對(duì)新的問題，往往有可能借用先前針對(duì)不同問題的算法。此時(shí)，關(guān)鍵在于要能在兩個(gè)問題之間做適當(dāng)?shù)摹坝成洹?，能夠從?duì)老問題的解中“解釋”出對(duì)新問題的解來。

匹配市場(chǎng)算法的性質(zhì)

至此，對(duì)圖3描述的匹配算法還能提什么問題嗎？至少還可以問兩個(gè)問題。第一，在調(diào)整價(jià)格的時(shí)候?yàn)槭裁纯偸恰?1”？一次多加點(diǎn)會(huì)不會(huì)效率高一些？例如，從圖2（a）到圖2（b）似乎沒起任何作用，如果一次性加2，就會(huì)省下一輪迭代。第二，算法是以完美匹配的形成作為終止條件的，為什么一定會(huì)形成呢？

這兩個(gè)問題其實(shí)有關(guān)聯(lián)?？磮D6所示n=2的小例子，調(diào)整價(jià)格的時(shí)候做“+2”，會(huì)出現(xiàn)什么現(xiàn)象。

可以看到，調(diào)整價(jià)格時(shí)做“+2”，整個(gè)情形就會(huì)在兩種狀態(tài)下無限循環(huán)往復(fù)，形成不了具有完美匹配的二部圖。下面就來證明，“+1”則會(huì)保證具有完美匹配二部圖的形成，即該算法一定會(huì)結(jié)束。

一般而言，算法是作用在某些數(shù)據(jù)上的處理過程。那些數(shù)據(jù)會(huì)在這個(gè)過程中得到某些改變。為了證明一個(gè)算法過程一定結(jié)束，尤其是對(duì)一些“框架性算法”（其結(jié)束條件可能是比較高層次的描述，就像這里的“出現(xiàn)了具有完美匹配的二部圖”），一種很有用的方法是選擇適當(dāng)?shù)臄?shù)據(jù)對(duì)象，證明在算法過程中其值是單調(diào)有界的。這種方法本欄目在2020年8月刊討論網(wǎng)絡(luò)最大流算法時(shí)就用過。當(dāng)時(shí)的結(jié)束條件是“不再有從s到t的增量路徑”，我們選取的數(shù)據(jù)對(duì)象是從s出發(fā)的剩余容量總和。

對(duì)本文討論的匹配市場(chǎng)算法，涉及的量包括估值矩陣中的值（在算法過程中不變）和在過程中變化的價(jià)格（初始為0）。為方便討論起見，用V來表示估值矩陣，a表示動(dòng)態(tài)調(diào)整的價(jià)格向量，如圖7所示。

我們基于它們構(gòu)造一個(gè)數(shù)據(jù)對(duì)象P如下。它包括兩個(gè)求和項(xiàng)，第二項(xiàng)是當(dāng)前價(jià)格之和，第一項(xiàng)對(duì)應(yīng)當(dāng)前價(jià)格下的最大差價(jià)之和。下面來證明P在算法執(zhí)行過程中具有“單調(diào)減且有下界”的性質(zhì)。

在理解了算法操作的基礎(chǔ)上這個(gè)證明不難。由于“+1”涉及至少一個(gè)物品，第二項(xiàng)在算法的每一輪一定是遞增的，如果涉及了m個(gè)物品，也就是增加了m。對(duì)應(yīng)到二部圖中的受限組，則至少涉及m+1個(gè)人，也就是在第一項(xiàng)中至少有m+1個(gè)max會(huì)減少1。減的多增的少，整個(gè)就是單調(diào)減了。如果是“+2”，第二項(xiàng)將增2m，但就不能保證第一項(xiàng)減量超過2m了。請(qǐng)讀者思考為什么。

為什么有下界呢？只要注意到V是給定不變的和下面的推導(dǎo)式就可以了，其中不等號(hào)是取k=i所致。

好了，到這里基本就完成了關(guān)于一個(gè)重要的匹配市場(chǎng)算法的討論。值得問的一個(gè)問題是，算法過程并沒有直接針對(duì)要獲得匹配估值總和的最大值，它只管按照物以稀為貴的原則調(diào)整價(jià)格，人們按照自己的估值和當(dāng)前價(jià)格做對(duì)自己最有利的訴求表達(dá)（二部圖中以最大差價(jià)為指示的邊），但“無意中的”結(jié)果就是社會(huì)最優(yōu)。這是必然的嗎？答案是肯定的。這個(gè)模型可以看成是對(duì)“無形之手”理論的一種非平凡的具體詮釋。

參考文獻(xiàn)

[1]David Easley， Jon Kleinberg.網(wǎng)絡(luò)、群體與市場(chǎng)[M].李曉明，等，譯.北京：清華大學(xué)出版社，2011，10：175-185.

[2]李曉明.網(wǎng)絡(luò)流問題[J].中國(guó)信息技術(shù)教育，2020（15-16）：16-21.

注：作者系北京大學(xué)計(jì)算機(jī)系原系主任。