Minmax in mixed strategies $\le$ minmax in pure strategies?

Question

Let $G$ be a finite game with set of players $N$ and strategy sets $(A_i)_{i\in N}$. For any player $i$ let his minmax-value in pure strategies be defined by $$ \underline v_i^p = \min_{a_{-i} \in A_{-i}} \max_{a_{i} \in A_i} u_i(a_i, a_{-i}), $$ and his minmax-value in mixed strategies by $$ \underline v_i^m = \min_{m_{-i} \in \Delta A_{-i}} \max_{m_{i} \in \Delta A_i} u_i(m_i, m_{-i}). $$

Question:

Is it always the case that $\underline v_i^m \le \underline v_i^p$?

The opposite inequality does not hold, because in the classical battle of the sexes with payoff matrix

$$ \begin{matrix} & \text{A} & \text{B} \\ \text{A} & 3,1 & 0,0 \\ \text{B} & 0,0 & 1,3 \\ \end{matrix} $$ player $1$'s min-max value in pure strategies is $1$ while it is $3 \over 4$ in mixed strategies.

This seems like an important question but so far I've failed to come up with a counterexample or a proof.

Thank you!

Answer 1

Yes, it is. Let me help you see why this is case.

First observe that for an arbitrary player $i$

$$\underset{\sigma_{-i}\in \Sigma_{-i}}{min}\;\underset{\sigma_i\in\Sigma_{i}}{max}\;u_{i}(\sigma_{-i}, \sigma_i)=\underset{\sigma_{-i}\in \Sigma_{-i}}{min}\;\underset{s_i\in S_{i}}{max}\;u_{i}(\sigma_{-i}, s_i),$$

where $\sigma_{i}=\Delta(S_i)$ and $\sigma_{-i}\in\prod_{j\ne i}\Delta(S_j)$(we are assuming every strategy set $S_i$ to be finite!). Why? because every (expected) payoff function for every player is multi-linear. So, for every possible strategy vector $\sigma_{-i}$, the payoff function $u_{i}(\sigma_{i},\sigma_{-i})$ is linear in $\sigma_{i}$ no matter which $\sigma_i$ we are considering.

The min-max for player $i$ should be the minimum payoff over every possible $\sigma_{-i}$, knowing that player $i$ Will choose the strategy $\sigma_i$ to maximize it, at every such $\sigma_{-i}$. The set $S_{-i}=\prod_{j\ne i}S_{j}$ is a subset of $\Sigma_{-i}$, so the minimum over $\Sigma_{-i}$ must be lower than the minimum over $S_{-i}$, right? formally, it must be that:

$$\underset{\sigma_{-i}\in \Sigma_{-i}}{min}\;\underset{s_i\in S_{i}}{max}\;u_{i}(\sigma_{-i}, s_i)\le \underset{s_{-i}\in S_{-i}}{min}\;\underset{s_i\in S_{i}}{max}\;u_{i}(s_{-i}, s_i).$$

Answer 2

$$v_i^{m}=\min_{m_{-i}\in \Delta A_{-i}} \max_{m_i\in \Delta A_i} u \leq \min_{m_{-i}\in \Delta A_{-i}} \max_{p_i\in A_i} u \leq \min_{p_{-i}\in A_{-i}} \max_{p_i\in A_i} u=v_i^p$$

The first inequality here holds because for any fixed strategy of the other players, the best thing to do for player $i$ is to pick a pure strategy. In fact, his payoff for any mixed strategy is the mean of the payoffs of pure strategies, and therefore cannot be larger than the largest pure payoff.

The second inequality is trivial.