STABLE MARRIAGES - THE MATHEMATICS OF HUMAN BEHAVIOR - The Remarkable Role of Evolution in the Making of Mathematics - Mathematics and the Real World

Mathematics and the Real World: The Remarkable Role of Evolution in the Making of Mathematics (2014)

CHAPTER VI. THE MATHEMATICS OF HUMAN BEHAVIOR

45. STABLE MARRIAGES

We will now present an example of a mathematical analysis of the possible actions of a group of people. We use the term possible actions and not desired actions or recommended actions. We will explain the reason for that later on, and here we will just note that following the successful experience of using mathematics in the natural sciences and technology, many hoped that in the social sciences too, mathematical analysis would show how a society should act. The current mathematics of human behavior is very far from being able to fulfill such hopes.

The example relates to an issue that arises in various situations in our lives. Graduates of medical school look for hospitals in which they would like to work in their chosen specialty, and the hospitals are looking for new interns. The graduates have their individual preferences regarding the hospitals, while the hospitals have their preferences relating to whom they would like as interns. How can and ought the aspirations of the two sides be matched? In a similar vein, how should candidates for a teaching position in a university be selected, how should footballers be taken on to join the team squad, and even how should brides and grooms be matched by a matchmaker?

The natural question that arises in this context is what is the best way of filling available positions. To answer this we need to define the criteria for “best,” and then to find a way to arrive at the solution. Two famous mathematicians, David Gale (1921–2008), of the University of California, Berkeley, and Lloyd Shapley, of the University of California, Los Angeles, tackled this problem using the following mathematical approach. It earned Shapley the Nobel Prize in Economics in 2012.

As this falls within the sphere of mathematics, we should first clearly define the framework of the discussion. Here we will focus on a particular instance, but it is not difficult to extend the solution, when we reach it, to other cases that are closer to reality. Assume that we have a group of N women and a group of N men, and our task is to find a match for each member of the one group with a member of the other. Each man has his priorities regarding the qualities he would like his potential partner to have, and likewise with the women. There is not necessarily any correlation between the preferences of the members of the groups, and if we were to match them randomly, many would be unhappy. In effect, in any system of matchmaking between them, there are likely to be men and women who would not end up with their ideal match and who may even be matched with someone very far from their initial preferences. In such a situation, what is the optimal match? In our context, “match” means the overall matching of all the men and all the women.

The first contribution made by Gale and Shapley was to change the question! Instead of trying to find a criterion for optimality, they formulated a condition, which in the days of the ancient Greeks was called an axiom, that the match had to satisfy. They called this the stability condition. It can be described simply, as follows. The match will be considered not stable if a man and a women can be found who prefer each other to the partner that the system proposed for them. The condition that Gale and Shapley set was that the match should be stable, that is, it should not be unstable. The reason for that condition is apparent: a match that is not stable will not last. The man and woman who can improve their situation by getting together will do so, and it will disturb the order that the matchmaking had determined. The next stage is to define a match as optimal if every man and woman is matched with the best partner among the stable matches. In other words, first of all the match must be stable, and among the stable matches the match has to be the best for every man and every woman. In a paper published in 1962, titled “College Admissions and the Stability of Marriage,” Gale and Shapley presented an algorithm that led to a stable match. The algorithm can be stated without formulae or equations, as can the proof that it results in a stable match. We will show the algorithm in a quasi-visual form, although clearly, in the computer age it can be produced in an instant, even if it relates to very large populations.

images

