Strategy-proof tie-breaking in matching with priorities

• 成果类型: Article
• 署名作者: Ehlers, Lars; Westkamp, Alexander
• 署名单位: Universite de Montreal; Universite de Montreal; University of Cologne
• 刊物名称: THEORETICAL ECONOMICS
• ISSN/ISSBN: 1555-7561
• DOI: 10.3982/TE2547
• 发表日期: 2018-09-01
• 页码: 1009-1041
• 关键词: Weak priorities; STABILITY; constrained efficiency; strategy-proofness

摘要

A set of indivisible objects is allocated among agents with strict preferences. Each object has a weak priority ranking of the agents. A collection of priority rankings, a priority structure, is solvable if there is a strategy-proof mechanism that is constrained efficient, i.e., that always produces a stable matching that is not Pareto-dominated by another stable matching. We characterize all solvable priority structures satisfying the following two restrictions: Either there are no ties or there is at least one four-way tie.For any two agents i and j, if there is an object that assigns higher priority to i than to j, there is also an object that assigns higher priority to j than to i.(A)(B) We show that there are at most three types of solvable priority structures: The strict type, the house allocation with existing tenants (HET) type, where, for each object, there is at most one agent who has strictly higher priority than another agent, and the task allocation with unqualified agents (TAU) type, where, for each object, there is at most one agent who has strictly lower priority than another agent. Out of these three, only HET priority structures are shown to admit a strongly group-strategy-proof and constrained efficient mechanism.