Bitte verwenden Sie diesen Link, um diese Publikation zu zitieren, oder auf sie als Internetquelle zu verweisen: https://hdl.handle.net/10419/222075 
Erscheinungsjahr: 
2020
Schriftenreihe/Nr.: 
CERS-IE Working Papers No. CERS-IE WP - 2020/6
Verlag: 
Hungarian Academy of Sciences, Institute of Economics, Centre for Economic and Regional Studies, Budapest
Zusammenfassung: 
We study the classical, two-sided stable marriage problem under pairwise preferences. In the most generalsetting, agents are allowed to express their preferences as comparisons of any two of their edges and they alsohave the right to declare a draw or even withdraw from such a comparison. This freedom isthen graduallyrestricted as we specify six stages of orderedness in the preferences, ending with the classical case of strictlyordered lists.We study all cases occurring when combining the three known notions of stability - weak, strongand super-stability - under the assumption that each side of the bipartite market obtains one of the six degreesof orderedness. By designing three polynomial algorithms and two NP-completeness proofs we determinethe complexity of all cases not yet known, and thus give an exact boundary in terms of preference structurebetween tractable and intractable cases.
Schlagwörter: 
stable marriage
intransitivity
acyclic preferences
poset
weakly stable matching
strongly stable matching
super stable matching
JEL: 
C63
C78
Dokumentart: 
Working Paper

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





Publikationen in EconStor sind urheberrechtlich geschützt.