熊新生 申進(jìn)

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

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

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

1 設(shè)計背景

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

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

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

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

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

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

=（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-圖中環(huán)C=（a1，wa1，a2，wa2，…，al，wal）滿足對任一i=1，2，…，l，有wai+1≥a1wai且上述二元關(guān)系中至少有一個是嚴(yán)格的，則稱為Pareto改進(jìn)環(huán)（PI-環(huán)）。

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

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

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

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

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

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

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

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

在介紹有向構(gòu)造規(guī)則之前，進(jìn)一步引進(jìn)一些概念。給定房屋市場問題和剩余的物品集，若個體擁有的物品是他最喜歡的物品（之一），則稱個體為滿意個體，否則稱之為不滿意個體。設(shè)S和S0分別由滿意個體和不滿意個體組成的集合。進(jìn)一步將滿意個體集劃分為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)造的有向圖中任一頂點有且僅有一條出邊，并且頂點有限，故有向圖中一定存在不相交環(huán)。又由于新構(gòu)造的向圖中任一路徑中都存在一個不滿意個體，故圖中環(huán)一定為PI-環(huán)。改進(jìn)的TTC算法描述見表1。

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

4? 結(jié)束語

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

參考文獻(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)整個體優(yōu)先級的雙邊匹配算法[J].計算機(jī)工程與應(yīng)用，2018（11）：198-203.

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

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