Bitte verwenden Sie diesen Link, um diese Publikation zu zitieren, oder auf sie als Internetquelle zu verweisen: https://hdl.handle.net/10419/222072 
Erscheinungsjahr: 
2020
Schriftenreihe/Nr.: 
CERS-IE Working Papers No. CERS-IE WP - 2020/3
Verlag: 
Hungarian Academy of Sciences, Institute of Economics, Centre for Economic and Regional Studies, Budapest
Zusammenfassung: 
An instance of the marriage problem is given by a graph G together with, for each vertex of G, a strict preference order over its neighbors. A matching M of G is popular in the marriage instance if M does not lose a head-to-head election against any matching where vertices are voters. Every stable matching is a min-size popular matching; another subclass of popular matchings that always exist and can be easily computed is the set of dominant matchings. A popular matching M is dominant if M wins the head-to-head election against any larger matching. Thus every dominant matching is a max-size popular matching and it is known that the set of dominant matchings is the linear image of the set of stable matchings in an auxiliary graph. Results from the literature seem to suggest that stable and dominant matchings behave, from a complexity theory point of view, in a very similar manner within the class of popular matchings.
Schlagwörter: 
popular matching
NP-completeness
polynomial algorithm
stable matching
JEL: 
C63
C78
Dokumentart: 
Working Paper

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





Publikationen in EconStor sind urheberrechtlich geschützt.