Is there always a pure strategy to be the best response to a mixed strategy in a two-player zero-sum game

game theory

The game is characterized by a matrix M. In this game, the player chooses the row $i$ of $M$, and the adversary chooses the column $j$ of $M$. They make their decisions simultaneously.

Suppose the player chooses a row from some distribution $p$ which is known to the adversary. Then the adversary wants to choose a distribution $q^\*$ so as to maximize its expected reward, denoted as
$q^\*=argmax_{q}\mathbb{E}_{i\in p,j\in q}[M(i,j)]$.

In my view: the best response to a mixed strategy should also be a mixed strategy. But I read one book which states that any column $j$ would maximize this reward too. Namely, $max_{q}\mathbb{E}_{i\in p,j\in q}[M(i,j)] = max_{j}\mathbb{E}_{i\in p}[M(i,j)]$.

This is my question: Is there always a pure strategy to be the best response to a mixed strategy in a two-player zero-sum game? Or in any more general setting? If possible, please provide the references.

Thanks!

Best Answer

If player has a fixed mixed strategy, and adversary has a best response to it, then any active (having non-zero probability) pure strategy should be the best response to it.

It follows from simple fact that expected reward from a mixed strategy is convex combination of expected rewards from active pure strategies with weights equal to probabilities. And if some of active pure strategies has lower expected reward than other, then, by dropping this pure strategy in favour of other with greater expected reward, adversary increases their reward.

In formulas, $E_{i \in p, j \in q} M(i, j) = \sum_j p_q(j) \cdot E_{i \in p} M(i, j)$ (where $p_q(j)$ is probability $q$ assigns to $j$), and, if we have $p_q(j_0) > 0$, $E_{i \in p} M(i, j_0) < E_{i \in p, j \in q} M(i, j)$, then for some $j_1$ we necessary have $E_{i \in p} M(i, j_1) > E_{i \in p, j \in q} M(i, j)$ and thus strategy $q'$ s.t. $$p_{q'}(j) = \begin{cases} 0,& j = j_0\\ p_q(j_0) + p_q(j_1),&j = j_1\\ p_q(j) \end{cases}$$ gives reward higher than $q$ by value $p_q(j_0) \cdot (E_{i \in p} M(i, j_1) - E_{i \in p} M(i, j_0))$.

So, as no active pure strategy gives reward lower than expected reward for mixed strategy, all active pure strategies give the same reward as the mixed (if it's best response), and so are best responses themselves.

Note, however, that if player playing $p$ and adversary playing $q$ is Nash equilibria, it's not necessary that player playing $p$ and adversary playing some pure strategy active in $q$ is Nash equilibria.

Related Solutions

[Math] The Notion Of Degenerate Two Player Game

Does it mean that this always happens in degenerate game, that we have few solutions with the same payoffs for each player?

Not few. Infinite. In the example row player can play infinite mixed strategies which are best response to the column player strategy. And yes, this is a property of all degenerate games.

On the other hand, in the above example, we can just use mixed strategy for the row player: play the first row with probability 0.5 and play the second row with probability 0.5.

If you choose that mixed strategy the game remains degenerate. In fact the dual definition says that a 2-player game is degenerate if exists a strategy of support k for which the number of pure best responses of the adversary are more than k.

The definition can be applied also in games with more than two players. If, in a n-players game, exists a strategy s of n-1 players, such that the n-th player has a number of pure best responses greater than the size of the smallest support in the strategy s, then the game is degenerate. One example follows:

     A                 B
0/0/0 0/10/10     0/0/0 0/10/10
0/0/0 0/10/10     0/0/0 0/10/10

The first player (player 1) can choose which table (A or B) to use, while other two players are row player and column player. If player 1 chooses a strategy of (0.5,0.5) and column player chooses the second column (support 1), then the row player is indifferent to play first or second row (2 best responses). This game is degenerate because Nash equilibria are not isolated points.

[Math] Game Theory – Mixed strategy Nash equilibria

Okay, let's try this. For the 3x2 game, there are two obvious pure strategy Nash equilibria, (8,8) and (6,6). Are there any mixed equilibria?

Start with player 2, the Column player, who chooses X with probability $r$ and Y with probability $(1-r)$, and player 1, the Row player, choose a with probability $p$, b with probability $q$, and c with probability $(1-p-q)$, so I've slightly changed OP's notation. Column's payoff is $$r[8p+2q+(1-p-q)5]+(1-r)[0p+6q+(1-p-q)5].$$ Taking the derivative with respect to Column's choice variable, $r$ yields $$8p-4q.$$ If we set that equal to zero, we get $p=1/2q$, but that is the wrong way to look at the problem. What the derivative really says is that if $p<1/2 q$ then $r=0$, because the derivative is negative and the maximum occurs at the lower endpoint, 0. Similarly, if $p>1/2 q$ then $r=1$ because the derivative is positive.

So the only hope for a mixed strategy equilibrium is if $p=1/2 q$. Will that work? Look at the problem from the viewpoint of player 1, who plays Row. Her expected value is $$pr8 +0 +qr2+q(1-r)6+(1-p-q)5.$$ Take the derivative with respect to $p$, simplify, and get $8r=5$, or $r=5/8$. As before, this says that if $r<5/8$ then $p=0$. Take the derivative with respect to $q$, and a similar approach shows that $r<1/4$ implies $q=1.$

So, the only places where $p$ and $q$ are not either zero or one, is $p=5/8$ and $q=1/4.$ But then we don't have $p=1/2q$ and so there is not mixed equilibrium. or so it seems to me.

Best Answer

Related Solutions

[Math] The Notion Of Degenerate Two Player Game

[Math] Game Theory – Mixed strategy Nash equilibria

Related Question