Nash Equilibrium in two person game reduction

Question

My game theory professor mentioned in class that finding a nash equilibrium in any two person game can be reduced to find a nash equilibrium in a symmetric two person game by constructing a symmetric two person game. He did not explicitly give out the construction and I am not able to construct it myself. Anyone can give the construction here?

Answer 1

Hint: Try computing the Nash of the following symmetric game (suppose the original matrix game is given by $(R, C)$).

$$ \left(\begin{bmatrix} \mathbf 0 & R \\ C^\top & \mathbf 0 \end{bmatrix}, \begin{bmatrix} \mathbf 0 & C \\ R^\top & \mathbf 0 \end{bmatrix}\right). $$

(Basically you may want to make things 'larger' if you want to reduce them to something (seemingly) simpler.)

In a Nash of the symmatric game, let $\{p_1, \dotsc, p_n\}$ be the probabilities used by player 1 for her first $n$ actions, $\{q_1, \dotsc, q_n\}$ the probabilities for player 2's second $n$ actions. Let $P=p_1 + \dotsb + p_n$ and $Q=q_1 + \dotsb + q_n$. Then $$\left(\frac{p_1}{P}, \dotsc, \frac{p_n}{P} \right), \quad \left(\frac{q_1}{Q}, \dotsc, \frac{q_n}{Q} \right) \tag{$\star$}$$ is one desired Nash.

A corner case. WLOG $R, C \in \mathbb R_+^{n \times n}$. If $P=0$, then $Q$ must also be zero (or the column player can switch to better strategies). In this case, just switch the strategies of the two players to obtain a Nash for the original game.

Why $(\star)$ is a Nash? The clue is in, for example, the row player's expected utility $$\begin{bmatrix} \mathbf p^\top & \mathbf p'^\top \end{bmatrix}\begin{bmatrix} \mathbf 0 & R \\ C^\top & \mathbf 0 \end{bmatrix} \begin{bmatrix} \mathbf q' \\ \mathbf q\end{bmatrix} = \mathbf p'^\top C^\top \mathbf q' + \mathbf p^\top R \mathbf q,$$ where $\mathbf p=(p_1, \dotsc, p_n), \mathbf q=(q_1, \dotsc, q_n)$. (It may help to imagine the two players are playing two simultaneous games, which I think also best describes the core idea of this reduction.)