Existence of mixed strategy involving a "best" pure strategy

82 Views Asked by At

$\textbf{Set up}$:

Let $G$ be a two player zero-sum game, and suppose $A$ is a $n \times m$ payoff matrix for this game, so that player $1$ has (pure) strategy set $\{s_1^1,...,s_n^1 \}$ and player $2$ has (pure) strategy set $\{s_1^2,...,s_m^2 \}$, and $A_{ij} = E(s_i^1,s_j^2)$ is the payoff to player $1$ when player $1$ uses their $i$-th pure strategy and player $2$ uses their $j$-th pure strategy. Denote by $E(X,Y)$ the payoff to player $1$ when player $1$ uses the mixed strategy $X = (x_1,...,x_n)$ and player $2$ uses the mixed strategy $Y = (y_1,...,y_m)$. Also $ E(X,j)$ is the payoff to player $1$ when player $1$ uses the mixed strategy $X$ and player $2$ uses their $j$-th pure strategy $s_j^2$, and $E(i,Y)$ is defined similarly.

A strategy $X$ for player $1$ is $\textbf{optimal}$ if it is part of a Nash equilibrium, i.e. there is some strategy $Y$ for player $2$ such that $(X,Y)$ is an equilibrium point. An optimal strategy $Y$ for player $2$ is defined in the same way.

Let $v(A)$ denote the value of the game, i.e. $v(A) = \max_{X} \min_{Y} E(X,Y) = \min_{Y} \max_{X} E(X,Y)$.

$\textbf{Question}$:

It is apparently a fact that if for every optimal strategy $Y$ of player $2$, $y_j = 0$ for a fixed $1 \leq j \leq m$, then there exists an optimal strategy $X$ of player $1$ for which $E(X,j) > v(A)$, but I struggle to prove this. Intuitively it seems likely that if $E(X,j) = v(A)$ for every optimal strategy $X$ of player $1$, then $j$ must be contained in the support of at least one optimal mixed strategy of $Y$, since it is a best response to every optimal strategy of player $1$.

The converse of this statement is something I can prove, namely that if for some optimal strategy $X$ of player $1$, $E(X,j) > v(A)$, we necessarily have that $y_j = 0$ for every optimal strategy $Y$ of player $2$, as this doesn't require demonstrating the existence of a particular optimal strategy. I don't think the proof of the converse statement is necessarily very helpful for the proof of this statement though.

Thanks for any help.