Originally posted by Palynka
My initial thought was that this probably would requires a mixed strategy. Maybe with players randomizing their choices of 1s and 2s. Intuitively, let's start with a choice of 2 with probability 1/3.
If all do so, then you have a prob. of:
1/3*2/3*2/3 = 4/27 of winning 3 - A (2,1,1)
1/3*1/3*1/3 = 1/27 of winning 1 - B (2,2,2)
2/3*1/ em with this "high tie" probability. Or maybe I'm just missing an obvious solution here.
Ha! Very nice work. I just did the calculation that you did so I could confirm the answer given on the website, but I got the surprising (to me, at least) result that given a choice between 1 and 2, it doesn't matter what your probability distribution is! This is contrary to the answer on the website, which I now expect is wrong (and I think I know why). However, this doesn't make life easier. It made me want to cry a little, actually. :'(
After some more calculations and a heckuva lot more scribbling, I came up with the following hypothesis:
First off, there is only one way to tie this game, and that is to have all three players pick the same number. There are also two ways to win - you can either: (1) pick a relatively high number, but get lucky when the other two players tie with a lower number and eliminate each other (call this a high-win); or (2) pick the lowest number (call this a low-win).
Let's say you're player A and you pick a number "x" with probability Px, and sort out your chances of tying and winning. (The optimal strategy should be adopted by each player so PAx = PBx = PCx = Px).
There is only one way to tie (all three players pick x), so the probability of a tie is Px^3
There are x-1 numbers lower than x which the other two players can tie on and eliminate themselves with, so the probability of a high-win is Px*(P1^2 + P2^2 + ... P(x-1)^2) = Px*SUM[i|1..(x-1)](Pi^2) using summation notation.
For the time being, let's constrain our analysis to numbers between 1 and n. There are n-x numbers bigger than x which each of the other players can choose from, so the probability of a low-win is Px*(P(x+1)*P(x+1) + P(x+1)*P(x+2) + ... + P(x+2)*P(x+1) + P(x+2)^2 + P(x+2)*P(x+3) + ... P(n)^2) = Px*SUM[j|(x+1)..n]SUM[k|(x+1)..n]Pj*Pk. Sorry if that looks a little ugly, it's supposed to be a double summation from (x+1) to n. Of course, the real probability over the natural numbers is the limit as n approaches infinity, but I'll include that at the end.
So to recap, we have:
P(tie,x) = Px^3
P(high-win,x) = Px*SUM[i|1..(x-1)](Pi^2)
P(low-win,x) = Px*SUM[j|(x+1)..n]SUM[k|(x+1)..n]Pj*Pk
Adding in the tie and win payoff values, V(tie) and V(win), we can calculate the expected value E(x) when choosing x between 1 and n:
E(x) = V(tie) * Px^3 + V(win) * (Px*SUM[i|1..(x-1)](Pi^2) + Px*SUM[j|(x+1)..n]SUM[k|(x+1)..n]Pj*Pk)
The total expected value E(total) is the sum over all x from 1 to n, being sure to take the limit now as n approaches infinity:
E(total) = lim(n-->inf) SUM[x|1..n]E(x)
I've kept the final expression in short form, but even that looks ugly as hell. And that's not even the end!! Once we calculate this expression, we have to take the derivative with respect to the probability distribution to find all the stationary distributions, which I don't even know how to do, if it's even possible (does it have anything to do with calculus of variations?!?). The whole thing makes me want to fart.
I'm hoping that some clever individual can find some sort of shortcut. I'll post the original website link to see if that helps. If anyone needs me, I'll be recovering from a coma.
Question 198 here: http://mathproblems.info/group10.html