Popular Matchings

Authors:
  • DADavid J. Abraham
    David J. Abraham
  • RIRobert W. Irving
    Robert W. Irving
  • TKTelikepalli Kavitha
    Telikepalli Kavitha
  • KMKurt Mehlhorn
    Kurt Mehlhorn

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.

This publication has 18 references indexed in Scilit: