Nobel voor ‘matching’
Het Nobel comité noemt het voorbeeld van de matching vanstudenten nadrukkelijk als verhelderend voorbeeld van het soortonderzoek, dat zij dit jaar wilde bekroneen. “This year’s Prizeconcerns a central economic problem: how to match different agentsas well as possible. For example, students have to be matched withschools, and donors of human organs with patients in need of atransplant.”
“How can such matching be accomplished as efficiently aspossible? What methods are beneficial to what groups? The prizerewards two scholars who have answered these questions on a journeyfrom abstract theory on stable allocations to practical design ofmarket institutions.”
Algoritme in praktijk
Het theoretische werk van Shapley is van essentieel belanggeweest voor de speltheorie. Roth zette het echter in voor heelandere vraagstukken, die toch weer niet zo heel anders bleken.”Lloyd Shapley made the early theoretical contributions,which were unexpectedly adopted two decades later when Alvin Rothinvestigated the market for U.S. doctors. His findings generatedfurther analytical developments, as well as practical design ofmarket institutions.”
“Traditional economic analysis studies markets where pricesadjust so that supply equals demand. Both theory and practice showthat markets function well in many cases.”
“But in some situations, the standard market mechanismencounters problems, and there are cases where prices cannot beused at all to allocate resources. For example, many schools anduniversities are prevented from charging tuition fees. Yet, inthese – and many other – cases, an allocation has to be made. Howdo such processes actually work, and when is the outcomeefficient?”
Hoe vind ik de beste opleiding?
Alvin Roth gebruikte het wiskundig werk van Shapley op allerleimanieren, zeer praktisch en innovatief. Het Nobel comité gebruikteen recent voorbeeld, waarin de matching van studenten en deschool/opleiding van hun voorkeur voorop stonden.
“The Gale-Shapley algorithm proved to be useful in otherapplications, such as high-school choice. Up until 2003, applicantsto New York City public high schools were asked to rank their fivemost preferred choices, after which these preference lists weresent to the schools. The schools then decided which students toadmit, reject, or place on waiting lists.”
“The process was repeated in two more rounds, and students whohad not been assigned to any school after the third round wereallocated through an administrative process. However, this did notprovide the applicants with enough opportunities to list theirpreferences, and the schools did not have enough opportunities tomake offers.”
“As a result, about 30,000 students per year ended up at schoolsthey had not listed. Moreover, the process gave rise tomisrepresentation of preferences. Since schools were more likely toadmit students who ranked them as their first choice, studentsunlikely to be admitted to their favorite school found it in theirbest interest to list a more realistic option as their firstchoice, while applicants who simply reported their true preferencessuffered unnecessarily poor outcomes.”
“In 2003, Roth and his colleagues helped redesign thisadmissions process, based on an applicant-proposing version of theGale-Shapley algorithm. The new algorithm proved to be successful,with a 90 percent reduction in the number of students assigned toschools for which they had expressed no preference. Today, agrowing number of U.S. metropolitan areas use some variant of theGale-Shapley algorithm.”
