Texas Hold 'Em: Nash Equilibrium Style

NASH EQUILIBRIUM

Nash Equilibrium is named after John Forbes Nash Jr., an american mathematician who had significant contributions to the fields of game theory, differential geometry and partial differential equations. In 1994, Nash along with two other prominent game theorists Reinhard Selten and John Harsanyi received the Nobel Memorial Prize in Economic Sciences. Nash was under controversy by the selection committee as a recipient due to his history with paranoid schizophrenia, as well as alleged antisemitism. 

There is no better way to begin our section on decision theory than by talking about everyone's favorite decision - should you hold 'em or should you fold 'em? Throughout this post and my presentation my goal is to show you Texas Hold 'Em style poker from a game theorist's perspective. This is what has come to be known as GTO poker, or Game Theory Optimal poker. By looking at poker using Nash equilibria, we can analyze poker mathematically, which is unique in a game that tends to be about psychology and one's ability to read people.

Let's break down a few definitions that we might find useful moving forward.

According to Investopedia: 

Game Theory - Explains how people and groups of people approach complex decisions.

Nash Equilibrium - Refers to a condition where every participant of the game has optimized their outcome, based on the other players' expected decision. 

In other words, the optimal outcome of a game is one where no player has incentive to deviate from their chosen strategy after considering an opponent's choice. 

For example, let's imagine that two companies dominate the shoe industry Nike and Adidas (forget all the others). Both companies make one million pairs of shoes annually for the price of $30 per pair, and both earn an equal profit of ten million dollars. Nike knows that there is a bigger industry for shoes though, so it decides to boost production and make two million pairs of shoes at the price of $27 dollars per pair. In this scenario Nike's profits would boost to fourteen million dollars, but obviously if Nike boosted production Adidas is going to follow suit and similarly produce two million pairs of shoes. Now there will be a surplus of two million pairs of shoes, causing Nike's profits to fall to eight million, as shoes would have to be sold at $24. It turns out the two companies were already in a state of Nash equilibrium, and ten million dollars is the maximum profit each company can make. 

"Neither business can make more money by unilaterally deciding to boost production."

Nash's Existence Theorem - This theorem proved that if mixed strategies are allowed, then every game with a finite number of players in which each player can choose from from finitely many pure strategies has at least one Nash equilibrium. 

Here is link to a formal proof and tutorial of Nash's Existence Theorem if you're intrigued: http://www.cs.ubc.ca/~jiang/papers/NashReport.pdf ...heavy stuff this guy was crazy smart (literally).

But Riley, what's a mixed strategy? I'm glad you asked, but you seek the answer to the wrong question. In order to understand what a mixed strategy is we first need know what a pure strategy is.

A pure strategy provides the complete definition of how a player will play a game. It determines the moves the player will make for any situation that player will face. A player's strategy set, is the set of pure strategies available to that player. 

A mixed strategy assigns a probability to each pure strategy that a player has. This allows a player to randomly choose a pure strategy. We know that probabilities are continuous, so it follows that there are infinitely many mixed strategies available to a given player. 

POKER

In terms of poker, this means that every possible situation in poker has a Nash equilibrium and poker in general, has a Nash equilibrium. WHAT?! Yup.

Alright, alright calm down. It's called Nash's Existence Theorem, there is a BIG difference between knowing that a Nash Equilibrium exists, and actually finding it. 

Let's begin our discussion about poker, by talking about how to play the game! Well Poker has tons of variations, there's Texas Hold 'Em as I said earlier, Razz, Omaha Hi, Omaha Hi/Lo, Seven Card Stud, Seven Card Stud Hi/Lo, Draw, Lowball, Twist, and everyone's favorite...Strip Poker!

https://media.giphy.com/media/xT5LMJnLbpxE41kQfu/giphy.gif

In Texas Hold 'Em, the game begins with a shuffle of the deck! 

What do you think the chances of this deck being the same as the one you previously held on a different poker night are? 1/100? 1/1000? It turns out that you should feel pretty special, as the configuration of cards being held that you shuffled have likely never been held before...like ever, and will likely never be held again. The total number of combinations is 52! or 80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000

If you don't find that number impressive, think about the alphabet. There are only 26 letters in the alphabet and just think about all the books that have been written by mixing those 26 letters around. There have to be like, tons of books.

Poker play happens in a clockwise fashion, moving from one player to the next. One player each round is on what is called "the button", which effectively acts as the dealer. Obviously in casinos and online the players aren't the dealers, but the button is still in effect. The player on the button receives the last action on all post flop streets of play. The player on the button typically has an advantage for that round because they can see what everyone else does before deciding whether to play or fold. 

Before every round of betting in Texas Hold 'Em style poker two players are required to pay the small and big blinds. These are forced bets that begin the wagering, without the blinds nobody would be required to put any money in the pot. The blinds are typically raised as time goes on in the game. The player directly to the left of the dealer or "button" as it is typically called, pays the small blind and the player to the left of the small blind pays the big blind. Typically the big blind is double the amount of the small blind. The blinds rotate throughout the game to ensure every player is paying an equal amount of blinds. 

