The number of stable matchings in models of the Gale-Shapley type with preferences given by partial orders

• Autorzy: Drgas-Burchardt E.

Identyfikatory

DOI

10.5277/ord150101

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

combinatorial problems; stable matching; Gale–Shapley model

• Wydawca: Oficyna Wydawnicza Politechniki Wrocławskiej
• Czasopismo: Operations Research and Decisions
• Rocznik: 2015
• Tom: Vol. 25, No. 1
• Strony: 5--15
• Opis fizyczny: Bibliogr. 10 poz., rys.

Twórcy

autor

Drgas-Burchardt E.

• Faculty of Mathematics, Computer Science and Econometrics, University of Zielona Góra, ul. Prof. Z. Szafrana 4a, 65-516 Zielona Góra, Poland

Bibliografia

• [1] DRGAS-BURCHARDT E., ŚWITALSKI Z., A number of stable matchings in models of the Gale–Shapley type, Discrete Applied Mathematics, 2013, 162 (18), 2932–2936.
• [2] GALE D., SHAPLEY L.S., College Admissions and the Stability of Marriage, American Mathematical Monthly, 1962, 69, 9–15.
• [3] GUSFIELD D., IRVING R.W., The Stable Marriage Problem: Structure and Algorithms, MIT Press, Cambridge, MA, 1989.
• [4] IRVING R.W., LEATHER P., The complexity of counting stable marriages, SIAM Journal on Computing, 1986, 15, 655–667.
• [5] IRVING R.W., Stable marriage and indifference, Discrete Applied Mathematics, 1994, 48, 261–272.
• [6] KNUTH D.E., Mariages Stables, Les Presses de l’Université de Montréal, Montréal 1976.
• [7] MANLOVE D.F., IRVING R.W., IWAMA K., MIYAZAKI S., MORITA Y., Hard variants of stable marriage, Theoretical Computer Science, 2002, 276, 261–279.
• [8] PITTEL B., The Average Number of Stable Matchings, SIAM Journal on Discrete Mathematics, 1989, 2–4, 530–549.
• [9] ROTH A.E., SOTOMAYOR M.A.O., Two-sided matchings, A study in game-theoretic modeling and analysis, Econometric Society Monographs, 18, 2003.
• [10] THURBER E.G., Concerning the maximum number of stable matchings in the stable marriage problem, Discrete Mathematics, 2002, 248, 195–219.