This year’s Nobel Prize in Economics: STABLE ALLOCATION, MARKET DESIGN AND ‘SCHOOL CHOICE’ + smf’s 2¢

by smf/4LAKidsNews

Jacob Goldstein, in Nobel Goes To Economists Who Actually Solved Problems In The Real World in NPR’s Planet Money blog writes this morning:

For economists, prices are like magic. They send all kinds of signals about who wants what, and how badly they want it. Prices are what makes markets work so well in so many settings.

But there are some things we don't want to put prices on. We don't pay organ donors. Children attend public high schools for free. Medical residents get paid a fixed stipend no matter where they do their hospital training.

This creates a challenge: What's the best way to match organ donors with recipients (when someone wants to give a kidney to a friend, but is not a good genetic match); kids with high schools (in big urban districts with many high schools and many kids); or medical residents with teaching hospitals (when medical residents are married couples and don't want to live thousands of miles apart)?

This year's Nobel (memorial) prize in economics just went to two guys who figured out how to answer questions like these.

Al Roth | Lloyd Shapley >

Lloyd Shapley is a game theorist who wrote some really influential papers in the 60s and 70s. Alvin Roth took that work (and what came after it) and figured out how to solve problems in the real world.

"This is a multi-generation Nobel," Justin Wolfers tweeted this morning. " First, Shapley generated the theory. In the next generation, Roth delivered the practical applications."

Alex Tabarrok writes in his blog Marginal Revolution this AM:

In honor of the Nobel prizes to Al Roth and Lloyd Shapley, here is a primer on matching theory. Matching is a fundamental property of many markets and social institutions. Jobs are matched to workers, husbands to wives, doctors to hospitals, kidneys to patients.

The field of matching may be said to start with the Gale-Shapley deferred choice algorithm. Here is how it works, applied to men and women and marriage (n.b. the algorithm is also good for gay marriage but it’s a little easier to explain with men and women). Each man proposes to his first ranked choice. Each woman rejects any unacceptable proposals but defers accepting her remaining suitors. Each rejected man proposes to his second ranked choice. Each woman now rejects again any unacceptable proposals, which may include previous suitors who have now become unacceptable. The process repeats until no further proposals are made; each woman then accepts her most preferred suitors and the matches are made.

A similar process works when proposal receivers may accept more than one suitor, not that useful for marriage in most of the United States but very useful for when students are applying to schools and each school accepts many students.

Now what is good about this algorithm? First, Gale and Shapley proved that the algorithm converges to a solution for a very wide range of preferences. Second, the algorithm is stable in the sense that there is no man and no woman who would rather be matched to each other than to their current match. There are of course, men who would prefer to marry other women and there are women who would prefer to marry other men but no mutually preferable match is possible. Thus, the algorithm produces a stable match.

The application to men and women is somewhat fanciful, although Match.com should clearly adopt this idea!, but the application to students and schools is very real. Gale and Shapley concluded their paper by writing:

It is our opinion, however, that some of the ideas introduced here might usefully be applied to certain phases of the admissions problem.

Indeed, this is exactly what has happened. Students in New York and in Boston are now matched to schools using versions of this algorithm.

Finally, from the Royal Swedish Academy of Sciences explainer in this morning’s Nobel award:

Matching students and high-schools

The Gale-Shapley algorithm proved to be useful in other applications, such as high-school choice.

Up until 2003, applicants to New York City public high schools were asked to rank their five most preferred choices, after which these preference lists were sent to the schools. The schools then decided which students to admit, reject, or place on waiting lists. The process was repeated in two more rounds, and students who had not been assigned to any school after the third round were allocated through an administrative process.

However, this did not provide the applicants with enough opportunities to list their preferences, and the schools did not have enough opportunities to make offers. As a result, about 30,000 students per year ended up at schools they had not listed.

Moreover, the process gave rise to misrepresentation of preferences.

Since schools were more likely to admit students who ranked them as their first choice, students unlikely to be admitted to their favorite school found it in their best interest to list a more realistic option as their first choice, while applicants who simply reported their true preferences suffered unnecessarily poor outcomes.

In 2003, Roth and his colleagues helped redesign this admissions process, based on an applicant-proposing version of the Gale-Shapley algorithm. The new algorithm proved to be successful, with a 90 percent reduction in the number of students assigned to schools for which they had expressed no preference.

Today, a growing number of U.S. metropolitan areas use some variant of the Gale-Shapley algorithm.

 

• ●● smf’s 2¢:
• ● In LAUSD’s Magnet and NCLB Public School Choice Program  {“Choices”, now “e-Choices”] (not to be confused with LAUSD’s Public School Choice Program, where the Board and the supe choose who runs neighborhood schools):
  • Applicants are allowed a first and second choice.
  • Acceptance is by lottery ( “Game Theory” as theorized by Bugsy Siegel).
  • If not accepted at the first choice applicants are put on a wait list for their second choice.
  • In a consolation prize: Applicants not accepted this year get priority points for the next year’s selection (“carrot’). If an applicant refuses a position they lose their accrued preference points (“stick.”). Accumulating points and cashing them it is part of the “Magnet Game.”
• In California’s (and most) Charter Schools, if there are more applicants than positions a lottery selects those who are admitted. When politicians say “School Choice” they usually refer to charter schools. Or vouchers.