一對(duì)一單邊匹配問題的機(jī)制設(shè)計(jì)

熊新生 申進(jìn)

摘 要：房屋市場匹配問題要求根據(jù)個(gè)體對(duì)物品的偏好，為每一個(gè)個(gè)體匹配一個(gè)盡可能滿意的物品，使匹配具有互利性和穩(wěn)定性?？紤]在弱偏好序下的房屋市場匹配問題，基于TTC算法提出了一個(gè)改進(jìn)的TTC算法，并證明了該算法滿足個(gè)體理性和Pareto的有效性。

關(guān)鍵詞：機(jī)制設(shè)計(jì);弱偏好序;TTC機(jī)制

文章編號(hào)：1004-7026（2019）22-0009-02? ? ? ? ?中國圖書分類號(hào)：F224? ? ? ? 文獻(xiàn)標(biāo)志碼：A

1 設(shè)計(jì)背景

單邊匹配有別于一般價(jià)格機(jī)制，主要用來解決序數(shù)效應(yīng)下的市場均衡問題[1-2]。在不考慮價(jià)格因素條件下，研究如何對(duì)不可分的兩類離散資源進(jìn)行匹配的市場機(jī)制?？紤]一類特殊的單邊匹配問題——房屋市場問題。房屋市場問題在現(xiàn)實(shí)生活中有著廣泛的應(yīng)用，如器官移植等。

當(dāng)個(gè)體的偏好序?yàn)閲?yán)格偏好序時(shí)，Shapley和Scarf[3]給出了經(jīng)典的首位交易環(huán)算法（Top Trading Cycles，TTC），該算法是在TTC-圖上執(zhí)行的。在算法的每次迭代過程中分成兩個(gè)階段，即改進(jìn)階段、移除和更新階段。改進(jìn)階段是在TTC-圖中尋找一個(gè)交易環(huán)，使環(huán)中個(gè)體相互交換他們擁有物品。移除、更新階段是移除那些不會(huì)出現(xiàn)在任何交易環(huán)的個(gè)體以及它們當(dāng)前匹配的物品，再更新個(gè)體的偏好序列表。由該算法確定的機(jī)制能同時(shí)滿足個(gè)體理性、Pareto有效性和防策略操縱性。Ma[4]證明了這是唯一能同時(shí)滿足上述3個(gè)性質(zhì)的機(jī)制。

在現(xiàn)實(shí)生活中，由于各種原因，個(gè)體往往會(huì)認(rèn)為某些物品是不分伯仲的，很難給出嚴(yán)格的偏好序。因此，很自然地將房屋市場問題的嚴(yán)格偏好序放松為弱偏好序。對(duì)于弱偏好序下房屋市場的匹配問題，簡單且常用的方法是將弱偏好序中平局隨機(jī)給出一個(gè)排序，使其變成嚴(yán)格偏好序，再采用TTC算法來計(jì)算。該方法的不足之處是不能保證得到的匹配滿足Pareto有效性[5-7]。

在TTC算法的基礎(chǔ)上，為弱偏好序下的房屋市場匹配問題設(shè)計(jì)了一種新的改進(jìn)TTC算法。用新構(gòu)造有向圖的方法用尋找PI-環(huán)，使算法時(shí)間復(fù)雜度比現(xiàn)行算法更有效。

2? 模型描述及其相關(guān)概念

記A={a1，a2，…，an}為個(gè)體集，H={h1，h2，…，hn}為物品集。每一個(gè)體在進(jìn)入市場前擁有一個(gè)物品，對(duì)任一ai∈A，記ai初始稟賦為wai。每一個(gè)體ai（ai∈A）對(duì)物品集H中的物品有一個(gè)滿足自反性，傳遞性的二元關(guān)系Rai，并稱這種關(guān)系為偏好序。記

=（Rai）ai∈A為偏好斷面，R-ai為除個(gè)體ai以外其他個(gè)體所組成的偏好斷面。子集Top（Rai，H）？哿H為H中個(gè)體ai最喜歡的物品，即Top（Rai，H）={h∈H：hRaih，？坌h∈H}。對(duì)任一A？哿A，令w={wai|ai∈A}。在TTC-圖中頂點(diǎn)集為物品和個(gè)體集;有向邊的定義為物品頂點(diǎn)指向其擁有者;個(gè)體頂點(diǎn)指向他最喜歡的物品。若TTC-圖中環(huán)C=（a1，wa1，a2，wa2，…，al，wal）滿足對(duì)任一i=1，2，…，l，有wai+1≥a1wai且上述二元關(guān)系中至少有一個(gè)是嚴(yán)格的，則稱為Pareto改進(jìn)環(huán)（PI-環(huán)）。

匹配為M：A→H的一個(gè)映射，M（ai）為個(gè)體在匹配M下所分配到的物品。機(jī)制M：? →M。房屋市場匹配問題是給出一個(gè)合理的個(gè)體與物品之間的匹配。目前對(duì)于這類問題主要考慮下面的原則。

定義1：個(gè)體理性。若對(duì)任意的a∈A有M（a）≥

aw（a），則稱匹配M滿足個(gè)體理性。

