NYC Board Of Ed's Algorithm Not Academic

Thousands of New York City parents are spitting mad because their kids are among the 7,000-plus who didn't get matched to a public high school.Their anger is intensified because of the mystery with which the Board of Education shrouds the process, which has actually changed for the better since 2004.

The Board of Ed uses the same kind of matching algorithm used to match medical residents with hospitals, and it's designed to be fair to the greatest number of people.

That said, the Board of Ed has refused to make some adjustments to how it implements the algorithm, and it could do a much better job of explaining how it works to the administrators who unintentionally end up giving kids and parents bad information.

Before I go any further, I should disclose the fact that my daughter just went through this process and got placed in an excellent school, so we're happy in this household.

But the process was difficult for a 12-year old to deal with (and maybe even harder for her 47-year old father), and it's been impossible to ignore the cries of anguish from parents whose worst fears came true.

In the autumn of their 8th-grade year, 12- and 13-year-old kids are asked to rank up to 12 high schools they wish to attend the following fall, and then have to endure tests, portfolio submissions, auditions and interviews for most of the most popular schools.

Beacon, for example, is one of the most popular schools, and received 4,600 applications in 2007, for a grand total of 262 seats. (This is for high school, folks.) You can imagine the angst statistics like that provoke in parents.

After the results came in, parents flooded the forums on sites like Inside Schools, many despairing over having to explain to their kid that just because none of the schools they applied to wanted them didn't mean they were losers.

What most parents don't realize is that the Board of Ed uses an algorithm written in-house, with assistance from a Harvard economist, that is intended to give as many kids as possible their first choices -- without, in the process, making life worse for the others. It's based on a principle from economics, called Pareto efficiency, where a change from one allocation of resources to another can make at least one individual better off without making any other individual worse.

From the Board of Ed's perspective, the new system has been a roaring success. Before putting this algorithm in place in 2004, more than 30,000 students didn't get matched. By the time the "consolation round" of matches takes place this year, only some 3,000 kids still won't have a match -- a ten-fold improvement.

Both before and after 2004, when the new process was first instituted, a computer matched kids and schools based on how the schools rated the kids and how the kids ranked their preferences.

Prior to 2004, the schools could see how they were ranked by the kids, and many only took kids who put them first on the list. Because the kids knew that, they tried to outguess the schools by placing their first choice second or third on the list, with the unfortunate result that a lot of kids ended up guessing their way out of any match whatsoever.

A kid could conceivably just miss the cut in her first choice, but because she placed it first in her list, would be locked out of the next school down the list, which had already filled up with kids that had put it first, bumping the kid all the way down the list like a Slinky down a set of stairs.

The new algorithm adopted by the Board of Ed in 2004 is designed to avoid this, by using a "student-proposing deferred acceptance mechanism," which is strategy-proof, according to Professor Alvin Roth of Harvard.

The way it works is sort of like this: Let's say for the sake of simplicity that each school has 10 spots. Every school that Kid A applies to looks at his record and ranks him numerically. Assume School 1 ranks Kid A 11th and School 2 ranks him seventh. Using the old method, Kid A doesn't get into School 1 because he's too low at 11th, and doesn't get into School 2 because it's already filled up with 10 kids who ranked it first on their list.

In the new system, schools accept kids, but defer their final decision until the whole selection process is finished (hence the phrase "deferred acceptance").

So what happens is Kid A is still rejected by School 1. School 2 has also filled up, but now that Kid A's name comes along because he was rejected by School 1, Kid A gets slotted into seventh place by School 2, the kid in the seventh slot of School 2 is bumped down to eight, and so on, until the kid in spot 10 is bumped to 11 and is no longer selected by School 2. His application is then presented to the school that is second on his list. And on and on and on.

The end result is that it takes guessing out of the equation for kids. "It no longer makes it a dominant strategy to not put their true preferences," Roth told me.

But the sad truth is that many school administrators not only don't understand the mechanism, they don't believe the Board of Ed when it says kids shouldn't try to game the system. I know a lot of parents who were told by their guidance counselor that, "School X won't pick anyone who doesn't put them first on the list."

Those guidance counselors need to catch up on their reading. The schools don't know where the kids rank them, and where kids rank them doesn't affect their mathematical chances of getting in. Period.

That still doesn't quite explain why more than 7,000 kids didn't get matched. One reason could be that kids only applied to top schools and didn't include any safety schools. Andy Jacob, a spokesman for the Board of Ed, told me, "it's conceivable you could be a pretty good A student, but if you only apply to Harvard, Yale and Princeton, you might not get into a school at all."

But there is one thing the Board of Ed could do to reduce the number of kids who don't get any of their choices. Roth told me he encouraged the Board of Ed to let students pick fifteen schools rather than twelve. "A substantial number of kids, around one-fifth, put down twelve choices. It's logical to assume that if they write down twelve, they might like to write down more." And that would result in more matches.

Roth wouldn't tell me why, but the Board of Ed decided to reject this advice.

The Board of Ed also counsels kids not to list twelve schools unless there are really twelve schools they'd like to attend. Not only is this a tacit admission that a very small percentage of the 500 public high schools in the city are acceptable to most kids, but it perpetuates the idea that you can somehow game the system.

The Board of Ed should understand that the algorithm isn't merely an academic exercise. It really works. It would be even better if they allowed kids to pick more schools -- and the issue would be moot if more schools were more acceptable to more parents.