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/>.