Modern civilized social love freedom, marriage independence. Modern marriage doesn't have to carry too many people will carry too much love, and modern men and women who have always loved brave and scream. Children's private taste is just a talker after people 's meals, but there is a good thing for this masterpiece. It is true that there is a matter of tricks to figure out the feelings, but the rigorous analysis and interesting conclusions are really worth seeing, and there is no way to interpret and deduct people, and you will say this. Bar.
Good things start from such an example. Suppose you are a marriage introduction, now there are (standby age) customers all hundreds of men and women to find you to help. The customers are obviously prepared, and each man is handed over to you a woman's list. The above name is ranked in the preference of his personal favorite preference: Xiaoxi is best, Xiaobei is not Lai, Xiao Xin. ..... Peer, the woman is also a list of men who have been ranked like this - of course, these preferred order is impossible, each person's preferences and requirements are impossible. He (she) the other like another may not catch a cold, another like him (she) sees that it is dizzy - now your task is to follow these lists as much as possible as possible to satisfy each other as possible Yes, until everyone finds their own objects.
The most economical approach to reaching your purpose is to engage in a big party, focusing him (she), engaged in a collective pairing activity, existing atmosphere and efficient. Of course, you have to give the law three chapters: First, love has exclusive, we are a wife and a wife, so each customer can only pursue (accept) one person throughout the pairing process, and a pedestal ship is not allowed. Second, the whole process must be a man to act first. This is a traditional and social consensus. Choose, you can't move towards three, so steady.
Reiterate the discipline, the pairing can begin. In order to avoid the chaos, you arrange activities in the form of a round, tell the male or female protagonist, as long as someone is still single after each match, Party will continue, so everyone will have results. Ok, the first round begins, men first act, each men first marriage to their favorite girls. After the noisy, the girls were divided into two piles (at least logic): The eyebrows who had a marriage proposal were laughed, and there was no male to marrying. At this time, I went to the woman to act, the girl's choice will see how many people are the favorite: If only one person is married to her, she is definitely (first) accepted, with him; if there is more than one man proposes her, Don't let go of your pleasure, the girl should pick her your favorite one with him (that is to pick the person in place in front of the preference list, this person is very likely. Not the top of the list - the favorite one in her heart!); If no one is loved? Cough, don't be discouraged, this means she is not the first choice of everyone (in fact, it is also enough), and some people will be appreciated in the future. Ok, after you choose, the first round is over. In theory, there will be such a result, all girls are engaged, no one is dropped, which means that all boy favorite people have no repetition, boys have found their favorite, do not compete with each other, this is The best result (who is the best result?), Engage in a collective wedding, the task is completed. But how big is the probability of such a round? In many cases, there will be some boy to taste the pain of rejection, and some girls have to feel the taste of being cold. Then, the second round begins. Or men act first, but this time they can only participate in the boy who loves to love in the last round (he was rejected by his favorite girl by his favorite, because the girl chose to be more than him. Better people). The brave boy continues to work hard to launch an offensive to his second favorite girl, regardless of whether the girl is already engaged! (Free competition). At this time, girls have to pick a favorite, but there is a little different from the first round, some girls already have a fiance. These girls who have already had a fiance must be more calm, because she wants to choose: If she is still the best, she should refuse all harassment in this turn, continue her little happiness; but if it is better to have a better She should take the previous one to accept the one of the people she think is the best (good); those who are the first time that people show love? Still use? Pick a best. In short, no matter which situation, girls must "choose excellent admission" in accordance with their own preferences. Everyone has selected the second round. In most cases, both men and women will also be divided into two gangs - famous grass has (none) master help, famous flowers have (none) master. It is worth noting that the staff in the bachelor's help will be out of the gang because some people have been separated from the gang because they find themselves (should be said to be herself), and there are some sorrows that have just been smashed by girlfriends. The characters joined the ranks.
Ok, as mentioned earlier, as long as someone is single, the activity will continue. The arrangement of each round is the same as the second round, and the boys who have been rejected by the last round have continued to marry his girl at first-level, and the remaining girls are constantly picking away. ... until everyone has booked marriage, the event ends. It is worth noting that in such a pairing process, the order of the boys love the object is his favorite, the second like, the third like, ..., every time the pursuit is a boy. At first-level like; and girls change boyfriend every time because she found it more like. Our problem is coming, will such a pairing process really will be ended? Does all have objects in the end? How is the result of pairing?
First consider the first question. Strict discussion should be analyzed with a collection theory, but there is no exemption, so it will only be explained using simple mathematics. Note that the current situation is that the number of men and women is equal and is not infinite. No matter how many people flow in each round, the number of married boys and the number of girls that have been engaged is equal (the husband and wife corresponds to a woman), and As long as a girl is married, she keeps engagement in the future (of course, the number of ordinary people choose is not necessarily), that is, the number of marriages is non-reduced (the event is not allowed to be engaged in the pairing process) Sub-breaking - unless someone adds competition, this does not affect the number of booked couples, in order to replace the person), so that the number of people who are not engaged is not increased, that is, the "supply" of the union is limited. For the "marriage demand" of single men, the number of single girls in each round is not increased, as long as the time is enough, all the girls will find the home; the most unjust boys love the number of times, not more than girls The quantity, so this pairing process will eventually end.
For the second question, we assume that the event ends the last boy and the girl Xiaoxi have no object. Is this possible? It is impossible, everyone remembers, as long as a girl is pushed, she will not be empty again. The girl Xiao Xi arrived in the end or single means she is likely to be welcomed by other boys, but because her name is in a certain place in the preference list of Xiaodong, Xiao East will definitely come in a certain stage. She, even if it is in the last round, they should be (early) is a pair. Therefore, all people will find objects after the activity, no one will fall.
For the third question, we have a payable conclusion that the combination of these men and women is definitely stable, but it will only be the best unilateral, and it is Male Optimal. Everyone may be very strange and disappointed, what is "stable"? How can a man is the best?
Let "stability problem" first. Suppose we eventually produce such two couples after pairing: (male) Xiaodong and (female) Xiaoxi, (male) Xiao Nan and (female) Beckham, but in fact, I prefer Beibei, I prefer Xiaobei, At the same time, it is more likely to be with the small east than Xiao Nan Bai (this situation we call it is not "stable"), is this possible? It is impossible. Because if you are more like Bay, you will definitely, you will be love to Xiaobei according to sorting him, but why can't they be together? This can only be, or Beckland later, it is better than the Xiaodong, or the little or Beckham has a better boyfriend than the small East. Please note that girls change the boyfriend will only happen when they will be better in the later people. So Xiaobei's last found Xiao Nan is better than the small east I have encountered before, so saying that the prelude is not existed. All couples are stable. However, it is to be noted that stability only occurs in the pairing result, and the unstable combination is present during the pairing process (some of the "weak stability" combinations). Finally, let's talk about the "male master". As mentioned earlier, the objects of the boy to seek love are all the first level, and each of the girls have moved into her favorite one, according to this, inference, the best definiteness of the two sides is not Yes, it should be the best woman? The fact is not. To give a simple example, take Xiaodong them, suppose (men) Xiaodong, (male) Xiao Nan, (female) Xiaoxi, and (female) Xiahe, these four people, where Xiaodong favorite is small Xi, Xiao Nan favorite is Baby, but the girls don't think so, Xiao Xi likes Xiao Nan, and Xiaobei likes Xiaodong. After the start of the pair, because the man moved first, Xiaodong immediately found Xiao Xi, Xiao Nan immediately picked the little shell, everyone found the object, paired! This is the best result for boys, but it is sad and embarrassing for girls. This is what said, if the first round solves the battle, it will only be a boys. So our conclusion is that active boys can always find as good people, passive girls are always chasing people who don't like. If you feel a bit unacceptable, you can understand this: Although the boy must lower your own requirements, because the starting point is high (from the favorite beginning), as long as each round is active, even if he is 10 A girl rejected, he can always find the best one in the last 90; and the girl is passive, although she will rise to her favorite, but because the starting point may be too low, if not how long? The top 20 boys found their love, she is most powerful to accept the 21st place. That is, the active party is aimed in matching, and the passive party is a disadvant-de-poorer; that is to say that the traditional conventionive process is the man's dominance. Male Optimal, because it is a man active.
Seeing that the girls are not angry, smart you may notice that the status of both men and women in the discussion above is actually equal, and the status is to be interchangeable. The woman can also be active, if you want to get my favorite words. This story is to tell us that you must fight for yourself, especially MM, you have to get a good GG yourself. It should be noted that the above is only a hyposcopic model of traditional marriage pairing, and there may be some assumptions and derivation processes of the model, but no one will doubt the true existence and practical significance of the problem. In fact, our lives are generally related to marriage and similar problems, and these pairing results are closely related to our interest, such as students' questions to upgrade universities (high school graduates with colleges and universities), in units of personnel post Question (pairing of personnel and position), etc. Borrowing the analysis processes and conclusions of the imaginary model, we can make appropriate analysis of these realities, and analyze the relevant policies, and analyze the practical problems can also let us find solving Reference to the reality method of marriage pairing theoretical problem.
Let us now observe another typical paired issue in reality, job search. There are two parties of job seekers and employment companies in the job hunting market, and the two parties are searched. Under normal circumstances, the job seeker will take the initiative to apply for a position to each company, and employment is admitted after receiving the application for job seekers. That is to say, in the job search market, the job seeker is a moving party, and the employment company is a passive party. In other conditions, if the above assumptions, according to an important conclusion of the previous article, the one-time selection of the active choice is excellent in the pairing process, and is it beneficial to the job seeker, but it is unfavorable to the employment company? Is the job seeker always find his satisfaction, and the company always accepts poor employees? But what we see is not the case, but every company can find the employees you need, but some job seekers should accept work without reluctance. Where is the problem?
It seems that we have to take care of it again. As in marriage pairing, before job seekers, the active job seekers will actively collect the situation of recruitment companies and form different preferences for these companies, and then apply according to these sorts. If the job seeker is different for each company's preferences, and as in marriage pairing, each round of pairing is carried out in the case of the number of two parties, which naturally forms a marriage pairing "demand" Some choices "," active ", in fact, the number of passive two sides in the job hunting process is not equal, and most of the case is the job of job seekers. It can be imagined. When each round of pairing is done between a few companies and a large number of or all of the job seekers, the following results can be caused: these companies can always find the best job seekers, and most of the job seekers Will be disappointed. On the one hand, this situation is due to the total number of job positions, the number of job seekers is always less than the number of job seekers. On the other hand, since the job seekers have similar standards for the so-called good companies, both are caused in every round. The pairing demand is greater than the supply, thereby forming the result of "Supply Party (Passive) Selection". Therefore, the contextuality of demand preferences is greater than the supply of "supplier choices" and "passive party". An extreme example, assuming that all job seekers in the market have the same preference sort: A company best, B company is good, C company third, ..., each round of pairing, all job hunting Everyone will apply to a company, you can imagine who is the most favorable; and when the number of job seekers is greater than the number of companies, the last company can choose the best in the remaining job seekers. That one, regardless of this job seeker is the most hate this company.
The demand preferences have a common demand side with common preference sorting. In the job search market, job seekers have the same evaluation (or similar evaluation), if the job seeker scores these companies. And the score is accumulated according to the company, and the score of these companies can be imagined is more obvious step-shaped distribution. The highest score is a job seeker recognizes the best company. Accordingly, this company will be very likely in pairing Find the best candidates - of course, because the best candidates don't think this company is the best, the first application of him (her) is another company (the total score does not mean Everyone thinks it is best). But if each round is only recruiting a few companies, this best candidate will be greatly possible to pick away this recognized company (this matching result is unfavorable). Extreme situation is if there is only one company recruitment every round, this should be a new employee of the company. From another perspective, the company is higher than other companies, indicating that in this company, this company is more status in comparison with other companies, and the result of pairing will be more beneficial to it; the same, candidate The leader also can always get satisfactory results in pairing (as long as he (her) is not too special than others compared to others). In other words, if you are more competitive in your own party, the more ranked, the more likely, you will finally get the results of yourself. Here, competition (ranking) within the pair of pairs (ranking) has become the key to affecting the results. It should be noted that if there is a reasonable evaluation and rating of the objective side (the other person other than the company), people will refer to these evaluations more, and the demand preferences will be strengthened. . (In the case of students, people choose universities, the order of colleges and universities is based on social evaluation, and universities are based on unified horizontal exam - college entrance examination.) From above, we can have the following conclusions: There are three factors affecting the matching results, and the first is the relative number of pairs, the second is the respective internal competition results of both parties, and the third is the activeness of the two parties. If the number of two parties of the pairing, the initiative will become a key to determining the matching result; if the quantity of the two parties is not equal, the competition results between the two sides will replace the active result. Key factors. In reasonable arrangements, the number of two parties will make the results of all parties beneficial results possible. But no matter how it is paired, if the number of both parties is limited, the matching result will last to be stable.
At this time, let's return to the problem of marriage. This time we arrange a pairing process: Both the men and women score each person of the opposite side, then add the score to each person and sort it, so that everyone is ranked by everyone's popularity. The first round, we only let the most popular "popular lover" in the woman accept the marriage, then she will accept all men's pursuit in the first round of pairing. It is obvious that she will get the person she wants; In the second round, we only let the second popular woman in the woman, the same, she will also get her happiness; the following rounds similarly arranged, it can be expected that such pairing results are large to both sides favorable. Our questions finally solved. Of course, the result of absolute "both sides satisfied" can only be very likely to be established. If someone is dissatisfied, I have a way. We have never allowed parties that have been paired in the pairing process, and if we introduce the "regret marriage" mechanism, it allows both parties paired in the pairing process, then the activeness of both parties will It will increase, you can imagine that the results will be better for both parties. At this time, even if you continue to join the competitors, the results of the pairing will be satisfied with both parties. Similarly, there will be equally effects in the process of introducing "destruction" mechanisms during job hunting pair (Is there a college entrance examination?). But these have greatly beyond our discussion, please add it. Postscript: The problem of marriage is earlier in the 1960s by two American mathematicians to strictly define the relevant concepts and prove that the best solution is not empty, and the following theoretical analysis is relatively rare, in my scope Only found three, discipline scope across mathematics aggregate, institutional economics and computer algorithm design (chart). There is also a shared tree on this issue, but I have not found it in a free channel. It is said that there is no strict algorithm now to solve this problem. The previous part of this paper, the survey and analysis of the marriage pairing process is the article of Harry Mairson, the University of Columbia University, can find the original text in the link below. Other related articles are found on Google Sholar.
Professor Harry Mairson's original text: http://www.cs.columbia.edu/~evs/intro/stable/writeup.html
