论文标题
一个最佳的程序，可以在单一偏好中检查房屋市场中的帕累托式优先性
An Optimal Procedure to Check Pareto-Optimality in House Markets with Single-Peaked Preferences
论文作者
论文摘要
最近，将每个代理商用初始捐赠（房屋市场）分配一种资源的问题已经引起了人们的重新兴趣：确实，在严格偏好的领域中，最高交易周期算法是唯一保证帕累托（Pareto）出色，个人合理性和策略的唯一程序。但是，情况在单峰域上有所不同。的确，Bade提出了越野士，这是一种享有相同特性的替代程序，其其他优势是可以在明显的主要策略中实施。在本文中，我们进一步研究了爬虫并提出了潜水员，该变体可以最佳地检查分配是否是单峰偏好的帕特托（Pareto）最佳选择，从而改善了用于检查更通用域中帕托托（Pareto）在更一般域中的已知技术。我们还证明，在交流复杂性方面，潜水员在渐近上是最佳的。
Recently, the problem of allocating one resource per agent with initial endowments (house markets) has seen a renewed interest: indeed, while in the domain of strict preferences the Top Trading Cycle algorithm is known to be the only procedure guaranteeing Pareto-optimality, individual rationality, and strategy proofness. However, the situation differs in the single-peaked domain. Indeed, Bade presented the Crawler, an alternative procedure enjoying the same properties, with the additional advantage of being implementable in obviously dominant strategies. In this paper we further investigate the Crawler and propose the Diver, a variant which checks optimally whether an allocation is Pareto-optimal for single-peaked preferences, thus improving over known techniques used for checking Pareto-optimality in more general domains. We also prove that the Diver is asymptotically optimal in terms of communication complexity.
