How Game Theory Helped Improve New York City’s High School Application Process

[Mitar]

Hi!

Good read:

http://www.nytimes.com/2014/12/07/nyregion/how-game-theory-helped-improve-new-york-city-high-school-application-process.html

"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."

Mitar

--

http://mitar.tnode.com/
https://twitter.com/mitar_m

[Warren D Smith]

That's interesting -- the school-child matchup problem was treated as
a "stable marriage problem." Votes are rank-orderings. The solution
is a stable marriage, i.e. has the property that you can't improve it
be swapping two children.

If we instead adopt the view (motivated by "score voting" as opposed
to rank-order ballot systems) that votes instead ought to be numerical
RATINGS on some fixed scale,
e,g students rate each school 0-to-9, schools also rate each potential
student...
then the matchup that maximizes the sum of all the USED ratings, can
be be found by solving a "maximum weight matching problem in a
bipartite graph" (actually a max-weight degree-constrained subgraph
problem in a bipartite graph, but this is known
to be an equivalent problem; there is a well known algorithmic theory
showing how
to solve these problems in polynomial time). Would this work better?
It would allow students and schools to weight preferences heavily or
lightly, as opposed to pretending all preferences have same strength.
That's one obvious advantage.



--
Warren D. Smith
http://RangeVoting.org <-- add your endorsement (by clicking
"endorse" as 1st step)

[Warren D. Smith (CRV cofounder, http://RangeVoting.org)]

If we instead adopt the view (motivated by "score voting" as opposed
to rank-order ballot systems) that votes instead ought to be numerical
RATINGS on some fixed scale,
e,g students rate each school 0-to-9, schools also rate each potential
student...
then the matchup that maximizes the sum of all the USED ratings, can

be found by solving a "maximum weight matching problem...Would this work better?

It would allow students and schools to weight preferences heavily or
lightly, as opposed to pretending all preferences have same strength.
That's one obvious advantage.

Some other obvious advantages: 

2. finds optimal matching, whereas stable marriage algorithm

does not find optimal stable marriage (well, there are many stable marriages, 

in general, and which is the best, is not clear and not found;

for my matching problem there generically is a unique best one, which is found

by the algorithm)

 

3. ratings are easier to produce, than rank-orderings.

So I suspect the problem here is this.

The "stable marriage" algorithm was invented by economists, hence the other 

economists who produced this plan for New York's school system, were aware of it. 

The max-weighted matching algorithm and theory, were produced by 

mathematicians and computer scientists; therefore, the 

economists who produced this plan for New York's school system, were 

unaware of it.

[Clay Shentrup]

Warren,

Why don't you do a little write-up of this as a page on scorevoting.net, and then send it to some of the administrators involved and/or the author of that article.

I remember discussing what I think is the same (or similar problem) years ago, regarding how doctors are assigned to residency programs.

[Clay Shentrup]

So, this problem has recently come up again for me, now that my son is almost two, and we're starting to think about his schooling in a couple years.

I just heard a segment on the radio this morning about the messy school assignment systems used in San Francisco and Oakland, and the Bay Area more broadly. There is some sort of rank ordering involved.

Warren in particular, can you state the most efficient algorithm for maximizing score sums if Score Voting were to be used? I know of a local school board member who might be receptive to this kind of wonky idea, and I'd love to be able to demonstrate a computer program that could take those scores as input and output the assignment.

In addition to the preference rankings though, there are "extra points" for keeping siblings in the same school, and for locality/nearness/neighborhood.

http://blog.pacificunion.com/san-francisco-public-school-lottery/

I would suggest that the sibling and neighborhood issues should just be dealt with by the parents when they assign their scores. There's this notion that people who live closer to a school should take priority over someone further away who assigns that school the same score. But if someone is willing to deal with a longer commute, that could be an indication that he'd actually derive more utility from having his kid attend that school than would someone who lives close to it yet still gives it the same score. An example might be a poor/minority family who wants to send their child to a school in a more affluent area that has better teachers, resources, safety, etc.

What if we were to put together a school assignment process plan the same way we proposed a solution to the problems faced by the Webby Awards?

[Clay Shentrup]

On Monday, August 17, 2015 at 10:49:45 AM UTC-7, Clay Shentrup wrote:

Warren in particular, can you state the most efficient algorithm for maximizing score sums if Score Voting were to be used?

This seems promising.

https://en.wikipedia.org/wiki/Hungarian_algorithm 

[Andy Jennings]

I would suggest that the sibling and neighborhood issues should just be dealt with by the parents when they assign their scores. There's this notion that people who live closer to a school should take priority over someone further away who assigns that school the same score. But if someone is willing to deal with a longer commute, that could be an indication that he'd actually derive more utility from having his kid attend that school than would someone who lives close to it yet still gives it the same score. An example might be a poor/minority family who wants to send their child to a school in a more affluent area that has better teachers, resources, safety, etc.

I agree on the neighborhood issue, but I don't think the sibling issue can be done that way.  Say there are two really good schools, the same distance from my house.  I give them both max scores.  But if I'm enrolling two kids, it's much nicer for me to have them at the same school, one or the other, rather than splitting them up.  How do I indicate that with my scores?  Even if I give one school a 10 and one school a 9 and there ends up being one spot left at the good school, should the assignment algorithm put one of my kids at each school or put them both at the slightly worse school?  It depends on the family, I guess, but in my case I'd probably prefer them to both be at the second school than to have one at each.

[Clay Shentrup]

On Monday, August 17, 2015 at 11:18:25 AM UTC-7, Andrew Jennings wrote:

I agree on the neighborhood issue, but I don't think the sibling issue can be done that way.

I meant, given that you already have a kid at one school and are enrolling the second.

I'm curious how much more complex the algorithm becomes if we add some ability to score for "both children attend same school".

However, even if the system takes absolutely no consideration of siblings, I'd bet it would still be far superior to the existing system they're using, which was not designed by mathematicians or game theorists.

[Clay Shentrup]

Here's a Ruby library that might be capable of the task.

http://www.rubydoc.info/github/monora/rgl/RGL/EdmondsKarpAlgorithm

But it uses some graph and flow/sink abstraction which makes no sense to me. How do I convert a bunch of scores to a graph? What is a sink? 

[Warren D Smith]

Jennings' point about siblings being together being worth more, is a
good one -- and
both the stable marriage and optimum matching frameworks ignore that.
You likely cannot make them take it into account without destroying
the polynomiality
of the algorithm(?). But perhaps you could "merge" siblings into one
"super person" with
increased score-range then run the usual algorithm... which
unfortunately would force
merged siblings always to attend same school. Or perhaps some later re-run
of the algorithm with "bonus points" added could provide a partial fix.

Yes, the Hungarian algorithm is a well known and pretty simple to
program method for solving bipartite max-weight matching problems. I
do not, however, know whether it would be efficient enough to handle
all the children and schools in a city. How many children-applicants
and schools are we talking about? There are more asymptotically
efficient algorithms than Hungarian, and methods faster for "sparse
graphs," as well as heuristic hacks that provide speedups that are not
fully understood. It is not trivial to program all of that... but
people already have, assuming one can find them.