The Stable Marriage Problem

Consider the set M of men and W of women, where |M| = |W| = n, Let M x W be the set of all possible ordered pairs (m, w) where m Î M and w Î W. A matching S is a set of ordered pairs, each from M x W with the property that each member of M and each member of W appears in at most one pair in S. A perfect matching S' is a matching with the property that each member of M and each member of W appears in exactly one pair in S'.

An instability in S' occurs when there exits at least two pairs (m, w) and (m', w') such that m prefers w' to w and w' prefers m to m'.

Given a set of M men and W women and a list of preferences for each m Î M and each w Î W,

· Does there exist a stable matching for every set of preference lists?

· Given a set of preference lists, can we efficiently construct a stable matching if there is one?

Proof that there exists a stable matching for each set of preference lists.

Assume that each man in M and each woman in W ranks their preferences from 1 to n in strictly descending order.

Let the base case be |M| = |W| = 1.

then the pair (m₁, w₁) is the only pair in S' and is stable.

Now assume that there is a stable matching in the subset M' x W' where |M'| = |W'| = n-1

Let m Ï M' and w Ï W'. Then either

1. m prefers w to every other woman in W that ranks him higher than her current match and w prefers m to every man in M that rates her higher than his present partner.
2. m prefers a woman w' to w and w' prefers m to her current partner.
3. w prefers m' to m and m' prefers w to his current partner

If case 1, there is a stable matching in M x W, and existence of such a matching is proved by induction

if case 2. There is a new stable matching of |M' x W'| = n-1 and (m', w) are not included in the matching

if case 3. There is a new stable matching of |M' x W'| = n-1 and (m, w') are not included in the matching

If case 2 or 3, then the three conditions pertain again, but the number of possible alternatives for the unpaired couple is reduced by at least 1 and eventually the remaining man and woman have no better alternative than each other.

This inductive proof points to an algorithm for determining a perfect matching.

The Gale-Shapley Algorithm

Initially all m Î M and allw Î W are free

While there is a man m who is free and hasn't proposed to every woman

Choose such a man m

Let w be the highest-ranked woman on m's preference list

to whom he has not yet proposed

If w is free then (m, w) become engaged

Else w is currently engaged to m'

If w prefers m' to m then m remains free

Else w prefers m to m'

(m, w) become engaged

m' becomes free

Endif

Endif

Endwhile

Return the set S of engaged pairs

Analysis of the Algorithm

1. w remains engaged from the time she receives her first offer, and the sequence of partners to whom she is engaged gets better and better in terms of her preferences.
2. The sequence of women to whom m proposes gets worse and worse in terms of his preferences.

The Gale-Shapley Algorithm terminates after at most n² iterations of the While loop

Let P(t) be the set of pairs (m, w) such that m has proposed to w by the end of iteration t.

We see that P(t) is strictly increasing, but P(t) must always be less than the total number of possible pairs of men and women. The number of possible pairs is n², so this algorithm must have at most n² iterations.

Proof of correctness of Gale-Shapley

Corollary 1. If man m is free at some point in the execution of the algorithm, then there exists some woman to whom he has not yet proposed.

Proof. Suppose there comes a point when m is free, but has proposed to all n women. Then by rule 1 above, all n women are engaged at this point. Since the set orf engaged pairs forms a matching, there must also be n engaged men at this point in time. But there are only n men in total, so this lead to a contradiction.

Corollary 2. The set S returned at termination is a perfect matching.

Proof. The set of engaged pairs always forms a matching. Suppose that the algorithm terminates with a free man m. At termination of the while loop it must be the case that m has already proposed to every woman, else the loop does not terminate. But this contradicts corollary 1 that says there cannot be a free man who has proposed to every woman.

Theorem. An execution of the Gale-Shapley Algorithm returns a set of pairs S that is a stable matching.

By corollary 2, S is a perfect matching. Assume that there is an instability in S. Consider two pairs (m, w) and (m', w') with the properties that

m prefers w' to w, and

w' prefers m to m'

If m were to choose before m', he would select w' before w and she would reject m prime's proposal.

If w' were already engaged to m' when m proposed, she would end her engagement and pair with m.

If m never proposed to w', then he would have proposed to w first contradicting the assumption that he prefers w'.

If he did propose to w' and was rejected, then w' must prefer some man m'' more than m. Man m' is the final partner of w', so either m'' = m', or by property 1 above, w' prefers her final partner m' to m''. Either way we have a contradiction.

Extensions of the Gale-Shapley Algorithm

1. Let |M| = n₁ and |W| = n₂ where n₁ > n₂. Does the algorithm still hold? If not, how must it be modified?
2. Let |M| = n₁ and |W| = n₂ where n₁ < n₂. Does the algorithm still hold? If not, how must it be modified?
3. Suppose that each man only proposed to some subset of all the women. Does the algorithm still hold?
4. Suppose that we allowed the men to be polygamous. Does the algorithm still hold? If not, how must it be modified?

Representative Problems

1. Bipartite matching -- The stable marriage problem is an example of a more general bipartite matching problem in Graph theory. Let G be a graph with two sets of vertices V₁ and V_2, and a set of Edges E on the set V₁ x V₂. Each edge may have an associated weight (such as a preference ranking in the stable marriage problem). We will encounter algorithms for solving the general bipartite matching problem when studying network flow problems.
2. Interval scheduling problem -- example of a greedy algorithm (where the locally best choice is also the optimal choice).
3. Weighted interval scheduling. One example of the interval scheduling problem is: Given a large hall that with a set of events to be scheduled for the hall between a certain period of time. Each of the requesting events has a starting and ending time, and it is the job of the organizers to schedule the maximum number of events during this time period. The selected set may not be unique, but it will be optimal. Scheduling the maximum number of events in the hall is not the same thing as maximizing the utilization of the hall. If we give each of the events a weight (such as the duration of the event in hours), then the weighted interval scheduling problem seeks to find the maximum weight (number of hours) that can be placed in the hall during the time period. Weighted interval scheduling is an example of a problem solved by using dynamic programming.
4. Independent Set -- Given a graph G = (V,E), we say that a set of nodes S Í V is independent if no two nodes in S are joined by an edge. The Independent Set problem encodes any situation in which you are trying to choose from among a collection of objects and there are pairwise conflicts among some of the objects. Interval scheduling and bipartite matching can both be encoded as special cases of the Independent Set Problem. The problem of finding the largest independent set in a graph G belongs to a class of problems known as NP-Complete. There is no known polynomial-time algorithm that solves every instance of Independent Set, but if you supply a solution to the decision problem (A given set is an independent set of size N and the original graph G), that solution can be verified in polynomial time.
5. Competitive Facility Location -- Given a graph that models a weighted set of choices (V) and a set of constraints (E). Competitive Facility Location is a 2 (or more) person game consisting of players P₁ and P₂ alternating moves and selecting nodes (vertices) to maximize their score (competitive advantage). Does either player have a winning strategy based upon starting position or in response to another player's previous move. There is no computationally efficient algorithm to determine if either player has a winning strategy, and it is also computationally difficult to verify that a particular strategy is always a winning strategy for some instance of the problem. Competitive Facility Location is an example of a problem that is PSPACE-Complete. This encompasses a set of problems that are polynomial in the amount of space (memory) that they require for any algorithmic "solution" but the problem is strictly harder than NP-Complete problems.