凸偏好下的室友问题

Roommates with Convex Preferences

摘要 Abstract

具有凸偏好的室友问题总是存在稳定的匹配。此外,在这类凸偏好下的室友问题中,效率与个体理性兼容策略证明。如果没有凸偏好的假设,这两个结果均不成立。在所研究的环境中,偏好为凸的当且仅当其为单峰偏好。任何个体理性且凸的室友问题都与婚姻市场同构,其中代理人的性别对应于代理人首选伴侣的方向。由此可得稳定匹配的存在性来自婚姻市场中稳定匹配的存在性。为了证明第二个存在性结果,我定义了一个针对凸偏好下室友问题的有效、个体理性且策略证明的机制。该机制通过从所有代理人都单身开始,然后逐步通过最小帕累托改进重新分配代理人到更好的伴侣,从而计算结果。一旦明确某些代理人无法参与进一步的帕累托改进时,这样的代理人即被匹配。

Roommate problems with convex preferences always have stable matchings. Efficiency and individual rationality are, moreover, compatible with strategyproofness in such convex roommate problems. Both of these results fail without the assumption of convexity. In the environment under study, preferences are convex if and only if they are single peaked. Any individually rational and convex roommate problem is homomorphic to a marriage market where an agent's gender corresponds to the direction of the agent's top-ranked partner. The existence of stable matchings then follows from the existence of stable matchings in marriage markets. To prove the second existence result, I define an efficient, individually rational, and strategyproof mechanism for convex roommate problems. To calculate outcomes, this mechanism starts with all agents being single and then gradually reassigns agents to better partners by performing minimal Pareto improvements. Whenever it becomes clear that some agent cannot be part of any further Pareto improvement, such an agent is matched.

凸偏好下的室友问题 - arXiv