Zero Sum Game

def. Zero Sum Game. When each box in the payoff (cost) matrix sums to zero.

thm. Min-Max Theorem. The stackleberg solution in a zero-sum game for player one going first, is same for player two going first. Thus this is a mixed nash equilibirum. You can compute this using Linear Programming. Example. In the following game: Row player will aim to:

$$\stackrel{\text{ Given column’s expected strategy, the best response }}{\overbrace{{\text{max}}_{x_1,x_2}\underset{\text{column’s expected strategy }}{\underbrace{\text{min}(\underset{\text{ column goes left}}{\underbrace{3x_1-2x_2}},\underset{\text{ column goes right }}{\underbrace{-x_1+x_2}})}}}}$$

This is also known as the Stackleberg solution. Letting $z=\text{min}(3x_1-2x_2,-x_1+x_2)$ we have the following linear program:

$$\begin{array}{rl}z& \le 3x_1-2x_2\\ z& \le -x_1+x_2\\ 1& =x_1+x_2\\ 0& \le x_1,x_2\end{array}$$

Equivalently, column player will aim to ${\text{min}}_{y_1,y_2}\text{max}(3y_1-y_2,-2y_1+y_2)$. Letting $w=\text{max}(3y_1-y_2,-2y_1+y_2)$ We have the following linear program:

$$\begin{array}{rl}w& \ge 3y_1-y_2\\ w& \ge -2y_1+y_2\\ 1& =y_1+y_2\\ 0& \le y_1,y_2\end{array}$$

In a Zero Sum Game like this game, the above two linear programs are dual problems to each other. The solution to both of these programs are:

$$\{\begin{array}{l}{x}_1=\frac{3}{7},x_2=\frac{4}{7}\\ y_1=\frac{2}{7},y_2=\frac{5}{7}\end{array}$$