Game Theory Part 1: What Is It?

Mathematics, Poker Concepts, Strategy

April 9, 2008

Game theory is somewhat of a hot topic right now. The application of said theory to poker has always been a topic of discussion amongst certain mathematicians and players. Then The Mathematics of Poker was published, and it temporarily put game theory front and center in the poker discussion. However, I would happily wager that 90%+ of winning players at any level could not give a correct and comprehensive explanation of what game theory is.

So for all you folks who don’t really know what game theory is, or what it has to do with poker, never fear. CardSharp is here to help.

What Kind Of Games Are We Theorizing About?

Previous we’ve discussed games that have the following basic property: you select your strategy, your opponent(s) select theirs, strategies are compared in some sense, and an outcome is determined. There are important background articles on this subject here, here, and here. Note that a wide variety of games fall in the category I’m describing. The two most important ones, for our discussion, are poker and rock-paper-scissors (now fashionably called roshambo for reasons that elude me). Note that the theory can be applied even to games where there is a random element, such as poker – the relationship between the strategies is defined based on expected results, not actual results.

MiniMax & Ideal (Optimal) Strategy

The core concept of game theory is the game theoretic definition if what constitutes an “optimal” strategy.

The optimal strategy for a game is the one which maximizes how well you will do assuming your opponent chooses the least favorable (to you) opposing strategy.

Sounds fairly simple right? Let’s see how it works in roshambo. Is rock the optimal strategy? The least favorable opposing strategy is paper, obviously, and every time you play rock and your opponent plays paper, you lose a point. You could repeat this process for the other two options, but youll find that in each case your minimum result is -1 point. Thus far game theory hasn’t been helpful at all since maximizing between those three -1 results isn’t useful.

The reason is that I’m intentionally doing it wrong. Unlike the “simple strategies” defined in the rho articles I pointed you at above, game theory allows randomized strategies. That is, you can make your overall strategy be that for each trial you randomly select one simple strategy X% of the time, another Y% etc. As long as all the percentages add up to 100%, you’ve got a legitimate composite strategy.
Let’s go back to roshambo and see what the effects of this are. Suppose you tested out the strategy 50% rock 50% scissors. Now your opponent’s best opposing strategy is 100% rock. You loose half you matches, and tie half your matches for a minimum expected result of -0.5 on any given result. Notice, this is better than the minimum expectation for any of the simple strategies, which all give you a result of -1. So maybe now this game theory thing is actually making us play better.

But there’s a problem – we now have infinite possible strategies since we can choose any weighting we want for the simple strategies that make up our composite strategy. So we’ve shown that some of these composite strategies are in some sense “better” than the simple strategies, but there are now too many of them to check them all and decide which is best by simple comparison. Thankfully, there’s mathematical help to be had. John von Neuman, the German-American mathematical giant, wrote (along with co-authors) a book called Theory of Games and Economic Behavior that provides a method of using matrix arithmetic to compute the optimal strategy once the expectation of combining every pair of strategies is well understood. The details of that method aren’t relevant to this article, but it’s useful to simply be aware that it exists. The book is heavy going because it’s written for a mathematically advanced audience, but it’s interesting in that it uses poker as one of its examples.

Back to roshambo, von Neumann’s method tells us that the optimal strategy is 1/3 rock, 1/3 paper, 1/3 scissors chosen randomly. Note what effect this has on the game: no matter what your opponent does to choose his strategy, you will win 1/3 of your games (for +1 point), lose 1/3 (for -1 point) and tie 1/3 (for 0 points). The total expectation is therefore 0 points – in this case for both you and your opponent. This is what is called a zero sum game. You can prove to yourself that this is a maximal minimum result – just move a percent or two towards doing one of the 3 plays more often, choose the best opposing strategy, and you’ll see that your expectation is less than 0.

The Head And Tail Of The Rho

From the previous discussion of rhos, we know that there are two kinds of simple strategies – strategies that are in the head of the rho, which are generally good, and strategies in the tail of the rho which are generally bad. Roshambo is a degenerate case because all three simple strategies are in the head of the rho. It turns out that when forming an optimal composite strategy, only simple strategies which are in the head of the rho are included. Those in the tail of the rho are weighted at 0% – they should never be used.

In the next installment of this series I’ll tell you how all this relates to poker.