Why is stable matching important?: so we don’t have a situation that could spiral out of control, with one person/object/etc. throwing off another object which throws off another object, etc.
How should you initially approach complex problems, especially matching ones?: creating a “bare-bones” version of the problem (ex: simplify the recruitment process to only look at ONE company looking to hire ONE candidate from a set of n applicants)
Defining instability for this problem: when a woman in one marriage prefers a man in a different marriage to her current husband, and the man also prefers that woman over his own wife → infidelity, marriage falling apart, spiraling out of control as the abandoned spouses seek new mates
Matching set = a set in which each member of each group (each male and each female) appear in at most one pair
Perfect matching = when each male and each female appear in exactly one pair
Defining stable for this problem: A matching set is stable if
It is perfect (as defined above)
There is no instability (as defined above)
How the algorithm works:
Participants rank members of the opposite sex in order of preference
While each man is free and hasn’t proposed to every woman…
A man proposes to the woman that is highest ranked on his list that he hasn’t proposed to yet
If the woman is single, she must accept; if she is engaged but prefers this new engagement more, she’ll dump her original engagement; if she prefers her existing arrangement, she will deny the proposal and the man will then ask his next favorite choice
Analyzing the algorithm: 3 observations
Any woman’s partner = the highest-ranked man who’s proposed to her up to that point (her partner’s will only increase in preference ranking over the execution of the algorithm)
A woman’s state can go from single to engaged, but not back to single (unlike the males)
A man has a higher chance of getting who he wants than a woman since he asks first, but he is also able to be bumped out of his engagement, forcing him to enter one he doesn’t prefer as much (he can only downgrade)
Does the algorithm terminate?: Yes. There are only n^2 possible proposals → O(n^2)
Proving perfection by contradiction
Remember that a “perfect match” is one in which everyone ends up in a single monogamous relationship
So the claim we’re trying to prove wrong = “not all men and women get matched”
Suppose some man and some woman weren’t matched before the algorithm terminated
By observation 2, the woman was never proposed to (since she would have had to remain single if she had)
However, if the loop terminated, it means that the last man standing must have either gotten engaged or proposed to each woman (by definition of the loop)
Contradiction: how could he have proposed to everyone, whereas the woman never got a proposal?
Every execution of the G-S algorithm yields the same matching set S