December 2014 - mathfun@mailman.xmission.com

[math-fun] Marriages, and schooling the children
by Warren D Smith 09 Dec '14

09 Dec '14

>> Essentially every election is a Nash equilibrium since no single voter can alter result. >This is why you use a randomized model in the first place! >If your basic model is that there are a thousand other voters who are going to roll dice between red, blue, or green (or x hundred of each, all flipping a coin to decide whether to stay home or vote, etc.), where your uncertainty about future events is built into the model, then you can have nontrivial equilibria. --uh, maybe. >For a very simple example: 300 voters want green > red > blue, 400 voters want red > green > blue, 400 voters want red > blue > green, and 1000 voters want blue > green > red; election method is FPTP. --in your very simple example here: I don't see where any randomization was. In this example, no one voter can change result, therefore, this election (like almost all elections) is a Nash equilibrium, which is an utterly useless fact. >It's not hard to see that the dominant strategy for the first group is to vote red to block the plurality-winning blues. --Nash equilibria don't have "strategies for groups." They have "strategies for individual players." >And you know as well as I do that this is very practical in voting systems around the world, e.g., in the US. You can't just throw up your hands and say it's impossible to reason about -- or I suppose you can, but that won't do any good. --there are many cases we can try to reason, tell stories, etc. I don't think they have much if anything to do with Nash equilibria, though. I don't know what you were trying to accomplish in this message. Anyhow, back in the schools+children problem, I think you can try to quantitatively assess how well methods work, and how well they work in the face of voters trying different strategic behaviors, via computer simulation. You can (and I did) also do such sims for voting systems. In many cases it gets quite tricky and/or non-quantitative if you try to work without a computer, so, I'd say doing computer sims would probably tell you quite a lot. Telling a few stories about some contrived scenarios might also be of some use, but will probably never unconfuse the situation enough to tell us how well the marriage/matching/etc solutions work, in any quantitative way. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 1

[math-fun] Marriages, and schooling the children
by Warren D Smith 09 Dec '14

09 Dec '14

>I don't think a full understanding is needed. How about a Nash equilibrium for the students, given that the schools report their preferences honestly? No collusion allowed in this model, just each student choosing on their own. Charles Greathouse Analyst/Programmer Case Western Reserve University --doubt it. See, it is kind of Yet Another Big Lie, that economists like to tell the world, that Nash Equilibria are useful. Well, maybe they are useful for something, but I can tell you that in voting theory (voting systems with N voters = N-player game) Nash equilibria are extremely extremely useless. Essentially every election is a Nash equilibrium since no single voter can alter result. Totally worthless. Anyhow, back in our children-schools problem, is a "stable marriage" a Nash equilibrium with honest scoring? I think not always. It is locally optimal in the sense of "stability" with respect to the (assumed honest) rank-order inputs, which also provides a sense in which honesty is a pretty good strategy. Meanwhile is an "optimum matching" with honest rating-vectors as inputs, a Nash equilibrium? Again I doubt that. But again, it is optimal in the sense of maximizing total used-rating sum. This unlike for stable marriages, is a global optimality notion, not merely local. Also generically unique also unlike for stable marriages. And again this suggests honesty is a pretty good strategy. If you knew everybody else's rating (or ranking) of everything, then had the power to change your own ratings (or rankings) while keeping everybody else's fixed, then you could exhaustively search the space to find the best possible strategy. But that is not the real world. And normally, by the way, Nash equilibria refer to RANDOMIZED strategies, where you provide every possible rating(or ranking) each with some probability, and then consider perturbing the giant vector of your probabilities, to achieve maximum expected reward. That scenario is in most situations like this, extremely extremely useless and unrealistic. I was speaking above of deterministic strategies.

2 1

[math-fun] area inside algebraic curve impossible to express?
by Warren D Smith 09 Dec '14

09 Dec '14

The area inside an algebraic curve of degree<=2 can be computed using well known functions. QUESTION: For general degree=3 curves, is it impossible to express area in closed form? For general-degree general curves, no closed form expression is possible in general... one cheesy proof being: consider P(x)*Q(y)>=0 where P,Q, are polynomials, and P is an unsolvable quintic, while Q(y)=y*(1-y). Then the area of the component is the difference between two successive of the quintic's roots, and we can make the quintic have exactly 3 real roots so this is only finite component. The reason I call that proof "cheesy" is that the impossibility is really a lot more serious than just the inability to solve quintics -- very highly transcendental functions woud be needed to express area in general I think, e.g. hyperelliptic integrals, etc. Anyhow, somebody more versed than I in the theory of what integrals can be done in closed form and what cannot, could possibly answer my degree-3 question above.

1 0

[math-fun] unexpected hangings redux
by Cris Moore 09 Dec '14

09 Dec '14

You, I, and Mr. Apollinax are traveling on a train. He leans over to you and says, with a leer, "whisper a natural number into my ear." You do so. He then turns to me and asks me to do the same. I do. He then claps his hands and says "Marvelous! Your numbers are distinct, and neither of you can deduce which one is larger." Get it? - Cris p.s. I heard this from Thilo Gross...

5 10

Re: [math-fun] math-fun Digest, Vol 142, Issue 29
by Warren D Smith 09 Dec '14

09 Dec '14

