Optimal mixed strategy in two player zero sum games

Question

I am currently studying game theory based on Peter Norvig's 3rd edition introduction to artificial intelligence book. In chapter 17.5, the two player zero sum game can be solved by using the $\textbf{minimax}$ theorem $$max_x \, min_y \, x^TAy = min_x \, max_y \, x^TAy = v$$

where $x$ is the probability distribution of actions by the max player (in the left equation) and the min player (in the right equation).

Regarding the minimax theorem, I have 2 questions.

1. Do both the min and the max players have the same probability distribution of actions ? In the book by Peter Norvig, the book demonstrated that in the game of $\textbf{Morra}$, both the min and max player had $[\frac{7}{12}:one, \frac{5}{12}:two]$ for the probability distributions.

2. Also, regarding minimax game tree, is the difference between minimax game tree and the zero sum game the fact that for minimax game tree, the opponent can react to the first player's move whereas for zero sum game defined in 17.5, both players are unaware of each other's move ?

Answer 1

I will answer the first question question based on information I have gathered so far. The probability of each action for the $\textbf{two player zero sum game}$ need not be the same for both players. It turns out that in the game of Morra, the probability vectors just turn out to be the same value.

In general to determine $\textbf{optimal mixed strategies}$ for two player two action game: Suppose we have 2 actions $a_1$ and $a_2$. In a mixed strategy, we let the probability of the row player taking action $a_1$ be $p$. The probability of the row player taking $a_2$ is then $1-p$. Now, we will try to find the probability $p$ such that the column player is indifferent to either action $a_1$ or $a_2$. (I.e the expected payoff for column player if row player plays $a_1$ with probability $p$ is the same for either actions).

Solving for $p$, we know that the column player can play any mixed strategy since any strategy played by the column player will yield the same payoff (since expected payoff is the same for either $a_1$ and $a_2$). Since column player can play any mixed strategy, we want to find a probability distribution over $a_1$ and $a_2$ for the column player such that the row player is indifferent to either action $a_1$ or $a_2$. We let the column player take action $a_1$ with probability $q$. It turns out we can repeat the same process for the column player and find the values of $p$. The game value for the row player can be computed from $x^TAy$ and this turns out to be the same value for the column player as well. (Only in zero sum games)

Doing this process yields a $\textbf{mixed strategy Nash Equilibrium}$, using such an approach does not always work however in the scenario when one action choice always dominates another action choice. (I.e in the case of the prisoner's dilemma of Alice and Bob, no matter what mixed strategy Bob tries to use, there will never be a mixed strategy such that Alice is indifferent to refusing or testifying). She will always testify.

I am not too sure about how to solve zero sum games involving more than 2 actions. I think linear programming would have to be used but i am not to familiar with how it can be applied.