# Stable Matching

## Definition

Goal: Given n men and n women, find a "suitable" matching.

• Participants rate members of opposite sex.
• Each man lists women in order of preference from best to worst.
• Each woman lists men in order of preference from best to worst.

Unstable pair: applicant x and hospital y are unstable if:

• x prefers y to its assigned hospital
• y prefers x to one of its admitted students.

Stable assignment: Assignment with no unstable pairs.

• Natural and desirable condition.
• Individual self-interest will prevent any applicant/hospital deal from being made.

Perfect matching: everyone is matched monogamously

• Each man gets exactly one woman.
• Each woman gets exactly one man.

Stability：no incentive for some pair of participants to undermine assignment by joint action。

• In matching M, an unmatched pair m-w is unstable if man m and woman w prefer each other to current partners.
• Unstable pair m-w could each improve by eloping.

Stable matching：perfect matching with no unstable pairs.

Stable matching problem: Given the preference lists of n men and n women, find a stable matching if one exists.

Stable roommate problem：

• 2n people; each person ranks others from 1 to 2n-1.
• Assign roommate pairs so that no unstable pairs.

## Gale-Shapley Algorithm

``````Initialize each person to be free.
while (some man is free and hasn't proposed to every woman) {
Choose such a man m
w = 1st woman on m's list to whom m has not yet proposed
if (w is free)
assign m and w to be engaged
else if (w prefers m to her fiancé m')
assign m and w to be engaged, and m' to be free
else
w rejects m
}

``````

## Proof of Correctness

### Termination

Observation:

• Men propose to women in decreasing order of preference
• Once a woman is matched, she never becomes unmatched; she only "trades up."

Claim: Algorithm terminates after at most \$n^2\$ iterations of while loop.

Each time through the while loop a man proposes to a new woman. There are only n2 possible proposals.

### Perfection

Claim. All men and women get matched.

• Suppose, for sake of contradiction, that Zeus is not matched upontermination of algorithm.
• Then some woman, say Amy, is not matched upon termination.
• By Observation 2, Amy was never proposed to.
• But, Zeus proposes to everyone, since he ends up unmatched. ▪

### Stability

Claim. No unstable pairs.

• Suppose A-Z is an unstable pair: each prefers each other topartner in Gale-Shapley matching S*.
• Case 1: Z never proposed to A.
• Z prefers his GS partner to A.
• A-Z is stable.
• Case 2: Z proposed to A.
• A rejected Z (right away or later)
• A prefers her GS partner to Z.
• A-Z is stable.
• In either case A-Z is stable, a contradiction. ▪

## Efficient Implementation

Representing men and women：

• Assume men are named 1, …, n.
• Assume women are named 1', …, n'.

Engagements：

• Maintain a list of free men, e.g., in a queue
• Maintain two arrays `wife[m]`, and `husband[w]`.
• set entry to 0 if unmatched
• if m matched to w then wife[m]=w and husband[w]=m

Men proposing:

• For each man, maintain a list of women, ordered by preference
• Maintain an array `count[m]` that counts the number of proposalsmade by man `m`.

Women rejecting/accepting：

• For each woman, create inverse of preference list of men.
• Constant time access for each query after O(n) preprocessing.

## Other Understanding

1. 对于解不唯一的样例，Gale-Shapley 算法总会给出相同的匹配吗？
• valid partner: Man m is a valid partner of woman w if there exists some stablematching in which they are matched.
• Man-optimal assignment: Each man receives best valid partner.

All executions of GS yield man-optimal assignment, which is a stable matching.

### Man Optimality

Claim. _GS matching S is man-optimal._*

1. (S* ) Suppose some man is paired with someone other than bestpartner. Men propose in decreasing order of preference  someman is rejected by valid partner.
2. (S* ) Let Y be **first** such man, and let A be **first** valid woman that rejects him.
3. Let S be a stable matching where A and Y are matched.
4. (S* ) **When Y is rejected, A forms (or reaffirms) engagement with a man, say Z, whom she prefers to Y**.
5. Let B be Z's partner in S.
6. (S* ) Z not rejected by any valid partner at the point when Y is rejected by A. Thus, **Z prefers A to B**. (2,4)
7. (S* ) But **A prefers Z to Y**. (4)
8. Thus A-Z is unstable in S.

### Woman Pessimality

• Woman-pessimal assignment. Each woman receives worst valid partner.

Claim. GS finds woman-pessimal stable matching S*

Pf.

1. Suppose A-Z matched in S*, but Z is not worst valid partner for A.
2. There exists stable matching S in which A is paired with a man, sayY, whom she likes less than Z.
3. Let B be Z's partner in S.
4. Z prefers A to B (in S*. A and B are both valid partners). [man-optimality]
5. Thus, A-Z is an unstable in S