Header menu link for other important links
Many-to-One Popular Matchings with Two-Sided Preferences and One-Sided Ties
Kavitha Gopal, , T. Pradeep Reddy
Published in Springer Verlag
Volume: 11653 LNCS
Pages: 193 - 205
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 M'. 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 (forumala presented)., 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. © Springer Nature Switzerland AG 2019.
About the journal
JournalData powered by TypesetLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherData powered by TypesetSpringer Verlag
Open AccessNo
Concepts (8)
  •  related image
    Combinatorial mathematics
  •  related image
  •  related image
  •  related image
    Polynomial-time algorithms
  •  related image
  •  related image
    Preference order
  •  related image
  •  related image
    Polynomial approximation