Popular Sets of Matching for Instances with Uniform Permutations of Preferences
| Autor: | Chieh-Yu Chen, 陳婕妤 |
|---|---|
| Rok vydání: | 2015 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 103 Popular matching problems have been explored in recent years, as they are highly related to realistic problems that allocate limited resources and taking requesters'' preference in concern. An instance of a popular matching problem consists of n applicants, m posts, and n preference lists which rank the posts for each applicant. A Popular matching M is the one that no other matching is preferred by more applicants when comparing with M. Since popular matching might not exist, we define the popular set S, which gathers a set of matching, such that for any given matching T, there exists a rival matching S in S that S is preferred by at least as many applicants as T. Our inspection focuses on a specialized case that m=n, and all preference lists are the same, each of which ranks all posts and contains no tie. We also compose the {em regular set} Rn, and prove when n is even, Rn is a popular set. For odd n, we show that if a given matching T contains no less than (n-1)/2 negative matches, there is a rival matching against T in the regular set. For further study on the case that n is odd, we also derive auxiliary functions for the regular set, and raise some observations from several different points of view. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|