Posted September 2009.
It may come as a surprise that mathematics is increasingly used in situations of this kind to elicit true information....
Part of good parenting is wanting to maximize the opportunities that are available for one's children. One adage in this spirit is "To get a good job get a good education." So for parents, a good education begins with the schools that a young child attends as he/she is growing up. For those not rich enough to consider private schools and for parents with the freedom to do so, often getting the best possible school for one's child is finding a place to live where the local school - the neighborhood school - is a good one. However, especially in many urban areas many neighborhoods have schools which are poorly regarded by parents, or became so after a family moved to a particular school district. School officials, partly with the view that competitiveness among schools would increase their quality, started to offer parents choice about where they could send their kids. (Although kids sometimes are involved or consulted about where they want to go - more so for high school students than elementary school students - in practice, the politics of school choice involves pleasing parents.) However, if parents are allowed to choose any (public) school in a city or a geographic area they wish, there may be a drastic imbalance between which schools parents would like their children to go to and the number of places that a given school has to accept students.
Here we will begin with a general discussion of mechanism design in a relatively narrow class of situations, but situations which nonetheless frequently affect us directly or indirectly. The kinds of situations involved are often referred to as matching problems or two-sided markets. The type of market we have in mind is not the kind of situation where random buyers and sellers interact but a "centralized market" where two kinds of agents are "paired." The basic idea is that one has two groups of "players," though it is not always the case that the players actively compete against each other. Perhaps we have boys and girls at a school dance who have to be paired off, or perhaps a central clearing house to match together students at a college who wish to join a sorority or fraternity. In real-world versions of these market problems one important consideration is that the market clears, that is, players involved get some form of satisfaction by providing matches for all those who desire them. In the school choice setting this means that every student gets assigned to some school, hopefully a highly preferred school, and the schools get as many students as they truly want.
Matching problems of this kind come up, with similarities and differences in the situations when:
What makes these kinds of problems interesting from a mathematical point of view is that there is a mathematical literature that deals with the theory of such two-sided markets as well as an empirical literature about such situations in practice that date to both before and after the theoretical discussions. Thus, we can see how theory and practice interact by using historical (actual) data. Sometimes the theory explains what has been seen in the past and sometimes the theory has to be extended to try to get insight into why similar situations play out in different ways.
Note that this is exactly the same matching as:
(Photo of David Gale courtesy of the University of California at Berkeley News Center)
(Photo of Lloyd Shapley obtained from Wikipedia)
(Photo courtesy of Rob Irving)
(Photo courtesy of Al Roth)
Here is how the algorithm (a step-by-step procedure, guaranteed to terminate in a finite number of steps) that Gale and Shapley developed works. It is sometimes called the Gale-Shapely Marriage Algorithm or, as we will sometimes refer to it here, the deferred acceptance algorithm. The basic idea is that either the men "propose" to the woman (or vice versa). At a given stage of the algorithm, say where the men propose, a woman will have no men to choose from or several. If there are several, a woman chooses the best of these but there is a possibility that from her perspective someone better may come along later, so if she has a choice she only accepts her best suitor provisionally (we are assuming there are no ties). Only at the end will the algorithm guarantee that every man will be matched with some woman, and that all the matches will be stable!
The Gale-Shapley algorithm can be run with either the boys proposing or the girls proposing, and in either case a stable matching exists, and in some rare cases it is also the same matching. However, in general, as in the example above, the two matchings one gets are different. Because of the elegance of the Gale-Shapley ideas and procedures and the strong symmetry of what happens for this algorithm, it may be tempting to think there are not a lot of stable marriages possible for "general" preferences of the men and women. However, this is definitely NOT the case. Although there are lots of lovely results about the number of stable marriages when there are n people involved, there are still lots of open questions.
Again, it is known that there are exactly 10 stable marriages for this set of preferences and that for n = 4 this is the largest possible number of stable matchings. These 10 matchings are listed below. For example, 3142 means that Man 1 married to Woman 3, Man 2 to Woman 1, ..., and Man 4 is married to Woman 2.
In the school choice environment there has been a fascinating and developing interplay between "theory" and "applications." Whereas the original deferred acceptance algorithm was formulated within the context of having n men and n women rank each other with strict preferences and no truncation (there was no possibility of being unmatched), the school choice environment does not allow the "vanilla" version of Gale-Shapley to be implemented. It was originally formulated so that no woman (or man) would rather be "not married" than paired with the particular choice of men (women) she (he) faced, and thus, had to make some choice among the persons available. Over the years there have been many extensions and generalizations of the theory that is associated with the basic Gale-Shapley model that we have described here. In particular, one realistic extension to the school choice case allows schools to rank groups of students equally and students to be indifferent between several schools.
Abdulkadiroglu, A., College admissions with affirmative action, Int. J. Game Theory, 33 (2005) 535-549.
Those who can access JSTOR can find some of the papers mentioned above there. For those with access, the American Mathematical Society's MathSciNet can be used to get additional bibliographic information and reviews of some these materials. Some of the items above can be accessed via the ACM Portal , which also provides bibliographic services.
Welcome to the
These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.
Search Feature Column
Feature Column at a glance