弱偏好序下存在租客的房屋匹配问题机制设计
摘要
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 ( n 3 m ), 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.