Stable Matching

Created

Stable Matching Hospital Problem

Given a set of nn hospitals HH and a set of nn students SS. This means there is one student per hospital.

  • Each hospital h∈Hh \in H ranks students.
  • Each student s∈Ss \in S ranks hospitals.

Goal: We want to design a self-reinforcing admissions process.

A hospital hh and student ss form an unstable pair if both conditions are true:

  • hh prefers ss to one of its admitted students
  • ss prefers hh to assigned hospital

A stable assignment is one with no unstable pairs. This is the natural and desirable condition. Individual self-interest prevets any hospital-student side deal.

A matching MM is a set of ordered pairs h−sh-s.

  • Each hospital h∈Hh \in H appears in at most one pair of MM.
  • Each studnet s∈Ss \in S appears in at most one pair of MM.

A matching MM is perfect if ∣M∣=∣H∣=∣S∣=n|M| = |H| = |S| = n.

Given a perfect matching MM, hospital hh and student ss form an unstable pair if both:

  • hh prefers ss to matched student
  • ss prefers hh to matched hospital

An unstable pair h−sh-s could each improve by joint action.

A stable matching is a perfect matching with no unstable pairs.

  • E.g., M={A−X,B−Y,C−Z}M = \{ A-X, B-Y, C-Z\}
  • Stable matching need not exist

Gale-Shapley Algorithm

The Gale-Shapley deferred acceptance algorithm is an intuition method that guarantees to find a stable matching.

Gale-Shapley Algorithm (preference lists for hospitals and students) Initialize MM to empty matching. While (some hospital hh is unmatched and hasn’t proposed to every student) ss is the first student in hh’s list whom hh has not yet proposed. If (ss is unmatched) Add h−sh-s to matching MM. Else if (ss prefers hh to current partner h’h’) Replace h’−sh’-s with the h−sh-s in matching MM. Else ss rejects hh. Return stable matching MM

Proofs

There are a few proofs we can observe.

  • Observation 1: hospitals propose to students in decreasing order of preference
  • Observation 2: once a student is matched, the student never becomes unmatched; only “trades up”

(1) Proof of correctness: termination.

  • Claim: algorithm terminates after at most n2n^2 iterations of the while loop.
  • Proof: each time throught he while look, a hospital proposes to a new student. Thus, there are at most n2n^2 possible proposals.

(2) Proof of correctness: perfect matching.

  • Claim: Gale-Shapley outputs a matching

  • Proof: hospital proposes only if unmatched => matched to <= 1 student student keeps only best hospital => matched to <= 1 hospital

  • Claim: In Gale-Shapley matching, all hospitals get matched

  • Proof by contradiction: Suppose, for the sake of contradiciton, that some hospital h∈Hh \in H is unmatched upon termination of Gale-Shapley algorithm. Then some student, say s∈Ss \in S is unmatched upon termination. By Observation 2, ss was never proposed to But, hh proposes to every student, since hh ends up unmatched.

  • Claim: In Gale-Shapley matching, all students get matched.

  • Proof by counting: By previous claim, all nn hospitals get matched. Thus, all nn students get matched.

(3) Proof of correctness: stability.

  • Claim: in gale-shapley matching M∗M*, there are no unstable pairs.

  • Proof: consider any pair h−sh-s that is not in M∗M*.

    • Case 1: hh never proposed to ss. hh prefers its Gale-Shapley partner s′s' to ss. (hospitals propose in decreaseing order of preference) h−sh-s is not ustable
    • Case 2: hh proposed to ss. ss rejected hh (either right away or later) ss prefers Gale-Shapley partner h′h' (students only trade up) to hh h−sh-s is not ustable

    In either case, the pair h−sh-s is not unstable.

Summary:

  • stable matching problem

Hospital Optimality

For a given probelm instance, there may be several stable matchings.

Definition: student ss is a valid partner for hospital hh if there exists any stable matching in which hh and ss are matched.

Hospital-optimal assignment means that each hospital receives best valid partner.

  • is this a perfect matching? is it stable?

Claim: all executions of Gale-Shapley yield hospital-optimal assingment.

  • Collorary: hospital-optimal assignment is a stable matching
  • Proof by contradiction Suppose a hospital is matched with student other than best valid partner. Hospitals propose in decreasing order of preference => some hospital is rejected by a valid partner during gale-shapley. Let hh be the first such hospital, and let ss be the first valid partner that rejects hh. Let MM be a stable matching where hh and ss are matched. When ss rejects hh in Gale-Shapley, ss forms (or re-affirms) commitment to a hospital, say h′h' => ss prefers h′h' to hh. Let s′s' be partner of h′h' in MM. h′h' has not been rejected by any valid partner (including s′s') at the point when hh is rejected by ss (because it is the first rejection). Thus, h′h' had not yet proposed to s′s' when h′h' proposed to ss => h′h' prefers ss to s′s'. Thus, h′−sh'-s is unstable in MM, a contradiction.

Student pessimality: hospital-optimality comes at the expense of the studnets. Student pessimality assignment: each student receives worst valid partner.

Claim: gale-shapley finds student-pessimal stable matching M∗M*.

  • Proof by contradiction: Suppose h-s matched in M∗M* but hh is not the worst valid partner for ss. There exists stable matching MM in which ss is paried with a hospital, say h′h', whom ss prefers less than hh. => ss prefers hh to h′h'. Let s′s' be the partner of hh in M. By hospital-optimality, ss is the best valid partner for hh => hh prefers ss to s′s'. Thus, h−sh-s is an unstable pair in MM, a contradiction.

Context

Extensions to this probelm

  • some agents declare others as unacceptable (med-school student unwilling to work in Cleveland)
  • some hospitals have more than one psoition
  • unequal number of positions and students.

Def: matching MM is unstable if there is a hospital hh and student ss such that

  • hh and ss are acceptable to each other; and
  • either ss is unmatced, or ss prefers hh to assigned hospital; and
  • either hh does not have all its places filled, or hh prefers ss to at least one of its assigned students.

Theorem: there exists a stable matching.

  • proof: straightforward generalization of gale-shapley algorithm.

Linked from Algorithms