This article originated from personal public account: TechFlow, original is not easy, for attention


Today, the 30th article in our algorithmic data structure series, we are going to talk about an interesting marriage matching problem.

This problem is one of the most interesting algorithm problems I have learned, and it is also the example chosen by our ACM school team when we preached to freshmen. We thought if we tricked them with a subject that freshmen would be interested in, like dating, they’d be more likely to take the bait.

Problem description

Marriage matching can also be called CP matching, and the problem scenario is very simple. We simulate real matchmaking scenes, such as offline matchmaking activities between N men and N women. Naturally, both men and women have a mental evaluation of the opposite sex, which they like and which they dislike, and have a priority list.

All we have to do is design an algorithm that takes these N males and N females and forms stable CP. The reason is that it is very easy to pair up randomly, but the CP formed randomly is not necessarily harmonious and may be unstable. We hope that couples can live together happily.


To explain the concept of stability, let’s assume that boys have two, male 1 and male 2, and girls have two female 1 and female 2. Let’s say our CP is male 1 and female 2, male 2 and female 1, but male 1 prefers female 1 among girls, and female 1 prefers male 1 among boys.

This means they like each other more than their partners. CP in this case is unstable, and problems may occur after a long time. To simplify the problem model, let’s assume that something must go wrong, that male 1 ends up with female 1, and that they each “break up” with their current partner.

We want N men and N women to be together, and we want none of them to break up, which means the whole situation is stable.

The solution to the problem

There are many different opinions on this question. For example, some people think that each boy and girl should be given a score based on how popular they are with each other. Let’s see who is the quality boy who is liked by many girls, and who is the quality girl who is popular with boys.

Since quality boys and girls get more attention from each other, arrange them well first to prevent them from being unstable. And then arrange for the less popular boys and girls.

This method seems to be possible, but it is very complicated and not feasible, because there may be instability between high quality men and women as well as between high quality men and women and not high quality men and women. There is a fundamental lack of logic to avoid instability.

We can do it with a search algorithm, and the search space is pretty clear, which is male-female pairing, and we just want to find a stable pairing. We can also do this with a search problem, looking through all the possibilities, and then sifting through them one by one to find the stable solution.

This is certainly possible, but the complexity is very high because the vast majority of our searches are invalid.

Is there an efficient and adequate solution to the problem?

Of course, there are some, and also very simple, is to let these boys according to their own heart rankings to pursue girls. In this case, there will be multiple boys pursuing the same girl at the same time or successively. Here, we make a very simple assumption, assuming that girls will always choose the boy with a high ranking in their list as their CP.


In the first round, we asked all the boys to pursue their favorite girl. After a series of competitions, some boys were bound to succeed in forming CP. In the second round, we asked the single guys to pursue their second favorite girl again, and after a round of competition, some of them left. We do this until everyone is matched.

So that’s the end of our algorithm.

Is it that simple? Yes, it’s as simple as that, but does that guarantee that all men and women will find a mate? Will there be some girls and boys left, or will there be instability?

It’s not, and it’s very easy to prove.

First of all, you can prove that there will never be a case where someone doesn’t make a match. Let’s assume that there is a situation where a man and a woman end up alone. The assumption is that the remaining man has already expressed his preference to all the girls and been rejected. But girls won’t say no if there is only one suitor, so this contradicts the assumption. Therefore, there will be no results in the algorithm, which can ensure that all men and women form CP.

Secondly, we can prove that there will be no male-female instability. We can also use contradiction, we can assume that there are male 1 and female 1 who are individually preferred to each other, but not together. But according to the rules of our algorithm, then male 1 must pursue female 1 before the current object. So for female 1, if male 1 is bigger than her current partner, she can’t possibly not be with him, so this is also a contradiction.

This is the end of the algorithm. This algorithm actually has a history, and it’s not our own, but it’s called gale-Shapley. As the name suggests, Gale and Shapley jointly studied and published the algorithm in 1962. It is said to have been used in some parts of the United States to assign jobs to medical school graduates a decade before it was published. So people have been aware of the importance of stable matching for a long time, and intuitively started using it.

