Many-to-One Popular Matchings with Two-Sided Preferences and One-Sided Ties

摘要

We consider the problem of assigning applicants to posts when each applicant has a strict preference ordering over a subset of posts, and each post has all its neighbors in a single tie. That is, a post is indifferent amongst all its neighbours. Each post has a capacity denoting the maximum number of applicants that can be assigned to it. An assignment M, referred to as a matching, is said to be popular, if there is no other assignment M' such that the number of votes M' gets compared to M is more than the number of votes M gets compared to M'. Here votes are cast by applicants and posts for comparing M and M'. An applicant a votes for M over M' if a gets a more preferred partner in M than in A/'. A post p votes for M over M' if p gets more applicants assigned to it in M than in M'. The number of votes a post p casts gives rise to two models. Let M(p) denote the set of applicants p gets in M. If |M(p)| > |M'(p)|, p can cast |M(p)| - |M'(p)|-many votes in favor of M, or just one vote. The two models are referred to as the multi-vote model and one-vote model in this paper. We give a polynomial-time algorithm to determine the existence of a popular matching in the multi-vote model, and to output one if it exists. We give interesting connections between the two models. In particular, we show that a matching that is popular in the one-vote model is also popular in the multi-vote model, however the converse is not true. We also give a polynomial-time algorithm to check if a given matching is popular in the one-vote model, and if not, then output a more popular matching.