Let us consider the following game: there are some players and a computer. Each player inputs one positive integer and his name (player doesn't know another's numbers, just his own). When all the players made their moves, computer outputs a name of winner – who submitted the lowest unique number.
How do you think, what is the best strategy for this game?
Asked By : vortexxx192
Answered By : Peter Shor
There are a number of discussions of this game online, but you should be wary because some of them give incorrect solutions. This website gives an excellent exposition of how to solve this game. (Based in part on this paper.) You assume that all players use the same mixed strategy, and that when all players use this strategy, there is a Nash equilibrium. This gives equations which for three players have a closed form solution: you choose the integer $i$ with probability
$$ 0.839286 \cdot (0.543689)^{\textstyle i}$$
where 0.543689 is the solution of $x^3 + x^2 + x = 1$.
For $k$ players, if $k \geq 4$, the equations can still be derived, but they appear to have no closed form solution. However, in the optimal strategy the probability of playing a number larger than $k$ is very small, so an explicit nearly-optimal strategy can be found by solving the equations numerically.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/13061
0 comments:
Post a Comment
Let us know your responses and feedback