To middle-school students and their parents, the high-school admissions process is a grueling and universally loathed rite of passage. But as awful as it can be, it used to be much worse. In the late 1990s, for instance, tens of thousands of children were shunted off to schools that had nothing going for them, it seemed, beyond empty desks. The process was so byzantine it appeared nothing short of a Nobel Prize-worthy algorithm could fix it.
Which is essentially what happened.
About a decade ago, three economists — Atila Abdulkadiroglu (Duke), Parag Pathak (M.I.T.) and Alvin E. Roth (Stanford), all experts in game theory and market design — were invited to attack the sorting problem together. Their solution was a model of mathematical efficiency and elegance, and it helped earn Professor Roth a Nobel Memorial Prize in Economic Science in 2012.
Before the redesign, the application process was a mess. Or, as an economist might say, it was an example of a congested market. Each student submitted a wish list of five schools. Some of them would be matched with one of their choices, and thousands — usually the higher-performing ones — would be matched with more than one school, giving them the luxury of choosing. Nearly half of the city’s eighth graders — many of them lower-performing students from poor families — got no match at all. That some received surplus offers while others got none illustrated the market’s fundamental inefficiency.
Thousands of unlucky teenagers wound up waiting through the summer to get placed, only to be sent to schools they had not listed at all. And those schools, Professor Pathak discovered in a recent analysis, were “worse in all dimensions” — including student achievement, graduation rate and college admissions — than the schools the students had asked to attend.
Even more bizarre, the system encouraged safe, rather than ambitious, choices. Some sought-after schools accepted only the applicants who had made them their first choice. So students who aimed high and listed several such schools but were rejected by the first could blow their chances all the way down the list.
To address this flaw, the Education Department’s high school directory advised students to “determine what your competition is for a seat in this program"— a vexing task for even the best-informed among them.
“It was an allocation problem,” explained Neil Dorosin, the director of high-school admissions at the time of the redesign. The city had a scarce resource — in this case, good schools — and had to work out an equitable way to distribute it. “But unlike a scarce resource like Rolling Stones tickets, where whoever’s willing to pay the most gets the tickets, here we can’t use price,” Mr. Dorosin said.
Professors Roth, Abdulkadiroglu and Pathak modeled their solution to this conundrum on a famous puzzle in economics: the stable marriage problem. In the early 1960s, the economists David Gale and Lloyd Shapley proved that it was theoretically possible to pair an unlimited number of men and women in stable marriages according to their preferences.
In game theory, “stable” means that every player’s preferences are optimized; in this case, no man and no woman matched with another partner would both prefer to be with each other. Professors Gale and Shapley called the mechanism for arranging these fortuitous matches a “deferred acceptance algorithm.”
Here is how it works: Each suitor proposes to his first-choice mate; each woman has her own list of favorites. (The economists worked from the now-quaint premise that men only married women, and did the proposing.) She rejects all proposals except her favorite — but does not give him a firm answer. Each suitor rejected by his most beloved then proposes to his second choice, and each woman being wooed in this round again rejects all but her favorite.
The courting continues until everyone is betrothed. But because each woman has waited to give her final answer (the “deferred acceptance”), she has the opportunity to accept a proposal later from a suitor whom she prefers to someone she had tentatively considered earlier. The later match is preferable for her, and therefore more stable.
The deferred acceptance algorithm, Professor Pathak said, is “one of the great ideas in economics.” It quickly became the basis for a standard lesson in graduate-level economics courses.
Of course, there seldom is much need for mass betrothals. It was Professor Roth who developed the first practical application for this idea. In 1995 he configured a deferred acceptance algorithm to connect graduating medical students with hospital residencies. Professor Shapley shared the Nobel for economics with Professor Roth for his pioneering work on the subject. When officials at the city’s Education Department learned about the residency formula, they realized that something similar might tame the chaotic school-choice system in New York.
Playing matchmaker to doctors or students is a little more complex than pairing off couples to be married, since hospitals and schools are, in effect, polygamous — they accept many proposals. But the principle is the same: Students list their favorite schools, in order of preference (they can now list up to 12). The algorithm allows students to “propose” to their favorite school, which accepts or rejects the proposal. In the case of rejection, the algorithm looks to make a match with a student’s second-choice school, and so on. Like the brides and grooms of Professors Gale and Shapley, students and schools connect only tentatively until the very end of the process.
In 2004, the first year that students were sorted in this way, the number who went unmatched plummeted, from 31,000 in 2003 to about 3,000 — still a lot of disappointed teenagers. That year, and every year since, the algorithm has assigned roughly half of all students to their first–choice schools; another third or so have been assigned to their second or third choices. (The city’s nine specialized high schools have their own separate admissions process.)
While those represent pretty good odds, parent chat groups roil with dark speculation about some mercurial trick through which a child may be deprived of her dream school. Parents worry that their children could “waste” the crucial first-place spot if they choose wrong. And they fret that a popular school will fill up with children who ranked it first, before the algorithm has a chance to consider their own, equally qualified, child.
Professor Abdulkadiroglu said he had fielded calls from anguished parents seeking advice on how their children could snare the best match. His advice: “Rank them in true preference order.”
The allocation problem has not disappeared. Good schools remain a scarce resource, especially in poor neighborhoods, and low-income and low-performing children are still more likely to end up in underfunded schools. Sean Corcoran, associate professor of educational economics at New York University’s Steinhardt School of Culture, Education and Human Development, has studied the choices made by low-achieving students, who are disproportionately poor. He found that the algorithm matches low- and high-achieving applicants with their first-choice schools at roughly the same rate. But Professor Corcoran said, “Lower-achieving kids are applying to lower-achieving schools and ranking them as their top choices.”
It seems that most students prefer to go to school close to home, and if nearby schools are underperforming, students will choose them nevertheless. Researching other options is labor intensive, and poor and immigrant children in particular may not get the help they need to do it.
But that is a political problem, and so far, there is no algorithm that can fix it.
No comments:
Post a Comment