Nash Equilibrium Quiz

I’m going to ask you a few questions to test your understanding of a Nash equilibrium. The answers to the first two questions come from the definition of Nash Equilibrium; the answer to the third involves some thinking.

  • Definition of Nash Equilibrium:

    A Nash equilibrium (for a 2-player game) between players X and Y is a pair of strategies S = (Sx, Sy) for X and Y respectively such that when both players use these strategies, neither can unilaterally alter their strategy to increase their payout.

I’ll start off listing questions and then I’ll give the solutions below.

Questions

Question 1: Comparing Different Equilibrium Strategies

Suppose you are playing rake free HUNL (heads up no limit) and you’ve discovered two different equilibrium strategies S and T. Is it possible for EV(S) > EV(T)? If so, provide an example. Otherwise, prove that this is impossible.

Question 2: Unused Lines in a Gametree

Suppose that we have an equilibrium strategy S = (Sx, Sy) for players X and Y such that player X never uses a particular action A at a given node in the game-tree. Now, suppose we modify the game-tree to remove X’s option to take action A at that node. Can Y modify their strategy Sy to exploit this altered game-tree (that is, can Y increase their payout in any way?)

Question 3: Nash Equilibria as Fixed-points of Maximally Exploitative Strategy Sequences

Suppose you are playing HUNL rake free. You and your opponent start off with strategies S0 and T0. You adjust your strategy to maximally exploit T0, resulting in S1. Villain then adjusts to maximally exploit your new strategy, resulting in T1. You continue iteratively exploiting each other until you reach a fixed point (neither one of you can do any better).

  1. Is this fixed point always an equilibrium pair?
  2. Do you always reach such a fixed point?

Solutions

Question 1

It is impossible that EV(S) > EV(T) for equilibrium strategies S = (Sh, Sv) and T = (Th, Tv); here Sh and Th are Hero’s (that is to say, your), equilibrium strategies, and Sv and Tv are villain’s equilibrium strategies.

Let’s prove by contradiction. Suppose that hero’s payout is higher for S than it is for T; that is, P(S)> P(T). Let’s look at what happens when Hero plays Sh against villain’s Tv. Since Sh is part of an equilibrium strategy it must win Hero at least P(S) > P(T). This means that Hero could have used Sh against villains Tv and gotten a payout higher than if they’d used strategy Th. Since (Th, Tv) is an equilibrium pair this is impossible, and we’ve derived a contradiction. Since we’ve derived a contradiction we conclude that it is impossible for two equilibria to have different expected payouts.

Question 2

Deleting an action unused by player X from the game-tree does not open a X up to being exploited. This again follows from the definition of Nash equilibrium: any strategy that would exploit this lack of a line would be gaining EV against X’s equilibrium strategy.

In more detail, fix X’s equilibrium strategy Sx and move it to the new game-tree with action A removed from the game-tree. If player Y exploits this strategy in the new game tree then they have increased their payout against Sx. But Sx has not changed at all, and this new exploitative strategy from Y would also be exploiting Sx in the original game tree, contradicting that Sx was an equilibrium strategy to begin with.

Question 3

  1. When a fixed point is reached it is always an equilibrium. This follows directly from the definition of a Nash equilibrium: a fixed point is simply a pair of strategies such that neither player can unilaterally increase their payout by altering their strategy.

  2. Such a fixed point is not always reached. In particular, finding maximally exploitative strategies does not handle mixing. A classic example is the AKQ game. If the polar player is under bluffing then the condensed player always folds, which makes the polar player always bluff, which makes the condensed player always call, which makes the polar player never bluff, which makes the condensed player always fold, etc.