匹配市場算法

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

匹配市場模型

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

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

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

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

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

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

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

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

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

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

匹配市場算法

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

一共有四個框，其中“初始價格”框沒什么說的。

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

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

而基于當(dāng)前價格按照最大差價原則重新“構(gòu)造二部圖”，確定該有哪些邊，也是直截了當(dāng)?shù)模春竺嬗懻撝袝吹降摹Ｆ渲校〉胢ax的k（可能多個）就指示“人”節(jié)點i就和“物”節(jié)點k之間有一條邊。

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

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

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

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

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

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

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

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

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

這兩個問題其實有關(guān)聯(lián)。看圖6所示n=2的小例子，調(diào)整價格的時候做“+2”，會出現(xiàn)什么現(xiàn)象。

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

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

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

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

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

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

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

參考文獻

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

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

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