Skip to main content Link Menu Expand (external link) Document Search Copy Copied

CSE 421

Lecture 1 - Sept 27

  • Stable matching: think about matching residents to hospitals
    • Unstable pair: two people prefer someone over their current partner
      • Applicant $x$ prefers hospital $y$ to their current one
      • Hospital $y$ prefers applicant $x$ to one of their own
    • Stable assignment: no unstable pairs
      • This is always prefered!
      • No joint action to switch partners
      • There is always a stable assignment
  • Finding a stable matching is the stable matching problem
  • Simple stable matching problem:
    • Two groups of $n$ people, match them
    • Participants rate members of each other group in order of preference
  • Perfect matching: everyone is matched to prcisely one person from the other group
  • Stable roommate problem, ranking within only one group
    • Stable matchings do not always exist
  • Propose-And-Reject algorithm:
    • Proposer group, receiver group
    • Keep proposing until they get accepted
    • $O(n^2)$ based on the fact that proposals are never repeated
      • Once someone gets to the last person on their list, all of $r$ has been proposed to
      • As people in $r$ always stay together once proposed to, all of $r$ has a match
      • As all of $r$ has a match, all of $p$ also has a match!

Lecture 2 - Sept 29

  • Gale-Shapley algorithm will always find a stable matching
  • Brute-force of stable matching is $O(n!)$
  • How to implement (and make each iteration $O(1)$):
    • Maintain a list of free proposers
    • Maintain two arrays of matched proposers and recievers
    • Maintain an array of the number of times a proposer has proposed
    • Use an inverse list for the preferences of the recievers
      • $O(n^2)$ to create these
      • Switch indexes and values
  • Proposer-optimal assignment: proposers get their best valid partner
  • Gale-Shapley is proposer-optimal and reciever-pessimal