Arbeitspapier
Pairwise preferences in the stable marriage problem
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.
- Sprache
-
Englisch
- Erschienen in
-
Series: CERS-IE Working Papers ; No. CERS-IE WP - 2020/6
- Klassifikation
-
Wirtschaft
Computational Techniques; Simulation Modeling
Bargaining Theory; Matching Theory
- Thema
-
stable marriage
intransitivity
acyclic preferences
poset
weakly stable matching
strongly stable matching
super stable matching
- Ereignis
-
Geistige Schöpfung
- (wer)
-
Cseh, Ágnes
Juhos, Attila
- Ereignis
-
Veröffentlichung
- (wer)
-
Hungarian Academy of Sciences, Institute of Economics, Centre for Economic and Regional Studies
- (wo)
-
Budapest
- (wann)
-
2020
- Handle
- Letzte Aktualisierung
-
10.03.2025, 11:41 MEZ
Datenpartner
ZBW - Deutsche Zentralbibliothek für Wirtschaftswissenschaften - Leibniz-Informationszentrum Wirtschaft. Bei Fragen zum Objekt wenden Sie sich bitte an den Datenpartner.
Objekttyp
- Arbeitspapier
Beteiligte
- Cseh, Ágnes
- Juhos, Attila
- Hungarian Academy of Sciences, Institute of Economics, Centre for Economic and Regional Studies
Entstanden
- 2020
Ähnliche Objekte (12)
Pairwise stable matching in large economies
Pairwise stable networks in homogeneous societies
The computation of pairwise stable networks
Stable Matchings for a Generalised Marriage Problem
Correction to: The computation of pairwise stable networks
The stable marriage problem with ties and restricted edges
Stable matchings beyond stable marriage: models, algorithms, complexity
Household consumption when marriage is stable
Stable marriage and roommates problems with restricted edges: complexity and approximability
Pairwise classification and pairwise support vector machines
Pairwise Classification and Pairwise Support Vector Machines
Solving routing problems with pairwise synchronization constraints
Pairwise stable matching in large economies
Pairwise stable networks in homogeneous societies
The computation of pairwise stable networks
Stable Matchings for a Generalised Marriage Problem
Correction to: The computation of pairwise stable networks
The stable marriage problem with ties and restricted edges
Stable matchings beyond stable marriage: models, algorithms, complexity
Household consumption when marriage is stable
Stable marriage and roommates problems with restricted edges: complexity and approximability
Pairwise classification and pairwise support vector machines
Pairwise Classification and Pairwise Support Vector Machines
Solving routing problems with pairwise synchronization constraints
Pairwise stable matching in large economies
Pairwise stable networks in homogeneous societies
The computation of pairwise stable networks
Stable Matchings for a Generalised Marriage Problem
Correction to: The computation of pairwise stable networks
The stable marriage problem with ties and restricted edges
Stable matchings beyond stable marriage: models, algorithms, complexity
Household consumption when marriage is stable
Stable marriage and roommates problems with restricted edges: complexity and approximability
Pairwise classification and pairwise support vector machines
Pairwise Classification and Pairwise Support Vector Machines