In the first stage every man places himself next to the woman who heads his list of priorities. Some women may have more than one man standing next to them. Each woman selects the man she prefers from those standing next to her, and she sends the others back to their places. In the next stage every man rejected by his first choice, his top priority, stands by the woman who is next in his list of priorities. Again there may be some women with more than one man near them, and each one of these selects the one she prefers from among those men. It may be that the one she chooses was the one she chose in the first stage, but it could also be that one of the newcomers around her now tops her list. The others she sends back to their places. This continues until there is only one man next to each woman. The algorithm ends, and the result is a stable match. The proof that this is so is that as long as there are at least two men by any woman, the one who is rejected will at the next stage go to the woman who is lower in his order of priorities. The number of such “declines” in the priorities of every man is finite, so that the process is completed when there can be no further declines, that is, there is only one man by each woman. The stability derives from the fact that at each stage the women either stay with the man who chose them previously, or they select a man higher in their own scale of priorities. If a man prefers a woman with whom he is not matched at the end of the process, the fact is that he had already offered himself to her at an earlier stage, but she had preferred to remain with a man who was higher in her own priorities. That woman will therefore not prefer him to the man whom the procedure matched with her, and hence the stability.

What about the optimality conditional on the stability condition, as defined above? Gale and Shapley showed that there are instances in which it is impossible to find an optimal match. They also showed that the algorithm we have described has the characteristic of partial optimality, meaning that every man gets the woman who is highest in his order of priorities from among those he could be matched within a stable match. Herein too lies the difficulty with this particular proposal. If at the outset, instead of every man approaching the woman he preferred we had decided that every woman would approach the man who headed her list, and so on, that procedure would also result in a stable match, which might be different from the final outcome in the process we described. It will be partially optimal in as much as every woman gets the man highest on her priority list from among those with whom she could have been matched as part of a stable match. Which of the two possibilities is preferable? Mathematics does not answer that question; it just offers alternatives and describes their features.

Gale and Shapley's analysis and algorithm had a marked effect on theoretical research into staffing and choice, and also on the practical side. The basic algorithm and its results were extended to more complex frameworks much closer to reality, and they were also extended conceptually, with proposals for changes and improvements. For example, it can readily be seen that when this algorithm is used, there is no advantage to either side in not revealing his or her real priority. This is in contrast to various situations in social conduct in which it is worthwhile to someone participating in a procedure to lie regarding his or her private preferences.

Several institutions have adopted classification and selection procedures that are consistent with Gale and Shapley's proposal, including hospitals selecting new interns. It is interesting to note that in both of the above instances the institutions chose to adopt the algorithm that was optimal from the candidates’, interns’ or students’ point of view. Their reason for this choice was apparently social. The institutions rated it more important that the candidates should feel that they had obtained the best possible position, consistent with the definition of stability, than that the institution itself should feel the same. Other institutions select candidates using different methods. American universities, for example, send candidates for faculty positions offers to which they must respond within a relatively short period of time; they do this to enroll their chosen faculty before they receive offers from other universities that they might prefer. The result is instability, as Gale and Shapley's basic assumption predicts.

Joint winner of the Nobel Prize in Economics in 2012 was Alvin Roth of Harvard University, who has moved since then to Stanford University. He developed an application of Gale and Shapley's method to match candidates for organ transplants with organs available for transplant, taking into consideration the quality of the match, the chances of success, personal details, and so on. Roth's research addressed also the issue of market design, namely, examination of the rules and procedures related to organ transplants, aiming at rules that take into account public beliefs and faith, yet increase the number of potential donors, a nontrivial goal that has deepened the use of the mathematical principles.

It is also interesting to compare the algorithm derived by mathematicians with the solutions to the problem of matching that nature arrived at via evolutionary development, at least in those cases where the couple must invest effort in establishing an economic base for themselves, such as a home for a human couple, or a nest for mating birds. That is why we can observe the stability characteristic in many species of animals that remain with their mate for many years, and even extreme cases in which their original choice of mate remains their lifelong partner. Nature, however, found ways of reaching stability that differ from the algorithm proposed by Gale and Shapley. In many types of animals, stability, in the form of loyalty to one partner, is embedded in the animals’ genes. Those that maintained their relationship survived, and now that whole species has the characteristic of maintaining the stability of their relationships. Another method, which can be seen in an acute form in human societies, is the imposition of difficulties or fines for breaching a partnership. If the very act of separating from a partner causes unpleasantness for the disloyal individual or for the couple that decides to split up, the tendency to preserve stability will grow.