The SHSAT matching algorithm isn’t that hard
My 13-year-old took the SHSAT in November, but we haven’t heard the results yet. In fact we’re expecting to wait two more months before we do.
What gives? Is it really that complicated to match kids to test schools?
A bit of background. In New York City, kids write down a list of their preferred public high schools that are not “SHSAT” schools. Separately, if they decide to take the SHSAT, they rank their preferences for those, which fall into a separate category and which include Stuyvesant and Bronx Science. They are promised that they will get into the first school on the list that their SHSAT score allows them to.
I often hear people say that the algorithm to figure out what SHSAT school a given kid gets into is super complicated and that’s why it takes 4 months to find out the results. But yesterday at lunch, my husband and I proved that theory incorrect by coming up with a really dumb way of doing it.
- First, score all the tests. This is the time-consuming part of the process, but I assume it’s automatically done by a machine somewhere in a huge DOE building in Brooklyn that I’ve heard about.
- Next, rank the kids according to score, highest first. Think of it as kids waiting in line at a supermarket check-out line, but in this scenario they just get their school assignment.
- Next, repeat the following step until all the schools are filled: take the first kid in line and give them their highest pick. Before moving on to the next kid, check to see if you just gave away the last possible slot to that particular school. If so, label that school with the score of that kid (it will be the cutoff score) and make everyone still in line erase that school from their list because it’s full and no longer available.
- By construction, every kid gets the top school that their score warranted, so you’re done.
A few notes and one caveat to this:
- Any kid with no schools in their list, either because they didn’t score high enough for the cutoffs or because the schools all filled up before they got to the head of the line, won’t get into an SHSAT school.
- The above algorithm would take very little time to actually run. As in, 5 minutes of computer time once the tests are scored.
- One caveat: I’m pretty sure they need to make sure that two kids with the same exact score and the same preference would both either get in or get out (because think of the lawsuit if not). So the actual way you’d implement the algorithm is when you ask for the next kid in line, you’d also ask for any other kid with the same score and the same top choice to step forward. Then you’d decide whether there’s room for the whole group or not.
So, why the long wait? I’m pretty sure it’s because the other public schools, the ones where there’s no SHSAT exam to get in (but there are myriad other requirements and processes involved, see e.g. page 4 of this document) don’t want people to be notified of their SHSAT placement 4 months before they get their say. It would foster too much unfair competition between the systems.
Finally, I’m guessing the algorithm for matching non-SHSAT schools is actually pretty complicated, which is I think why people keep talking about a “super complex algorithm.” It’s just not associated to the SHSAT.
mathbabe 
Wow, this post brought back memories! Way back in 98 I went to Bronx Science and I remember that wait time for the results very well. I wish your son the best of luck, getting into a SHS changed everything for me.
LikeLiked by 1 person
I hope your child gets into the school of their choice.
I think you left out the most obvious answers.
1. DOE aims to be as opaque as possible, thus conveying complexity where none exists.
2. It’s the DOE and everything they do is S-L-O-W.
My question to you, Cathy, is whether the algorithm is FAIR. It seems to be biased against lesser qualified students of color and, currently, rewards an unusually large number of Asian-Americans. Should SHSAT schools admit based on merit as defined by scores, or should they use a “holistic” approach?
LikeLike
It’s not at all fair. Especially if you consider the test prep. Unbelievable and unethical.
LikeLike
Yes, but the Chinese-American students typically come from low socio-economic status homes, but their working parents sacrifice a great deal on prep courses so that their children will be better off then them.
And, FTR, my older daughter got into Stuyvesant without any prep, but declined the offer.
Even though you consider it unfair, I hope your child gets in to the school of their choice.
LikeLike
It’s obviously a nuanced kind of unfairness. And it’s not obviously more unfair than other systems!
Thanks.
On Fri, Jan 15, 2016 at 9:54 AM, mathbabe wrote:
>
LikeLike
When I was there, white and Asian students made up about 80% of the population. I’m not sure what the numbers are today.
I was accepted into a program called MSI that helped kids from low socio-economic backgrounds get test prep and additional lessons to “catch us up”. I only hope that there are more programs like that out there to help kids realize just how much they can accomplish. Once I got there, it was my first time interacting with kids from a different background and I really flourished.
LikeLike
I used to be against all the test prep but now I’m not so sure. To add to the fact that many workingg class and middle class families do test prep is the overall end result.
The top scoring kids would have made it in test prep or not so it’s more that if you take the bottom let’s say quarter of the accepted class and the an equal number of kids below the cutoff — they’re all probably of similar ability and the test prep probably jumbled that bunch a bit but then, the test prep kids are being rewarded for hard work and industriousness to separate them from the kids just below the cutoff that didn’t do the prep.
LikeLike
A couple days ago I was prompted to ponder the question “So, why the long wait?” in the waiting room of an abysmally low-rated MD’s office. The aha! moment came when I observed a drug peddler bypass the waiting room and walk straight back: “Of course! Silly me…this isn’t a doctor’s office, it’s a drug dealership!”
LikeLike
The only reason I was there in the first place was to get some forms signed on short notice, a service this particular MD specializes in providing.
LikeLike
This is known as the “stable marriage problem” and you have, I’m pretty sure, reinvented the Gale-Shapley algorithm (1962). https://en.wikipedia.org/wiki/Stable_marriage_problem
LikeLike
Actually, this is a simpler version of the problem, because in the general problem, each of the schools would have their own order of preference. Here you’re assuming that all the schools have the same preference; namely the score.
LikeLiked by 1 person
You may be interested in how Brazilian students get matched to (public) higher education institutions, based on their national admission exam score. It’s an interactive (online) system where student state their two preferred schools (courses, actually). The system than calculates cut-off scores for every course (the lowest score you need to get in) and the next day students can change their preferences. Repeat this for three days.
LikeLike
This is almost exactly how university admissions work in Ireland. The only difference is that ties are broken by random selection (which is ok, because we are a less litigious people). As you say, this is completely trivial and takes essentially zero time, at least for a list of approximately 60,000 kids.
LikeLike
Even the full algorithm, which involves both specialized and nonspecialized high schools isn’t that bad. The paper describing it is here: http://economics.mit.edu/files/3024
But, if I recall, the kicker is the following (page 366, second column): “NYCDOE wanted students who are offered specialized-school positions also to be given an offer from a nonspecialized school.” So you are explicitly waiting on the non-specialized schools.
LikeLike
Funny, your algorithm is exactly the one the guidance counselor just explained to me was used in Paris, where sadly, the government has now reorganized the whole high school system by excellence, meaning a few schools contain ALL of the top kids and all the other schools contain only mediocre students and none of the best ones. So much for social mixing, not even to mention the long-lost notion of catchment areas. Then they wonder about Islamic fundamentalism blooming in those miserable schools where all the kids who live nearby and actually care about studying have been sent somewhere else.
One difference is that instead of scores on one test, the city’s computer system uses a formula that inputs all of a kids grades over the last three trimesters as well as a correction factor associated to each junior high school, and makes a total score out of that. This may be a little bit faster since they just have to use the kids’ grades rather than score any tests. According to the guidance counselor this part of the program takes a few days.
The next part, sorting kids into schools, also seems to take months. I think this must have something to do with the amount of paperwork necessary and the amount of people involved in the central office and all the different schools, setting up a file on each child and goodness knows what. It seems crazy but hey. The results only come out at the end of June when people are all leaving on vacation and too distracted by other things to go complain, protest etc. so that’s probably why they do it.
LikeLike
I think it’s *all* about the time left to complain. That’s why we get our classroom assignments the day before school starts!
Cathy
On Fri, Jan 15, 2016 at 12:22 PM, mathbabe wrote:
>
LikeLiked by 1 person
The part of this I’ve never understood is that mid last century, the most desired school was Bronx Science (Feynman, Weinberg, etc.) but around 1970 it switched to Stuy. Why?
In large part, I’d figure the more desirable school is the one with the better students. But then the order would perpetuate, rather than switching as it did.
Btw when I went to Stuy in the ’80s, it was 1/3 Asian; I’ve read that it is now 2/3.
LikeLike
“The Bronx, particularly the South Bronx, saw a sharp decline in population, livable housing, and the quality of life in the late 1960s and the 1970s, culminating in a wave of arson.”
Furthermore, many would say that there has been a marked decline in the quality of the leadership of that school, especially in the current century, including a much publicized bullying scandal.
LikeLike
It is the NON-specialized high school algorithm that has long been though to be hard. The way you describe the SHS placement is just how it works, and those placements used to get to families pretty quickly, ahead of kid’s notifications of their placements in regular high schools. It is the joint notification that delays the SHSAT placements no the algorithm.
LikeLike
On the caveat, the proposed implementation actually isn’t entirely fair – if two kids with the same score have as a top choice a school which has only one spot left, then it would be a kid with a lower score the one who gets the spot.
LikeLike
The algorithm used by the non-SSHAT schools in NY helped its designer, Al Roth, win the Nobel Prize in economics.
LikeLike
So what are your kid’s preferences, and why? I don’t know your kids, but I’m guessing they will be okay whereever they go. Parents matter more than schools.
LikeLike
Probably revealing my ageism and cynicism, but I’m guessing it actually isn’t done by a computer program, but by a 50 year old accountant in a 10 year old version of Microsoft Excel.
LikeLike