Game Theory: Nash Equilibrium For Mixed Strategies ( Part 6 )

Continuous actions and Stochastic Strategic Games

Introduction

We introduced Nash Equilibrium solution concept in the previous blog. In this blog we will start with a continuous action example and we will discuss the applicability of Nash equilibrium in mixed strategies.

Mixed strategies are class of games where player chooses actions stochastically( i.e. Instead of chooses a single strategy, player chooses a distribution of strategies).

Example: Scarce Resource

Let’s try to understand how self interested players might behave in scenario of scarce resources. Imaging there are n fertilizer manufacturing companies each choosing how much to produce around a fresh water lake. Each manufacturing companies degrades some amount of fresh water in that lake and uses, Lets say the total units of water in lake is K. Each player i chooses his own consumption of clean water for production, kᵢ ≥ 0, and the amount of clean water left is therefore K -⅀ki .
The benefit of consuming an amount kᵢ ≥ 0 gives player i a benefit equal to ln(kᵢ) to the fertilizer company, and no other player benefits from i’s choice.
Each player also enjoys consuming the remainder of the clean air, giving each a benefit ln(K −⅀ kj). Hence the total payoff of player i is

For player i from the choice k= (k₁, k₂, . . . , kn).
To compute Nash equilibrium, we need to find a strategy profile for which all players choose best-response to their beliefs about his opponent).
That is we find strategy profile (k∗₁, k∗₂, . . . , k∗n) for which k∗ᵢ= BRi(k∗₋ᵢ) for all i ∈ N. For player I, we can get best response the by maximizing the value function written above. To find ki, which maximizes the value function of industry i, We can equate its derivative to zero.

Solving above equation gives player’s i best response.

Lets take only 2 industries case and solve this. ki(kj ) be the best response of player i.

Lets plot this with k1 payoff in x axis and k2 payoff in y axis.

If we solve the two best-response functions simultaneously, we find the unique Nash equilibrium, which has both players playing k₁= k₂ = K/3.

Mixed Strategies

So far we discussed pure strategies, but we need to discuss the problem where player may choose to randomize between several of his pure strategies. There are many interesting applications to this kind of behavior where player chooses actions stochastically( i.e. Instead of chooses a single strategy, player chooses a distribution of strategies). The probability of choosing any of pure strategy is nonnegative, and the sum of the probabilities of choosing any all pure strategies events must add up to one.
We will also closely observe applicability of Nash equilibrium to these mixed strategies. In fact, Nash equilibrium is applied to the games only if player chooses mixed strategies instead of pure strategies.

We start with the basic definition of random play when players have finite strategy sets Sᵢ:
Let Sᵢ = {sᵢ₁, sᵢ₁, . . . , sᵢm} be player i’s finite set of pure strategies. Define ΔSᵢ as the simplex of Sᵢ , which is the set of all probability distributions over Sᵢ . A mixed strategy for player i is an element σᵢ ∈ Sᵢ, so that
σᵢ= {σ(sᵢ₁), σᵢ(sᵢ₂), . . . , σᵢ(sᵢm)) is a probability distribution over Sᵢ ,
where σᵢ(sᵢ) is the probability that player i plays sᵢ .

Now consider the example of the rock-paper-scissors game, in which Sᵢ= {R, P, S} (for rock, paper, and scissors, respectively). We can define the simplex as
ΔSi ={(σᵢ(R), σᵢ(P ), σᵢ(S)) : σᵢ(R), σᵢ(P ), σᵢ(S)≥0, σᵢ(R)+σᵢ(P )+σᵢ(S)=1},

The player i and his opponents -i both choose mixed actions. It implies that player’s i belief about his opponents -i is not fixed but random. Thus a belief for player i is a probability distribution over the strategies of his opponents.

Definition: A belief for player i is given by a probability distribution πᵢ∈S₋ᵢ over the strategies of his opponents. We denote by πᵢ(s₋ᵢ) the probability player i assigns to his opponents playing s₋ᵢ ∈ S₋ᵢ .

For example in the rock-paper-scissors game, Belief of player i is represented as (πᵢ(R), πᵢ(P ), πᵢ(S)). We can think of σ*₋ᵢ as the belief of player i about his opponents, πᵢ, which captures the idea that player i is uncertain of his opponent’s behavior.

Expected payoff

In pure strategy, the payoff is straight forward. In mixed strategy, to evaluate payoff we need to reintroduce the concept of expected payoff.

The expected payoff of player i when he chooses pure strategy sᵢ∈ Sᵢ and his opponents choose mixed strategy σ₋ᵢ∈ ΔS−ᵢ
Please note that pure strategy is part of mixed strategy.

When player i choose mixed strategy σᵢ∈ ΔSᵢ and his opponents choose mixed strategy σ₋ᵢ∈ ΔS₋ᵢ.

Example !

Let calculate payoff in mixed strategy scenario.

lets assume that player 2 plays σ₂(R) = 0.5
σ₂(P ) = 0.5
σ₂(S) = 0
We can now calculate the expected payoff for player 1 if he chooses pure strategy.
V₁(R, σ₂) = 0.5*(0)+ 0.5*(-1) + 0 *(1)=-0.5
V₁(P, σ₂) = 0.5*(1)+ 0.5*(0) + 0 *(-1)= 0.5
V₁(S, σ₂) = 0.5*(-1)+ 0.5*(1) + 0 *(0)=0

V₁(P, σ2)>V₁(S, σ2)>V₁(R, σ₂)

To given player 2’s mixed strategy, we see a best response to player 1, which is action P.

Now let’s understand how Nash equilibrium solution concept applies to mixed strategies. It actually simpler than it looks, we just replace strategy profile with mixed strategy profile.

Definition: The mixed-strategy profile σ* = (σ*₁ , σ*₂ , . . . , σ*n ) is a Nash equilibrium if for each player σ*ᵢ is a best response to σ*₋ᵢ . That is, for all i ∈ N, vᵢ(σ*ᵢ , σ*₋ᵢ) ≥ vᵢ(σᵢ, σ*₋ᵢ). ∀ σᵢ∈ Sᵢ .
Each mixed strategy in a Nash equilibrium is a best response to all other mixed strategies in that equilibrium.
Let’s close the discussion on mixed strategies here. We will discuss more about them in the next blog in my blog series.

Thanks for your time.