### Problem

Input: Two set of equal size + the preferences of each element

Goal: Find a perfect stable matching

We can formulating the problem as a stable marriage problem.

Given $$n$$ men and $$n$$ women, find a stable matching. Each man lists women in order of preference from best to worst. So as each woman.

### Explanation

Perfect: Everyone is matched monogamously.

Unstable pairs: In matching M, an unmatched pair $$m-w$$ if $$m$$ and $$w$$ prefer each other to current partners.

Stability: No unstable pairs.

There can be multiple stable matchings.

Valid partner: Man $$m$$ is a valid partner of woman $$w$$ if there exists some stable matching in which they are matched.

Best valid partner: $$w$$ is defined as the best valid partner for m if she is a valid partner and no $$w’$$ that ranks higher in $$m$$’s list is a vlid partner.

Worst valid partner is defined similarly.

Man-Optimal: Every man gets matched to its best valid partner.

Women-Pessimal: Each woman receives worst valid partner.

### Solution

Propose-and-reject algorithm (G-S)

Input: Preferences Lists of n Men and n Women
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)
m and w become engaged
else if (w prefers m to her fiancé m')
m and w become engaged
m’ becomes free
else
}
w rejects m /* m remains free*/


### Proof

#### 1 Termination

Observation 1. Men propose to women in decreasing order of preference.

Observation 2. Once a woman is matched, she never becomes unmatched.

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

Pf. Each time through the while loop a man proposes to a new woman. There are only $$n^2$$ possible proposals.

#### 2 Perfect

Claim. All men and women get matched.

Suppose, for sake of contradiction, that $$Z$$ is not matched upon termination of algorithm.

Then some woman say $$A$$ is, is not matched upon termination.

By Observation 2, $$A$$ was never proposed to.

But, $$Z$$ proposes to everyone, since he ends up unmatched.

#### 3 Stability

Claim. Any execution of the algorithm does not return unstable pairs.

Suppose $$A-Z$$ is an unstable pair: each prefers each other to partner in G-S matching $$S^*$$.

Case 1: $$Z$$ never proposed to $$A$$. Then $$Z$$ prefers his GS partner to $$A$$. So $$A-Z$$ is stable.

Case 2: $$Z$$ proposed to $$A$$. Then $$A$$ rejected $$Z$$ (right away or later). $$A$$ prefers his GS partner to $$Z$$. $$A-Z$$ is stable.

In either case $$A-Z$$ is stable, a contradiction.

#### 4 Man-Optimality

Claim. GS matching $$S^*$$ is man-optimal.

$$S^*$$: Suppose GS pairs some man with someone other than his best valid partner. Men propose in decreasing order of preference. So some man is rejected by valid partner.

$$S^*$$: Let $$Y$$ be the first such man, and let $$A$$ be first valid woman that rejects him.

$$S^*$$: When $$Y$$ is rejected, $$A$$ forms (or reaffirms) engagement with a man, say Z, whom she prefers to Y.

Let $$S$$ be another stable matching where $$A$$ and $$Y$$ are matched.

$$S$$: Let $$B$$ be $$Z$$’s partner in $$S$$.

$$S^*$$: Z not rejected, by any valid partner at the point when $$Y$$ is rejected by A. Thus, Z prefers A to B.

$$S^*$$: But $$A$$ prefers $$Z$$ to $$Y$$.

$$S$$: Thus $$A-Z$$ is unstable in $$S$$.

#### 5 Woman Pessimality

Claim. GS finds a woman-pessimal stable matching $$S^*$$.

Suppose A-Z matched in $$S^*$$, but $$Z$$ is not worst valid partner for $$A$$.

There exists stable matching $$S$$ in which $$A$$ is paired with a man, say $$Y$$, whom she likes less than $$Z$$.

Let $$B$$ be $$Z$$’s partner in $$S$$.

$$Z$$ prefers $$A$$ to $$B$$.

Thus, $$A-Z$$ is unstable in $$S$$.

### Conclusion

Input includes mens preferences, women’s preferences. The size is $$2n^2$$.

There are $$(n!)^{2n}$$ inputs.

Best case running time: $$n$$

Worst case running time: $$n^2$$

If using a brute force algorithm, all $$n!$$ perfect matchings should be visited. So GS is faster.