We study the problem of matching applicants to jobs under one-sided preferences; that is, each applicant ranks a non-empty
subset of jobs under an order of preference, possibly involving ties. A matching
M is said to be
more popular than
T if the applicants that prefer
M to
T outnumber those that prefer
T to
M. A matching is said to be
popular if there is no matching more popular than it. Equivalently, a matching
M is popular if
φ(
M,
T) ≥
φ(
T,
M) for all matchings
T, where
φ(
X,
Y) is the number of applicants that prefer
X to
Y.
Previously studied solution concepts based on the popularity criterion are either not guaranteed to exist for every instance
(e.g., popular matchings) or are NP-hard to compute (e.g., least unpopular matchings). This paper addresses this issue by
considering mixed matchings. A mixed matching is simply a probability distributions over matchings in the input graph. The function φ that compares two matchings generalizes in a natural manner to mixed matchings by taking expectation. A mixed matching P is popular if φ(P,Q) ≥ φ(Q,P) for all mixed matchings Q.
We show that popular mixed matchings always exist and we design polynomial time algorithms for finding them. Then we study their efficiency and give tight bounds on
the price of anarchy and price of stability of the popular matching problem.
The second author was supported by an Alexander von Humboldt Fellowship. Part of this work was done when the first author
visited MPI für Informatik through the DST-MPG partner group on Efficient Graph Algorithms, IISc Bangalore.