As explained earlier, the program only checks a particular entire pairing for stability. It does not generate, for given preferences, an entire pairing that is stable. The task of generating such a stable entire pairing is known as the stable marriage problem.
Some simple cases allow a stable entire pairing to be written by inspection:
1. People have a unique way of looking at the world. This case comes up when the first column of mpref has n distinct entries: every man most prefers a different woman. Simply pair each man with his heart's desire. The case where wpref has this property is similar.
2. People are all the same. This case occurs when the rows of mpref are all exactly alike: every man has exactly the same preferences. Pair the most preferred woman with the man she most prefers. Pair the next most preferred woman with the man she most prefers among those not yet paired, and so on. For example:
Pair W2 with M3, W4 with M4, W3 with M2, and W1 with M1. The case where wpref has this property has a similar solution.
Not only is an algorithm for generating a stable entire pairing not apparent; it is not even evident that one always exists. The following algorithm does construct one; you might try your hand at convincing yourself that it always does so.
1. Set man to 1.
2. While (man is not paired)
a. find the woman most preferred by man who is not yet paired, or, if paired, prefers man to her current mate
b. if the woman is not yet paired, then
i. pair man to woman,
ii. set man to an unpaired man if there is one
else
i. break the pair between the woman and her current mate,
ii. pair woman to man,
iii. set man to her ex-mate
To illustrate this algorithm, apply it to the preferences of Table 2.1. The sequence of pairs generated by the algorithm is as shown in Table 2.3. Asterisks indicate conflicts that cause breaks when they occur. The final pairings are then 3-1, 4-3, 2-5, 5-2, 1-4.
This is a good example of a correct algorithm that surely requires both a proof of correctness (produces the proper result) and a proof that it will eventually stop. These are the essential ingredients of an algorithm. (The proofs are left as exercises.)
mpref wpref
----------------------
2 4 3 1 3 1 2 4
2 4 3 1 3 1 4 2
2 4 3 1 4 2 1 3
2 4 3 1 4 3 2 1
Table 2.3 Sequence of Pairs
Man Active Pairs
--------------------------
1 1 2
1 2 2 3*
3 3 1
4 4 3*
--------------------------
1 2*
2 3 1
4 3
2 2 5
5 5 2*
--------------------------
3 1
4 3
3 2 5
5 2
1 1 4