def. Stable Marriage Problem. Given equal number of heterosexual men and women, where each person has ranked all members of the opposite sex in order of preference, how can we marry the men and women together such that there are no non-married pair who would both marry each other than their current partners (=in a unstable marriage)?


  • Resident—hospital matching
  • high school—student matching

def. Gale–Shapely Stable Matching Algorithm (GSSMA) (=propose-accept algorithm)

  • Every day…
    • Each man who isn’t engaged proposes to their top women that didn’t reject them before
    • Every women who gets proposed to by
      • …if they’re already engaged to some : accept , reject everybody else.
      • …if they’re not engaged to some : accept , reject everybody else
  • Repeat until completes

thm. (GS always terminates at full matching) Lemma. If woman rejects man , in all future scenarios is engaged to who she likes better than . Proof by Contradiction. Suppose there is a man who is not matched; i.e. is rejected by everybody.

  • By the lemma, all women are engaged to somebody better than .
  • But if all women are engaged, and there are equal number of men and women, cannot exist.

thm. (GS matching is stable) Proof by contradiction. Assume there exists an unstable match , but and :

  • must have proposed to and been rejected before proposing to by the structure of the algorithm
  • By lemma above, ’s final fiancé, , must have been preferable to . But this is not true. This is a contradiction.

def. Valid Partner. is a valid partner of if there exists any stable matching where is a match (doesn’t have to be found by GS).

thm. (Proposer wins in GS). GS where men propose, men get the best valid partner possible. In other words all men with their set of valid partners , never get rejected by any women in . Proof by Contradiction. Assume there exists a valid rejection of a man’s proposal by a woman. Consider the first timepoint when a man gets rejected by a valid partner .

  • must have rejected because she is already engaged with who she prefers more. (‡)
  • is engaged to man . ’s most preferred partner in is by definition of this timepoint (†) Now, consider a completely different stable match (not by GS). There must exist a stable matching where is a match because is a valid partner of . In this matching, let be ’s match. Now, is not the most preferred valid partner because prefers the most, as we saw in (†). also is unsatisfied with because she prefers more (‡). Therefore this is not a stable matching; this is a contradiction.

Remark. Extensions of this stable matching problem is done in CS535 HW5.