一对一单边匹配问题的机制设计

熊新生 申进

摘 要：房屋市场匹配问题要求根据个体对物品的偏好，为每一个个体匹配一个尽可能满意的物品，使匹配具有互利性和稳定性。考虑在弱偏好序下的房屋市场匹配问题，基于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.