Saturday, April 27, 2013

Blotto Games

I'm currently taking the Model Thinking class on Coursera, which is about applying mathematical models to real-world scenarios in order to derive interesting properties about how people or organizations make choices and why certain things happen. One model that was recently discussed in the class is Blotto games, which has applications in understanding presidential elections, terrorism, trials, hiring, etc. It has a nice mathematical formulation, which is why I decided to learn a bit more about it. The specific Blotto game I want to briefly discuss is as follows: there are two players in the game and they must allocate resources across three different "fronts." They each have an equal number of resources (assumed to be one without loss of generality), and whoever has more resources allocated to a front wins that front. The winner of the game is the one who wins two of the three fronts.

We can think of each player's allocation as a point in Euclidean space lying on the triangle given by $x + y + z = 1$ and $x, y, z \ge 0$. It has vertices at $(1, 0, 0)$, $(0, 1, 0)$, and $(0, 0, 1)$. If we visualize the plane of the triangle we get something like this:

Here, suppose the red dot is some allocation (or strategy). Then we can divide the rest of the triangle into two regions: the green region is the set of strategies which beat the red strategy and the blue region is the set of strategies which the red strategy beats. This follows from the fact that the strategies in the green region are closer to two of the triangle's vertices than the red strategy, and the opposite holds true for the blue strategies. From this picture we can immediately see that the regions close to the vertices are very bad, which is intuitively obvious because you are almost certainly going to lose the two fronts you have not allocated much to. It is also the case that any strategy has a "counter" strategy, so if the two players alternately picked pure strategies there would be no equilibrium.

It turns out, however, that there are mixed strategies for which you are guaranteed to win with probability at least $1/2$ regardless of what the other player chooses, so that allows for an equilibrium. To visualize one such strategy, consider the following picture:
The strategy involves only choosing points inside this hexagon, which has vertices at $(0, 1/3, 2/3)$ and permutations of that. It is not uniform, however, as the strategies near the edge of the hexagon are better than those inside. The exact distribution is constant along the edge of the hexagon, zero at the center, and increasing linearly from the center to the edge. This strategy, along with a number of others, can be proved "optimal" in the sense that your probability of winning is always at least $1/2$. So while none of these strategies is individually optimal, randomizing the choice makes it so that the other player cannot effectively counter your strategy. Since the game is symmetric, the existence of such a strategy solves the game; both players will opt to play one of these mixed strategies, and they will each of a $1/2$ chance of winning.

Mathematical games are often pretty interesting to think about, and even this simple Blotto game has unexpected properties and equilibria. Mixed strategies, in particular, are not very intuitive, yet quite valuable in understanding these games and sometimes even in understanding how the world works.

No comments:

Post a Comment