Popular Sets of Matching for Instances with Uniform Permutations of Preferences
Date Issued
2015
Date
2015
Author(s)
Chen, Chieh-Yu
Abstract
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.
Subjects
matchings
popular matchings
one-sided preference lists
bipartite graphs
permutation
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-104-R94922054-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):bd0475fe75df542f3d96299a86c8f196