Many-to-One Popular Matchings with Two-Sided Preferences and One-Sided Ties
| Autor: | Kavitha Gopal, T. Pradeep Reddy, Meghana Nasre, Prajakta Nimbhorkar |
|---|---|
| Rok vydání: | 2019 |
| Předmět: | |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783030261757 COCOON |
| Popis: | 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 \(|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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|