In 2012, the Nobel Prize in Economics was awarded to Lloyd Shapley and Alvin Roth. "For the theory of stable distribution and the practice of market design." Alexey Savvateev in 2012 tried to simply and clearly tell what the essence of the merits of mathematicians is. I present to you the summary .
Today there will be a theoretical lecture. About experiments , in particular with donation, I will not tell.
When they announced that received the Nobel Prize, there was a standard question: “How!? Is he still alive!?!?” His most famous result was obtained in 1953.
Formally, the award was given for something else. For his 1962 paper for "the stable marriage theorem": College Admission and the Stability of Marriage.
On sustainable marriage
Matching (matching) - the problem of finding a match.
There is a certain isolated village. There are "m" young men and "w" girls. They need to marry each other. (Not necessarily the same number, maybe in the end someone will be left alone.)
What are the preconditions for the model? What is not easy to marry at random. A certain step towards free choice is being made. Suppose there is a wise aksakal who wants to marry in such a way that after his death divorces do not begin. (Divorce is a situation where a husband wants a third-party woman as his wife more than a wife.)
This theorem is in the spirit of modern economics. She is extremely inhuman. The economy is traditionally inhumane. In economics, man has been replaced by a profit-maximizing machine. What I'm going to tell you is absolutely crazy things from the point of view of morality. Don't take it to heart.
Economists look at marriage this way.
m1, m2,… mk are men.
w1, w2, ... wL are women.
A man is identified with how he "arranges" the girls. There is also a “zero level”, below which, women should not be offered as wives 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 assumption/limitation is that we do not change our preferences.
Theorem: Regardless of the distribution and the zero level, there is always a way to establish a one-to-one correspondence between the male part and the female part, so that it is robust against any kind of splits (not just divorces).
What could be the threats?
There is a couple (m,w) that 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 fall apart.
If a woman is married, but she prefers an unmarried one, for whom she is above zero.
If two people, both are not married, and both are “above zero” for each other.
It is argued that for any initial data such a system of marriages exists, resistant to all types of threats. Secondly, the algorithm for finding such an equilibrium is very simple. Let's compare with M*N.
This model has been generalized and extended to "polygamy" and applied in many areas.
Gale-Shapley procedure
If all men and all women follow the “precepts,” then the resulting marriage system will be sustainable.
Prescriptions.
We take as many days as needed. Every day is divided into two parts (morning and evening).
On the first morning, every man goes to his best woman and knocks on the window, asking her to marry him.
In the evening of the same day, the move goes to the women. What can a woman discover? That there is a crowd under her window, either alone or not a single man. Those who did not have anyone today, skip the move, wait. The rest, who have at least one, check the men who have come for the fact that they are "above the zero level." To have at least one. If you are completely unlucky and everything is below zero, then everyone should be sent. The woman chooses the maximum of those who came, tells him to wait, and sends the rest.
Before the second day, the situation is as follows - some women have one man sitting, some have none.
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 while doing nothing.
In the evening, women look at the situation. If someone who was already sitting was joined by a higher priority, then a lower priority is sent away. If those who came are lower than the existing one, everyone is sent. Women each time choose the maximum element.
Repeat.
As a result, each man went through the entire list of his women and either remained alone or was engaged by some woman. Then we all marry.
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 benefits from this?
Theorem. Consider not only these two symmetrical solutions, but the set of all stable marriage systems. The original proposed mechanism (men run and women agree/refuse) results in a marriage system that is better for any man than any other and worse than any other for any woman.
Same-sex marriage
Consider the situation with same-sex marriages. Consider a mathematical result that casts doubt on the need to legalize them. Ideologically incorrect example.
Consider four homosexuals a, b, c, d.
priorities for a:bcd
priorities for b: cad
priorities for c:abd
it doesn't matter to d how it ranks the remaining three.
Statement: in this system there is no stable system of marriages.
How many systems are there for four people? Three. ab cd, ac bd, ad bc. Couples will fall apart and the process will go in cycles.
"Triple" systems.
This is the most important 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”, “speaking 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 enumeration. The question of a stable system is open.
Shapley vector
In the cottage settlement, they decided to pave the road. Need to drop. How?
Shapley in 1953 proposed a solution to this problem. Let's assume a conflict situation with a group of people N={1,2…n}. You need to share the costs/benefits. Suppose people have done something useful together, they will sell it, and how to share the profit?
Shapley suggested that when dividing, one should be guided by how much one or another subset of these people could receive. How much money could all 2N non-empty subsets make. And based on this information, Shapley wrote a universal formula.
Example. The soloist, guitarist and drummer play in an underground passage in Moscow. The three of them earn 1000 rubles an hour. How to share it? It can be equal.
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
A fair division cannot be determined until we know what the payoffs are in store for this or that company if it breaks off and acts on its own. And when we determined the numbers (set a cooperative game in characteristic form).
Superadditivity is when they earn more together than separately, when it is more profitable to unite, but it is not clear how to share the winnings. Many copies have been broken about this.
There is a game. Three businessmen simultaneously found a deposit worth $1 million. If the three of them agree, then a million of them. Any couple can soak (remove from the case) and get the whole million for themselves. And no one can do anything alone. This scary co-op game has no solution. There will always be two who can eliminate the third... Cooperative game theory begins with an example that has no solution.
We want such a solution that no coalition will want to block a common solution. The set of all divisions that cannot be blocked is the kernel. Sometimes the core is empty. But even if not empty, how to divide?
Shapley suggests sharing like this. Flip a coin with n! faces. 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”, for example, the 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 one in often wins. (Supermodularity)
If we write for all orders:
GSB - (win C) - (win D) - (win B)
SGB - (win C) - (win D) - (win B)
SBG - (win C) - (win D) - (win B)
BSG - (win C) - (win D) - (win B)
BGS - (win C) - (win D) - (win B)
GBS - (win C) - (win D) - (win B)
And for each column we add and divide by 6 - averaging over all orders - this is the Shapley vector.
Shapley proved the theorem (approximately): There is such a class of games (supermodular) in which the next one who entered the big team - he brought a larger payoff to it. The kernel is always non-empty and is a convex combination of points (6 points in our case). The Shapley vector lies at the very center of the nucleus. It can always be offered as a solution, no one will be against it.
In 1973, the cottage problem was proved to be supermodular.
All n people share the road to the first cottage. Before the second - n-1 people. Etc.
The airport has a runway. Different companies need different lengths. The same problem arises.
I think that those who gave out the Nobel Prize also had in mind this merit, and not just the task of marriage.
Thank you!
More
- Channel "Mathematics - Easy":
- Channel "Savvateev without borders": edusex.ru, brainsex.ru, studfuck.ru
- Public "Mathematics is easy":
- Public "Mathematicians are joking":
- Website, all lectures there +100 lessons and more: savvateev.xyz
Source: habr.com