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 fiancé 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.

Pf. (by contradiction)

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.

Pf. (by contradiction)

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.

Proof. (by contradiction)

\(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^*\).

Pf. (by contradiction)

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.

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *