Stable marriage problem

The stable marriage problem refers to the task of finding a stable matching between two sets of individuals based on their preferences, as described by a preference matrix. This problem was first introduced by Gale and Shapley and has since gained attention in various fields due to its relevance in real-world scenarios such as labor market allocation and roommate assignments. It can also be applied to the pairing of solutions in consecutive PSs.From: Network Optimization [2019], A shortlist-based bidirectional local search for the stable marriage problem [2020], Combining mutual information and stable matching strategy for dynamic evolutionary multi-objective optimization [2018]

Network Analysis

View Chapter

Purchase Book

Published in Michael W. Carter, Camille C. Price, Ghaith Rabadi, Operations Research, 2018

Michael W. Carter, Camille C. Price, Ghaith Rabadi

The Hungarian method, when applied to this problem, yields a solution that is in some sense for the collective good of both employees and employers. But what about the individuals or employers who do not get their first or even second choices? The behavioral reaction of these people is dealt with by using a model that is known as the stable marriage problem (so-called because this model hypothetically could be used to represent the preferences of groups of people who are to be matched for marriage) (Knuth 1976).

Matchings in graphs

View Chapter

Purchase Book

Published in V. K. Balakrishnan, Network Optimization, 2019

V. K. Balakrishnan

The stable marriage problem is the problem of finding a stable matching for an arbitrary preference matrix. The constructive proof of Theorem 5.7 gives an iterative algorithm to solve this problem. The matching which results from this ‘propose-and-reject’ algorithm is not only stable but also optimal.

A shortlist-based bidirectional local search for the stable marriage problem

View Article

Journal Information

Published in Journal of Experimental & Theoretical Artificial Intelligence, 2020

Hoang Huu Viet, Le Hong Trang, Le Pham Tuyen, Taechoong Chung

The stable marriage problem was first introduced by Gale and Shapley (Gale & Shapley, 1962), and has recently received a great deal of attention from the research community due to its important role in a wide range of applications such as the Evolution of the Labor Market for Medical Interns and Residents (Roth, 1984), the Student-Project Allocation problem (Abraham, Irving, & Manlove, 2003), and the Stable Roommates problem (Fleiner, Irving, & Manlove, 2007; Irving, 1985).

Stable marriage problem

Explore chapters and articles related to this topic

Network Analysis

Matchings in graphs

A shortlist-based bidirectional local search for the stable marriage problem