2020/07/14 by Vijay K. Garg, Garg, Vijay Kumar, Changyong Hu +1 · 1 citation
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Complexity and Algorithms in Graphs #Computer Science and Game Theory (cs.GT) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.2007.07121
openalex publication_date 2020/07/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The stable marriage problem requires one to find a marriage with no blocking pair. Given a matching that is not stable, Roth and Vande Vate have shown that there exists a sequence of matchings that leads to a stable matching in which each successive matching is obtained by satisfying a blocking pair. The sequence produced by Roth and Vande Vate's algorithm is of length O(n3) where n is the number of men (and women). In this paper, we present an algorithm that achieves stability in a sequence of matchings of length O(n2). We also give an efficient algorithm to find the stable matching closest to the given initial matching under an appropriate distance function between matchings.