How to marry everyone (one-, two- and three-sex marriage) in terms of mathematics and why men always win
In 2012, the Nobel Prize in Economics was awarded to Lloyd Shapley and Alvin Roth. “For the theory of stable distribution and market practice.” Alexey Savvateev in 2012 tried to simply and clearly explain what the essence of the merits of mathematicians is. I bring to your attention the video lecture notes.
Today will be a theoretical lecture. About the experiments of Al Roth , in particular with donation, I will not talk.
When it was announced that Lloyd Shapley (1923-2016) received the Nobel Prize, there was a standard question: “How !? He is still alive!?!? ”His most famous result was obtained in 1953.
Formally, the prize was given for another. For the work of 1962 for the “theorem on sustainable marriage”: “College Admission and the Stability of Marriage”.
Matching - the task of finding a match.
There is a certain isolated village. There are “m” young people and “w” girls. It is necessary to marry them on each other. (Not necessarily the same amount, maybe someone will end up alone.)
What prerequisites should be made in the model? Which is not just randomize. A step is being taken towards free choice. Suppose there is a wise aksakal who wants to get married so that after his death divorces do not begin. (Divorce is a situation where a husband wants a third-party woman to marry more than a wife.)
This theorem is in the spirit of modern economics. She is extremely inhuman. The economy is traditionally inhuman. In economics, a person is replaced by a machine to maximize profits. What I am going to tell is completely crazy things in terms of morality. Do not take to heart.
Economists look at marriage like that.
m 1 , m 2 , ... m k are men.
w 1 , w 2 , ... w L - women.
A man is identified with how he “orders” the girls. There is also a “zero level”, below which women should not be offered to marry at all, even if there are no others.
Everything happens in both directions, the girls have the same thing.
The initial data is arbitrary. The only suggestion / limitation is that we do not change our preferences.
Theorem: Regardless of the distribution and level of zero, there is always a way to establish a one-to-one correspondence between a part of men and a part of women, so that it will be stable in relation to any kind of splits (not only divorces).
What threats can be?
There is a couple (m, w) who is not married. But for w, the current husband is worse than m, and for m, the current wife is worse than w. This is an unstable situation.
There is another option that someone was married to someone who is “below zero”, in this situation the marriage will also break up.
If the woman is married, but she likes the unmarried, for whom she is above zero.
If two people, both unmarried, and both are “above zero” for each other.
It is argued that for any initial data, such a marriage system exists that is resistant to all types of threats. Secondly, the algorithm for finding such an equilibrium is very simple. Commensurate with M * N.
This model was generalized and expanded to “polygamy” and applied in many areas.
If all men and all women comply with the “precepts,” then the resulting marriage system will be stable.
Prescriptions.
We take a few days as needed. Every day we break into two parts (morning and evening).
On the first morning, every man goes to his best woman and knocks on the window, inviting her to marry him.
In the evening of the same day, the move goes to women. What can a woman discover? That under the window she has a crowd, either one or not a single man. Those who did not have anyone today miss the course, wait. The rest, who have at least one, check the men who have come that they are "above the zero level." To have at least one. If you are completely unlucky and everything is below zero, then everyone needs to be sent. The woman chooses the maximum of those who come, tells him to wait, and sends the rest.
Before the second day, the situation is this: some women have one man sitting, some have not one.
On the second day, all “free” (sent) men need to go to the second-priority woman. If there is none, then the man is declared single. Those men who are already sitting with women are not doing anything yet.
In the evening, women look at the situation. If the one who was already sitting joined the higher priority, then the lower priority is sent away. If the visitors are lower than the existing one, all are sent. Women each time choose the maximum element.
We repeat.
As a result, each man went through the entire list of his women and either remained alone or was biased by some woman. Then we will marry everyone.
Is it possible to drive away this whole process, but so that women run to men? The procedure is symmetrical, but the solution may be different. But the question is, who is better off from this?
Theorem. Consider not only these two symmetrical solutions, but the set of all stable marriage systems. The initial proposed mechanism (men run and women agree / refuse) leads to a marriage system that is better for any man than any other and worse than any other for any woman.
Consider the situation with same-sex marriage. Consider a mathematical result that casts doubt on the need to legalize them. An ideologically incorrect example.
Consider the four homosexuals a, b, c, d.
priorities for a: bcd
priorities for b: cad
priorities for c: abd
for d, it doesn't matter how it ranks the remaining three.
Statement: there is no sustainable marriage system in this system.
How many systems are there for four people? Three. ab cd, ac bd, ad bc. The pairs will fall apart and the process will loop.
“Three-sexed” systems.
This is a crucial question that opens up a whole field of mathematics. This was done by my colleague in Moscow, Vladimir Ivanovich Danilov. He considered “marriage” as drinking vodka and the roles were: “pouring”, “talking toast” and “the one who cuts the sausage”. In a situation where there are 4 or more representatives of each role, it is impossible to solve by brute force. The issue of a sustainable system is open.
In the cottage village, they decided to pave the road. Need to chip in. How?
Shapley in 1953 proposed a solution to this problem. Suppose a conflict situation with a group of persons N = {1,2 ... n}. Need to share the costs / benefits. Suppose people have done something useful together, will they sell and how to share profits?
Shapley suggested sharing when guided by how much one or another subset of these people could get. How much money all 2 N nonempty subsets could earn. And based on this information, Shapley wrote a universal formula.
Example. Soloist, guitarist and drummer play in the underpass in Moscow. The three of them earn 1000 rubles per hour. How to share it? You can equally.
V (1,2,3) = 1000
Let's pretend that
V (1,2) = 600
V (1.3) = 450
V (2,3) = 400
V (1) = 300
V (2) = 200
V (3) = 100
It is impossible to determine a fair divide until we know what winnings await this or that company if it disconnects and acts independently. And when we determined the numbers (we asked a cooperative game in a characteristic form).
Superradditivity is when together they earn more than individually, when it is more profitable to unite, but it is not clear how to divide the gain. Many copies have been broken about this.
There is a game. Three businessmen simultaneously found a $ 1 million deposit. If the three of them agree, then a million of them. Any couple can dunk (remove from business) and get the whole million. And nobody alone can do anything. This is a scary cooperative game in which there is no solution. There will always be such two that they can eliminate the third ... The cooperative game theory begins with an example that has no solution.
But we want such a solution that no coalition wants to block a common solution. The set of all shares that cannot be blocked is the core. It happens that the core is empty. But even if not empty, how to share?
Shapley suggests sharing like that. Throw a coin with n! facets. In this order, we write out all the players. Let's say the first drummer. He comes in and takes his 100. Then comes the "second", say, a soloist. (Together with the drummer, they can earn 450, the drummer has already taken 100) The soloist takes 350. The guitarist enters (together 1000, -450), takes 550. The last person who comes in quite often gets a win. (Supermodularity)
If we write for all orders:
GSB - (win C) - (win G) - (win B)
GBS - (win C) - (win G) - (win B)
SBG - (win C) - (win G) - (win B)
BSG - (win C) - (win G) - (win B)
BGS - (win C) - (win G) - (win B)
GBS - (win C) - (win G) - (win B)
And for each column we add and divide by 6 - averaging over all orders is a Shapley vector .
Shapley proved the theorem (approximately): There is a class of games (supermodular) in which the next person to join the big team - he brought in a bigger win. The kernel is always not empty and is a convex combination of points (in our case, 6 points). The Shapley vector lies in the very center of the nucleus. It can always be offered as a solution, no one will mind.
In 1973, it was proved that the problem with cottages is supermodular.
The road to the first cottage is shared by all n people. Up to the second - n-1 people. Etc.
There is a runway at the airport. Different companies need different lengths. The same problem arises.
I think that those who issued the Nobel Prize had in mind this merit, and not just the task of marriage.
Thank!
Today will be a theoretical lecture. About the experiments of Al Roth , in particular with donation, I will not talk.
When it was announced that Lloyd Shapley (1923-2016) received the Nobel Prize, there was a standard question: “How !? He is still alive!?!? ”His most famous result was obtained in 1953.
Formally, the prize was given for another. For the work of 1962 for the “theorem on sustainable marriage”: “College Admission and the Stability of Marriage”.
About Sustainable Marriage
Matching - the task of finding a match.
There is a certain isolated village. There are “m” young people and “w” girls. It is necessary to marry them on each other. (Not necessarily the same amount, maybe someone will end up alone.)
What prerequisites should be made in the model? Which is not just randomize. A step is being taken towards free choice. Suppose there is a wise aksakal who wants to get married so that after his death divorces do not begin. (Divorce is a situation where a husband wants a third-party woman to marry more than a wife.)
This theorem is in the spirit of modern economics. She is extremely inhuman. The economy is traditionally inhuman. In economics, a person is replaced by a machine to maximize profits. What I am going to tell is completely crazy things in terms of morality. Do not take to heart.
Economists look at marriage like that.
m 1 , m 2 , ... m k are men.
w 1 , w 2 , ... w L - women.
A man is identified with how he “orders” the girls. There is also a “zero level”, below which women should not be offered to marry at all, even if there are no others.
Everything happens in both directions, the girls have the same thing.
The initial data is arbitrary. The only suggestion / limitation is that we do not change our preferences.
Theorem: Regardless of the distribution and level of zero, there is always a way to establish a one-to-one correspondence between a part of men and a part of women, so that it will be stable in relation to any kind of splits (not only divorces).
What threats can be?
There is a couple (m, w) who is not married. But for w, the current husband is worse than m, and for m, the current wife is worse than w. This is an unstable situation.
There is another option that someone was married to someone who is “below zero”, in this situation the marriage will also break up.
If the woman is married, but she likes the unmarried, for whom she is above zero.
If two people, both unmarried, and both are “above zero” for each other.
It is argued that for any initial data, such a marriage system exists that is resistant to all types of threats. Secondly, the algorithm for finding such an equilibrium is very simple. Commensurate with M * N.
This model was generalized and expanded to “polygamy” and applied in many areas.
Gale-Shapley procedure
If all men and all women comply with the “precepts,” then the resulting marriage system will be stable.
Prescriptions.
We take a few days as needed. Every day we break into two parts (morning and evening).
On the first morning, every man goes to his best woman and knocks on the window, inviting her to marry him.
In the evening of the same day, the move goes to women. What can a woman discover? That under the window she has a crowd, either one or not a single man. Those who did not have anyone today miss the course, wait. The rest, who have at least one, check the men who have come that they are "above the zero level." To have at least one. If you are completely unlucky and everything is below zero, then everyone needs to be sent. The woman chooses the maximum of those who come, tells him to wait, and sends the rest.
Before the second day, the situation is this: some women have one man sitting, some have not one.
On the second day, all “free” (sent) men need to go to the second-priority woman. If there is none, then the man is declared single. Those men who are already sitting with women are not doing anything yet.
In the evening, women look at the situation. If the one who was already sitting joined the higher priority, then the lower priority is sent away. If the visitors are lower than the existing one, all are sent. Women each time choose the maximum element.
We repeat.
As a result, each man went through the entire list of his women and either remained alone or was biased by some woman. Then we will marry everyone.
Is it possible to drive away this whole process, but so that women run to men? The procedure is symmetrical, but the solution may be different. But the question is, who is better off from this?
Theorem. Consider not only these two symmetrical solutions, but the set of all stable marriage systems. The initial proposed mechanism (men run and women agree / refuse) leads to a marriage system that is better for any man than any other and worse than any other for any woman.
Same-Sex Marriages
Consider the situation with same-sex marriage. Consider a mathematical result that casts doubt on the need to legalize them. An ideologically incorrect example.
Consider the four homosexuals a, b, c, d.
priorities for a: bcd
priorities for b: cad
priorities for c: abd
for d, it doesn't matter how it ranks the remaining three.
Statement: there is no sustainable marriage system in this system.
How many systems are there for four people? Three. ab cd, ac bd, ad bc. The pairs will fall apart and the process will loop.
“Three-sexed” systems.
This is a crucial question that opens up a whole field of mathematics. This was done by my colleague in Moscow, Vladimir Ivanovich Danilov. He considered “marriage” as drinking vodka and the roles were: “pouring”, “talking toast” and “the one who cuts the sausage”. In a situation where there are 4 or more representatives of each role, it is impossible to solve by brute force. The issue of a sustainable system is open.
Shapley Vector
In the cottage village, they decided to pave the road. Need to chip in. How?
Shapley in 1953 proposed a solution to this problem. Suppose a conflict situation with a group of persons N = {1,2 ... n}. Need to share the costs / benefits. Suppose people have done something useful together, will they sell and how to share profits?
Shapley suggested sharing when guided by how much one or another subset of these people could get. How much money all 2 N nonempty subsets could earn. And based on this information, Shapley wrote a universal formula.
Example. Soloist, guitarist and drummer play in the underpass in Moscow. The three of them earn 1000 rubles per hour. How to share it? You can equally.
V (1,2,3) = 1000
Let's pretend that
V (1,2) = 600
V (1.3) = 450
V (2,3) = 400
V (1) = 300
V (2) = 200
V (3) = 100
It is impossible to determine a fair divide until we know what winnings await this or that company if it disconnects and acts independently. And when we determined the numbers (we asked a cooperative game in a characteristic form).
Superradditivity is when together they earn more than individually, when it is more profitable to unite, but it is not clear how to divide the gain. Many copies have been broken about this.
There is a game. Three businessmen simultaneously found a $ 1 million deposit. If the three of them agree, then a million of them. Any couple can dunk (remove from business) and get the whole million. And nobody alone can do anything. This is a scary cooperative game in which there is no solution. There will always be such two that they can eliminate the third ... The cooperative game theory begins with an example that has no solution.
But we want such a solution that no coalition wants to block a common solution. The set of all shares that cannot be blocked is the core. It happens that the core is empty. But even if not empty, how to share?
Shapley suggests sharing like that. Throw a coin with n! facets. In this order, we write out all the players. Let's say the first drummer. He comes in and takes his 100. Then comes the "second", say, a soloist. (Together with the drummer, they can earn 450, the drummer has already taken 100) The soloist takes 350. The guitarist enters (together 1000, -450), takes 550. The last person who comes in quite often gets a win. (Supermodularity)
If we write for all orders:
GSB - (win C) - (win G) - (win B)
GBS - (win C) - (win G) - (win B)
SBG - (win C) - (win G) - (win B)
BSG - (win C) - (win G) - (win B)
BGS - (win C) - (win G) - (win B)
GBS - (win C) - (win G) - (win B)
And for each column we add and divide by 6 - averaging over all orders is a Shapley vector .
Shapley proved the theorem (approximately): There is a class of games (supermodular) in which the next person to join the big team - he brought in a bigger win. The kernel is always not empty and is a convex combination of points (in our case, 6 points). The Shapley vector lies in the very center of the nucleus. It can always be offered as a solution, no one will mind.
In 1973, it was proved that the problem with cottages is supermodular.
The road to the first cottage is shared by all n people. Up to the second - n-1 people. Etc.
There is a runway at the airport. Different companies need different lengths. The same problem arises.
I think that those who issued the Nobel Prize had in mind this merit, and not just the task of marriage.
Thank!
Still
- Simple Math Channel: youtube.com/punkmathematics
- Channel “Savvateev without borders”: edusex.ru, brainsex.ru, studfuck.ru
- Public "Mathematics Is Easy": vk.com/alexei_savvateev
- Public "Maths are joking": vk.com/bsu_mmf_jokes
- Site, all lectures there +100 lessons and more: savvateev.xyz
All Articles