This is an old revision of the document!
Chapter One
The Stable matching problem originated in 1962 when two mathematical economists David Gale and Lloyd Shapley asked if one could design a college admissions process,or job recruiting process that was self-enforcing. The goal would be to get a stable outcome where both applicants and recruiters would be happy.To solve the problem, Gale and Shapley simplified it to the problem of devising a system by which each n men and n women can end up getting married. In this case, two genders represent the applicants and the companies, and everyone is seeking to be paired with exactly one individual of the opposite gender.
With a set of M men and a set W of women,a matching S is a set of ordered pairs,each member of the pair coming from one of the two sets.A perfect matching S' is a matching where each member of M and each member of W appears in exactly one pair in S'. Each individual in one set has ordered rankings of individuals in the other set called preference list. If there are two pairs (m,w) and (m',w') in S where m prefers w' to w and w' prefers m to m', the pair (m,w') is an instability to S. A matching S is stable if it is perfect and there is no instability with respect to S. So the goal of the problem is to find a set of marriages with no instabilities.
The Algorithm
- Initially everyone is unmarried.When a single man m chooses the woman w who ranks highest on his preference list and proposes to her, the pair (m,w) enter an intermediate state: engagement.
