[math-fun] Marriages and schooling the children
"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)
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
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
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
Assume u(x) and v(x) are arbitrary infinitely differentiable functions R -> R. Suppose I want to find the 7th derivative f^(7)(x) of f(x) := (u(x)^2 + 1) / (v(x)^2 + 1) Is there a straightforward (or otherwise) way to do this in Mma??? Even better, can it give a general formula for the nth derivative in terms of n ??? (The online Mma documentation is pretty good -- much better than what you get with a ?? command while running the program -- but it doesn't make finding the answer to such questions easy.) Thanks, Dan
That reminds me ... wasn't Stephen Wolfram on math-fun for a while way back in the day? Is this a false memory? On Sun, Dec 7, 2014 at 7:23 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Assume u(x) and v(x) are arbitrary infinitely differentiable functions R -> R.
Suppose I want to find the 7th derivative f^(7)(x) of
f(x) := (u(x)^2 + 1) / (v(x)^2 + 1)
Is there a straightforward (or otherwise) way to do this in Mma???
Even better, can it give a general formula for the nth derivative in terms of n ???
(The online Mma documentation is pretty good -- much better than what you get with a ?? command while running the program -- but it doesn't make finding the answer to such questions easy.)
Thanks,
Dan _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
For the 7th derivative question, Dan, I think you want D[ (u^2+1)/(v^2+1), {x,7}, NonConstants->{u,v} ]. The documentation seems pretty good here to me; http://reference.wolfram.com/language/tutorial/Differentiation.html covers both higher-order derivatives and symbols that depend on x in its first few examples. I don't know of a way to have Mma give you an nth derivative for unspecified n, though. --Michael On Sun, Dec 7, 2014 at 7:58 PM, Allan Wechsler <acwacw@gmail.com> wrote:
That reminds me ... wasn't Stephen Wolfram on math-fun for a while way back in the day? Is this a false memory?
On Sun, Dec 7, 2014 at 7:23 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Assume u(x) and v(x) are arbitrary infinitely differentiable functions R -> R.
Suppose I want to find the 7th derivative f^(7)(x) of
f(x) := (u(x)^2 + 1) / (v(x)^2 + 1)
Is there a straightforward (or otherwise) way to do this in Mma???
Even better, can it give a general formula for the nth derivative in terms of n ???
(The online Mma documentation is pretty good -- much better than what you get with a ?? command while running the program -- but it doesn't make finding the answer to such questions easy.)
Thanks,
Dan _______________________________________________ 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
-- Forewarned is worth an octopus in the bush.
OK, I suppose Mathematica isn't going to answer my real question. Which is: Let u(x) be any infinitely differentiable function. Then if f(x) = exp(u(x)), its nth derivative f^(n)(x) (n >= 1) is a polynomial with positive integer coefficients in the derivatives u', u'', ..., u^(n), times exp(u(x)): f^(n)(x) = P_n(u', u'', ..., u^(n)) exp(u(x)) The polynomial P will be homogenous of (let's call it) "index" n if in each monomial, the factor u^(k) is assigned index k, and the indices of all factors are added. Using x_1,...,x_n as the variables in P_n, we'd have for instance P_3(x_1, x_2, x_3) = (x_1)^3 + 3 x_1 x_2 + x_3 Question: Is there a closed formula for P_n (without recursion) ? Do they have a specific name? What properties do they have? --Dan
Dan, You about Faa di Bruno's formula, right? Best regards Neil Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com On Sun, Dec 7, 2014 at 9:15 PM, Dan Asimov <dasimov@earthlink.net> wrote:
OK, I suppose Mathematica isn't going to answer my real question.
Which is: Let u(x) be any infinitely differentiable function.
Then if f(x) = exp(u(x)), its nth derivative f^(n)(x) (n >= 1) is a polynomial with positive integer coefficients in the derivatives u', u'', ..., u^(n), times exp(u(x)):
f^(n)(x) = P_n(u', u'', ..., u^(n)) exp(u(x))
The polynomial P will be homogenous of (let's call it) "index" n if in each monomial, the factor u^(k) is assigned index k, and the indices of all factors are added.
Using x_1,...,x_n as the variables in P_n, we'd have for instance
P_3(x_1, x_2, x_3) = (x_1)^3 + 3 x_1 x_2 + x_3
Question: Is there a closed formula for P_n (without recursion) ? Do they have a specific name? What properties do they have?
--Dan
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I joined around 1991, and I don't recall Stephen Wolfram being on math-fun. --Dan
On Dec 7, 2014, at 4:58 PM, Allan Wechsler <acwacw@gmail.com> wrote:
That reminds me ... wasn't Stephen Wolfram on math-fun for a while way back in the day? Is this a false memory?
participants (7)
-
Allan Wechsler -
Charles Greathouse -
Dan Asimov -
meekerdb -
Michael Kleber -
Neil Sloane -
Warren D Smith