A Survey of the Stable Marriage Problem and Its Variants

The stable marriage problem is to find a matching between men and women, considering preference lists in which each person expresses his/her preference over the members of the opposite gender. The output matching must be stable, which intuitively means that there is no man- woman pair both of which...

Full description

Saved in:
Bibliographic Details
Main Authors: Iwama, K., Miyazaki, S.
Format: Conference Proceeding
Language:English
Subjects:
Application software
Bipartite graph
Computer science
Game theory
History
Hospitals
Impedance matching
Informatics
matching
Mathematics
Samarium
stable marriage
stable matching
stable roommates
Citations: Items that cite this one
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The stable marriage problem is to find a matching between men and women, considering preference lists in which each person expresses his/her preference over the members of the opposite gender. The output matching must be stable, which intuitively means that there is no man- woman pair both of which have incentive to elope. This problem was introduced in 1962 in the seminal paper of Gale and Shapley, and has attracted researchers in several areas, including mathematics, economics, game theory, computer science, etc. This paper introduces old and recent results on the stable marriage problem and some other related problems.
DOI:10.1109/ICKS.2008.7