Journal of Dynamics and Games (JDG)

Finding all stable matchings with couples

Pages: 321 - 330, Volume 2, Issue 3/4, July/October 2015      doi:10.3934/jdg.2015008

       Abstract        References        Full Text (356.5K)       Related Articles       

Fuhito Kojima - Department of Economics, Stanford University, 579 Serra Mall, Stanford, CA 94305, United States (email)

Abstract: In two-sided matching markets in which some doctors form couples, a stable matching does not necessarily exist. We characterize the set of stable matchings as the fixed points of a function that is reminiscent of a t√Ętonnement process. Then we show that this function is monotone decreasing with respect to a certain partial order. Based on these results, we present an algorithm that finds all the stable matchings whenever one exists, and otherwise demonstrates that there is no stable matching.

Keywords:  Two-sided matching, stability, couples, algorithm, fixed point.
Mathematics Subject Classification:  Primary: 91B68; Secondary: 91A12.

Received: April 2015;      Revised: May 2015;      Available Online: November 25 2015.