Answers.Body: <p>I will answer the first question question based on information I have gathered so far. The probability of each action for the <span class="math-container">$\textbf{two player zero sum game}$</span> 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.</p>
  <p>In general to determine <span class="math-container">$\textbf{optimal mixed strategies}$</span> for two player two action game: Suppose we have 2 actions <span class="math-container">$a_1$</span> and <span class="math-container">$a_2$</span>. In a mixed strategy, we let the probability of the row player taking action <span class="math-container">$a_1$</span> be <span class="math-container">$p$</span>. The probability of the row player taking <span class="math-container">$a_2$</span> is then <span class="math-container">$1-p$</span>. Now, we will try to find the probability <span class="math-container">$p$</span> such that the column player is indifferent to either action <span class="math-container">$a_1$</span> or <span class="math-container">$a_2$</span>. (I.e the expected payoff for column player if row player plays <span class="math-container">$a_1$</span> with probability <span class="math-container">$p$</span> is the same for either actions).</p>
  <p>Solving for <span class="math-container">$p$</span>, 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 <span class="math-container">$a_1$</span> and <span class="math-container">$a_2$</span>). Since column player can play any mixed strategy, we want to find a probability distribution over <span class="math-container">$a_1$</span> and <span class="math-container">$a_2$</span> for the column player such that the row player is indifferent to either action <span class="math-container">$a_1$</span> or <span class="math-container">$a_2$</span>. We let the column player take action <span class="math-container">$a_1$</span> with probability <span class="math-container">$q$</span>. It turns out we can repeat the same process for the column player and find the values of <span class="math-container">$p$</span>. The game value for the row player can be computed from <span class="math-container">$x^TAy$</span> and this turns out to be the same value for the column player as well. (Only in zero sum games)</p>
  <p>Doing this process yields a <span class="math-container">$\textbf{mixed strategy Nash Equilibrium}$</span>, 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.</p>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-19T15:41:16.230Z
Answers.LastActivityDate: 2020-11-19T15:41:16.230Z
Answers.UserDisplayName: calveeen
Body: <p>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 <span class="math-container">$\textbf{minimax}$</span> theorem
  <span class="math-container">$$max_x \, min_y \, x^TAy = min_x \, max_y \, x^TAy = v$$</span></p>
  <p>where <span class="math-container">$x$</span> is  the probability distribution of actions by the max player (in the left equation) and the min player (in the right equation).</p>
  <p>Regarding the minimax theorem, I have 2 questions.</p>
  <ol>
  <li><p>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 <span class="math-container">$\textbf{Morra}$</span>, both the min and max player had <span class="math-container">$[\frac{7}{12}:one, \frac{5}{12}:two]$</span> for the probability distributions.</p>
  </li>
  <li><p>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 ?</p>
  </li>
  </ol>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-11-16T23:48:33.130Z
Comments.Text: I don't have the book in front of me, but for question #2 you are correct - they are using game theory to model a simultaneous-action game, while minimax is for sequential action games.
Comments.UserDisplayName: Nathan S.
Tags: <minimax><game-theory><zero-sum-games>
Title: Optimal mixed strategy in two player zero sum games
UserDisplayName: calveeen
ThreadText: # Optimal mixed strategy in two player zero sum games
  
  (Asked by: username_0 on 2020-11-16)
  
  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 ?
  
  **Tags:** minimax, game-theory, zero-sum-games
  > **Comments:**
  > **username_1**: I don't have the book in front of me, but for question #2 you are correct - they are using game theory to model a simultaneous-action game, while minimax is for sequential action games.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_0 on 2020-11-19. Score: 1 | Accepted answer
  
  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.
  
  
  ---
  
  