The SHSAT: A Matching Game
Like lots of New York City kids, I distinctly remember the rainy October morning I boarded the downtown A train towards Chambers street to take the Specialized High School Admissions Test (SHSAT). The SHSAT is a multiple choice high school entrance exam taken by eighth grade students. Before the exam, students rank the eight specialized high schools in order of their preference, but students are not required to rank all eight schools. The multiple exams are graded on an 800 point scale and admission to a specialized high school is based solely on a student’s SHSAT score. With 30,000 eighth graders sitting for the SHSAT each year and just over 8,000 seats available, the bipartite graph for this situation is a constricted set with students representing nodes S and the number of available spots N(S).
In the simplified version of a bipartite graph below, there are 7 nodes in set S representing 7 students with different SHSAT scores. Set N(S) has three specialized high schools, each having 2 available spots for the students. Student rankings of each school are provided on the right. Students A, B, and C score the highest and they get their first choice schools. Student D ranks Bronx Science first, but there are no more seats in that school so they get their second choice, Stuyvesant. Student E gets their first choice, but Student D ranks Stuyvesant first but because all seats in that school are full they get their next choice, Brooklyn Tech. Unfortunately, there are no more seats available for node G, and like a majority of test takers, they will not get an offer to a specialized high school. Although this graph is an oversimplification and each seat in each school should be a separate node, it demonstrates the process by which matching occurs and students are admitted in the Specialized High School admissions. Ultimately, using the matching theory discussed in Networks has explained the once mysterious process by which I was admitted to my specialized high school. Go Bronx Science!
References:
https://orcaarisk.com/articles/2016/10/12/the-shsat-matching-algorithm
http://economics.mit.edu/files/3024