Popular Matchings
Authors:
- David J. AbrahamDADavid J. Abraham
- Robert W. IrvingRIRobert W. Irving
- Telikepalli KavithaTKTelikepalli Kavitha
- Kurt MehlhornKMKurt Mehlhorn
- 1 January 2007
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 37 (4) , 1030-1045
Abstract
We consider the problem of matching a set of applicants to a set of posts, where each applicant has a preference list, ranking a nonempty subset of posts in order of preference, possibly involving ties. We say that a matching M is popular if there is no matching $M'$ such that the number of applicants preferring $M'$ to M exceeds the number of applicants preferring M to $M'$. In this paper, we give the first polynomial-time algorithms to determine if an instance admits a popular matching and to find a largest such matching, if one exists. For the special case in which every preference list is strictly ordered (i.e., contains no ties), we give an $O(n + m)$ time algorithm, where n is the total number of applicants and posts and m is the total length of all of the preference lists. For the general case in which preference lists may contain ties, we give an $O(\sqrt{n}m)$ time algorithm.
Keywords
This publication has 18 references indexed in Scilit:
- Rank-maximal matchingsACM Transactions on Algorithms, 2006
- Random Serial Dictatorship and the Core from Random Endowments in House Allocation ProblemsEconometrica, 1998
- Residence exchange wanted: A stable residence exchange problemEuropean Journal of Operational Research, 1996
- On a conjecture by gale about one-sided matching problemsJournal of Economic Theory, 1990
- The Efficient Allocation of Individuals to PositionsJournal of Political Economy, 1979
- Weak versus strong domination in a market with indivisible goodsJournal of Mathematical Economics, 1977
- Match making: Assignments based on bilateral preferencesSystems Research and Behavioral Science, 1975
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite GraphsSIAM Journal on Computing, 1973
- College Admissions and the Stability of MarriageThe American Mathematical Monthly, 1962
- On Representatives of SubsetsJournal of the London Mathematical Society, 1935