| Title | : | Many-to-one Popular Matchings with Two-sided Preferences and One-sided Ties. |
| Speaker | : | Tenkayya Gari Pradeep Reddy (IITM) |
| Details | : | Wed, 12 Jun, 2019 11:00 AM @ A M Turing Hall |
| Abstract: | : | 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. 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 M0 such that the number of votes M0 gets compared to M is more than the number of votes M gets compared to M0 . Here votes are cast by applicants and posts for comparing M and M0 . An applicant a votes for M over M0 if a gets a more preferred partner in M than in M0 . A post p votes for M over M0 if p gets more applicants assigned to it in M than in M0 . The number of votes a post p casts gives rise to two models. If |M(p)| > |M0 (p)|, p can cast |M(p)|−|M0 (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. Here M(p) denotes the set of applicants p gets in M. 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. A paper based on this work co-authored by Kavitha Gopal, Meghana Nasre, Prajakta Nimbhorkar, and T Pradeep Reddy has been accepted for oral presentation at the 25th International Computing and Combinatorics Conference (COCOON 2019). |
