Pareto Optimality in House Allocation Problems
Pareto Optimality in House Allocation Problems
复制标题
房屋分配问题中的帕累托最优
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
K. Mehlhorn
中科院分区：
文献类型：
--
作者：
David J. Abraham;K. Cechlárová;D. Manlove;K. Mehlhorn
我们研究帕累托最优匹配的背景下，房屋分配问题。我们提出了一个$O（\sqrt{n}m）$算法，基于盖尔的顶部交易周期方法，寻找最大基数帕累托最优匹配，其中n是代理的数量和m是偏好列表的总长度。相比之下，我们发现，找到一个最小的基数帕累托最优匹配的问题是NP-困难的，虽然在一个因子2近似。然后，我们表明，存在帕累托最优匹配之间的最小和最大基数帕累托最优匹配的所有大小。最后，我们引入了签名的概念，它使我们能够给出一个表征，在线性时间检查，承认一个独特的帕累托最优匹配的实例。
We study Pareto optimal matchings in the context of house allocation problems. We present an $O(\sqrt{n}m)$ algorithm, based on Gale's Top Trading Cycles Method, for finding a maximum cardinality Pareto optimal matching, where n is the number of agents and m is the total length of the preference lists. By contrast, we show that the problem of finding a minimum cardinality Pareto optimal matching is NP-hard, though approximable within a factor of 2. We then show that there exist Pareto optimal matchings of all sizes between a minimum and maximum cardinality Pareto optimal matching. Finally, we introduce the concept of a signature, which allows us to give a characterization, checkable in linear time, of instances that admit a unique Pareto optimal matching.