一對一單邊匹配問題的機制設計

熊新生 申進

摘 要：房屋市場匹配問題要求根據個體對物品的偏好，為每一個個體匹配一個盡可能滿意的物品，使匹配具有互利性和穩定性。考慮在弱偏好序下的房屋市場匹配問題，基于TTC算法提出了一個改進的TTC算法，并證明了該算法滿足個體理性和Pareto的有效性。

關鍵詞：機制設計;弱偏好序;TTC機制

文章編號：1004-7026（2019）22-0009-02? ? ? ? ?中國圖書分類號：F224? ? ? ? 文獻標志碼：A

1 設計背景

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

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

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

在TTC算法的基礎上，為弱偏好序下的房屋市場匹配問題設計了一種新的改進TTC算法。用新構造有向圖的方法用尋找PI-環，使算法時間復雜度比現行算法更有效。

2? 模型描述及其相關概念

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

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

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

定義1：個體理性。若對任意的a∈A有M（a）≥

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

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

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

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

3? 改進的TTC算法

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

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

由規則A可知，新構造的有向圖中任一頂點有且僅有一條出邊，并且頂點有限，故有向圖中一定存在不相交環。又由于新構造的向圖中任一路徑中都存在一個不滿意個體，故圖中環一定為PI-環。改進的TTC算法描述見表1。

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

4? 結束語

首先給出了一個構造有向圖的規則，使得圖中每個頂點都只有一條出邊，且該圖中的環中至少包含一個不滿意個體。從而避免了TTC-圖中個體可能會出現在不同的環中，保證了算法的有效性，同時也防止了個體采取策略行為。基于新構造的有向圖，提出了一個改進的TTC算法。該算法適合于大規模市場中的單邊匹配問題中的匹配計算。

參考文獻：

[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]王彥博，于瀚辰，沈體雁.可調整個體優先級的雙邊匹配算法[J].計算機工程與應用，2018（11）：198-203.

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

[7]柏匯崧，張崢.非完全信息偏好下一對一匹配問題的Gale-Shapley分配機制[J].企業技術開發：下旬刊，2014（3）： 15-16.