Two-Sided Markets (2018)
Prepared by:
Joseph Malkevitch
Department of Mathematics
York College (CUNY)
Jamaica, New York 11451
email:
malkevitch@york.cuny.edu
web page:
http://york.cuny.edu/~malk
Four students are graduating from high school and they are required to have a summer (unpaid) internship in order to graduate. Unfortunately, this summer they are only 4 internships available. The school system's goal is to pair off students to the internships based on information provided by the students, and companies providing the internships. The students are to rank the internships available without being indifferent between any of the choices, and similarly, the companies must rank the students without the option of being indifferent. Students are not allowed to not take an internship and companies cannot say that any student is unacceptable - so the goal is to pair off the students to internships in some "sensible" way based on the information that is available, which is limited to the "preference" information provided. This assignment is to be done by a "central" clearing house, and our concern is to make the assignment on some "sensible" basis.
Problems of this kind are known as two-sided markets and the simplest case involves have two equal sized collections of "things" to be paired. Rather than pairing students to internships as above, tradition usually sets problems of this kind as pairings between men and women - and sometimes this kind of problem is referred to as a "marriage problem." So the men and women, rank each other without ties and there will be no option to stay "single." Men will be paired off with women and the goal is to do this in some "sensible" or "optimal" manner. The only input we will have in choosing a pairing will be the preferences of the people involved. In an actual application for a dating service we might have information about income of the men and women and/or their previous marital history. While one might want to "improve" the model this "simple" model is very rich from a mathematical point of view.
Our next task is to try to represent the information of the problem in a succinct and useful manner. One way to do this might be to indicate each man's preferences for the women using the notation shown below similar to a ballot in conducting an election:
What this diagram says is that man 1 ranks woman 1 first, woman 3 second and woman 2 third. However, diagrams like this are not that easy for typesetters! For our situation where we have 4 men and women we would need 4 diagrams like the one above for each man (which included the man's rank for woman 4) and 4 diagrams like the one above for the women (which included ranks for all 4 men). Instead, we will work with the assistance of two tables (matrices), one showing the male preferences and the other showing the women's preferences. We will denote the women by w1, w2, ..., wn and the men by m1, m2, ...., mn. The rows of these matrices (tables) will display the numbers from 1 to n with the LOWER the number the higher the rank. So, when man i ranks woman j with a k, it means she is his kth highest choice. If there are 4 women and men, the highest ranked woman by man i will have the label 1 and the lowest will have rank 4.
Figure 2 shows what might be the information provided by the students and companies offering internships for the situation described at the beginning. To move to the male/female approach, we will say that the boys are taking the role of the students and girls the role of the companies. Note that in Figure 2, for the men's preferences each row uses the numbers 1 to 4 since each man must rank the women without ties and similarly for the women ranking the men.
Men's preferences:
| w1 | w2 | w3 | w4 | |
| m1 | 1 | 4 | 3 | 2 |
| m2 | 1 | 3 | 2 | 4 |
| m3 | 2 | 1 | 4 | 3 |
| m4 | 2 | 3 | 4 | 1 |
| m1 | m2 | m3 | m4 | |
| w1 | 4 | 1 | 2 | 3 |
| w2 | 3 | 1 | 4 | 2 |
| w3 | 4 | 3 | 2 | 1 |
| w4 | 4 | 2 | 3 | 1 |
Let us compute for each man and woman in the pairings ("marriage") in Figure 3, how satisfied each man and each woman is with the partner assigned to them. For example, man 1 got his 4th favorite choice (woman 2) who got her 3rd choice) while man 4 got his 4th favorite choice (woman 3), and woman 3 got her first choice.
Now woman 2 can get on her cell phone and contacts man 4. She points out that if they get together he will go from his 4th favorite choice to his 3rd favorite choice and she will go from her third favorite choice to her second favorite choice. The pairings shown in Figure 3 are, thus, said to be unstable, and w2 and m4 are called a blocking pair for the pairing (matching) in Figure 3. Two people not paired with each other can be paired and both of them think they are doing better than the "marriage" they currently have.
A pairing M is called a stable matching if no man and woman would rather be paired with each other than with whom they are assigned by M (i.e. no blocking pair.).
Theorem (David Gale and Lloyd Shapley - now both deceased)
Given preference tables for n men and n women (each man ranks each woman; each woman ranks each man; indifference is not allowed) it is always possible to find at least one way to pair the men with the women so the result is stable.
The algorithm given by Gale and Shapley to find a stable marriage is often referred to as the deferred acceptance algorithm. It guarantees at least one stable matching. When the men do the proposing one gets a stable matching and when the women do the proposing one gets a stable marriage. Sometimes these are the same stable matching but often they are different. In general, there can be many more stable marriages than these two. The Gale-Shapley algorithm, works in the following way when the women propose. The procedure is carried out in rounds. In a given round, women "propose" to the next highest man on their preference list who has not already refused them. The men temporarily become engaged to the best woman who makes them an offer in a given round, but will move to a higher ranked woman if one materializes in a later round. Women who are refused in a given round make a proposal to the next highest man on their preference list in the next round. One can prove that after a finite number of rounds there is exactly one woman paired with one man.
Perhaps surprisingly, when women propose the women get their best result among all possible stable matchings and the men get their worst result among all possible stable matchings. The opposite is true when the men propose.
There are many ways to describe an algorithm that is equivalent to the one originally described by Gale-Shapley. However, the G/S algorithm will find a maximum of two stable marriages depending on whether the men propose or the women propose. There are other algorithms which will find all stable marriages. Gale-Shapely can be carried out in polynomial time (quadratic in n, the number of men and women).
There are many applications that have been found for Gale-Shapley algorithm or its extensions. There include matching residents to hospitals, sorority and fraternity rushes, college admissions (here, one side of the market can select many members of the other side of the market because they admit many students each year) and school choice (parents and children working to select k-12 public schools for the benefit of their children).
One interesting footnote about matching markets is that Great Britain has a similar problem to the one in the US of pairing up medical school graduates with "surgeries." In the US, from the beginning a stable matching algorithm was employed. In Britain, however, the initial choice of algorithm did not guarantee (and often in fact did not give) stable matches. These "markets" fell apart in various ways and it is insightful for studying two-sided markets to compare what happens when the market http://www.ams.org/news?news_id=3137 uses an algorithm that gives stable pairings versus unstable ones.
In the United States many male/female doctors marry or become engaged in medical school. They desire to have hospital assignments at the same hospital or at least at nearby hospitals. When information about couples is taken into account there is no guarantee that stable marriages are always possible. However, the US system has been modified to try to take the needs of couples into account. At times in the US the "hospital" optimal version of the algorithm was used and at other times the "student" optimal version. There are still many practical as well as theoretical aspects of two-sided markets that continue to be explored.
References:
Gale, D., and L. Shapley, College admissions and the stability of marriage, Amer. Math. Monthly, 69 (1962) 295-309.
Gusfield, D., and R. Irving, The Stable Marriage Problem, MIT Press, Cambridge, 1989.
Roth, A., and M. Sotomayor, Two-Sided Matching, Cambridge U. Press, New York, 1990.