摘要
已知一房屋集合和一个体集合(房屋数不小于个体数),房屋匹配问题要求根据个体对房屋的偏好,为每一个体分配一个尽可能满意的房屋,使得匹配具有互利性和稳定性.此类问题目前主要研究个体均具有初始分配或均无初始分配这两种情形,且个体对房屋具有严格的偏好序.本文研究一类一般化的房屋匹配问题,即个体对房屋有弱偏好序,且只有部分个体具有初始分配的房屋.基于Shapley和Sacrf的首位交易环算法以及相关的改进算法,设计了求解此一般化问题的扩展首位交易环算法(extended top trading cycle algorithm,ETTC),并证明了由该算法所确定的首位交易环机制满足Pareto有效性、个体理性和防策略操纵性.ETTC算法的时间复杂度为O(n3m),其中n为个体数,m为房屋数.ETTC算法复杂度低于近期已见发表的代表性算法TTAS和TCR.
Given a set of houses and a set of agents （the number of houses is no less than the number of agents）, the house matching problem asks to allocate each agent a different house based on the preferences of the agents such that the requirement of each agent is met as much as possible, and the allocation is in a mutually beneficial and stable way. The problem, usually classified into two categories based on whether each agent has an initial endowment or not. And researchers usually consider the case where the preference is strict. This paper addresses a generalized version of the housing matching problem, which allows the agents to have indifferent preference on houses, and there are only a part of agents who have initial allocations. Based on the top trading cycles （TTC） algorithm proposed by Shapley and Sacrf and some related algorithms, we propose an extended top trading cycle （ETTC） algorithm for this general house matching problem, and prove that ETTC is characterized by individual rationality, Pareto efficient and strategy-proof. The time complexity of ETTC algorithm is O（n3m）, where n is the number of agents and m is the number of houses, which promises a lower complexity compared with state of art TTAS and TCR algorithm.
出处
《中国科学：信息科学》
CSCD
2014年第9期1140-1155,共16页
Scientia Sinica(Informationis)
基金
国家自然科学基金(批准号:61173180
71071063
61273206)
关键词
匹配
机制设计
弱偏好序
Pareto有效
防策略操纵
matching, mechanisms design, weak preference orders, Pareto efficient, strategy-proof
