Bitte verwenden Sie diesen Link, um diese Publikation zu zitieren, oder auf sie als Internetquelle zu verweisen: https://hdl.handle.net/10419/190484 
Erscheinungsjahr: 
2017
Schriftenreihe/Nr.: 
IEHAS Discussion Papers No. MT-DP - 2017/23
Verlag: 
Hungarian Academy of Sciences, Institute of Economics, Budapest
Zusammenfassung: 
We are given a bipartite graph G = (A B;E) where each vertex has a preference list ranking its neighbors: in particular, every a A ranks its neighbors in a strict order of preference, whereas the preference list of any b B may contain ties. A matching M is popular if there is no matching M' such that the number of vertices that prefer M' to M exceeds the number of vertices that prefer M to M'. We show that the problem of deciding whether G admits a popular matching or not is NP-hard. This is the case even when every b B either has a strict preference list or puts all its neighbors into a single tie. In contrast, we show that the problem becomes polynomially solvable in the case when each b B puts all its neighbors into a single tie. That is, all neighbors of b are tied in b's list and b desires to be matched to any of them. Our main result is an O(n2) algorithm (where n =Bfor the popular matching problem in this model. Note that this model is quite different from the model where vertices in B have no preferences and do not care whether they are matched or not.
Schlagwörter: 
popular matching
NP-complete
polynomial algorithm
ties
JEL: 
C63
C78
ISBN: 
978-615-5457-13-5
Dokumentart: 
Working Paper

Datei(en):
Datei
Größe
649.79 kB





Publikationen in EconStor sind urheberrechtlich geschützt.