Pure and Mixed Strategy Nash equilibrium

In this article, we will discuss about the pure and mixed strategy nash equilibrium which are important concepts in Game Theory.

What we'll see,

• Game Theory
• Nash Equilibrium in Game Theory
• Example of a nash equilibrium
• Pure strategy Nash Equilibrium
• Mixed strategy Nash Equilibrium
• Explained through examples
• Conclusion

Game Theory

Game theory is the study of mathematical models of strategic interactions among rational agents. It has various applications in fields of social science, in logic, systems science and computer science. It applies to a wide range of behavioral relations, it is an umbrella term for the science of logical decision making in humans, animals, and computers as well.

Nash Equilibrium in Game Theory

In game theory, nash equilibrium is a decision-making theorem that states a player can achieve the desired outcome by not deviating from their initial strategy. The nash equilibrium is a concept of game theory where the optimal outcome of a game is one where no player has an incentive to deviate from their chosen strategy or choose a different strategy after considering an opponent's choice. An individual can receive no incremental benefit from changing any actions, assuming other players remain constant in their strategies. A game can have no nash equilibrium or can have multiple nash equilibria.

Example of a Nash Equilibrium

Let us imagine a game between two players X and Y. It is a simple game in which both players can choose strategy A, to receive ₹1, or strategy B, to lose ₹1. Logically, both players would choose strategy A to receive a payoff of ₹1. If we revealed player X's strategy to Y and player Y's strategy to X, we see that no player will deviates from the initial choices they made. Knowing the opponent player's move will not make much of difference to change either player's behavior. The outcome A represents a Nash equilibrium as both the players would choose strategy A and would stick to their choice.

Payoff matrix for the game played between players X and Y:-

A Nash equillibrium is a strategy profile S_i = (S₁, S₂, . . . , S_n) with the property that

f_i(s) ≥ f_i(s₁, s₂,..., s_i',..., s_n)

for all i, where s_i' ∈ S denotes a strategy other than s_i available to player i.
In the event that this inequality is strict; i.e.

f_i(s) > f_i(s₁, s₂,..., s_i',..., s_n)

for all i, the profile s is called a strict Nash equilibrium. Otherwise, s is called a weak Nash equilibrium.

Pure strategy Nash Equilibrium

A Pure strategy Nash equilibrium is an action with the property that no single player i can obtain a higher payoff by choosing an action different from a_i, given every other player j adheres to their choice a_j.

Mathematically,
Given a strategic form game Γ = ⟨N, (S_i), (u_i)⟩, the strategy profile s^∗ = ( s₁* , s₂* , . . . , s_n* ) is said to be a pure strategy Nash equilibrium of Γ if,
u_i ( s_i* , s_-i* ) ≥ u_i (s_i , s_-i* ), ∀s_i ∈ S_i, ∀ i = {1,2,...,n}.
That is, each player’s Nash equilibrium strategy is a best response to the Nash equilibrium strategies
of the other players.

For example, let us imagine, there is a game played between two players A and B in which each player could choose two available choices, which are X and Y. If the players choose different actions, they each get a payoff of ₹0. If they both choose X, they each get ₹2, and if they both choose Y, they each get ₹1. The action profile (Y, Y) is an equilibrium, since if any one player chooses X, it would result in a lower payoff for the player. Simillarly, the action profile (X, X) is also an equilibrium. Such Nash equilibrium maintains a steady state that every player's behavior is the same whenever she or he plays the game.

Mixed strategy Nash Equilibrium

In addition, more general notions of a steady state allow the player's choices to vary or deviate on each occasion while playing the game. Which means that players might choose probability distributions over a set of actions available to them. Such a steady state is called Stochastic (involving Probability), and modeled by a Mixed strategy Nash equilibrium. A Mixed strategy Nash equilibrium is a mixed strategy action profile with the property that single player cannot obtain a higher expected payoff according to the player's preference over all such lotteries.

As in the example taken in pure strategy nash equilibrium, there is a third equilibrium that each player has a mixed strategy (1/3, 2/3) assigning action X with probability 1/3 and Y with probability 2/3.

Explained through examples

There is no pure strategy Nash equilibrium in this game. If we play this game, we should be unpredictable, i.e., we should randomize between strategies so that we do not get exploited. Suppose Player X has 75% chance of playing Heads and 25% of playing Tails, then, Player Y by choosing Tails with 100% chance can get an expected payoff of 0.75 x (1) + 0.25 x (-1) = 0.5. But that cannot happen at equilibrium since Player X then wants to play Tails with 100% chance deviating from the original mixed strategy. Since this game is completely symmetric it is easy to visualize that at mixed strategy Nash equilibrium, both players will choose Heads with 50% chance and Tails with 50% chance. In this case, the expected payoff to both players is 0.5 x (1) + 0.5 x (-1) = 0 and neither can do better by deviating to another strategy. In general, there is no gurantee that mixing will be 50/50 at equilibrium.

Now, let us find the mixed strategy Nash equilibrium of the following game which has no pure strategy Nash equilibrium.

Let p be the probability of Player X playing U and q be the probability of Player Y playing L at mixed strategy Nash equilibrium. Our objective is finding p and q.

At mixed strategy Nash equilibrium both players should have same expected payoffs from their two strategies as shown above.

At mixed strategy Nash equilibrium both players should have same expected payoffs from their two strategies.

Considering Player X, If it plays U, it'll receive a payoff of 2 with probability q and 1 with probability (1-q). Therefore, it has an expected payoff E(U) from playing U which is 2q + (1-q). If it plays D, it'll receive a payoff of 1 with probability q and 4 with probability (1-q). Therefore, it has expected payoff E(D) from playing D which is q + 4(1-q).

It'll mix between the two strategies only if these two expected payoffs are the same:
E(U) = E(D)
⇒ 2q+(1−q) = q+4(1−q)
⇒ 4q = 3
⇒ q = 3/4.
Therefore Player X will mix between the two strategies only if q=3/4.

Now, let us consider Player 2, if it plays L, it’ll receive a payoff of -3 with probability p and 1 with probability (1-p). Therefore it's expected payoff E(L) from playing L is -3p+(1-p). If it plays R, it’ll receive a payoff of 2 with probability p and -1 with probability (1-p). Therefore her expected payoff E(R) from playing R is 2p+(-1)(1-p).

It’ll mix between the two strategies only if these two expected payoffs are same:
E(L) = E(R)
⇒ −3p+(1−p) = 2p−(1−p)
⇒ 7p = 2
⇒ p = 2/7.
Therefore Player Y will mix between the two strategies only if p=2/7.

Therefore the mixed strategy Nash equilibrium is:-

• Player X: U with probability 2/7 and D with probability 5/7
• Player Y: L with probability 3/4 and R with probability 1/4.

The payoff for Player X is:-
(2 x 3/4) + (1 x 1/4) = (1 x 3/4) + (4 x 1/4) = 7/4
and the mixed Nash equilibrium payoff to Player Y is:-
(-3 x 2/7) + (1 x 5/7) = (2 x 2/7) + (-1 x 5/7) = -1/7

Conclusion

In this article at OpenGenus, we discussed about the pure and mixed strategy Nash equilibrium using the Game Theory concepts and examples.