Finding support of optimal mixed strategy

Question

Considering a finite zero-sum game represented by a matrix $\mathbf{A}$, I understand one method to solve for the game is to use the principle of indifference. If the optimal strategy of Player 1 (who chooses the rows of the matrix game) uses each pure strategy with positive probability, the optimal strategy of Player 2 can be found by solving the linear system $$\mathbf{A}\mathbf{q}=\mathbf{1}$$ for the column vector $\mathbf{q}$, which is then a scalar multiple of the probabilities for Player 2's mixed strategy.

The problem is that the values of $\mathbf{q}$ may turn out to be negative, which indicates that Player 1 does not use all pure strategies. Of course if we take the submatrix which retains only those pure strategies which are used with positive probability in the optimal strategies we can still use the indifference principle. But the problem is finding the submatrix.

Is there an algorithm to find this submatrix? I read that the simplex algorithm may be used to solve for the optimal strategies, but I don't understand the algorithm well enough to see the connection to principle of indifference approach. It seems solve the game and determine which strategies are never used at the same time.

Answer 1

I'm supposing the the game is symmetric (i.e., both players 1 and 1 have the same payoff matrix $\boldsymbol{A}$). I also suppose that when you say "optimal strategy" you mean "Nash equilibrium strategy". Recall that $\boldsymbol{q} \in \mathbb{R}$ is a strategy if:

$$ \boldsymbol{q} \in \Delta = \{\forall i\in\{1, \ldots, N\} ~q_i \in [0, 1] \wedge \sum_{i=1}^N q_i = 1\},$$ $C(q)$ denotes the support of the strategy $q$:

$$C(\boldsymbol{q}) = \{i\in\{1, \ldots, N\} : q_i > 0\},$$

vectors $\boldsymbol{q} \in \mathbb{R} \setminus \Delta$ can't be classified as strategies and $$[\boldsymbol{Aq}]_i$$ is the $i$-th entry of the vector $\boldsymbol{A q}$.

First of all, if $q$ is a Nash equilibrium, then:

$$\left\{ \begin{array}{ll} [\boldsymbol{Aq}]_i=[\boldsymbol{Aq}]_j ~\forall i, j \in C(\boldsymbol{q})\\ [\boldsymbol{Aq}]_i \geq [\boldsymbol{Aq}]_k ~\forall i \in C(\boldsymbol{q}), \forall j \not\in C(\boldsymbol{q})\end{array}\right. . ~~~~ (1) $$

From this, it follows that it is not always true that:

$$\boldsymbol{Aq} = \boldsymbol{1}.$$

Having said that, one must solve the system $(1)$ in order to find all the possible optimal strategies $\boldsymbol{q} \in \Delta$ having a certain support.

Example. If $N = 3$, then system $(1)$ must be solved $2^3-1 = 7$ times. Indeed, only $7$ different support are feasible when $N=3$:

In general, system $(1)$ must be solved $2^N-1$ times. Notice also that the total number of non-redundant equalities and inequalities for the system $(1)$ is always $N-1$ for each chosen support.

Example. If $N = 4$ and one chooses the support $\{1, 3, 4\}$ then the system to be solved is:

$$\left\{\begin{array} = [\boldsymbol{Aq}]_1 = [\boldsymbol{Aq}]_3 \\ [\boldsymbol{Aq}]_1=[\boldsymbol{Aq}]_4 \\ [\boldsymbol{Aq}]_1\geq[\boldsymbol{Aq}]_2 \end{array}\right. , $$

with $q_2 = 0$.

Although we are solving different "reduced problem", I don't know if it is really correct to say "finding the submatrix". Indeed, each system is built up of both equalities and inequalities. This means that generally doesn't have to calculate the inverse of a (sub)matrix to solve a standard system in order to find an optimal strategy. Anyway, if we move our attention only on the $q$ that are candidate to be optimal, then one can extract a submatrix looking at the subsystem built up only by equalities. The remaining inequalities are afterwards used as an "optimality test".

Hope this could be useful.