個(gè)體理性表示在匹配M下，個(gè)體最終分配到的物品不劣于其最初擁有的物品。若在任一偏好斷面下，由機(jī)制M得到的匹配都滿足個(gè)體理性，則稱M滿足個(gè)體理性。

定義2：Pareto有效。若不存在匹配M'，使得對(duì)任意的a∈A有M'（a）≥aM（a）且至少存在某個(gè)b∈A使得M'（b）>bM（b），則稱該匹配是Pareto有效的。

Pareto有效表示在不損害他人利益的前提下，當(dāng)前匹配中每個(gè)個(gè)體都分到了最好的物品。若在任一偏好斷面下，由機(jī)制M得到的匹配都滿足Pareto有效性，則稱M滿足Pareto有效性。

3? 改進(jìn)的TTC算法

任一不滿足Pareto有效性的匹配，其中至少存在一個(gè)Pareto改進(jìn)環(huán)。因此，為了得到一個(gè)Pareto有效的匹配，只需從任一匹配開始，不斷尋找和刪除PI-環(huán)直至匹配中不存在PI-環(huán)。刪除PI-環(huán)的過程相對(duì)應(yīng)于TTC算法的改進(jìn)階段。在迭代刪除Pareto改進(jìn)環(huán)的過程中，有些個(gè)體和物品是不會(huì)出現(xiàn)在往后的任何Pareto改進(jìn)環(huán)中。因此，在構(gòu)造有向圖用以尋找PI-環(huán)時(shí)，可以不考慮這些個(gè)體和物品，并將它們移除匹配問題。

在介紹有向構(gòu)造規(guī)則之前，進(jìn)一步引進(jìn)一些概念。給定房屋市場問題和剩余的物品集，若個(gè)體擁有的物品是他最喜歡的物品（之一），則稱個(gè)體為滿意個(gè)體，否則稱之為不滿意個(gè)體。設(shè)S和S0分別由滿意個(gè)體和不滿意個(gè)體組成的集合。進(jìn)一步將滿意個(gè)體集劃分為S1，S2，…，Sq，S*，其中Sk={a|a∈S且T? ? 下面給出構(gòu)造有向圖G（V，E）的規(guī)則。規(guī)則A：G（V，E）的構(gòu)造規(guī)則。

由規(guī)則A可知，新構(gòu)造的有向圖中任一頂點(diǎn)有且僅有一條出邊，并且頂點(diǎn)有限，故有向圖中一定存在不相交環(huán)。又由于新構(gòu)造的向圖中任一路徑中都存在一個(gè)不滿意個(gè)體，故圖中環(huán)一定為PI-環(huán)。改進(jìn)的TTC算法描述見表1。

由于在算法中個(gè)體每次交換的物品不會(huì)比原來的差，故在最終的匹配中，個(gè)體匹配到的物品不會(huì)劣于初始稟賦，因此，匹配滿足個(gè)體理性。又由于算法中每次刪除的個(gè)體，都匹配到了當(dāng)前最好的物品，且其最好的物品也分配了同時(shí)刪除的個(gè)體了。因此，這些個(gè)體不會(huì)出現(xiàn)在任何的PI環(huán)中了，從而在最終的匹配中不會(huì)出現(xiàn)PI改進(jìn)環(huán)，即不會(huì)存在Pareto改進(jìn)。因此，匹配滿足Pareto有效性。

4? 結(jié)束語

首先給出了一個(gè)構(gòu)造有向圖的規(guī)則，使得圖中每個(gè)頂點(diǎn)都只有一條出邊，且該圖中的環(huán)中至少包含一個(gè)不滿意個(gè)體。從而避免了TTC-圖中個(gè)體可能會(huì)出現(xiàn)在不同的環(huán)中，保證了算法的有效性，同時(shí)也防止了個(gè)體采取策略行為?；谛聵?gòu)造的有向圖，提出了一個(gè)改進(jìn)的TTC算法。該算法適合于大規(guī)模市場中的單邊匹配問題中的匹配計(jì)算。

參考文獻(xiàn)：

[1]Alcalde-Unzu J，Molis E.Exchange of indivisible goods and indifferences：the top trading absorbing sets mechanisms [J].Game Econ Behav，2011，73（1）：1-16.

[2]Jaramillo P，Manjunath V.The difference indifference makes in strategy-proof allocation of objects[J].J Econ Theory，2012，147（5）：1913-1946.

[3]Shapley L，Scarf H.On cores and indivisibility [J].J Math Econ，1974，1（1）：23-37.

[4]Ma J.Strategy-proofness and strict core in a market with indivisibilities[J].Int J Game Theory，1994，23（1）：75-83.

[5]王彥博，于瀚辰，沈體雁.可調(diào)整個(gè)體優(yōu)先級(jí)的雙邊匹配算法[J].計(jì)算機(jī)工程與應(yīng)用，2018（11）：198-203.

[6]林楊，王應(yīng)明，陳圣群.基于證據(jù)推理與最優(yōu)指派策略的多屬性單邊匹配決策[J].運(yùn)籌與管理，2016年 （6）： 47-52.

[7]柏匯崧，張崢.非完全信息偏好下一對(duì)一匹配問題的Gale-Shapley分配機(jī)制[J].企業(yè)技術(shù)開發(fā)：下旬刊，2014（3）： 15-16.