Title: Popular Matchings
Speaker: Prof. Kavitha Telikepalli
Affiliation: IISc. Bangalore
Date: February 26, 2009
Abstract:
We consider the problem of matching applicants to jobs under one-sided preferences, that is, each applicant ranks a subset of posts under an order of preference. A matching M is said to be more popular than T if the applicants who prefer M to T outnumber the applicants who prefer T to M. A matching M is popular if there is no matching more popular than M.
We first consider the problem of computing a popular matching and show a simple combinatorial algorithm for this problem. Though popular matchings seem to be a stable answer to the question of how to assign applicants to jobs, this is not a complete answer since there are simple instances that do not admit popular matchings. We address this issue by considering ``mixed matchings'', that is, probability distributions over matchings. We extend the notion of popularity to mixed matchings and show that popular mixed matchings always exist and give polynomial time algorithms for finding them.