Nash

Recall: A finite game:

·         Has a finite number of players

·         With a finite number of strategies

A strategy set defines what strategies are available for a player

A player has a finite strategy set if they have a fixed number of discrete strategies available to them. (rocks, paper, scissors in rocks paper scissors)

A mixed strategy is a probability distribution over two or more pure strategies:

i)                    Players choose randomly among their options in equilibrium

ii)                   If mixtures are mutual best responses, the set of strategies is a mixed strategy Nash equilibrium

A pure strategy completely defines how a player will pay definitely play a game (given the assumptions at the end)

i)                    It determines the move a player will make given any potential situation

ii)                   The strategy set is the set of pure strategies available to that player.

Nash’s Existence Theorem-

There must be at least one Nash Equilibrium (NE) for all finite games.

Taking this further: if no equilibrium exists in pure strategies, one must exist in mixed strategies

Nash’s Existence Proof:  http://www.cs.ubc.ca/~jiang/papers/NashReport.pdf

Generally, a Nash Equilibrium is a set of strategies, one for each player, such that no player has incentive to change his/her strategy given what the other player is doing.

This implies things:

1) We only care about individual strategic changes (not collaborated changes)

2)Nash equilibria are inherently stable (what one player is doing is optimal given what the other player is doing and vice versa)

       

3)3)  No regrets for either player in a NE(yolo!)

Combining payoff matrices creates an overall matrix that illustrates payoff for each player given a strategy.

To see if a strategy is in NE, we will isolate that outcome and see if any player can do better by changing their strategy.

The game of Stag Hunt (look it up fool):

• -          Two hunters (players) going out for food
• -          There are two hares and one stag in the woods
• -          The hunters are only able to bring equipment to hunt either the hares or the stag, but not both
• -          Hunters cannot coordinate between themselves
• -          The stag is worth 6 meat, while the hares are worth 1 each
• -          To successfully hunt the stag both players must hunt the stag (bring stag hunting equipment), while hare hunters can catch all of their prey by themselves

Condensed into a payoff matrix(player 1 represents the rows and player 2 represents the columns):

	Stag	Hare
Stag	(3,3)	(0,2)
Hare	(2,0)	(1,1)

Take note that there is no dominating strategy for each player: the optimal play for one player is completely dependent on what the other player does.

One player only wants to hunt a stag if the other player is hunting the stag, likewise if one player is hunting a hare the other player wants to hunt the hare.

To find Nash Equilibrium (there can be more than one)

-                                       Isolate each outcome and see if either player can individually do better by changing their strategy (BUT NOT THEIR OPPONENTS!)

We see that (stag, stag) and (hare, hare) are Nash Equilibria.

(stag, stag) makes sense, but why (hare,hare)? Comment what you think… I will be going over this in class…

Also, is the Stag Hunt a mixed strategy equilibrium or a pure strategy equilibrium?

I will be presenting more examples in class so be prepared and maybe do some research(?).

Cool…

Conditions that guarantee the Nash Equilibrium is played are:

1. 1.       Players all will do their utmost to maximize their expected payoff
2. 2.       Players have sufficient knowledge to deduce the solution
3. 3.       Players understand the planned equilibrium strategy of all the other players
4. 4.       Players believe that a deviation in their own strategy will not cause deviations by any other players
5. 5.       There is common knowledge between players that all players meet these criteria

When the previous conditions are not met, in numerical correspondence:

1. 1.       If the game does not correctly describe the quantities a player wishes to maximize. For instance, if a player in the Stag Hunt game wishes to starve themselves.
2. 2.       This condition may not be met because even though an equilibrium exists, it is unknown due to lack of knowledge. i.e. a child playing tic-tac-toe.
3. 3.       Players wrongly distrusting each other’s rationality may adopt counter strategies to expected irrational play. Remember the game of chicken? Driving with sunglasses on and grasping whiskey bottles towards your opponent. 

Takeaway points: 

• 1.       Holding all other players’ actions constant, a best response is the most profitable move a particular player can make.
• 2.       A game is in Nash equilibrium when all players are playing best responses to what the other players are doing.
• 3.       Put differently, a Nash equilibrium is a set of strategies, one for each player, such that no player has incentive to change his or her strategy given what the other players are doing. 
• 4.       Nash equilibria can be inefficient.
• 5.       At least one Nash equilibrium exists for all finite games.
• 6.       A game is finite if the number of players in the game is finite and the number of pure strategies each player has is finite. The stag hunt has two players, each of whom has two strategies. Therefore, it is a finite game.
• 7.       There may or may not be one in infinite games.

And what is a blog without a gif:

https://giphy.com/gifs/producthunt-mind-blown-blow-your-26ufdipQqU2lhNA4g

Also, forget about the formatting issues... 

Sources:

 http://www.math.tau.ac.il/~mansour/course_games/2006/lecture6.pdf

JimBobJenkins. "Game Theory 101 MOOC (#5): What Is a Nash Equilibrium?" YouTube. YouTube, 01 Sept. 2012. Web. 05 Apr. 2017. <https://www.youtube.com/watch?v=5TcYV6CZ7mI>.

"Nash equilibrium." Wikipedia. Wikimedia Foundation, 05 Apr. 2017. Web. 05 Apr. 2017. <https://en.wikipedia.org/wiki/Nash_equilibrium>.

"Strategy (game theory)." Wikipedia. Wikimedia Foundation, 26 Feb. 2017. Web. 05 Apr. 2017. <https://en.wikipedia.org/wiki/Strategy_(game_theory)#Mixed_strategy>.

"The Stag Hunt and Pure Strategy Nash Equilibrium." Game Theory 101. N.p., n.d. Web. 05 Apr. 2017. <http://gametheory101.com/courses/game-theory-101/the-stag-hunt-and-pure-strategy-nash-equilibrium/>.

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.