Mixed Strategy Nash Equilibrium

This post discusses about Mixed Strategy Nash Equilibrium, which is based on nash equilibrium. If you are not familier with Nash Equilibrium, please refer to this article.

Definition of Mixed Strategy Nash Equilibrium

A mixed strategy profile $\sigma = (\sigma_1, \sigma_2 \dots \sigma_n)$ is a nash equilibrium if, for each player i, $\sigma_i$ is the best response to $\sigma_{-i}$
That is, $u_i(\sigma_i , \sigma_{-i}) \geq u_i(\sigma_i', \sigma_{-i}) \text{ for all } \sigma_i' \text{ and } i$
Which means, no one in the game has any incentive to choose another strategy including mixed strategy.
It is sufficent to check all of player i's pure strategies: $u_i(\sigma_i , \sigma_{-i}) \geq u_i(s_i, \sigma_{-i}) \text{ for all } s_i \in S_i \text{ and } i$
This is because, mixed strategy is only a linear interpolation beteween different strategies. For example, if the strategy a gives expected payoff 10, and strategy b gives expected payoff 15, then mixing between strategy a and b will always give a lower expected payoff than 15, which clearly cannot be a best response. This is the reason we can only care about pure strategies.
For a mixed strategy to be a best response, it must put positive probabilites only on pure strategies that are best responses.

	H	T
H	1, -1	-1, 1
T	-1, 1	1, -1

Suppose that payer 2 chooses heads or tails in equal probability.
The expected payoff of player 1 is, $u_1(H, (0.5, 0.5)) = 0.5-0.5 = 0$ $u_1(T, (0.5, 0.5)) = -0.5 + 0.5 = 0$
Notice that the expected payoff is same in either choices, Heads or Tails.
This implies that for player 1, there is no incentive to deviate from any mixed strategy, thus any strategy for player 1 is a best response.
Assume that player 1 also chooses in equal probability, Then because of the symmetry of the game, we notice that both players are best responding to each other.
Thus the mixed strategy profile, $((0.5, 0.5), (0.5, 0.5))$ is a maxed strategy nash equilibrium.

	A	B
A	1, 1	0, 0
B	0, 0	1, 1

suppose that player 1 chooses A in probability p, and player 2 chooses A in prbability q
The expected payoff for player 1 playing A is q, and for playing B, it is 1 - q.
If q is 0.5, choosing A or B for player 1 is indifferent. Thus any mixed strategy is a best response.
If q is not 0.5, then choosing either A or B is always better than mixed strategy.
Note that the same logic applies to player 2. Thus, there are nash equilibriums in this game. $NE = \{((0.5, 0.5), (0.5, 0.5)), ((1, 0), (1, 0)), ((0, 1), (0, 1))\}$

	A	B
A	2, 2	0, 0
B	0, 0	1, 1

As the example above, suppose that player 1 chooses A in probability p, and player 2 chooses A in prbability q.
We can first notice that we have two pure nash equilibrium, (A, A) or (B, B).
The expected payoff for player 1 playing A is 2q, and for playing B, it is 1 - q.
Those expected payoff must be equal for mixed strategy nash equilibrium to exist.
Thus, p must be 1/3

Calculate the set of rationalizable strategies by performing the iterated dominance procedure.
Restricting attention to rationalizable probabilites that make the other player indifferent between the relevant pure strategies.
Solve these equations to determine the equilibrium mixing probabilities.

	X	Y
A	0, 5	4, 3
C	3, 0	0, 2

Notice that we cannot find any pure strategy nash equilibrium.
Suppose player 2 chooses X by probability q.
The expected payoff for A is 0q+4(1-q), and 3q+0(1-q) for B. These values should be same. Thus, 4-4q = 3q, p=4/7.
Then suppose player 1 chooses A by probability p.
The expected payoff for X is 5p+0(1-p), and 3p + 2(1-p) for Y. Thus, 5p = 3p+2-2p, p=1/2.
We found out the unique nash equilibrium, $((1/2, 0, 1/2), (4/7, 3/7))$

Every finite game (having a finite number of players and finite strategy space) has at least one Nash equilibrium in pure or mixed strategy.

All pure strategies that are being played in a mixed-strategy Nash equilibrium must yield the same expected payoff.
All pure strategies that are not being played in a mixed-strategy Nash equilibrium cannot yield a higher payoff.
Every finite game (having a finite number of players and a finite strategy space) has at least one Nash equilibrium in pure or mixed strategies.

	H	T
H	1, -1	-1, 1
T	-1, 1	1, -1

Suppose player 1 chooses head in probability p, and player 2 chooses head in probability q.
Then, the strategy profile can be represented as a point in $R^2$ . More formally, $(p, q) \in [0, 1] \times [0, 1]$
Assume that player 1 will play H (p = 1). Then for player 2, T is the best response.
If player 1 playes T, thne H is the best response.
If player 1 playes mixed strategy $(0.5, 0.5)$ , any mixed strategy of player 2 is indifferent.
If player 1 playes H in a probability less than 1/2, Then for player 2 playing H is the best response, and if player 1 playes H in probability greater that 1/2, Then for player 2 playing T is the best response.
Thus the mixed strategy best response is,

$MSBR_2(p) = \begin{cases} 1 \text{ if } p<1/2\\ \forall q \in [0, 1] \text{ if } p=1/2 \\ 0 \text{ if } p>1/2\end{cases}$

One can find mixed strategy best response function for player 1, and then find the intersection point to find MSNE.

There is a pedestrian hit by the car, and there are n bystaners. Assume cost c is required for somebody to call, and if anybody calls, then everybody gets the payoff v for finding out pedestrian safe. Also assume the situation where one people tends to call and other does not (pure strategy).
This situation is a pure strategy nash equililbrium, because for the person who doesent call, it is only paying more if they call.
The question rising is that, is there a mixed strategy nash equilibrium?
Assume there is, and let $\alpha$ be the probability that a player would call. Becuause we are assuming mixed strategy, boh choices, calling and not calling has to make indifferent payoff. If a player calls, then he gets payoff of $v - c$ .
If a player doesn't call, there are two cases. The first case is that no one calls, and the second case where someone else calls.
The probability of no one else calls, is $(1 - \alpha)^{n - 1}$ , and the probability that at least some one calls, is $1 - (1 - \alpha)^{n - 1}$ Thus the expected payoff when player doesn't call, is $0(1 - \alpha)^{n - 1} + v(1 - (1 - \alpha) ^ {n - 1})$ , and this value must equal $v - c$
Solving for v,

$c = v (1 - \alpha)^{n - 1}\\$ $1 - \alpha = (\frac{c}{v})^{\frac{1}{n - 1}}\\$ $\alpha^* = 1 - (\frac{c}{v})^{\frac{1}{n - 1}}$

Thus in MSNE, probability that an individual would call is, $\alpha^* = 1 - (\frac{c}{v})^{\frac{1}{n - 1}}$ The probability that no one calls is, $(\frac{c}{v})^{\frac{n}{n - 1}}$
Note that as n increases, the exponent, $1 + \frac{1}{n - 1}$ decreases, thus the total probability goes to 1, because $\frac{c}{v} < 1$ . This means that more and more people involved, the probability of no one calling increases.