论文部分内容阅读
已知一房屋集合和一个体集合(房屋数不小于个体数),房屋匹配问题要求根据个体对房屋的偏好,为每一个体分配一个尽可能满意的房屋,使得匹配具有互利性和稳定性.此类问题目前主要研究个体均具有初始分配或均无初始分配这两种情形,且个体对房屋具有严格的偏好序.本文研究一类一般化的房屋匹配问题,即个体对房屋有弱偏好序,且只有部分个体具有初始分配的房屋.基于Shapley和Sacrf的首位交易环算法以及相关的改进算法,设计了求解此一般化问题的扩展首位交易环算法(extended top trading cycle algorithm,ETTC),并证明了由该算法所确定的首位交易环机制满足Pareto有效性、个体理性和防策略操纵性.ETTC算法的时间复杂度为O(n3m),其中n为个体数,m为房屋数.ETTC算法复杂度低于近期已见发表的代表性算法TTAS和TCR.
A set of houses and a set of individuals are known (the number of houses is not less than the number of individuals). The problem of house matching requires that each individual be given as much satisfaction as possible according to the individual’s preference for the house, so that the matching is mutually beneficial and stable. At present, there are two kinds of cases, such as initial distribution or no initial distribution, and the individuals have strict preference order.This paper studies a generalized house matching problem, that is, individuals have weak preference order , And only some of the individuals have initially allocated houses.According to Shapley and Sacrf’s first-order transaction-loop algorithm and the related improvement algorithms, an extended top-trading cycle algorithm (ETTC) is designed to solve this generalization problem It is proved that the first-order transactional ring mechanism determined by this algorithm satisfies the Pareto validity, individual rationality and anti-strategy maneuverability.The time complexity of ETTC algorithm is O (n3m), where n is the number of individuals and m is the number of houses.ETTC algorithm The complexity is lower than the representative algorithms TTAS and TCR that have been published recently.