[발췌: Gale & Shapley] College Admissions and the Stability of Marriage.

자료: http://pages.cs.wisc.edu/~cs787-1/GaleShapley.pdf

※ 발췌 (excerpt):

A certain community consists of n men and n women. Each person ranks those of the opposite sex in accordance with his or her preferences for a marriage partner. We seek a satisfactory way of marrying off all members of the community. Imitating our earlier definition, we call a set of marriages ^unstable^ (and here the suitability of the term is quite clear) if under it there are a man and a woman who are not married to each other but prefer each other to their actual mates. 

Question: For any pattern of preferences is it possible to find a stable set of marriages?

Before giving the answer let us look at some examples.

Example 1. The following is the "ranking matrix" of three men α, β, and γ, and three women, A, B, an C.

    A    B    C
α    (1, 3)    (2, 2)    (3, 1)
β    (3, 1)    (1, 3)    (2, 2)
γ    (2, 2)    (3, 1)    (1, 3)

The first number of each pair in the matrix gives the ranking of women by the men, the second number is the ranking of the men by the women. Thus, α ranks first A, B second, C third, while A ranks β first, γ second, and α third, etc.

There are six possible sets of marriages; of these three are stable. ( ... ... )


Example 2. The ranking matrix is the following.

( ... ... )


Example 3. A problem similar to the marriage problem is the "problem of the roommates." An even number of boys wish to divide up into pairs of roommates. A set of parings is called ^stable^ if under it there are no two boys who are not roommates and who prefer each other to their actual roommates. An easy example shows that there can be situations in which there exists no stable pairing. Namely, consider boys α, β, γ and δ, where α ranks β first, β ranks γ first, γ ranks α first, and α, β and γ all rank δ last. Then regardless of δ's preferences there can be no stable pairing, for whoever has to room with δ will want to move out, and one of the other two will be willing to take him in.

The above examples would indicate that the solution to the stability problem is not immediately evident. Nevertheless,

Theorem 1. ^There always exists a stable set of marriages.^

^Proof.^ We shall prove existence by giving an iterative procedure for actually finding a stable set of marriages.

To start, let each boy propose to his favorite girl. Each girl who receives more than one proposal rejects all but her favorite from among those who have proposed to her. However, she does not accept him yet, but keeps him on a string to allow for the possibility that someone better may come along later.

We are now ready for the second stage. Those boys who were rejected now propose to their second choices. Each girl receiving proposals chooses her favorite from the group consisting of the new proposers and they boy on her string, if any. She rejects all the rest and again keeps the favorite in suspense.

We proceed in the same manner. Those who are rejected at the second stage propose to their next choices, and the girls again reject all but the best proposal they have had so far.

Eventually (in fact, in at most n^2 -2n + 2 stages) every girl will have received a proposal, for as long as any girl has not been proposed to there will be rejections and new proposals, but since no boy can propose to the same girl more than once, every girl is sure to get a proposal in due time. As soon as the last girl gets her proposal the "courtship" is declared over, and each girl is now required to accept the boy on her string.

We assert that this set of marriages is stable. Namely, suppose John and Marry are not married to each other but John prefers Mary to his own wife. Then John must have proposed to Mary at some stage and subsequently been rejected in favor of someone that Mary liked better. It is now clear that Mary must prefer her husband to John and there is no instability.

The reader may amuse himself by applying the procedure of the proof to solve the problems of Examles 1 and 2, or the following example [3] which requires ten iterations:

( ... ... )

It is clear that there is an entirely symmetrical procedure, with girls proposing to boys, which must also lead to a stable set of marriages. The two solutions are not generally the same as shown by Example 1; indeed, we shall see in a moment that when boys propose, the result is optimal for the boys, and when the girls propose it is optimal for the girls. The solution by two procedures will be the same only when there is a unique stable set of marriages.


4. Stable Assignments and the Admissions Problem.s ( ... ... )


* * *

Example 3:

    A    B    C    D
α    1,3    2,2    3,1    4,3
β    1,4    2,3    3,2    4,4
γ    3,1    1,4    2,3    4,2
δ    2,2    3,1    1,4    4,1

1st: α(A), β(A), γ(B), δ(C)    → A(α,β), B(γ), C(δ), D(-),    β(rejected)
2nd: β(B)            → A(α), B(γ,β), C(δ), D(-),    γ(rejected)
3rd: γ(C)            → A(α), B(β), C(δ,γ), D(-),    δ(rejected)
4th: δ(A)            → A(α,δ), B(β), C(γ), D(-),    α(rejected)
5th: α(B)            → A(δ), B(β,α), C(γ), D(-),    β(rejected)
6th: β(C)            → A(δ), B(α), C(γ,β), D(-),    γ(rejected)
7th: γ(A)            → A(δ,γ), B(α), C(β), D(-),    δ(rejected)
8th: δ(B)            → A(γ), B(α,δ), C(β), D(-),    α(rejected)
9th: α(C)            → A(γ), B(δ), C(β,α), D(-),    β(rejected)
10th: β(D)            → A(γ), B(δ), C(α), D(β)         -