Next week I will present a paper about public school choice based on the mechanism design approach. A mechanism design approach for the matching between schools and students have a long history. As a background information, an introduction for the one of the earliest studies, Gale and Sharpley (1962) is given here.
We first look what’s called College Admission Problem. A set of applicants is to be assigned among a set of colleges. Each applicant ranks the college in the order of his/her preference. Similarly each college ranks the student in order of preference. We want to find the assignment that is stable and optimal:
* An assignment of applicants to colleges will be called unstable if there are two students X and Y assigned to college A and B, although student X prefers college B to A and student Y prefers college A to B.
* A stable assignment is called optimal if every applicant is at least as well off under it as under any other stable assignment.
To solve the problem, deferred-acceptance procedure is introduced. First, all student apply to their first choice college. A college puts preferred student in the waitlist, and rejects the rest. Then rejected applicants apply again, but this time to their second choice. And then the college compares all the student among new applicants and those in the waitlist, and rejects the rest. This procedure terminates when every applicant is either on a waitlist or has been rejected by every single college he/she applied. This deferred-acceptance procedure is proven to achieve the stable, optimal matching between students and colleges.
Another (and possibly more interesting) well-known matching market is Marriage Problem. Think of a community with n boys and n girls. To use deferred acceptance procedure, let each boy propose to his favorite girl. Each girl who receives more than one proposal rejects all but her favorite from among those who have proposed to her. However, she does not accept him yet, but keep him on a string to allow for the possibility that someone better may come along later (!).
It’s time for the second round. Those boys who were rejected from the girl last time now proposes to their second favorite girl. Each girl receiving multiple proposals compares all proposers (including the boy on a string..!) and rejects all but the favorite boy. The procedure continues until all girls gets her proposal, and then finally each girl truly accept the boy on her string.
Now this community has n stable, optimally married couples.
Reference: Gale D. and Shapley L.S., College Admissions and the Stability of Marriage, The American Mathematical Monthly (1962).