The number of stable matchings in models of the Gale-Shapley type with preferences given by partial orders
Journal Title: Operations Research and Decisions - Year 2015, Vol 25, Issue 1
Abstract
From the famous Gale–Shapley theorem we know that each classical marriage problem admits at least one stable matching. This fact has inspired researchers to search for the maximum number of possible stable matchings, which is equivalent to finding the minimum number of unstable matchings among all such problems of size n. In this paper, we deal with this issue for the Gale–Shapley model with preferences represented by arbitrary partial orders. Also, we discuss this model in the context of the classical Gale–Shapley model.
Authors and Affiliations
Ewa DRGAS-BURCHARDT
Keywords
Related Articles
- EP ID EP323587
- DOI -
- Views 38
- Downloads 0
Probabilistic characteristics supporting the management of a production-supply system
The construction of a model and quantitative measures have been presented aimed at improving the efficiency of a production-supply system described by a three-dimensional stochastic process. For this purpose, the laws go...
Branch and bound algorithm for discrete multi- level linear fractional programming problem
An algorithm is proposed to find an integer solution for bilevel linear fractional programming problem with discrete variables. The method develops a cut that removes the integer solutions which are not bilevel feasible....
A game theoretical study of generalised trust and reciprocation in Poland: II. A description of the study group
The first article describing this project presented the three games that the participants played: the Ultimatum Game, the Trust Game and the Public Goods Game. This article describes the study group on the basis of a que...
A multifaceted analysis of the electoral system of the Republic of Suriname
The electoral system of Suriname has been analyzed. Suriname has a unicameral parliament, the National Assembly. The 51 seats of the National Assembly are distributed among 10 districts. There are large discrepancies bet...
Perturbation algorithm for a minimax regret minimum spanning tree problem
The problem of finding a robust spanning tree has been analysed. The problem consists of determining a minimum spanning tree of a graph with uncertain edge costs. We should determine a spanning tree that minimizes the di...