Skip to main content
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