Matt Fay

Last Friday, FiveThirtyEight's Friday puzzle column, The Riddler, posted another exciting game theory competition. I'll let the author, Oliver Roeder, explain:

If this sounds familiar to my two previous posts on The Riddler's two previous Colonel Blotto tournaments, then you're onto something. The key lies in the "beat the house" requirement to entry. There are 13! or 6,227,020,800 permutations of the thirteen cards (what I'll refer to as a deck), only ~15% of which beat the house. Without the entrance requirement, the Nash equilibrium of this game is simply a random choice of those six billion options, i.e. no deck is better than any other. To visualize this, I've simulated a tournament of 40,000 random entrants, and calculated their win margin percentage against the field. This is defined a deck's winning percentage minus its losing percentage. Here, I've plotted the win margins as a function of their percentile:

As you can see, the spread of win margins is quite minimal, and can entirely be explained by chance. For example, the best deck in the field only won 1.7% more games than it lost, with a record of 16717 wins, 7247 ties, and 16036 losses. Another way to visualize this is by comparing the win margin of a random sample of decks against two different random fields. In the figure below, I've plotted the win margin of 1,000 random decks against two different random fields of 10,000 decks:

The R squared, or coefficient of determination, is practically zero, showing no relation between the scores. Thus, even the most successful decks against field one were completely average against the second one, i.e. the scores are due to random chance. However, when requiring that decks beat the house, these figures change noticeably. First, the percentiles of win margin percentage for a field of 40,000 random decks that beat the house:

The spread of win margins is much larger, with some entries dominating the field, and others being, well, utterly dominated. Next, we'll repeat the correlation plot, comparing the win margin of a random sample of decks that beat the house against two different similarly qualified random fields. Again. this is 1,000 decks scored against two fields of 10,000:

In my two previous posts on the Colonel Blotto tournament, I used a simple multi-start hill climbing algorithm to search the space for optimal troop distributions. Since the troop distributions were discretized, i.e. the number of troops defending each castle was a round number, each distribution had 90 nearest neighbors, found by taking a troop from one castle and moving him/her to another. The hill climber, given an initial start, would try out one nearest neighbor at a time (in random order) until it found a better one, at which point it would step to that distribution and start its search of nearest neighbors all over. At some point, after stepping one troop movement at a time, it would find a local maximum, at which each nearest neighbor was inferior. To combat the existence of many local but not global maxima, I would start the algorithm multiple times, i.e. multi-start, giving me a higher likelihood of searching the entire space.

It turns out a very similar framing can work wonders for this tournament. We can step through all possible decks by swapping one card with another, our new definition of nearest neighbor. In this case, a deck has 78 nearest neighbors to choose from. The only catch is that some of these nearest neighbor decks no longer beat the house, so before stepping to a new deck, we have to check its validity first.

Running this optimization algorithm with 1,000 random starts over a random field of 10,000, I found that the deck [5, 8, 7, 3, 4, K, Q, 2, A, J, 9, 10, 6] has a win margin of 52%. The distribution of win margins for locally optimal decks looks like the following:

Optimizing over the random field is interesting, but ultimately not the way to win this tournament. This is because the field against which our deck will be matched up will not be random. Instead, each competitor will, to varying degrees of obsessiveness, also be strategically planning their own deck. The question is, to what degree?

As I discussed in my second Colonel Blotto post, this tournament can be thought of as a Keynesian beauty contest:

In this analogy, first degree thinkers randomly choose the first deck they find that beats the house. Second degree thinkers optimize around beating the first degree thinkers, i.e. the deck we previously found. Third degree thinkers optimize around beating the second degree thinkers, and so on. An infinitely rational thinker corresponds with the Nash equilibrium.

I previously used publicly available data from a "Guess ⅔ of the Average" game to estimate the "level of rationality" of the public, but in the case of this game, I don't think that data applies very well. Its clear that the complexity of a game partially determines to what depth the players analyze it. While "Guess ⅔ of the Average" is simple, and only takes a multiplication of ⅔ to dive one level deeper, some games, like this one, require a deep analysis to do so. As well, the audience of the Riddler is decidedly more analytical than your average Jack & Jill. For these reasons, I arbitrarily chose a distribution of 57% first level, 29% second level, and 14% third level thinkers (each level has half of the previous one).

One final note: one important consideration to my analysis of the Colonel Blotto tournament was factoring in the "trolls," i.e. players intentionally playing sub-optimal strategies. Notably, someone found and submitted a troop distribution guaranteed to lose every time. Impressive! By my calculation, trolls made up about a quarter of the entrants.

However, even after channeling my inner troll, I was unable to come up with a strategy meant to throw people off and/or lose for this game. For that reason, I didn't take them into account.

The results of the tournament should post in this week's Riddler on Friday, so look out for an update soon thereafter!

UPDATE: FiveThirtyEight didn't end up publishing the data from this competition in the next week's post, and since I didn't place in the top 5, I'll never know how I did. Ah well! That said, it looks like they incorrectly reported the percentage of decks that beat the house, so that's a bummer.