Generalized matchings, or how to marry and distribute applicants
In practice, there is often a problem of distributing objects or people in pairs with each other. For example, the distribution of employees by vacancies, the formation of committees, the distribution of applicants to universities. Today's lecture is devoted to the theory and practice of constructing mechanisms for such a distribution, taking into account the preferences of individuals. It was read at the Faculty of Computer Science, opened at HSE with the support of Yandex.
Lecturer - Sofia Gennadyevna Kiselgof , Junior Researcher at the International Research Laboratory for Analysis and Decision Making at HSE. Lecturer, Department of Mathematics, Faculty of Economics. At the Faculty of Computer Science reads the course Operations Research and Game Theory . She defended her thesis on the topic "Generalized matchings with preferences that are not linear orders." Sophia Gennadievna conducted a study of the mechanism of enrollment of applicants in Russian universities as a result of which a model was constructed describing the behavior of an applicant when choosing a university.
')
Under the cut - a detailed transcript of the lecture.
I understand that economics is not quite the topic of this seminar, maybe I will get a little out of what usually sounds here. But the topic is so enticing, more precisely the subtitle of the topic, not sure that I can fully disclose it, but I will try. In fact, before starting to talk about what is called generalized matching, I want to say a few words about sections of the economy, it is even broader than the concept of economics, more like social science in general, such as the development of social mechanisms.
Setting a task is similar to setting a task for an engineer who develops a mechanism for a given purpose. For example, if we need to lift a load, then we come up with a mechanism that does this with minimal effort to the desired height. For some time now, economists have begun to set such a task, how to come up with an interaction mechanism for economic agents, that is, people, firms, organizations, companies, and so on, which would lead to the desired result, provided that individual economic entities behave in accordance with their properties, pursue your gain. In general, a task is formulated in the development of a mechanism as follows: we are developing a certain game in which agents with unknown characteristics will play. The task of the developer of the mechanism is to come up with such rules of the game that each of the participants, acting in their own interests (egotistical or cooperating), as they naturally would, would come to "good" results.
There are two questions left. First: usually we don’t know something about the participants, some assumptions are made. And the second, which means "good" result, this is already determined by the developer of the mechanism. In economic and social aspects, this task is often more difficult. Depending on who sets the development task, the desired result may be different.
Today I will not talk about all the possible tasks of the development of mechanisms, but will focus on the topic of generalized matching. I think everyone is familiar with the task of finding matching patterns. There is a bichromatic graph and you need to find the simplest matching in this graph, that is, to find such a subset of edges so that their number is maximum and in each subset at the vertex there is one edge. This task is familiar, there are various modifications to it, when we can assign some weights to these edges, corresponding to the desirability of including these links in the final matching and then the task turns into an optimization one in terms of maximizing the functional. This makes the task closer to the realities of various socio-economic situations.
In the classical formulation, this task can be called "workers, the distribution of workers by vacancies, between men and women" subsets of vertices of the graph. In essence, none of their properties, except for possible connections that they can form, in a subset of vertices of a graph, they are not taken into account in the solution of the problem. There is a central planner who set the task: put down the maximum number of pairs, and this task is solved. If these peaks correspond to economic agents with independent goals and objectives to act outside the framework, outside the influence of the central organizer, then the usual task from discrete mathematics stops working because participants may be dissatisfied with what they received and if they have the freedom of choice, they can to be not just dissatisfied, but to be actively dissatisfied, that is, to refuse what was offered to them.
In fact, the very formulation of the problem of finding a generalized matching differs from the usual task of finding the maximum matching in the graph in that we set the preferences of our objects; I will call them men and women, although in general use. These mechanisms are actually used in practice, especially when organizing weddings this is done, you can probably guess why. Calling them men and women, it is more convenient to talk about these objects.
In this example, it is known that the second man M2 can marry (dance, marry) either with a woman W2 or with a woman W4. The task of generalized matching allows this man to communicate his preferences. He can express his wishes: some woman is pretty, some is not. There is a central planner who concludes these marriages or puts them to dance, he, as a free person, will simply refuse such an offer. In the simplest case, every man and woman can streamline all potential partners.
Generally speaking, since the word "economy" sounds, they can not just sort them, but ask some values ​​in rubles. In fact, it can be done. By applying it to marriages, it causes a smile rather than a serious idea. There are a number of situations where, for various reasons, this monetary component is incorrect, it can be added to the theoretical model, but in real life people: a) cannot formulate these estimates, b) even if they could for some reason make such a translation of relationships in the form of money is perceived as undesirable. Therefore, this section concerns agents whose preferences are given by arbitrary binary relations, but not utility functions or quantitative units.
That is, on the one hand, this is a restriction, but, on the other hand, without this restriction, the task changes fundamentally. And then the generalized matching is called the generalization of men with women, who with whom becomes a couple, and in the simple case, each man is paired with no more than one woman, each woman is paired with no more than one man. And someone can be left alone. Everything is as usual.
If in this task we had a clear idea: let's build the maximum number of matchings, then what could be the goal from the point of view of the developer of the mechanism, if we want to take into account the preferences of agents. This is a formal definition, a set of wishes, which was formulated by the researchers.
What is required here: two very simple things. The first (individually rational): we should not put a woman in a couple of men, which he considers unacceptable. If we put it with her a pair. then he will leave as a free man, breaking the whole system for us. The second requirement (pairwise stability) is also a very simple thing. If we have pairs formed as drawn on the right. The first man is paired with the first woman. the second man is paired with the second woman. What could be the problem. The first man claims that the second woman is nicer for him than the potential spouse that our distribution offered him. And the second woman, in turn, considers the first man preferable to the one she was offered. If they are free citizens, then these two will flee, trying to create a red pair, instead of what they were offered.
I would not like to observe such situations, so we prohibit pictures, build so that there are no blocking pairs (the first man and the second woman are called blocking pairs), because after they saw the distribution they block it, they say that we are not agree Such two wishes. It turned out that they are rather non-restrictive, because such a matching can always be constructed, if the preferences of men and women are given by ordered lines, then matching which satisfy these two requirements can always be built.
Moreover, this is all the result of the first task that was set for Gale and Shepley. They suggested precisely the mechanism that allows finding this matching. It works as follows. Since at the level of theory groups of men and women are symmetrical. In the first step, the man makes an offer to the woman he likes best. If there is such a man who does not want to marry, then he is not even considered. Some women can get more than one sentence at a time, what she does: she considers all the offers that she received and chooses the one she likes the most. Chooses the man she likes the most. And then she accepts his offer, but temporarily. All other men learn that marriage is impossible with her, they begin to act further. At the second step, the story repeats: the men make an offer to the woman that they have next on the list. Again, some women may receive several offers, she again chooses the best.
The only thing that I would like to say is still concerned about the economic component. Well, we proposed such a mechanism to implement it in real life or computationally, we need the preferences of the participants. The question arises whether they will tell us the truth, we do not know what is in their head, and we need to know what they think. The question is: will they tell the truth? A good answer would be that yes - there will be, but unfortunately, he is not. If we look at the mechanism with offering men, then men are interested in telling the truth, for them the weakly dominant strategy is that they want to communicate real preferences. They may report something else. This will not change their result or worsen. Unfortunately, this cannot be said about women, because women, by giving incorrect information to the mechanism, can improve their results. First but If they manipulate in their own interests, then the matching that will be built will be stable with the initial preferences. If they even lied, the matching will be stable, because women have improved their position, apparently at the expense of men, but the result that has turned out is still stable.
Further, in order to successfully manipulate preferences, a woman needs information about the preferences of everyone else. This history of searching for the maximum number of matchings is only based on preferences. In practice, an interesting one-to-many task. Conventionally, it is described in terms of "the applicant and the university," indeed, for applicants and universities this task is applied in practice. But it can be not only applicants and universities. Here is the difference. Everything was symmetrical with men and women: a man marries a woman, a woman marries a man.
The applicant enters one university, and the university sets a certain quota, and enrolls applicants to the maximum number of places that they have. Further, we can say that there is not a control figure of admission, but a mechanism for choosing applicants. The number of people we are ready to accept depends on their properties. Acceptance digits look something like this. If there are a lot of olympiadics, then we take them more than the control figures. Everything, including the mechanism of deferred acceptance, properties, and so on, expands when we have not just a quota, but some sort of choice function, preferences on a subset of enrolled applicants.
The definition of a sustainable matching is formulated here. The requirements are very similar, individual rationality. We must send an entrant to study at a university in which they study worse than go to the army. And for the university: if the university believes that the training of such an applicant is worse than not filling this place.
Further requirement: blocking pairs. What may be blocking pairs. May be the same couple as with men and women. Ivanov is better than the applicant Petrov, so we choose Ivanov, “dismiss” Petrov. Not the fact that in reality this happens for all sorts of bureaucratic reasons. The second option: Ivanov is studying at MSU, wants to get to the HSE, there is a free place and HSE thinks Ivanova is worthy of training, then Ivanov should go to the HSE. Such requirements are an extension of the concept of sustainability, such a matching exists, it can be built using a similar mechanism, only in the past, examples of proposals were made by men to women, and here the offer is made by applicants, then the university accepts the offer from as many applicants as it has. In the task with many, life from the point of view of manipulation of preferences, deteriorates even more because any mechanism that builds stable matchings allows any universities to manipulate preferences. When we start talking about the applied problems of the “entrant-university” distribution, the party that is the university, does not have the ability to manipulate, because her preferences are set by the “single exam,” the internal exam, that is, I first conduct the exam, recognize the results of the applicants, and only then submit their applications . Therefore, to manipulate at the stage of grading for this exam is almost impossible, because I do not know anything about the preferences of those who will apply. The problem of manipulation on the part of universities is theoretical, but it does not create practical problems due to informational limitations and others.
As for the examples where this is all used. The system of distribution of graduates - interns in hospitals. The theoretical mechanism was invented by chance and is now being actively put into practice. Distribution of children in kindergartens. Other.
Let's start with the first National Resident Program. How does the distribution work? The doctor finishes his studies at a higher educational institution, and then, in order to obtain a medical license, he must also complete an internship. This is a job contract with a medical association that hires him. The system of distribution of universities and hospitals offered to establish a single date for signing contracts with graduates of the current year. When the target dates were set, immediately the most savvy hospital managers sought to enter into contracts before these dates in order to get the best graduates as early as possible. All this happened on the phone, the Internet was not there yet. The Unified Medical Association used different methods (the code of honor, which forbade making proposals before the set date; I used different algorithms). They suffered for about 6 years. Then they began to offer centralized procedures (each graduate expressed his wishes about the hospital, where he would like to work). Hospitals reported who they would like to take. First, a mechanism was proposed that built matchings. When the researchers after the fact had already analyzed the mechanism that they proposed, they found out that he was building the distributions, but unstable, that is, blocking pairs were formed. This mechanism did not last even two years. In the absence of open information about preferences, about free places, the mechanism did not work. It came down to the preliminary conclusion of contracts.
In 1952, a complicated mechanism was invented, which was equivalent to the mechanism of deferred acceptance, when the proposals were made by hospitals and this mechanism was fixed, because it did not work out a word, there were no blocking pairs. The mechanism worked until the early 1990s. All spoiled women.
In the 1950s, when it all began, the level of emancipation was low, there were 3-5% of women. By 1980, it was about 50 \ 50. Families began to form, and family preferences are not preferences of one individual, it is much more difficult (personal interests of each spouse are taken into account, plus joint interests, in order to be in one region). Such couples tried to negotiate workarounds in order to get work in one place, and since private clinics and graduates who don’t owe anything to them, hospitals had the right not to declare part of their seats in the centralized procedure and negotiate with people around the system.
The problem was solved by researchers Elliot and Piranson, who worked on theoretical models. From a theoretical point of view, their result was sad. From the point of view of preference for married couples, there may be no stability at all. They invented a mechanism that builds a stable matching, if it exists. Or stops at some number of blocking pairs, which he managed to find. In 1998, we finished the implementation, found that the mechanism never stopped at an unstable matching.
If you go back to the words of the university entrant, the centralized admission scheme is used in different countries. In order for such a system to exist, we do not necessarily need a single state examination or a unified assessment system. This may be preliminary interviews. If we return to the issue of manipulation, universities do not manipulate preferences at the stage of ranking of those with whom they interviewed. , . .
, , , ? : , .
, — « », , . – , , . , , , , - , , , .
: , , . ? , , . , , , , , . , . : , . . , , - , - - , . , . , , . , , . , : 1- 2- , 2- 1- , , , , , . , , .
Lecturer - Sofia Gennadyevna Kiselgof , Junior Researcher at the International Research Laboratory for Analysis and Decision Making at HSE. Lecturer, Department of Mathematics, Faculty of Economics. At the Faculty of Computer Science reads the course Operations Research and Game Theory . She defended her thesis on the topic "Generalized matchings with preferences that are not linear orders." Sophia Gennadievna conducted a study of the mechanism of enrollment of applicants in Russian universities as a result of which a model was constructed describing the behavior of an applicant when choosing a university.
')
Under the cut - a detailed transcript of the lecture.
I understand that economics is not quite the topic of this seminar, maybe I will get a little out of what usually sounds here. But the topic is so enticing, more precisely the subtitle of the topic, not sure that I can fully disclose it, but I will try. In fact, before starting to talk about what is called generalized matching, I want to say a few words about sections of the economy, it is even broader than the concept of economics, more like social science in general, such as the development of social mechanisms.
Setting a task is similar to setting a task for an engineer who develops a mechanism for a given purpose. For example, if we need to lift a load, then we come up with a mechanism that does this with minimal effort to the desired height. For some time now, economists have begun to set such a task, how to come up with an interaction mechanism for economic agents, that is, people, firms, organizations, companies, and so on, which would lead to the desired result, provided that individual economic entities behave in accordance with their properties, pursue your gain. In general, a task is formulated in the development of a mechanism as follows: we are developing a certain game in which agents with unknown characteristics will play. The task of the developer of the mechanism is to come up with such rules of the game that each of the participants, acting in their own interests (egotistical or cooperating), as they naturally would, would come to "good" results.
There are two questions left. First: usually we don’t know something about the participants, some assumptions are made. And the second, which means "good" result, this is already determined by the developer of the mechanism. In economic and social aspects, this task is often more difficult. Depending on who sets the development task, the desired result may be different.
Today I will not talk about all the possible tasks of the development of mechanisms, but will focus on the topic of generalized matching. I think everyone is familiar with the task of finding matching patterns. There is a bichromatic graph and you need to find the simplest matching in this graph, that is, to find such a subset of edges so that their number is maximum and in each subset at the vertex there is one edge. This task is familiar, there are various modifications to it, when we can assign some weights to these edges, corresponding to the desirability of including these links in the final matching and then the task turns into an optimization one in terms of maximizing the functional. This makes the task closer to the realities of various socio-economic situations.
In the classical formulation, this task can be called "workers, the distribution of workers by vacancies, between men and women" subsets of vertices of the graph. In essence, none of their properties, except for possible connections that they can form, in a subset of vertices of a graph, they are not taken into account in the solution of the problem. There is a central planner who set the task: put down the maximum number of pairs, and this task is solved. If these peaks correspond to economic agents with independent goals and objectives to act outside the framework, outside the influence of the central organizer, then the usual task from discrete mathematics stops working because participants may be dissatisfied with what they received and if they have the freedom of choice, they can to be not just dissatisfied, but to be actively dissatisfied, that is, to refuse what was offered to them.
In fact, the very formulation of the problem of finding a generalized matching differs from the usual task of finding the maximum matching in the graph in that we set the preferences of our objects; I will call them men and women, although in general use. These mechanisms are actually used in practice, especially when organizing weddings this is done, you can probably guess why. Calling them men and women, it is more convenient to talk about these objects.
In this example, it is known that the second man M2 can marry (dance, marry) either with a woman W2 or with a woman W4. The task of generalized matching allows this man to communicate his preferences. He can express his wishes: some woman is pretty, some is not. There is a central planner who concludes these marriages or puts them to dance, he, as a free person, will simply refuse such an offer. In the simplest case, every man and woman can streamline all potential partners.
Generally speaking, since the word "economy" sounds, they can not just sort them, but ask some values ​​in rubles. In fact, it can be done. By applying it to marriages, it causes a smile rather than a serious idea. There are a number of situations where, for various reasons, this monetary component is incorrect, it can be added to the theoretical model, but in real life people: a) cannot formulate these estimates, b) even if they could for some reason make such a translation of relationships in the form of money is perceived as undesirable. Therefore, this section concerns agents whose preferences are given by arbitrary binary relations, but not utility functions or quantitative units.
That is, on the one hand, this is a restriction, but, on the other hand, without this restriction, the task changes fundamentally. And then the generalized matching is called the generalization of men with women, who with whom becomes a couple, and in the simple case, each man is paired with no more than one woman, each woman is paired with no more than one man. And someone can be left alone. Everything is as usual.
If in this task we had a clear idea: let's build the maximum number of matchings, then what could be the goal from the point of view of the developer of the mechanism, if we want to take into account the preferences of agents. This is a formal definition, a set of wishes, which was formulated by the researchers.
What is required here: two very simple things. The first (individually rational): we should not put a woman in a couple of men, which he considers unacceptable. If we put it with her a pair. then he will leave as a free man, breaking the whole system for us. The second requirement (pairwise stability) is also a very simple thing. If we have pairs formed as drawn on the right. The first man is paired with the first woman. the second man is paired with the second woman. What could be the problem. The first man claims that the second woman is nicer for him than the potential spouse that our distribution offered him. And the second woman, in turn, considers the first man preferable to the one she was offered. If they are free citizens, then these two will flee, trying to create a red pair, instead of what they were offered.
I would not like to observe such situations, so we prohibit pictures, build so that there are no blocking pairs (the first man and the second woman are called blocking pairs), because after they saw the distribution they block it, they say that we are not agree Such two wishes. It turned out that they are rather non-restrictive, because such a matching can always be constructed, if the preferences of men and women are given by ordered lines, then matching which satisfy these two requirements can always be built.
Moreover, this is all the result of the first task that was set for Gale and Shepley. They suggested precisely the mechanism that allows finding this matching. It works as follows. Since at the level of theory groups of men and women are symmetrical. In the first step, the man makes an offer to the woman he likes best. If there is such a man who does not want to marry, then he is not even considered. Some women can get more than one sentence at a time, what she does: she considers all the offers that she received and chooses the one she likes the most. Chooses the man she likes the most. And then she accepts his offer, but temporarily. All other men learn that marriage is impossible with her, they begin to act further. At the second step, the story repeats: the men make an offer to the woman that they have next on the list. Again, some women may receive several offers, she again chooses the best.
The only thing that I would like to say is still concerned about the economic component. Well, we proposed such a mechanism to implement it in real life or computationally, we need the preferences of the participants. The question arises whether they will tell us the truth, we do not know what is in their head, and we need to know what they think. The question is: will they tell the truth? A good answer would be that yes - there will be, but unfortunately, he is not. If we look at the mechanism with offering men, then men are interested in telling the truth, for them the weakly dominant strategy is that they want to communicate real preferences. They may report something else. This will not change their result or worsen. Unfortunately, this cannot be said about women, because women, by giving incorrect information to the mechanism, can improve their results. First but If they manipulate in their own interests, then the matching that will be built will be stable with the initial preferences. If they even lied, the matching will be stable, because women have improved their position, apparently at the expense of men, but the result that has turned out is still stable.
Further, in order to successfully manipulate preferences, a woman needs information about the preferences of everyone else. This history of searching for the maximum number of matchings is only based on preferences. In practice, an interesting one-to-many task. Conventionally, it is described in terms of "the applicant and the university," indeed, for applicants and universities this task is applied in practice. But it can be not only applicants and universities. Here is the difference. Everything was symmetrical with men and women: a man marries a woman, a woman marries a man.
The applicant enters one university, and the university sets a certain quota, and enrolls applicants to the maximum number of places that they have. Further, we can say that there is not a control figure of admission, but a mechanism for choosing applicants. The number of people we are ready to accept depends on their properties. Acceptance digits look something like this. If there are a lot of olympiadics, then we take them more than the control figures. Everything, including the mechanism of deferred acceptance, properties, and so on, expands when we have not just a quota, but some sort of choice function, preferences on a subset of enrolled applicants.
The definition of a sustainable matching is formulated here. The requirements are very similar, individual rationality. We must send an entrant to study at a university in which they study worse than go to the army. And for the university: if the university believes that the training of such an applicant is worse than not filling this place.
Further requirement: blocking pairs. What may be blocking pairs. May be the same couple as with men and women. Ivanov is better than the applicant Petrov, so we choose Ivanov, “dismiss” Petrov. Not the fact that in reality this happens for all sorts of bureaucratic reasons. The second option: Ivanov is studying at MSU, wants to get to the HSE, there is a free place and HSE thinks Ivanova is worthy of training, then Ivanov should go to the HSE. Such requirements are an extension of the concept of sustainability, such a matching exists, it can be built using a similar mechanism, only in the past, examples of proposals were made by men to women, and here the offer is made by applicants, then the university accepts the offer from as many applicants as it has. In the task with many, life from the point of view of manipulation of preferences, deteriorates even more because any mechanism that builds stable matchings allows any universities to manipulate preferences. When we start talking about the applied problems of the “entrant-university” distribution, the party that is the university, does not have the ability to manipulate, because her preferences are set by the “single exam,” the internal exam, that is, I first conduct the exam, recognize the results of the applicants, and only then submit their applications . Therefore, to manipulate at the stage of grading for this exam is almost impossible, because I do not know anything about the preferences of those who will apply. The problem of manipulation on the part of universities is theoretical, but it does not create practical problems due to informational limitations and others.
As for the examples where this is all used. The system of distribution of graduates - interns in hospitals. The theoretical mechanism was invented by chance and is now being actively put into practice. Distribution of children in kindergartens. Other.
Let's start with the first National Resident Program. How does the distribution work? The doctor finishes his studies at a higher educational institution, and then, in order to obtain a medical license, he must also complete an internship. This is a job contract with a medical association that hires him. The system of distribution of universities and hospitals offered to establish a single date for signing contracts with graduates of the current year. When the target dates were set, immediately the most savvy hospital managers sought to enter into contracts before these dates in order to get the best graduates as early as possible. All this happened on the phone, the Internet was not there yet. The Unified Medical Association used different methods (the code of honor, which forbade making proposals before the set date; I used different algorithms). They suffered for about 6 years. Then they began to offer centralized procedures (each graduate expressed his wishes about the hospital, where he would like to work). Hospitals reported who they would like to take. First, a mechanism was proposed that built matchings. When the researchers after the fact had already analyzed the mechanism that they proposed, they found out that he was building the distributions, but unstable, that is, blocking pairs were formed. This mechanism did not last even two years. In the absence of open information about preferences, about free places, the mechanism did not work. It came down to the preliminary conclusion of contracts.
In 1952, a complicated mechanism was invented, which was equivalent to the mechanism of deferred acceptance, when the proposals were made by hospitals and this mechanism was fixed, because it did not work out a word, there were no blocking pairs. The mechanism worked until the early 1990s. All spoiled women.
In the 1950s, when it all began, the level of emancipation was low, there were 3-5% of women. By 1980, it was about 50 \ 50. Families began to form, and family preferences are not preferences of one individual, it is much more difficult (personal interests of each spouse are taken into account, plus joint interests, in order to be in one region). Such couples tried to negotiate workarounds in order to get work in one place, and since private clinics and graduates who don’t owe anything to them, hospitals had the right not to declare part of their seats in the centralized procedure and negotiate with people around the system.
The problem was solved by researchers Elliot and Piranson, who worked on theoretical models. From a theoretical point of view, their result was sad. From the point of view of preference for married couples, there may be no stability at all. They invented a mechanism that builds a stable matching, if it exists. Or stops at some number of blocking pairs, which he managed to find. In 1998, we finished the implementation, found that the mechanism never stopped at an unstable matching.
If you go back to the words of the university entrant, the centralized admission scheme is used in different countries. In order for such a system to exist, we do not necessarily need a single state examination or a unified assessment system. This may be preliminary interviews. If we return to the issue of manipulation, universities do not manipulate preferences at the stage of ranking of those with whom they interviewed. , . .
, , , ? : , .
, — « », , . – , , . , , , , - , , , .
: , , . ? , , . , , , , , . , . : , . . , , - , - - , . , . , , . , , . , : 1- 2- , 2- 1- , , , , , . , , .
Source: https://habr.com/ru/post/262561/
All Articles