Abstract
Let I be a stable matching instance with N stable matchings. For each man m, order his N stable partners from his most preferred to his least preferred. Denote the ith woman in his sorted list as p i (m). Let α i consist of the man-woman pairs where each man m is matched to p i (m). Teo and Sethuraman proved this surprising result: for i = 1 to N, not only is α i a matching, it is also stable. The α i ’s are called the generalized median stable matchings of I.
In this paper, we present a new characterization of these stable matchings that is solely based on I’s rotation poset. We then prove the following: when i = O(logn), where n is the number of men, α i can be found efficiently; but when i is a constant fraction of N, finding α i is NP-hard. We also consider what it means to approximate the median stable matching of I, and present results for this problem.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abdulkadiroglu, A., Pathak, P., Roth, A.: The New York City high school match. American Economic Review, Papers and Proceedings 95, 364–367 (2005)
Abdulkadiroglu, A., Pathak, P., Roth, A., Sönmez, T.: The Boston public school match. American Economic Review, Papers and Proceedings 95, 368–371 (2005)
Blair, C.: Every finite distributive lattice is a set of stable matchings. Journal of Combinatorial Theory A 37, 353–356 (1984)
Fleiner, T.: A fixed-point approach to stable matchings and some applications. Mathematics of Operations Research 28, 103–126 (2003)
Gale, D., Shapley, L.: College admissions and the stability of marriage. American Mathematical Monthly 69, 9–15 (1962)
Gusfield, D.: Three fast algorithms for four problems in stable marriage. SIAM Journal on Computing 16, 111–128 (1987)
Gusfield, D., Irving, R.: The Stable Marriage Problem: Structure and Algorithms. The MIT Press, Cambridge (1989)
Irving, R., Leather, P.: The complexity of counting stable marriages. SIAM Journal on Computing 15, 655–667 (1986)
Irving, R., Leather, P., Gusfield, D.: An efficient algorithm for the optimal stable marriage. Journal of the ACM 34, 532–544 (1987)
Klaus, B., Klijn, F.: Median stable matchings for college admissions. International Journal of Game Theory 34, 1–11 (2006)
Klaus, B., Klijn, F.: Procedurally fair and stable matching. Economic Theory 27, 431–447 (2006)
Knuth, D.: Mariages Stables. Les Presses de l’Université de Montréal (1976)
Provan, J., Ball, M.: The complexity of counting cuts and of computing the probability that a graph is connected. SIAM Journal on Computing 12, 777–788 (1983)
Roth, A., Peranson, E.: The redesign of the matching market of American physicians: Some engineering aspects of economic design. American Economic Review 89, 748–780 (1999)
Teo, C.-P., Sethuraman, J.: The geometry of fractional stable matchings and its applications. Mathematics of Operations Research 23, 874–891 (1998)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cheng, C.T. (2008). The Generalized Median Stable Matchings: Finding Them Is Not That Easy. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds) LATIN 2008: Theoretical Informatics. LATIN 2008. Lecture Notes in Computer Science, vol 4957. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78773-0_49
Download citation
DOI: https://doi.org/10.1007/978-3-540-78773-0_49
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-78772-3
Online ISBN: 978-3-540-78773-0
eBook Packages: Computer ScienceComputer Science (R0)