This is an old revision of the document!
Table of Contents
Emily's Journal
The Stable Matching Problem - Gale and Shapely
- design an admissions/recruiting process that was self-enforcing
- based on matching preference lists
- if the process is based on self interests, then there will be situations where people will commit and possibly go back on their commitments if a better offer comes along (retract and redirect)
- question asked: given a list of preferences can we assign applicants to employers so at least one of the following is the case
- the employer prefers one of its accepted applicants to another
- the applicant prefers her current situation over working for another employer
- Formulating the Problem
- to eliminate complications we assume that each n applicants applies to each n companies and each company accepts one applicant → we will use the case of devising a system of matching males and females for marriage
- a matching S is a set of ordered pairs from the sets of M men and W women where each member of M and W appears in at most 1 pair
- a perfect matching S' is a matching where each member of M and W appears in exactly one pair in S'
- there is neither single hood nor polygamy
- each M and W creates a preference list where they rank the opposite gender
- instability a pair is unstable if one of the pair prefers another male/female
- it is possible for an instance to have more than one stable matching
- Designing the Algorithm
- women will naturally accept an engagement even if she prefers another male
- if a free m proposes to a woman w who is already engaged to m', she may accept the proposal from m if he ranks higher than m' on her preference list
- the algorithm will stop when everyone is engaged.
- Analyzing the Algorithm
- from the view of the woman
- once w is engaged she will remain engaged to a sequence of men who get higher on her ranking list as they propose
- from the view of a man
- as m proposes, the sequence of women he proposes to gets lower on his list of ranked women
- maximum iterations needed for termination is n^2
- PROOF:
- measure the progress- way of saying each step of the algorithm brings it closer to termination
- each iteration is a man proposing to a woman he has never proposed to before → P(t) denotes the set of pairs (m,w) where m has proposed to w by the end of the iteration t
- there are only n^2 possible pairs of men and women total so P() can only increase n^2 times over the whole algorithm
- How do we show that the set S at the end of termination is a perfect matching?
- if a man is free at some point during the algorithm then there is a women he has not proposed to
- proof by contradiction
- the set of engaged pairs always forms a perfect matching because the algorithm cannot terminate with a free man
- How do we prove that the algorithm returns a set of stable matching?
- we already know that S is a perfect matching so by way of contradiction we prove that S is a stable matching. (if m did not proposed to w then w' must be higher on his preference list)
- there is an unfairness in the algorithm that favors male preferences over female
- question do all executions of the algorithm yield the same matching? … YES!
- characterize the matching by showing each man gets the “best possible partner”
- a woman, w, is a valid partner for m if there is a stable matching with the pair (m, w)
- the order of the proposals in the algorithm has no effect on the final outcome
- PROOF
- by way of contradiction prove that S' is stable
- in this stable matching each woman is paired with her worst valid partner
