稳定婚姻问题

1. Introduction

In this tutorial, we’ll study the stable marriage problem.

2. Problem

The stable marriage problem is finding a stable match between the sets of men and women. Each man has a preference order for the women; likewise, each woman has a preference order for the man.

Furthermore, there are no ties in the orderings. So, for each man and any two different women and , it holds that either prefers over or over . The same goes for every woman and two different men and .

We call matching between men and women unstable if it satisfies these two conditions:

In other words, a matching is stable if and only if there doesn’t exist any pair such that both partners prefer other people, and those other people prefer them over their matches.

3. Example

Let’s check out an example.

Let be men and women. Let the men have the following preferences:

Man

First

Second

Third

John

Bethany

Anna

Rose

Smith

Bethany

Rose

Anna

Tony

Rose

Bethany

Anna

Here are the women’s preferences:

Woman

First

Second

Third

Anna

Smith

Tony

John

Bethany

Tony

John

Smith

Rose

Smith

Tony

John

3.1. Marriage Matching

Let’s now define a marriage matching set . It has pairs. Each pair contains members from and such that each man from is paired with exactly one woman from and vice versa.

Further, we call a pair , where and , a blocking pair for a marriage matching if man and woman aren’t matched in despite preferring each other to their chosen mates in .

For example, is a blocking pair for the marriage matching . This is so because wants more than , while prefers over .

3.2. Matching Stability

We conclude this section by describing the stability of a matching.

We call a marriage matching stable if and only if there is no blocking pair for it. Otherwise, we say is unstable. Hence, we find the matching  unstable because and prefer each other over their matches.

4. Algorithm

All the men and women are initially free, so the matching is empty. After that, we perform the following steps iteratively:

1. First, we randomly select a man and let him propose to the first woman on his preference list that hasn’t rejected him so far
2. Then, if is free, she accepts his proposal, and they become a pair in . If is not free, she compares with her current match . If she prefers to , she accepts the proposal and replaces with . This way, we get a new pair . Otherwise, rejects the proposal of , and remains unmatched

We iterate these two steps until no man remains unmatched. Since no two men get matched with the same woman, all the women have their matches when the algorithm terminates.

4.1. Pseudocode

Now, we look at the pseudocode for this algorithm:

algorithm StableMarriageAlgorithm(Y, X, n, preferenceLists):
    // INPUT
    //    Y = the set of men
    //    X = the set of women
    //    n = the number of elements in each set
    //    preferenceLists = the preference lists of men and women
    // OUTPUT
    //    M = the stable matching

    // Initially, all the people are free (unmatched)
    Free_Men <- Y
    Free_Women <- X

    // Initialize matching M to an empty set
    M <- an empty set

    // Continue while there is a free man in Free_Men
    while Free_Men != empty set:
        m <- randomly select a free man from Free_Men
        w <- the highest-preference woman to whom m has not proposed yet

        if w in Free_Women:
            // w can accept the offer from m
            M <- M + {(m, w)}
            
            // Remove m and w from Free_Men and Free_Women
            Free_Women <- Free_Women - {w}
            Free_Men <- Free_Men - {m}
        else:
            m_current <- the current match of w in M

            if w prefers m to m_current:
                // Update the matching
                M <- M - {(m_current, w)}
                M <- M + {(m, w)}
                
                // Add m_current to Free_Men and remove m from it
                Free_Men <- Free_Men + {m_current}
                Free_Men <- Free_Men - {m}

    return M

5. Working Example

Let’s run this algorithm on the example from above.

5.1. Initiation

Initially, all three men in are free and so are all three women in :

5.2. Iterations

Let’s say we randomly chose to start with. proposes to since he prefers her over the rest, and she accepts since she is currently free. So, we have after the first iteration:

Let be the next free man to match. proposes to but since prefers over , she rejects him:

Let’s say we randomly chose again in the next iteration. Now, he proposes to , who is next on his priority list. is free, so she accepts, and we get a new pair , which we add to to get  :

Next, our only choice is since he’s our last free man. He proposes to but since prefers over , she refuses and stays with :

Then, Tony proposes to . Since prefers the most, she ditches and accepts . So, our matching changes to :

Now, we pick as the next free man. Since already rejected , proposes , the next girl on his ranking list. is free, so she accepts the proposal. As a result, we get the matching :

We stop here since no man is free anymore.

6. Theory

In this section, we talk about the correctness of this algorithm and prove that it always terminates.

6.1. The Algorithm Always Terminates

This algorithm terminates after iterations at most.

Why? Because we start with free men, each of which has a preference list of women. Thus, we have the total of  women in the matrix of the men’s preferences. In each iteration, we take one man, and that man proposes to one woman in the order of preference. Irrespective of the woman accepting or refusing, we reduce the total number of women in his preference list by 1. This is so because we rule out any man proposing to the same woman more than once by removing any woman he proposed to from his preference list.

Hence, our algorithm must terminate after at most iterations. In the end, each man gets matched to a unique woman.

6.2. Correctness

Now, we show that our final matching is a stable marriage matching. The termination property shows that each man in is matched to a unique woman in . So, we need to show the stability of this assignment.

We prove this by contradiction. Let’s say that is unstable. So, this implies that a blocking pair exists such that both partners prefer each other but aren’t matched in . So, in , we have man matched to another woman and woman matched to another man .

Further, proposes to every woman on his ranking list (sorted from the highest to the lowest preference order), and got included in before . So, we know that  must have proposed to  before proposing to . That’s only possible if he prefers to . However, that’s a contradiction since we assumed there’s a blocking pair in which he prefers to . As a result, we conclude no blocking pair can exist, which proves the matching this algorithm returns is stable.

7. Space and Time Complexity

This algorithm has time complexity of . In the worst case, each man finds his match after proposing to all the other women. So, we make iterations for each man and to change their respective partners. Hence, the time complexity is . However, a necessary assumption is that women can compare two men in constant time.

The space complexity of this algorithm is since the male and female preference lists require space.

8. Real World Application

This problem can have multiple real-world applications**.**

First, this algorithm can match first-time resident doctors to hospitals. Each participating hospital and resident doctor prepares their preference list. Then, the algorithm for stable marriages matches the residents-to-be with hospitals to get a stable matching.

Second, we can use this to help the central admission system to match students with universities as per the students’ and universities’ preference lists. Since this algorithm is stable and always terminates, we guarantee that a student gets a school from his preference list. Further, the student can’t secure admission to a more preferred school (than what he got from the system) by manipulating their preferences. This is how the admissions system works in India for most engineering schools.

9. Conclusion

In this tutorial, we studied the stable matching problem. The goal is to find a stable matching for elements of two sets (each having elements) based on each element’s given matching preferences. We can solve it in time and space.