Algorithm implementation

This algorithm is actually very easy to implement, we just need to record the following current matching situation of boys and girls, as well as the rounds of boys’ pursuit of girls, the logic in the middle is very simple.

If a woman is single, she must accept a man’s pursuit or compare her priorities with her current partner. If the priority is higher, the next guy competes for the job, and the guy ahead gets laid off and goes back to being single. We just need to clarify these states, and the code implementation is very simple. I implemented a version, to provide you with a reference:

import random

import sys



# Generate test data to generate the order of objects in the minds of boys and girls

def generate_list(n):

    base = list(range(n))

    random.shuffle(base)

    return base



if __name__ == "__main__":

    boys, girls = [], []

    n = int(sys.argv[1])

    for i in range(n):

        boys.append(generate_list(n))

        girls.append(generate_list(n))



    print('The preference of boys')

    print(boys)

    print('The preference of girls')

    print(girls)



    The initial matching state is -1

    girls_matched = [- 1 for _ in range(n)]

    The number of rounds initiated by the male student is 0, indicating which preference the female student will pursue next time

    boys_round = [0 for _ in range(n)]

    boys_matched = [- 1 for _ in range(n)]



    while True:

        all_matched = True

        for i in range(n):

            If the match is already matched, skip it

            ifboys_matched[i] ! =- 1:

                continue



            all_matched = False

            girl = boys[i][boys_round[i]]

            boys_round[i] += 1



            # If she doesn't have a date, say yes

            if girls_matched[girl] == - 1:

                girls_matched[girl] = i

                boys_matched[i] = girl

            else:

                Compare the order with the current object

                idx = girls[girl].index(i)

                mate = girls_matched[girl]

                mate_idx = girls[girl].index(mate)

                if idx < mate_idx:

                    boys_matched[i] = girl

                    boys_matched[mate] = - 1

                    girls_matched[girl] = i



        if all_matched:

            break



    print('The match result of boys:')

    print(boys_matched)



    print('The match result of girls:')

    print(girls_matched)



Copy the code

Let’s run the code to see the result:


We can simulate the result of the first round is [0-3], [1-4], [3-0], [4-2]. Among them, no. 2 and No. 3 boys both initiated courtship to No. 0 girl, who accepted No. 3 and rejected No. 2. Therefore, in the second round, Boy No. 2 began to pursue girl No. 2. Because girl No. 2 had formed a CP with boy No. 4, the best object of desire, so boy No. 2 failed. Continue to no. 3 female launch pursuit, no. 3 female original object is no. 0 male, because no. 0 male platoon name is very low, so no. 0 male was dumped. So the results of the second round are [1-4],[2-3],[3-0],[4-2].

The result of the second round is that no. 0 man falls behind, and No. 0 man fails to pursue No. 4 and No. 0 woman, and finally forms a CP with No. 1 woman. All the men and women formed CP, and there was no instability. The result of our manual reasoning is exactly the same as that given by our program.

conclusion

This algorithm is not difficult, but it is very interesting. In fact, there are many allocation schemes that use gale-Shapley directly or indirectly. If you’re familiar with the algorithm, you’ll see that the essence of this problem is binary graph matching. We can use binary graph matching algorithm to solve this problem.

If we look at the logic at the heart of the algorithm, it turns out that boys actually have an advantage. Although girls seem to have the ultimate choice, boys are more likely to pursue their favorite partner, while girls have to passively wait for the man to initiate the pursuit and make the choice. If a girl likes a guy who doesn’t choose her, she’ll never have a chance to be with him. This story tells us that the object we like should be chosen by ourselves, and initiative is king.

If you’re single, I hope it helps.

This is the end of today’s article, if you like this article, please invite a wave of quality three companies, give me a little support (follow, read, like).