There are two players each has $n$ balls. At the same time they distribute their balls among $m$ boxes. For each box 1 point is given to the player with more balls and zero points to other one (When a tie occurs they toss a coin to give 1 point to a player and zero to other) At the end winner is the one with more points (again toss a coin at the case of tie). For which pairs of $(m,n)$ this game might have a pure strategy Nash equilibrium? If not what is the easiest proof?
1
-
$\begingroup$ Sounds like a Blotto game. $\endgroup$– Milo BrandtCommented Nov 19, 2014 at 0:21
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
If $m \gg n$, (i.e. $m$ is much larger than $n$), then it seems clear that the optimal strategy is to randomly choose $n$ bins and place one ball in each bin. The reason why this should be optimal is that if someone decides to place more than one ball in a bin, then they probably would have gotten one point for that bin anyway if they just put one ball in that bin because the other player put 0 balls in that bin, but also they could have gotten one extra point for each other ball in bin except the first ball in the bin if they put the rest of the balls from the bin into other randomly selected bins. This is a pure Nash equilibrium where each player chooses $n$ random bins and puts one ball in each bin. If $m$ is close to $n$ or worse if $n \geq m$ then I'm not sure.
