Computing at Glasgow University
Paper ID: 7756

Pareto optimality in house allocation problems
Abraham,D.J. Cechlarova,K. Manlove,D.F. Mehlhorn,K.

Publication Type: Conference Proceedings
Appeared in: Proceedings of ISAAC 2004: The 15th Annual International Symposium on Algorithms and Computation, volume 3341 of Lecture Notes in Computer Science
Page Numbers : 3-15
Publisher: Springer Verlag
Year: 2004

URL: This publication is available at this URL.

Note: (c) Springer-Verlag


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.

PDF Bibtex entry Endnote XML