Thursday, September 27, 2012

Election Arithmetic

Pretend for a minute that you're a general of a vast army, and that you are in charge of defending your city from the ruthless Colonel Blotto. You know that you both have 1,000 troops, and there are ten battlefields between your two armies.

Assuming that whoever sends the most troops to a battlefield wins that battle, and whoever wins the most battles wins the war, what is the optimal distribution of troops in order to maximize your chances of winning? Think about it for a minute.

Certainly there are some very poor possible choices - for instance, allocating all 1,000 troops on one battlefield means that the best you can do is tie if your opponent does the exact same, and you lose under any other configuration. But is there a best strategy?

As you may have guessed, this is a classic and well-established game theory game (they're called games but are often not fun) known as the Blotto game. However, unlike many games there is no perfect strategy to this one. No matter what you do, your opponent can beat you if only they know your strategy. For instance, a strategy of evenly splitting 166 troops onto the first six battles and 0 on the remaining four gives you a very high chance of winning six of the fields, but is very easily countered by your opponent with troops to spare if they knew your plan.

This has led to a classification of a large series of games as "Blotto" games - there is an optimal strategy, but it is only identifiable after the fact (once you know your opponent's strategy). Another example of this type of game is rock-paper-scissors - your best bet is to pick randomly from any number of good strategies, but after the game is over both sides can identify the one strategy that could have beaten their opponent.

A wonderful paper published fairly recently hypothesized that the American elections may be able to be modeled as a Blotto game, but with a couple other parameters tossed in as well. A Blotto game is fairly similar to the electoral college system, they thought, because each side has a fixed amount of money to distribute across a 51 electoral colleges, with the winner being whoever can get at least 270 electoral college votes.

First, though, they had to consider how much strategic variables, which they chose to be polling numbers ten weeks before the election and campaign spending ratios, impacted the vote (if at all). They came up with three game possibilities: either the election could be modeled as a Lotto, Blotto, or Frontrunner game (which is, coincidentally, the name of the paper). In a Lotto game, knowing your opponent's strategy couldn't help you - much like in a lottery, you can't identify any strategy that could lead to victory beforehand, even though afterwards you could see where you went wrong. In a Frontrunner game, there is an identifiable connection between strategic variables and victory, but one side has such an insurmountable advantage that they cannot lose.

The paper analyzed the 1996 and 2000 American presidential elections, and determined that campaign spending per state did have a strong impact on winning or losing that state. They further determined that the 1996 election was a Frontrunner game - Clinton has so much money and such favorable polls that it was easy for him to pick a winning strategy, and that even if Dole had known that strategy he still couldn't have won.
The results from the 2008 election. In general you'd expect states up and to the right to be won by Democrats (due either to higher spending or higher poll numbers). This is indeed the case.

Much more interestingly, though, the 2000 election was in fact determined to be a Blotto game - in other words, Al Gore could have re-allocated his money in such a way that Bush would have lost the election. The authors of the paper estimated that he only had about a 4% chance of choosing the strategy at random, but it was still a possibility.

Fast-forward to 2012, and these results have an interesting impact on the upcoming presidential election. A glance at the current polling numbers shows that this election is nearly as tight as the 2000 election, suggesting that a Blotto-like model may turn out to be valid. Considering that Obama is currently leading the expected vote count as well as fundraising, though, it seems more likely than ever that Romney has a steep uphill climb ahead of him.

No comments: