Friday, December 2, 2011

Seattle backs away from transparent (strategy-proof) school choice

It appears that, after a decade of using a school choice system based at least in part on a deferred acceptance algorithm, in the course of making some other changes, Seattle schools may have backed into using a non-strategy-proof immediate acceptance algorithm instead.

Here's a Q&A on How to Rank Schools for the Seattle Public Schools Choice Process for 2010-2011

"My true first choice option school is very popular and hard to get in to. If I list it first on my School Choice form, am I throwing away my chances of getting in?

"For the 2010-2011 school year, you would not be throwing away your chances.

"This year the district is using what it refers to it as the Barnhart/Waldman processing algorithm, named after the school board members who suggested it. It is more properly called the Gale/Shapley “Stable Marriage” algorithm. This algorithm is well studied and understood by computer scientists and mathematicians. It has been specially designed so that there is never an advantage to listing your school choices in any order other than your true preference. The Gale-Shapley paper referenced below is highly recommended. It is well written and does not require special software or mathematics skills to understand. In addition to being used for school assignments in many districts, a variation of this algorithm is used for the yearly matching of graduating medical students to residency programs.

"Note that this will change when the NSAP is complete. The final plan calls for using a simpler algorithm in which families who list a school as their first choice have priority over families who list the school second choice or later. This can result in cases where your best chance for getting into one of your choices is to “lie” and list your second choice first."

And here's an analysis by a concerned parent, Chris MacGregor, who happens to be a software engineer and took the trouble to examine the school district's school choice algorithm source code: Serious Problem With New Student Assignment Plan

It sounds like the plan may have been passed hastily, with the change in algorithm being a detail in a more politically charged discussion: Student-assignment plan passed behind closed doors.

Here's some background on school choice in Seattle, in the form of court documents from 2001, about the use of race as a tie-breaker in school assignment.

Here's a 1998 story about the adoption of the deferred acceptance algorithm, with some discussion touching on strategy-proofness and making it safe to submit true preferences: New Student-Assignment Plan Set
"The change, devised by board members Scott Barnhart and Nancy Waldman, will extend the district's "hold harmless" rule to all choices. Currently, when students apply to alternative schools, they don't lose their place in line for a regular school.
But, when students apply to popular regular schools and don't get in, the computer bumps them down the list until it finds a school with a vacancy - even though they may have siblings in their second-choice school or may live right across the street.
Barnhart and Waldman's system will ensure that more students get their real second choice and eliminate bumping down to lower and lower choices, which has discouraged parents and driven some to send their children to private schools, according to Waldman.
At last night's meeting, Waldman said that had happened to her.
Space wasn't available at her first-choice kindergarten, so her daughter was assigned to a school Waldman hadn't even listed. So, Waldman put her daughter in private school for three years."
Note that Scott Barnhart is a medical prof at U. of Washington, who was matched to a number of residency positions, and so would have been familiar with the medical match.

And here's a 1996 story (short on detail, but gives some of the political atmosphere) about the run-up to the adoption of the deferred acceptance algorithm that is apparently on its way out: Vote On Reform Plan -- School Board To Tackle Student-Assignment System
For those of you new to discussions of making school choice simple and safe for parents to reveal their preferences over schools, see the papers here about New York and Boston, and see the Institute for Innovation in Public School Choice which has more recently been involved in the design of school choice programs in Washington D.C., Denver, and New Orleans.

HT: Parag Pathak

No comments: