Problem : Consider a constant-sum game with payoff matrix $$\left( \begin{array}{ccc} 0 & 2 & -1 \\ 1 & -2 & 0 \\ -2 & 0 & 2 \end{array} \right)$$.
- Find $v^-$ and $v^+$ for this game.
$v^- = -1$, $v^+ = 1$
- Does this game have an equilibrium in pure strategies?
No, because $v^- \ne v^+$.
- Compute the value of $E(X,Y)$ for $X=(0 {1 \over 2} {1 \over 2})$ and $Y=({2 \over 3} 0 {1 \over 3})$.
$E(X, Y) = \frac{1}{2} \cdot \frac{2}{3} \cdot 1 + \frac{1}{2} \cdot \frac{1}{3} \cdot 0 + \frac{1}{2} \cdot \frac{2}{3} \cdot -2 + \frac{1}{2} \cdot \frac{1}{3} \cdot 2 = 0$
- Using Theorem 1.3.8c, verify that $X^*=({2 \over 5} {2 \over 5} {1 \over 5})$,$Y^*=({2 \over 5} {1 \over 5} {2 \over 5})$
is a saddle point for this game.
$E(X^*, Y^*) = 0$. \begin{array}{rcccccl} E(X^*, 1) & = & \frac{2}{5} \cdot 0 + \frac{2}{5} \cdot 1 + \frac{1}{5} \cdot -2 & = & 0 & \ge & 0 \\ E(X^*, 2) & = & \frac{2}{5} \cdot 2 + \frac{2}{5} \cdot -2 + \frac{1}{5} \cdot 0 & = & 0 & \ge & 0 \\ E(X^*, 3) & = & \frac{2}{5} \cdot -1 + \frac{2}{5} \cdot 0 + \frac{1}{5} \cdot 2 & = & 0 & \ge & 0 \\ E(1, Y^*) & = & \frac{2}{5} \cdot 0 + \frac{1}{5} \cdot 2 + \frac{2}{5} \cdot -1 & = & 0 & \le & 0 \\ E(2, Y^*) & = & \frac{2}{5} \cdot 1 + \frac{1}{5} \cdot -2 + \frac{2}{5} \cdot 0 & = & 0 & \le & 0 \\ E(3, Y^*) & = & \frac{2}{5} \cdot -2 + \frac{1}{5} \cdot 0 + \frac{2}{5} \cdot 2 & = & 0 & \le & 0 \\ \end{array} All inequalities are true, so $X^*, Y^*$ is indeed a saddle point.
- Find player I's best response to $Y=({1 \over 3} {1 \over 3} {1 \over 3})$.
\begin{array}{rcccl} E(1, Y) & = & \frac{1}{3} \cdot 0 + \frac{1}{3} \cdot 2 + \frac{1}{3} \cdot -1 & = & \frac{1}{3} \\ E(2, Y) & = & \frac{1}{3} \cdot 1 + \frac{1}{3} \cdot -2 + \frac{1}{3} \cdot 0 & = & -\frac{1}{3} \\ E(3, Y) & = & \frac{1}{3} \cdot -2 + \frac{1}{3} \cdot 0 + \frac{1}{3} \cdot 2 & = & 0 \\ \end{array} The maximum value is $E(1, Y)$, so the best response is $(1\ 0\ 0)$.
Problem : Find a saddle point and its value for the constant-sum game with payoff matrix $$ \left( \begin{array}{cc} 3 & 2 \\ 0 & 4 \\ \end{array} \right) $$
For $Y$ the inequalities are \begin{array}{rcccl} E(1, Y) &=& y + 2 &\le& v \\ E(2, Y) &=& 4 - 4y &\le& v \\ \end{array} The minimum value of $v$ above both lines is at their intersection, which is where $y + 2 = 4 - 4y$, or $y = \frac{2}{5}$, so $Y^* = (\frac{2}{5} \frac{3}{5})$.
$E(X^*, Y^*) = \frac{12}{5}$.
Problem : Set up the linear program to find a saddle point for the constant-sum game with payoff matrix $$ \left( \begin{array}{ccc} 4 & 7 & 3 \\ 0 & 5 & 4 \\ 10 & 6 & 2 \\ \end{array} \right) $$
There are many possible solutions depending on what transformations you choose to apply. The following is the result of adding 1 to the payoff matrix to make all entries positive and then transforming to eliminate $v$.
Minimize $p_1 + p_2 + p_3$ subject to \begin{array}{rcl} -5p_1 - p_2 - 11p_3 & \le & -1 \\ -8p_1 - 6p_2 - 7p_3 & \le & -1 \\ -4p_1 - 5p_2 - 3p_3 & \le & -1 \\ p_1, p_2, p_3 & \ge & 0 \\ p_1, p_2, p_3 & \le & 1 \\ \end{array}
Minimize $-q_1 - q_2 - q_3$ subject to \begin{array}{rcl} 5q_1 + 8q_2 + 4q_3 & \le & 1 \\ q_1 + 6q_2 + 5q_3 & \le & 1 \\ 11q_1 + 7q_2 + 3q_3 & \le & 1 \\ q_1, q_2, q_3 & \ge & 0 \\ q_1, q_2, q_3 & \le & 1 \\ \end{array}