Please use this identifier to cite or link to this item: https://hdl.handle.net/10419/222075 
Year of Publication: 
2020
Series/Report no.: 
CERS-IE Working Papers No. CERS-IE WP - 2020/6
Publisher: 
Hungarian Academy of Sciences, Institute of Economics, Centre for Economic and Regional Studies, Budapest
Abstract: 
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.
Subjects: 
stable marriage
intransitivity
acyclic preferences
poset
weakly stable matching
strongly stable matching
super stable matching
JEL: 
C63
C78
Document Type: 
Working Paper

Files in This Item:
File
Size
957.33 kB





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.