On 12/7/2014 12:17 PM, Warren D Smith wrote:
"How Game Theory Helped Improve New York City's High School Application Process" http://www.nytimes.com/2014/12/07/nyregion/how-game-theory-helped-improve-ne...
This article (pretty good press math piece) explains how the problem of matching children to schools in NY city is treated as a "stable marriage problem" -- schools & children both provide preference rank-orderings of the other -- repairing a totally brain-dead previous system.
However, I suspect there is a better approach. Instead of children & schools providing rank-orderings, have them provide numerical RATINGS on a fixed allowed-score-range such as the real interval [0,100]. (Greater scores preferred.) Then find the pairing (associating of children--schools) that maximizes the sum of the used ratings, subject to valency constraints (e.g. each school can accomodate at most X children, where X depend on the school and is known). This is a max-weight "degree constrained subgraph" problem within a complete bipartite graph and is soluble in polynomial time using known algorithms (theory related to "maximum weight matching" graph problem). Also should be soluble using max-flow min-cut technique to find min-cost flows.
Advantages: 1. ratings allow strengths of preference, not pretending all preferences same strength.
Why would any applicant rate a school he wanted less than 100 or rate a school he didn't want higher than 0? Brent Meeker