It's important to remember that although David Gale and Lloyd Shapley solved the stable marriage problem with a constructive, efficient algorithm, there are usually a huge multiplicity of stable solutions, some of which seem intuitively "unfair". The matching algorithm can be "stacked" to favor attractive or unattractive partners in either role. It's a good step forward to use any such algorithm, but people should be aware that there are multiple algorithms, and all stakeholders should participate in an open selection of the procedure that is to be used. On Sun, Dec 7, 2014 at 5:16 PM, Charles Greathouse < charles.greathouse@case.edu> wrote:
In the tactical limit this becomes (as Brent suggests) analogous to approval voting, which conveys less information than rank ordering. Stable matching still performs well under adversarial conditions. It's not open and closed, but that suggests that it's at least not obviously better.
Charles Greathouse Analyst/Programmer Case Western Reserve University
On Sun, Dec 7, 2014 at 3:17 PM, Warren D Smith <warren.wds@gmail.com> 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. 2. ratings easier to produce than rank orderings. 3. generically unique optimum solution found, unlike with stable marriages where there are generically many solutions and which is optimum is not known (and often not even defined).
So why didn't New York City do it in this better way? 1. Since it really isn't better for some reason? 2. the article lauds on and on about how this system was invented by Nobel prize economists. Well, that was the problem. Stable marriage theory was done in substantial part by economists. Matching theory was done by mathematicians & computer scientists. If we then add as an axiom that Nobel Prize Economists are incapable of knowing anything about anything a non-economist did, we explain this.
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun