This is a problem I've been discussing with a friend just for fun. Neither of us has formally studied game theory so it may be that this is a well-known fact and we've just been lacking the appropriate terminology to successfully search for the answer.
Consider a two-player, zero-sum, symmetric game, represented by a finite matrix $R$, where $r_{ij}$ is player 1's reward when playing strategy $i$ against player 2's strategy $j$ (so the assumptions imply $r_{ij}=-r_{ji}$).
Suppose the game is in reduced form, so that no row of $R$ is equal to, or dominated by, any convex combination of other rows.
Conjecture: any Nash equilibrium for this game involves players using a mixed strategy with strictly positive probability for every state.
There seem to be two directions to approach a proof of the claim but we haven't made progress with either:
- If you claim to have a Nash strategy which doesn't use $i$, perhaps I can show that adding a little bit of state $i$ to your strategy (and removing something else) yields a better strategy. Formally, this claim is more or less that there exists a convex combination of other pure strategies which is dominated by strategy $i$. This seems plausible because $i$ is not itself dominated by any convex combination of the other pure strategies, but is not automatic from the definition.
- If I know you won't be using state $i$, I should be able to choose a strategy which highly weights those states $j$ which lose to $i$, since I don't need to worry about that outcome. If my strategy then beats yours, that shows you can't be playing the Nash strategy. However, you may have options available for beating each state which loses to $i$ even without using $i$ itself (e.g. in a game with 5 strategies, where each strategy wins vs two and loses vs two, forbidding yourself one option still leaves you able to beat anything I choose).
It feels like induction on the number of strategies is a natural approach, but inductive arguments are hurt by the fact that even though $R$ is in reduced form, removing a row needn't leave it in reduced form (e.g. in rock paper scissors, removing rock leaves scissors as the dominant strategy).
Proofs, counterexamples, or references related to the conjecture are welcome!
Best Answer
The name used for a mixed equilibrium strategy which involves every state is a "completely mixed" strategy, so the key terminology here is "completely mixed (Nash) equilibria".
A precise condition under which the exists a completely mixed Nash equilibrium is given in the paper "Completely mixed equilibria in bimatrix games", Igal Milchtaich and Tadeusz Ostrowski (see equation 8; the paper is written for games which are not necessarily symmetric, so the condition on the matrix B can be ignored, with $R$ in the notation from the question here substituted for $A$ in the paper).
However, it's not clear to me whether $R$ being in reduced form implies the condition of equation 8 holds.