My colleague Sven Feldmann presented a talk today on Game Theory in Action. The city council where he lives has been using a very common approach for matching children to kindergartens. The Boston Approach (see here for details) involves asking for a preference ranking and making several rounds of offers. This approach is fraught with problems including: inefficient matching, an incentive for parents to misrepresent their preferences, and “justified envy“, whereby a student prefers a school S that she was not admitted to, despite having a higher priority than another student who was in fact admitted to school S.

Sven has persuaded his City Council that they should implement the Gale-Shapley Mechanism instead (see here for details). In step 1, parents get to propose their first ranked kindergarten. Schools temporarily assign seats to proposers based on their expressed priority, others are rejected. In step 2, each rejected parent proposes her next choice. Schools then consider the pool of accepted students plus the proposer, and update their tentative offers based on expressed priorities. This repeats until a stable state is reached, at which point the tentative offers are finalized. So it is a pretty feasible approach to implement. One of its benefits is that it is strategy-proof so parents do not have an incentive to lie about their preferences. Theory also predicts that stable envy-free matching will always occur under the Gale-Shapley approach. So a few changes in behavior can make for a better matching system. But it takes a bit of work to explain this approach and its merits to city councils and parents, as Sven has apparently done with some success.

It is great to see that practical applications of game theory are making a difference in daily life. If you live in a school district that needs help, ask your city council to contact Sven who has a clear and concise explanation of how the different matching techniques work. Or move to Darebin City, Victoria, Australia.

Update: lots of good writeups on school choices are available at http://marketdesigner.blogspot.com/search/label/school%20choice