School Choice
Posted September 2009.
It may come as a surprise that mathematics is increasingly used in situations of this kind to elicit true information....
Joseph Malkevitch
York College (CUNY)
malkevitch at york.cuny.edu
Introduction
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.
Another complicating factor is that although parents may be aware of the choices for schools available to their children, they may not know how best to use this information. For example, they may not understand the way that information about their preferences among several school choices are actually used. Thus, they may, when asked to give information to a school system about what schools they would like their children to attend, be tempted not to give their true preferences but mis-report their true preferences in the expectation that this misrepresentation will actually help their child get a better school assignment than would otherwise have been the case.
It may come as a surprise that mathematics is increasingly used in situations of this kind to elicit true information. Mechanism design is the area of mathematics and economics that is concerned with issues of this kind. The idea is to design a system which by the nature of its operations encourages people to "disclose" information which is private to them (i.e. give truthful information) because otherwise they will be "hurt." If an organization announces in advance certain information, there are times when one can use mathematics to show that mis-reporting information in such a situation is to one's advantage. However, there are circumstances where using mathematical ideas, typically from the theory of games, one can show that the best response someone has to the way a system is designed is to act in a truthful way. When this truthful way is not only of benefit to the individual but also to a broader community (society), something important has been accomplished.
Two-sided markets
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.
The example we will use here is that of school choice. One group of players is the parents of children who need to be placed in schools. The other set of players are the schools the students will enroll in. In practice, the individual schools may not select the students to attend but the decision may be made by a single player, the "school system." Thus, we have a centralized system for doing the pairings.
Before discussing the way mathematics comes into the school choice environment, first let me give some additional highly studied examples of two-sided markets (matching problems). Every year students who graduate from various professional programs such as medical schools need to be matched with hospitals which offer initial employment and additional training for the medical school graduates. These positions are know as residencies. Medical school graduates try to get residencies in cities they find it attractive to live in and at hospitals which are seeking someone with their particular area of interest (family medicine, neurology, psychiatry, etc.) or which are perhaps affiliated with famous universities or medical schools. The hospitals, on the other hand, want students with particular specialties and perhaps better-than-average grades.
There is a long history of "markets" to match medical school graduates and medical residents in both the United States and Great Britain (though in Britain the terminology is not the same as in the US). To fill in more detail of what is involved we have a situation where in essence the hospitals rank the students and the students rank the hospitals. For simplicity here we will assume that the rankings which are produced do not have ties. How does one handle that there may be students whom no hospitals want and hospitals that no students want? Is there a way to deal with the fact that some hospitals might rather have positions unfilled than take some students? Might there be some hospitals that a student would rather not be matched with at all? Yes, this situation can be handled but here we will shortly look at how the matching procedure can be carried out in its simplest form.
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.
Again, before returning to the school choice problem, let me say a bit about the simplest of these models and show how there is a very elegant theory of such markets from a mathematical perspective.
For simplicity let us use the terminology of men and women. Suppose that there are equal numbers of men and women and that we want to pair off men and women, as at a dance. Sometimes the language of "marriage" - proposals and rejected proposals is used here. We will assume each man ranks each of the women without indifference and each woman ranks each of the men without ties.
By way of a specific example, Figure 1 shows 4 men, names m1, ...., m4 who have ranked the four women w1, ..., w4, while Figure 2 shows the rankings that the 4 women ranked by the men, give the men. This particular notation was developed by the British political scientist Duncan Black in the context of ranking candidates in an election. The arrows show the direction of preference, more preferred towards the top. There are many notations for the ways of giving preference, in the form of lists or tables. The notation below is perhaps clearer than many but is not typographically succinct.
Figure 1
Figure 2
One can give the rankings of the women by the men in a table or matrix form as shown in Figure 3, and the information in Figure 2 is given in matrix form in Figure 4.
Figure 4
This notation also takes up a lot of room, so a variety of condensed notations that involve lists ordered from left to right, with preferred "mates" appearing further to the left are used. Such notations make it easier to enter data for large problems into computers so they can be solved quickly. Other notations have been developed that preprocess the information in the preferences so that the algorithms involved in finding "good" matches are speeded up.
One way to match men to women would be to just set up pairs at random. However, if we do this it is not very likely that any particular individual will be happy with whom they were assigned to. However, just to get the flavor of what is going on here, consider the matching:
m1 with w3
m2 with w2
m3 with w1
m4 with w4
Note that this is exactly the same matching as:
w1 with m3
w2 with m2
w3 with m1
w4 with m4
The only thing that has changed is the order in which the man or woman in a pair is listed first.
Consider the pairing (matching) w2 with m2. Note, w2 is m2's second choice and m2 is w2's 3rd choice. Who is m2's first choice? This would be w1 as can be seen by consulting Figure 3. Now, whom is w1 paired with in the current matching? She is paired with m3. By consulting Figure 4 we see that m3 is her 4th choice. So had we paired m2 with w1, these two individuals would be happier than they are with the current pairing. Assuming that the "jilted" people now pair, we have:
m1 with w3
m2 with w1
m3 with w2
m4 with w4
Thus, there is the risk, in some matchings, that two individuals will break their current pairing to get together. When one or both of the individuals in a pairing P, say person p, would rather be paired with someone else, q, than the person they are paired with, and q would rather be paired with p than with q's current "mate," the pairing P is called unstable (with respect to the current matching). Matchings which include unstable pairings seem to be undesirable because it makes "divorce" possible. There is no guarantee that unstable pairs will break up but the potential is there. So if we can avoid such pairs in a matching, this would seem to be highly desirable.
Starting with a random pairing, if all the pairs in this matching are stable we might be happy but we might wonder if there are unstable pairs and if we can break these pairs to get a new matching. In the example above we got rid of an unstable pairing but there is no guarantee that the new matching pairs are all "stable." In fact, it turns out that one cannot be certain that this approach results in a stable matching eventually because one can move from one new matching to another, each time breaking up an unstable pairing but eventually going around in a cycle to a matching one has been at previously.
Is there a procedure (algorithm) which starts with preference tables such as those in Figure 3 and Figure 4 and which can guarantee that when the procedure terminates we have a stable matching? The surprising and amazing answer is "yes!"
The theory of stable marriages and how to find them basically goes back to Lloyd Shapley and David Gale. The question was originally posed by Gale, and Shapley provided an algorithm.
(Photo of David Gale courtesy of the University of California at Berkeley News Center)
(Photo of Lloyd Shapley obtained from Wikipedia)
David Gale did important work in mathematical programming, mathematical economics, and game theory. Lloyd Shapley is one of America's most prominent game theorists. The game solution concept known as the Shapley Value is named for him.
Literally hundreds of theoretical and applied research papers have grown out of the work of Gale and Shapley. These papers are shaped by people with expertise in mathematics, computer science, economics, business, and many other areas of expertise. Two significant contributors to different aspects of the Gale-Shapley circle of ideas are Robert W. Irving and Alvin Roth. They have contributed by collaborations with many people and working with many students and colleagues (see references for their many joint and solo publications).
(Photo courtesy of Rob Irving)
(Photo courtesy of Al Roth)
Their work has ranged over a wide range of variants, pure and applied, of Gale-Shapley models. Roth comes at these questions from the perspective of an economist and Irving from that of a computer scientist. More and more we are getting insight into pure and applied aspects of the Gale-Shapley model via a broader and broader range of skills and interests on the parts of the people who investigate these problems.
Vanilla Gale-Shapley
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!
Rather than describe the algorithm in abstract general terms we will work through a specific example (the one coded in Figures 3 and 4 above), from which it should be clear how the algorithm works in general. We will consider first how the Gale-Shapley algorithm works when the men "propose" to the women. Later, we will consider the version where the women "propose" to the men. The algorithm will progress in "rounds." At the start, each woman is sitting behind a desk (say in a gym). In each round each man will "propose" to some woman. A particular woman may get no suitors or several. If she gets none, she waits until a future round when a suitor will appear. (There are variants of this algorithm where men might rather be single than paired with any particular woman, and women might prefer to be single than paired with any particular man, in which case one has to modify what is described here.) Each round begins with a signal (say, a bell). When the bell rings any man who has not been provisionally accepted by some woman goes to the highest woman on his list who has not already rejected him. Women who get proposals pick provisionally the highest man on their list from the suitors who show up.
For our example, with the men proposing, here is what happens:
Round 1:
m1 proposes to w1 as does m2, while both m3 and m4 propose to w3.
Now, w1 has two suitors m1 and m2. Since she prefers m2 she provisionally accepts him (and her other suitor m1 will have to try the next woman on his list in the next round). Similarly, w3 accepts m3 (since she prefers m3 to m4) and m4 will go on to a lower preference choice in the next round.
Round 2:
m1 will propose to w3 and m4 will propose to w1.
Now w3 was provisionally matched with m3 so she now has to pick between him and her newly arriving suitor m1. Since she prefers m1 to m3, she lets go of m3 and provisionally accepts m1.
Also, w1 was provisionally matched with m2 and now m4 also arrives as a suitor. Since m2 is, in fact, her first choice, she sends m4 on to a lower choice.
Round 3:
Both m3 and m4 propose to w4. Previously, she had no suitors. She prefers m4 and so m3 will try to find acceptance from some lower choice. The other two women (w1 and w3) will continue to the next round with their provisional choices.
Round 4:
Now, m3 tries w1 (who provisionally has m2) and given her current choices she again stays with m2 and m3 must again try for a lower choice.
Round 5:
m3 tries w2. Since she has no suitors she accepts him, and we now have a matching since no woman has several suitors.
This matching is:
w1 with m2
w2 with m3
w3 with m1
w4 with m4
Is this match stable? The theorem that Gale and Shapely proved indicates that it must be. Furthermore among all matchings that can be found which are stable, each individual male is as well off as he can be in any stable matching and each woman is as badly off as she can be in any stable matching! When the men propose we get a "male optimal" and "woman pessimal" matching, already a perhaps surprising consequence of doing the mathematics.
What happens when the women propose? Following the same procedure as above but with the men behind the desks and the women moving around as required, we get the matching:
m1 with w1
m2 with w2
m3 with w3
m4 with w4
By symmetry, it is perhaps not surprising that this stable matching is favorable to the women at the "expense" of the men. This matching is woman optimal and male pessimal.
It is not difficult to extend this basic theory to the case where some men would rather not be paired with any of the available women and some women would rather not be paired with the available men. Furthermore, for the case where the men are "students" and the women are "hospitals" and we seek to fill hospital positions with students, we can allow for the hospitals to have more than a single slot to be paired with, so we can think of the hospitals as having quotas or positions to be filled.
In conjunction with the matching situation for hospitals and medical students, a bit generalized for allowing students or hospitals to be matched with themselves (which from a student point of view there are hospitals which they will turn down by preferring to be matched with "themselves" rather than go to these hospitals), we can get an insight into the way that the desire for stability interacts with society's goal of having hospitals in rural and/or unpopular cities get desired staff.
Theorem: If students and hospitals have strict preferences in ranking each other, the set of students who get offers and the set of hospitals which get their positions filled are the same for every stable marriage!!
This means that stability has very important implications for students who have characteristics that might be "unpopular" and "hospitals" that have characteristics which might be unpopular. We can't remedy the situation by moving to some other stable pairing. Furthermore, there is also this remarkable theorem (due to A. Roth) which sheds light on using the Gale-Shapley "theory" in applied settings:
If students and hospitals have strict preferences, and if a particular hospital does not get all of the students it wishes (i.e. fill the quota of seats that it wants to have filled) in some specific stable matching M, then for all other stable matchings it will have exactly the same set of students!
These theorems have the effect that those hospitals which have trouble finding doctors to come to them cannot solve their situation by "tinkering" with the way a stable matching is picked out from the set of stable matchings. There is a trade-off between having stability and getting these hospitals to have their quotas filled when there is a broad perception they wold not be a good place to work.
Stable matchings
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.
Let's begin with the example of the preference tables below. How many stable marriages do you think there are in this case? (This example is due to Dan Gusfield and R. Irving.) It turns out there are 10 stable marriages.
| |
1st |
2nd |
3rd |
4th |
| m1 |
w1 |
w2 |
w3 |
w4 |
| m2 |
w2 |
w1 |
w4 |
w3 |
| m3 |
w3 |
w4 |
w1 |
w2 |
| m4 |
w4 |
w3 |
w2 |
w1 |
| |
1st |
2nd |
3rd |
4th |
| w1 |
m4 |
m3 |
m2 |
m1 |
| w2 |
m3 |
m4 |
m1 |
m2 |
| w3 |
m2 |
m1 |
m4 |
m3 |
| w4 |
m1 |
m2 |
m3 |
m4 |
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.
Stable marriages:
1234 (male optimal), 2134, 1243, 2143, 2413, 3142, 3412, 4312, 3421, and 4321 (woman optimal)
John Conway (as reported by Donald Knuth) called attention to the fact that the collection of all stable marriages forms an algebraic structure called a "distributive lattice." Intuitively, this systematically offers a way to "order" the stable marriages which lie "between" the male optimal and female optimal stable marriages. Furthermore, though it is still an open problem to count the largest number of stable marriages in terms of the number of people in the market n, it is known that for every n which is a power of 2, there are preference tables for the men and women where there are at least 2n-1 stable marriages. (For example, for n = 8 (eight men and women rank each other), this theorem says there is an example with 128 stable marriages.)
It would be nice to know for a given n the formula for the largest number of stable marriages. Furthermore, one might not care too much if there are lots of stable marriages for some "weird" set of preferences. What might really matter is what happens for either "typical" cases or "random" cases. Not surprisingly scholars have taken an interest in questions of this kind not only because they seem interesting from a theoretical point of view but because there are also practical concerns about how much "freedom" there is to find a stable marriage. When might finding a stable marriage be like looking for a needle in a haystack? (In the simplest version of Gale-Shapley problems we know there are typically two (at least 1) stable matchings, the male and female optimal ones. However, in some extensions of the basic model there is no guarantee that stable marriages exist. Yet, in practice, for large markets (ones with lots of players) there often seem to be stable marriages even though the theory does not guarantee this.
Borrowing from issues that have turned out to be important in other areas involving fairness questions (elections and fair division) we might ask what the consequences are of the men and women "mis-reporting" their true preferences. For example, if one has information about other men's likes and dislikes, a particular man might believe that if he misrepresents his true preferences he might be better off. Roth has shown that under fairly general assumptions about the nature of a two-sided market there is no "stable" matching mechanism design where stating one's true preferences always makes each player (hospital or student) better off. On the other hand, when one of the parties to a matching situation (say the school system) is not an active but a passive player, then one can under some circumstances design a mechanism which encourages the student side of the market to be truthful.
The most studied interaction between ideas related to the Gale-Shapely model and settings in which two-sided markets actually exist has been in the area of placing doctors seeking "residencies" with hospitals, or the equivalent situation in Great Britain. A variety of systems using different algorithms have actually been set up and implemented. The fascinating discovery has been that when these matching systems obeyed the requirement of stability, they "worked" while when the did not obey stability they tended to "unravel." What this means is either the hospitals would make commitments earlier and earlier in the education process of the doctors who would years later be seeking hospital placements, or the time that a doctor had to accept a placement would get shorter and shorter to prevent the doctors from negotiating with other hospitals to find what they hoped would be a better placement than the one offered to them. Many fascinating studies have appeared to get insight into why systems that do not guarantee stability might not "unravel" and what is special about those "markets" where, despite the fact that stability is not guaranteed, sometimes the "markets" do not fall apart. This information sets the stage for an interplay between having the theory of two-sided markets be in closer accord with what is planned in advance (versions of deferred acceptance systems in new settings) as well as historically implemented or evolving 2-sided markets.
Another aspect of these placement markets is that the theory has shed light on why it is difficult for rural communities to get doctors to accept placements in their hospitals as mentioned above.
The NRMP (National Residents Matching Program, - which evolved from the NIMP program, National Intern Matching Program) is a voluntary system for pairing doctors seeking residencies and hospitals seeking doctors. NRMP has a long and fascinating history. In response to a market which was "chaotic," this matching system was developed; it used an algorithm which led to stable matchings though the approach was not that of the Gale-Shapley work which came later. For a long time the system used the hospital optimal approach but the system has evolved to its current algorithm in a variety of ways to deal with being more "student" friendly and also to deal with the problem of "couples." Theory shows that when one tries to expand the Gale-Shapley model to deal with couples, one can produce examples where stability is not always guaranteed. Nonetheless steps can be taken to avoid having the market break down in a way that handles couples much of the time. NRMP has approved new changes in the way its system works (to start in 2011).
School choice
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.
To give some of the flavor of what happens in a realistic version of the school choice problem, here is a simplified description of the evolution of what happened in New York City at the high school level. Students typically (together with their parents) must decide at the end of the 8th grade (or for some schools at the end of 9th grade) in which high school to continue their education. Students have the choice of attending a public school, but some will choose to attend a private high school if their family can afford it when they are unable to get an acceptable public high school assignment from their point of view. In the fall of each new academic year, parents and children work to apply for a high school placement for the following year. New York City maintains a system of "neighborhood high schools" but it also has specialized schools which require that students who wish to attend these schools take a special examination. Approximately 90,000 students are involved each year in wanting placements; the specialized high schools have 4000-5000 places. In designing a system to match schools and applicants, the city reached out to experts in the field. There were a variety of considerations that the "mechanism designers" needed to take into account.
These included:
a. Producing stablematchings of students to schools. (The difficulty of having a market using unstable matchings is alluded to above.)
b. Producing matchings which are "efficient" (Pareto optimality kinds of conditions). The issue here is that while a matching might be stable, there would be other stable marriages that some students prefer while other students are no less happy with these other matchings. One can look at "efficiency" from the point of view of all players, only the schools, or only the students. In the background here is that when a relatively simple version of Gale-Shapley that we discussed is used in the student propose version, then the students can do no better than with any other stable matching.
c. Having students (parents) report preferences for the schools being applied to honestly, rather than using some strategic reporting of preferences in the hope of getting better placements. Having a system that encouraged honesty would be valuable. (Data from the use of a school choice system in Boston which had been based on a mechanism design different from the Gale-Shapley deferred acceptance approach suggested a discrepancy between the pride being taken by the school system in giving students high ranking choices, and the reality of the satisfaction with actual placement. Thus, the school system claimed high level of satisfaction because the satisfaction was being based on rankings which, in fact, were not true rankings. When polls were taken which compared actual assignments with true rather than "strategic" preferences, the results were much less positive. Eventually Boston changed the system it used to try to avoid problems which had arisen from the system it was using.)
Another issue with respect to the honesty of the expressed preferences which are produced by the participants in the two-sided market has emerged from the analysis of what was done with choice mechanisms in the past. For example, in the school choice environment a school can announce publicly that it has 150 seats, when in fact it really has 200 seats and it plans to use those "hidden" seats in some way outside the matching mechanism to help it fill seats. Researchers are now trying to study how to avoid this situation and get more "transparency."
d. Dealing the assignment of students to specialized schools which have limited capacity.
e. Dealing with ties (although in some cases the schools have preferences for particular students, there are also large groups of students about whom the schools are "indifferent"). The reality is that depending on how ties are broken the students may not be equally satisfied with the outcomes of the different ways ties are broken. Thus, the system by which ties are broken might affect the efficiency of the system in a subtle way. One can break ties using a number assigned to each student at each of the schools or one can assign student tie-breaking numbers for the individual schools differently.
f. Limits to how many schools a student can apply for.
Many school systems have so many choices that it is not realistic to have all the students rank all of the programs. Hence, it seems that it may give better outcomes to limit how many choices the students can make in the number of schools they apply to.
Mathematics evolves because it generates intrinsically interesting internally generated questions and responds to the need to solve problems that arise in fields like business, economics, biology or physics. Jeff Dinitz posed a "pure mathematical" question in 1979 about latin squares which Fred Galvin answered in 1994. The method of solution used the Gale-Shapley model! Unexpected connections of this kind are one of mathematics' great charms. Gale-Shapley's beautiful model continues to grow and be used in response to problems arising in such areas as school choice. These are exciting times for both pure and applied mathematics.
References:
Abdulkadiroglu, A., College admissions with affirmative action, Int. J. Game Theory, 33 (2005) 535-549.
Abdulkadiroglu, A. and Y. Che, Y. Yasuda, "Expanding Choice" in School Choice, Duke University, (Unpublished manuscript.)
Abdulkadiroglu, A. and P. Pathak, A. Roth, The New York City high school match, Amer. Econ. Review, Papers and Proceedings, 95 (2005) 368-371.
Abdulkadiroglu, A. and P. Pathak, A. Roth, T. Sönmex, The Boston public school match, American Econ. Review, Papers and Proceedings, May, 2005.
Abdulkadirogu, A. and T. Sönmez, House allocation with existing tenants, J. Econ. Theory, 88 (1999) 233-260.
Abdulkadirogu, A. and T. Sönmez, School choice: A mechanism approach, American Econ. Rev., 93 (2003) 729-747.
Balinski, M. and T. Sönmez, A tale of two mechanisms: Student placement, J. of Econ. Theory, 84 (1999) 73-94.
Barberà,S. and B. Dutta, Protective behavior in matching models, Games Econ. Behavior, 8 (1995) 281-296.
Chen, Y. and T. Sönmez, Improving the efficiency of on-campus housing: an experimental study, Amer. Econ. Rev., 92 (2002) 1669-1686.
Chen, Y. and T. Sönmez, School choice: an experimental study, J. Econ. Theory, 127 (2006) 202-231.
Demange, G. and D. Gale, M. Sotomayor, A further note on the stable matching problem, Discrete Applied Math., 16 (1987) 217-222.
Dubins, L. and D. Freedman, Machiavelli and the Gale-Shapley Algorithm, Amer. Math. Monthly, 88 (1981) 485-494.
Ehlers, L., Respecting priorities when assigning students to schools, CIREQ, Feb., 2006.
Erdil, A., Two-side Matching with Ties, Doctoral Thesis, Department of Mathematics, U. of Chicago, 2006.
Erdil, A. and H. Ergin, What's the matter with tie breaking? Improving efficiency in school choice, Amer. Econ. Review, 98 (2008) 669-689.
Ergin, H. and T. Sönmez, Games of school choice under the Boston mechanism, J. of Public Economics, 90 (2006) 215-237.
Featherstone, C. and M. Niederle, Manipulation in school choice mechanisms, Working paper, Stanford U., 2008.
Featherstone, C. and M. Niederle, Ex ante efficiency in school choice mechanisms: an experimental investigation, (to appear).
Gale, D. and L. Shapley, College Admissions and the stability of marriage, Amer. Math. Monthly, 69 (1962) 9-15.
Gale, D. and M. Sotomayor, Some remarks on the stable matching problem, Discrete Applied Math., 11 (1985) 223-232.
Gale, D. and M. Sotomayor, Ms. Machiavelli and the stable matching problme, Amer. Math. Monthly, 69 (1985) 261-268.
Gusfield, D., Three fast algorithms for four problems in stable marriage, SIAM J. on Computing, 16 (1987) 111-128.
Gusfield, D., The structure of the stable roommate problem: efficient representation and enumeration of all stable assignments, SIAM J. on Computing, 17 (1988) 742-769.
Gusfield, D. and R. Irving, The parametric stable marriage problem, Information Processing Letters, 30 (1987) 255-259.
Gusfield, D. and R. Irving, The Stable Marriage Problem, MIT Press, 1989.
Gusfield, D. and R. Irving, P. Leather, M. Sakes, Every finite distributive lattice is a set of stable matchings for a small stable marriage instance, J. of Comb. Theory A, 44 (1987) 304-309.
Haeringer, G. and F. Klijn, Constrained school choice, J. Economic Theory, (to appear)
Huang, C., Cheating by men in the Gale-Shapley matching algorithm. (Preprint)
Huange, C., How hard is it to cheat in the Gale-Shapley stable matching algorithm, (Preprint).
Irving, R., An efficient algorithm for the stable room-mates problem, Journal of Algorithms, 6 (1985) 577-595.
Irving, R. and P. Leather, The complexity of counting stable marriages, SIAM J. on Computing, 15 (1986) 655-667.
Irving, R. and P. Leather, and D. Gusfield, An efficient algorithm for the "optimal" stable marriage, Journal of the A.C.M., 34 (1987) 532-543.
Kesten, O., Coalitional strategy-proofness and resource monotonicity for house allocation problems, International J. Game Theory, 38 (2009) 17-21.
Knuth, D., Marriages stable, Les Presses de l"Universite de Montreal, Montreal, 1976.
Kojima, F., Games of school choice under the Boston mechanism with general priority structures, Soc. Choice Welfare, 31 (2008) 357-365.
Kojima, F. and P. Pathak, Incentives and stability in large two-sided markets. (Preprint)
McVittie, D. and L. Wilson, Stable marriage assignments for unequal sets, BIT, 10 (1970) 295-309.
McVittie, D. and L. Wilson, The applications of the stable marriage assignment in university admissions, Operational Research Quarterly, 21 (1970) 425-433.
McVittie, D. and L. Wilson, The stable marriage problem, Communications of the ACM, 14 (1971) 486-492.
Mongell, S., Sorority rush as a two-sided matching mechanism: A Game Theoretic Analysis, Doctoral Dissertation, Department of Economics, University of Pittsburgh, 1987.
Mongell, S. and A. Roth, A note on job matching with budget constraints, Economics Letters, 21 (1986) 135-138.
Niederle, M. and A. Roth, T. Sönmez, Matching, The New Palgrave Dictionary of Economics, (Second edition).
Pais, J. and A. Pinter, School choice and information: an experimental study on matching mechanisms, Games and Econ. Behavior, 64 (2008) 303-328.
Romero-Medina, A., Equitable selection in bilateral matching markets, Theory and Decision, 58 (2005) 305-324.
Roth, A., The economics of matchings: stability and incentives, Math. of Operations Research, 7 (1982) 617-628.
Roth, A., The evolution of the labor market for medical interns and residents: A case study in Game theory, J. of Pol. Econ., 92 (1984) 991-1016.
Roth, A., The college admissions problem is not equivalent to the marriage problem, J. of Economic Theory, 36 (1985) 277-288.
Roth, A. A natural experiment in the organization of entry level labor markets: regional markets for new physicians and surgeons in the U.K., Amer. Economic Review, 81 (1991) 415-440.
Roth, A., The economist as engineer: Game theory, experimental economics and computation as tools of design economics, Econometica 70 (2002) 1341-1378.
Roth, A., What have we learned from market design?, Economic Journal, 118 (2008) 285-310.
Roth, A. and E. Peranson, The redesign of the matching market for American physicians: some engineering aspects of economic design, American Econ. Rev., 89 (1999) 748-780.
Roth, A. and T. Sönmez, M. Ünver, Pairwise kidney exchange, J. Economic Theory, 125 (2005) 151-188.
Roth, A. and M. Sotomayor, Interior points in the core of two-sided matching markets, J. of Economic Theory, 45 (1988) 85-101.
Roth, A. and M. Sotomayor, The college admissions problem revisited, Econometrica, 57 (1989)559-570.
Roth, A. and M. Sotomayor, Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis, Cambridge U. Press, Cambridge, 1990.
Roth, A. and M. Sotomayor, Two-Sided Matching, Chapter 16, in Handbook of Game Theory, R. Aumann and S. Hart (eds.), Elsevier, 1992, pp. 459-541.
Roth, A. and X. Xing, Turnaround time and bottlenecks in market clearing: Decentralized matching in the market for clinical psychologists, J. of Pol. Econ., 105 (1997) 284-329.
Shapley, L. and H. Scarf, On cores and indivisibility, J. Math. Economics, 1 (1974) 23-37.
Shapley, L. and M. Shubik, The assignment game I: The Core, International J. of Game Theory, 1 (1971) 111-130.
Sönmez, T., Manipulation via capacities in two-sided matching markets, J. Economic Theory, 77 (1997) 197-204.
Sönmez, T., Can prearranged matches be avoided in two-sided matching markets? J. of Economic Theory, 86 (1999) 148-156.
Sotomayor, M., A non-constructive elementary proof of the existence of stable marriages, Games and Econ. Behavior, 13 (1996) 135-137.
Sotomayor, M. Reaching the core of the marriage market through a non-revelation matching mechanism, International J. Game Theory, 32 (2003) 241-251.
Sotomayor, M., The stability of the equilibrium outcomes in the admissions games induced by stable matching rules, International J. Game Theory, 36 (2008) 621-640.
Sotomayor, M., My encounters with David Gale, Games and Economic Behavior, 66 (2009) 643-646.
Teo, C. and J. Sethuraman, W. Tan, Gale-Shapley stable marriage problem revisited: strategic issues and applications, Management Science, 47 (2001) 1252-1267.
Ünver, M., Backward unraveling over time: the evolution of strategic behavior in the entry-level British medical labor market, J. Econ. Dyn. Control, 25 (2001) 1039-1080.
Ünver, M., On the survival of some unstable two-sided matching mechanims, International J. of Game Theory, 33 (2005) 239-254.
Joseph Malkevitch
York College (CUNY)
malkevitch at york.cuny.edu
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.