Once the blinds are in the pot, then the dealer can begin by giving every player two cards, these cards are called "hole cards". Players conceal their cards to the other players in the game, view their hand, and then have the choice of whether or not they want to "push" or "fold". Pushing is wagering an amount of money equal to or greater than the big blind, or greater than or equal to the previous bet. Folding is cutting your losses early, if you were one of the blinds this means forfeiting that money, or if you weren't - losing no money. 

Now the exciting part begins, the flop! The dealer flops 3 cards in the middle of the table, and now every player still in the round has a 5 card hand. After the flop players once again have the choice to push or fold. No betting is required at this point, every player can "check" or push no chips, but more often than not betting will occur. Once betting has finished, a fourth card called, "the turn" card is dealt out to the table - so players now have 6 cards to make the best 5 card hand possible. Players once again have the option to push or fold, and then there is a fifth and final card dealt to the table, called "the river". Now players have all 7 cards in front of them, and hopefully can make a winning 5 card hand. If they believe they have a hand nobody else can beat, they'll probably bet big! Finally, after all the betting occurs - there is the great reveal where players display their hole cards. At long last, we know who has been bluffing and who has got the goods!

NASH POKER

Nash Equilibria in poker occurs when players ranges are in equilibrium with each other. This means that players are playing optimally against each other, where no player can gain anything by deviating from the equilibrium strategy. This would lead to a stalemate situation, because if one player changed away from equilibrium, the other players could adjust their ranges and have an advantage over the player who changed their strategy. Thus, the GTO strategy cannot be exploited!

Now like I said earlier, it is one thing to know that there is a Nash Equilibrium but the hard part is trying to find it! 

So far, poker has only been "solved" in very simple cases. One simple case is during an all-in or fold instance in a head's up game. Heads Up Poker is a poker game that is played between two players. This would be equivalent to Texas Hold 'Em where only two players remain on the table, as they have beaten the other players off the table. Obviously this is a very specific example and finding the Nash Equilibrium for more complicated cases would become exponentially more difficult. 

Let's take a look at a solved example: In this Heads Up game, the player in the small blind position can only go all in or fold, and the player in the big blind position can only call or fold. The small blind player is what is called the "pusher" in this scenario, and the big blind player is what is called the "caller."

The numbers in the tables represent the number of big blinds a player needs to have in order to make a play. This means pushing when you are in the small blind position or calling when you are in the big blind position. The color coding represents suited hands, off suit hands and pocket pairs. There are a few different calculators online that calculate a player's probability of winning by either shoving, folding, or calling in a Heads Up game, and there is one found here: http://gtorangebuilder.com/#home that solves Game Theory Optimal Postflop play, an exciting development.

In the end there are obviously many more variables involved in poker, that's why although the game is "solved" we may not live long enough to learn how to "beat" poker. Computing power is only increasing though, so we can't really say! In the mean time, I always recommend a solid bluff and pair of dark sunglasses. 

https://media.giphy.com/media/ClhVz6L3tnple/giphy.gif

As always, please feel obligated free to ask me questions!! 

I look forward to chatting more about Poker in class on Thursday.

UPDATE:

Hey all, just in case my explanation of Kuhn Poker wasn't crystal clear during my presentation today, here are my notes on that:

KUHN POKER

The poker game with a complete game theoretic analysis! 

In Kuhn poker, the deck includes only three playing cards, for example a King, Queen, and Jack, but these can be any cards so long as they aren't the same card (that'd be interesting to look at). One card is dealt to each player, which may place bets similarly to a standard poker. If both players bet or both players pass, the player with the higher card wins, otherwise, the betting player wins.

Kuhn proved that there are infinitely many equilibrium strategies for the first player, forming a continuum governed by a single parameter.

In one possible formulation, player one freely chooses the probability α ϵ [0, 1/3] with which he will bet when having a Jack. Then when having a King, he should bet with the probability of 3α; he should always check when having a Queen, and if the other player bets after this check should call with the probability of α + 1/3.

The second player has a single equilibrium strategy: Always betting or calling when having a King; when having a Queen, checking if possible, otherwise calling with the probability of 1/3; when having a Jack, never calling and betting with the probability of 1/3.

This image shows the game tree that we broke down a bit today in class. 

https://en.wikipedia.org/wiki/Kuhn_poker#/media/File:Kuhn_poker_tree.svg

( Clicking on it will make it bigger :) )

SOURCES:

Daws, Josh, and Federico Cruz. "6 Insane True Statistics That Laugh In The Face Of Logic."Cracked.com. 19 May 2015. Web. 31 Mar. 2017.

Kuhn, Harold W. "Kuhn Poker." Wikipedia. Wikimedia Foundation, 26 Mar. 2017. Web. 01 Apr. 2017.

McDonald, Mikey. "The Nash Calculator and the Nash Equilibrium Strategy in Poker."ICMIZER. 19 Oct. 2013. Web. 31 Mar. 2017.

Staff, Investopedia. "Nash Equilibrium." Investopedia. 06 Sept. 2013. Web. 31 Mar. 2017.

"Texas Hold'em Poker Rules." Texas Hold'em Poker Rules: The Official Learning Guide to Play Poker | PokerNews. Web. 31 Mar. 2017.

VIP, Matt. "Nash Equilibrium Explained." PokerVIP. 29 Mar. 2016. Web. 03 Apr. 2017.