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

1、    一对一单边匹配问题的机制设计    熊新生 申进摘 要：房屋市场匹配问题要求根据个体对物品的偏好，为每一个个体匹配一个尽可能满意的物品，使匹配具有互利性和稳定性。考虑在弱偏好序下的房屋市场匹配问题，基于ttc算法提出了一个改进的ttc算法，并证明了该算法满足个体理性和pareto的有效性。关键词：机制设计;弱偏好序;ttc机制：1004-7026（2019）22-0009-02         中国图书分类号：f224        文献标志码：a1 设计背

2、景单边匹配有别于一般价格机制，主要用来解决序数效应下的市场均衡问题1-2。在不考虑价格因素条件下，研究如何对不可分的两类离散资源进行匹配的市场机制。考虑一类特殊的单边匹配问题房屋市场问题。房屋市场问题在现实生活中有着广泛的应用，如器官移植等。当个体的偏好序为严格偏好序时，shapley和scarf3给出了经典的首位交易环算法（top trading cycles，ttc），该算法是在ttc-图上执行的。在算法的每次迭代过程中分成两个阶段，即改进阶段、移除和更新阶段。改进阶段是在ttc-图中寻找一个交易环，使环中个体相互交换他们拥有物品。移除、更新阶段是移除那些不会出现在任何交易环的个体以及它们

3、当前匹配的物品，再更新个体的偏好序列表。由该算法确定的机制能同时满足个体理性、pareto有效性和防策略操纵性。ma4证明了这是唯一能同时满足上述3个性质的机制。在现实生活中，由于各种原因，个体往往会认为某些物品是不分伯仲的，很难给出严格的偏好序。因此，很自然地将房屋市场问题的严格偏好序放松为弱偏好序。对于弱偏好序下房屋市场的匹配问题，简单且常用的方法是将弱偏好序中平局随机给出一个排序，使其变成严格偏好序，再采用ttc算法来计算。该方法的不足之处是不能保证得到的匹配满足pareto有效性5-7。在ttc算法的基础上，为弱偏好序下的房屋市场匹配问题设计了一种新的改进ttc算法。用新构造有向图的方

4、法用寻找pi-环，使算法时间复杂度比现行算法更有效。2  模型描述及其相关概念记a=a1，a2，an为个体集，h=h1，h2，hn为物品集。每一个体在进入市场前拥有一个物品，对任一aia，记ai初始禀赋为wai。每一个体ai（aia）对物品集h中的物品有一个满足自反性，传递性的二元关系rai，并称这种关系为偏好序。记=（rai）aia为偏好断面，r-ai为除个体ai以外其他个体所组成的偏好断面。子集top（rai，h）？哿h为h中个体ai最喜欢的物品，即top（rai，h）=hh：hraih，？坌hh。对任一a？哿a，令w=wai|aia。在ttc-图中顶点集为物品和个体集;有向边的

5、定义为物品顶点指向其拥有者;个体顶点指向他最喜欢的物品。若ttc-图中环c=（a1，wa1，a2，wa2，al，wal）满足对任一i=1，2，l，有wai+1a1wai且上述二元关系中至少有一个是严格的，则称为pareto改进环（pi-环）。匹配为m：ah的一个映射，m（ai）为个体在匹配m下所分配到的物品。机制m：  m。房屋市场匹配问题是给出一个合理的个体与物品之间的匹配。目前对于这类问题主要考虑下面的原则。定义1：个体理性。若对任意的aa有m（a）aw（a），则称匹配m满足个体理性。个体理性表示在匹配m下，个体最终分配到的物品不劣于其最初拥有的物品。若在任一偏好断面下，由机制m

6、得到的匹配都满足个体理性，则称m满足个体理性。定义2：pareto有效。若不存在匹配m'，使得对任意的aa有m'（a）am（a）且至少存在某个ba使得m'（b）>bm（b），则称该匹配是pareto有效的。pareto有效表示在不损害他人利益的前提下，当前匹配中每个个体都分到了最好的物品。若在任一偏好断面下，由机制m得到的匹配都满足pareto有效性，则称m满足pareto有效性。3  改进的ttc算法任一不满足pareto有效性的匹配，其中至少存在一个pareto改进环。因此，为了得到一个pareto有效的匹配，只需从任一匹配开始，不断寻找和删除pi-

7、环直至匹配中不存在pi-环。删除pi-环的过程相对应于ttc算法的改进阶段。在迭代删除pareto改进环的过程中，有些个体和物品是不会出现在往后的任何pareto改进环中。因此，在构造有向图用以寻找pi-环时，可以不考虑这些个体和物品，并将它们移除匹配问题。在介绍有向构造规则之前，进一步引进一些概念。给定房屋市场问题和剩余的物品集，若个体拥有的物品是他最喜欢的物品（之一），则称个体为满意个体，否则称之为不满意个体。设s和s0分别由满意个体和不满意个体组成的集合。进一步将满意个体集划分为s1，s2，sq，s*，其中sk=a|as且t    下面给出构造有向图g（v，e）的规则

8、。规则a：g（v，e）的构造规则。由规则a可知，新构造的有向图中任一顶点有且仅有一条出边，并且顶点有限，故有向图中一定存在不相交环。又由于新构造的向图中任一路径中都存在一个不满意个体，故图中环一定为pi-环。改进的ttc算法描述见表1。由于在算法中个体每次交换的物品不会比原来的差，故在最终的匹配中，个体匹配到的物品不会劣于初始禀赋，因此，匹配满足个体理性。又由于算法中每次删除的个体，都匹配到了当前最好的物品，且其最好的物品也分配了同时删除的个体了。因此，这些个体不会出现在任何的pi环中了，从而在最终的匹配中不会出现pi改进环，即不会存在pareto改进。因此，匹配满足pareto有效性。4&#

9、160; 结束语首先给出了一个构造有向图的规则，使得图中每个顶点都只有一条出边，且该图中的环中至少包含一个不满意个体。从而避免了ttc-图中个体可能会出现在不同的环中，保证了算法的有效性，同时也防止了个体采取策略行为。基于新构造的有向图，提出了一个改进的ttc算法。该算法适合于大规模市场中的单边匹配问题中的匹配计算。参考文献：1alcalde-unzu j，molis e.exchange of indivisible goods and indifferences：the top trading absorbing sets mechanisms j.game econ behav，2011

10、，73（1）：1-16.2jaramillo p，manjunath v.the difference indifference makes in strategy-proof allocation of objectsj.j econ theory，2012，147（5）：1913-1946.3shapley l，scarf h.on cores and indivisibility j.j math econ，1974，1（1）：23-37.4ma j.strategy-proofness and strict core in a market with indivisibilitiesj.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.企业技术开发：下旬刊，