## School ChoiceIt may come as a surprise that mathematics is increasingly used in situations of this kind to elicit true information....Joseph Malkevitch
## IntroductionPart 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. ## Two-sided marketsHere 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 of this kind come up, with similarities and differences in the situations when: - boys are to be matched with girls for a school dance
- students are applying to colleges which have preferences for who gets admitted
- students apply to fraternities or sororities with preferences on each side
- students who apply for housing at a university and must be matched to available housing stock
- people who are willing to donate a kidney to someone who needs a transplant and people needing a transplant
- law school graduates who apply for a court internship and judges seeking interns.
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. Figure 1 Figure 2
Figure 3
Figure 4
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)
## Vanilla Gale-ShapleyHere 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 ## Stable matchingsThe 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
Again, it is known that there are exactly 10 stable marriages for this set of preferences and that for ## School choiceIn 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 ## References:Abdulkadiroglu, A., College admissions with affirmative action, Int. J. Game Theory, 33 (2005) 535-549. Joseph Malkevitch 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 |