> You really can't say anything about strategic voting here? At all? > > Let's suppose I receive 50, 75, or 90 utils for attending school A, B, or C > respectively (or 0 for not attending any). At a minimum, I should rate A at > 0 and C at 100 to maximize incentive to be assigned to the school of my > choice. If I knew that C was extremely selective and I was unlikely to get > in, it would be strategically sound for me to assign many points to it > (rather than simply scaling up the difference) rather than honestly/naively > reporting my true preference. Exactly how many points depends on the chance > I think I'd get in, but it's not unreasonable to expect that I would want > to assign 99 or 100 points to it. > > On the other hand, suppose I would receive -10, -5, or 100 utils for > attending A, B, or C (or 0 for not attending any). Then I should rate them > at 0, 0, and 100 points, since I am truly indifferent to A and B (I > wouldn't go if accepted). > > A voting method that can't handle strategic voting is a bad method. Sure, > we know complete strategyproof-ness is impossible (Gibbard 1973, > Satterthwaite 1975) but that doesn't mean (1) that tactical voting doesn't > exist or (2) that we shouldn't plan for it. > > Charles Greathouse > Analyst/Programmer > Case Western Reserve University --well, one can give anecdotal examples such as this, but a full understanding of optimal strategy is probably impossible. Further, usually in multiplayer games the "best strategy" involves collusions between large subsets of the players, which is kind of why you can't describe optimal strategy, they collude, they cheat on the collusions with other collusions, etc etc. You can empirically try to reckon performance of these sorts of things by computer simulation, including (if you want) the players in the sim apply various strategic behaviors. That was in fact exactly what I did in 2000 with single-winner voting methods, finding "score voting" aka "range voting" was the best of the methods in my (then) simulator. I'm unaware of any sim-study of the current sort of problem (matching children to schools). Might be interesting to try to do one.

2 1

[math-fun] Atropa Belladonna redux
by Fred Lunnon 08 Dec '14

08 Dec '14

Eventually I did get my head properly around Gareth's combinatorial solution to my Atropa Belladonna (Deadly Knightshade) Q3. Whereupon several strange things happened. Against all my expectations, his argument did generalise relatively straightforwardly to counting the number of shortest knight paths to any point on an infinite chessboard. Even more bizarrely, it did not depend on knowing the shortest distance beforehand: instead that comes almost for free as a consequence, along with the knight circle circumference (number of points at given distance). With the dust finally settled, the outcome is concise, rigorous combinatorial constructions of solutions to those three problems, very nearly also settling which points have maximal paths counts for given distance. Tantalisingly, the last stage of this last, tougher nut --- establishing dominance order among 7 axial and diagonal sequences --- still seems to require wheeling in heavy equipment, in the shape of computer-assisted `real algebraic geometry'. Waiting for its to-do list to empty promises to last for ever; so the draft has finally been uploaded to https://www.dropbox.com/s/1t51ivltm6l32gq/knight_path.pdf --- comments are solicited as usual. Fred Lunnon

1 0

[math-fun] Marriages, and schooling the children
by Warren D Smith 08 Dec '14

08 Dec '14

> From: Charles Greathouse <charles.greathouse(a)case.edu> > What is the correct tactical strategy? Surely this is known... --au contraire. There is in general no such thing as an "optimum strategy" for an N-player game if N>2. So not only is it not known, it is probably not even defined. (And that's for both the marriage and ratings versions of the problem.)

2 1

[math-fun] Marriages, and schooling the children
by Warren D Smith 08 Dec '14

08 Dec '14

--1. re the idea that the rating might tactically degenerate to "approval voting" (all 100 and 0 ratings) A. we could forbid two equal ratings. B. it is likely tactically unwise to give all 100s and 0s anyway. If you do, then you are unable to distinguish among the 0s. You might get an 0, then you'll be stuck with a bad 0 rather than a less-bad 0 which you could have easily avoided. --2. I am buoyed to hear about Guy Haworth and his matching task. This seems to me to be a "proof of principle" demonstration. And apparently Univ. of Reading agreed that ratings worked better than rankings, otherwise they switched for no reason. > The task of matching final year students to Individual Final Year Projects, > with no two students doing the same project, is the same. > > At the University of Reading (SSE), we switched from: > > a) asking students to rank their most favoured five projects in order, to > b) asking them to say how much they wanted to do the project with an > integer in the range [3, 10] > > This gives the students more 'voice' in their application form - as awarding > points does express a ranking, admittedly possibly with some ties. > > > With 200 students, the LP program runs in a fraction of a second. > > In a second running of this program, when limits on the number of students > going to one supervisor were imposed, more students got their lower > choices. > > The solution, available to us but not available to the school-assignment > problem, is to nominate alternative supervisors for projects - and avoid > portmanteau projects like 'Create an App for a mobile phone'. > > > The LP theory of all this has been known for a long time. > > Guy

2 1

[math-fun] Marriages, and schooling the childrenb
by Guy Haworth 07 Dec '14

07 Dec '14

The task of matching final year students to Individual Final Year Projects, with no two students doing the same project, is the same. At the University of Reading (SSE), we switched from: a) asking students to rank their most favoured five projects in order, to b) asking them to say how much they wanted to do the project with an integer in the range [3, 10] This gives the students more 'voice' in their application form - as awarding points does express a ranking, admittedly possibly with some ties. With 200 students, the LP program runs in a fraction of a second. In a second running of this program, when limits on the number of students going to one supervisor were imposed, more students got their lower choices. The solution, available to us but not available to the school-assignment problem, is to nominate alternative supervisors for projects - and avoid portmanteau projects like 'Create an App for a mobile phone'. The LP theory of all this has been known for a long time. Guy

1 0

Re: [math-fun] The triangular squares
by Bill Gosper 07 Dec '14

07 Dec '14

On 2014-12-07 20:07, Neil Sloane wrote: > you might have referenced http://oeis.org/A001110 > and A001109! > 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(a)gmail.com > Done. --rwg > > On Sun, Dec 7, 2014 at 11:01 PM, Bill Gosper <billgosper(a)gmail.com> wrote: >> Something for the youngsters: >> gosper.org/triangsq.pdf >> But you might see a Mathematica trick, e.g. >> --rwg

1 0