Chapter 2: Zero Sum Games

Assuming that we have only two players, the idea on which zero sum games are based on is that in every outcome of the game what one gets is the opposite of what the other one does. More formally, we can define a zero sum game in the following way:

A two player zero sum game in strategic form is the triplet $(X, Y , f : X × Y \rightarrow \mathbb{R})$, where $X$ and $Y$ Represent the strategy space of the two players, while $f(x,y)$ is what player 1 gets when he plays $x$ and player 2 plays $y$. Note that since we said before that what one player gets is the opposite of what the other one does, the utility function of the second player can be defined as $-f$.

Given a $n\hspace{0.2em}\times\hspace{0.2em}m$ matrix $P = (p_{ij})$, player 1 chooses a row $i$ and player 2 chooses a column $j$. The entry $p_{ij}$ represents the amount that player 2 must pay to player 1. To find a rational outcome, we must calculate the value of the game for both players.

Conservative values, value of the game

We call $v_1$ and $v_2$ respectively the conservative value of player 1 and 2:

$$v_1 = max_j \hspace{0.2em} min_i \hspace{0.2em} p_{ij} = sup_x \hspace{0.2em} inf_y \hspace{0.2em} f(x,y); \\ v_2 = min_j \hspace{0.2em} max_i \hspace{0.2em} p_{ij} = inf_y \hspace{0.2em} sup_x \hspace{0.2em} f(x,y);$$

This is because when player 1 is choosing which row to play, first he finds the smallest payoff for each of them, and then he chooses the row which has the higher value among those to minimize losses. Following the same reasoning but in reverse, player 2 first finds the higher payloff for each column, and then he chooses the smallest one among them. Note also that the following proposition is always true:

$$\sup _{x} \inf _{y} f(x, y) \leq \inf _{y} \sup _{x} f(x, y)$$

And as a consequence, in every game $v_1 \le v_2$.

If $v_1=v_2$, then $\exist \hspace{0.1em} v$ such that $v=v_1=v_2$, which is the value of the game. What is $v_1 \ne v_2$? Take for example the game 'rock, paper, scissors':

$$\left(\begin{array}{ccc} 0 & 1 & -1 \\ -1 & 0 & 1 \\ 1 & -1 & 0 \end{array}\right) \\ \begin{cases} v_1 = -1 \\ v_2 = 1 \\ v_1 \ne v_2 \end{cases}$$

From that we can deduce that no matters the play, players always risk to lose. In reality, it is not wise to play this kind of game in a totally random fashion. If you make the opponent know that you do not like playing stone (this means that you play stone with probability zero) she will react by playing only scissors, guaranteeing himself at least the draw. Thus in general the players facing these games should choose rows and columns with probabilities suggested by some optimum rule, rather than using always the same strategy.

Optimal strategies

Suppose the following:

$$\begin{cases} v_1=v_2=v \\ \exist \hspace{0.1em} \bar{i} \hspace{0.3em} s.t. \hspace{0.3em} p_{\bar{i}j} \ge v \hspace{0.3em} \forall j \\ \exist \hspace{0.1em} (\bar{j}) \hspace{0.3em} s.t. \hspace{0.3em} p_{i\bar{j}} \le v \hspace{0.3em} \forall i \\ \end{cases}$$

Where $\bar{i}$ is a row and $(\bar{j})$ a column, then:

• $\bar{i}$ is an optimal strategy for player 1, because he cannot get more than $v$, since $v=v_{2}$ is the conservative value of the second player;

• $\bar{j}$ is an optimal strategy for player 2, because he cannot pay less than $v$, since $v=v_{1}$ is the conservative value of the first player.

How to find the optimal strategies and value of the game in mixed strategies

First of all we find the conservative values of the players and check if they coincide. If so, that value is both the value of the game and the optimal strategies of the players.

Otherwise, we need to assume that one of the players is mixing, and then we can use the graphical method to find the optimal strategies. If for example we assume player one to mix, we can calculate the expected payoff w.r.t. choices of player 2 (for each column, we multiply payoffs by player 1 probabilities) and find the intersection point/segment between expected payoff graphs by applying the maxmin method graphically (if we assume player 2 to mix we'll apply the minmax method). This point is the value (or interval) that $p$, which is the probability that player 1 plays a specific row, must have to make that strategy optimal for him. The value of the game is the intersection point after applying the minmax method.

Once we have found $p$, we can find $q$ by applying the indifference principle on the column player 2 is mixing (which we found by applying maxmin to the graph). Once we have both, we have the optimal strategies of the players.

Von Neumann minmax theorem

A two player, finite, zero sum game as described by a payoff matrix $P$ has equilibrium in mixed strategies.

Note also that:

• The set of optimal strategies for the players is a nonempty closed convex set

• The outcome, at each pair of optimal strategies, is the common conservative value v of the players

• In a zero sum finite game with mixed strategies, if we find a pair of values $(\bar{x}, \bar{y})$ such that:

  $$f(x, \bar{y}) \leq f(\bar{x}, \bar{y}) \leq f(\bar{x}, y) \quad \forall x \in X, \forall y \in Y ;$$

  Then $(\bar{x}, \bar{y})$ is a NE and the game has value $v$, $(\bar{x})$ is optimal for player 1 and $(\bar{y})$ is for player 2. This observation generalizes the Von Neumann theorem:

  Any $(\bar{x}, \bar{y})$ Nash equilibrium of the zero sum game provides optimal strategies for the players and any pair of optimal strategies for the players provides a Nash equilibrium for the zero sum game.

• Some more observations on NE, in particular w.r.t. strategic form games:

  • Players can find their optimal behavior independently for the other players

  • Any pair of optimal strategies provides a Nash equilibrium; this implies no need of coordination to reach an equilibrium

  • Every Nash equilibrium provides the same utility (payoff) to the players: multiplicity of solutions does not create problems

Symmetric (or fair) games

A square matrix $n \times n P=\left(p_{i j}\right)$ is said to be antisymmetric provided $p_{i j}=-p_{j i}$ for all $i, j=1, \ldots, n$. A (finite) zero sum game is said to be fair if the associated matrix is antisymmetric.

In simpler words, in fair games there is no favorite player.

Outcome in fair games

If $P = (p_{ij})$ is antysimmetric, the value is 0 and $\bar{x}$ is an optimal strategy for player 1 if and only if it is optimal also for player 2.

How to solve fair games

to find the N.E. of a fair game a system of equations of the following type is needed:

$$\begin{cases} x_{1}p_{11}1+···+x_{n}p_{n1} ≥0 \\ \dots \\ x_{1}p_{ij}1+···+x_{n}p_{nj} ≥0 \\ \dots \\ x_{1}p_{1m}1+···+x_{n}p_{nn} ≥0 \end{cases}$$