Zero-sum games
¶

Alfred Galichon (NYU & Sciences Po) and Antoine Jacquet (Sciences Po)
¶

'math+econ+code' masterclass series
¶

With python code examples
¶

© 2018–2025 by Alfred Galichon. Past and present support from NSF grant DMS-1716489, ERC grant CoG-866274 are acknowledged, as well as inputs from contributors listed here.

If you reuse material from this masterclass, please cite as:
Alfred Galichon, 'math+econ+code' masterclass series. https://www.math-econ-code.org/

Learning objectives¶

  • Zero-sum games
  • Computing equilibria using linear programming

References¶

  • Palacios–Huerta (2003). "Professionals play minimax." The Review of Economic Studies.
In [1]:
#!pip install mec --upgrade

import numpy as np
import gurobipy as grb

The penalty game¶

We use the example of penalty kicks from Palacios–Huerta (2003). Player 1 (kicker) takes action $i \in \{L,C, R \}$, and so does Player 2 (goalkeeper). The following matrix indicates the probability $A_{ij}$ of scoring a goal if Player 1 plays $i$ and Player 2 plays $j$ (it is constructed from Table 2 in the paper).

In [2]:
A_i_j = np.array([[53.21, 71.35, 93.80], 
                  [90.26, 42.81, 86.12], 
                  [96.88, 100.0, 75.43]])

A_i_j
Out[2]:
array([[ 53.21,  71.35,  93.8 ],
       [ 90.26,  42.81,  86.12],
       [ 96.88, 100.  ,  75.43]])

The next table indicates the observed probability $\pi_{ij}$ that player 1 takes action $i$ and that player 2 takes action $j$.

In [3]:
π_i_j = np.array([[.160,.004,.229],
                  [.034,.004,.037],
                  [.207,.008,.313]])

π_i_j
Out[3]:
array([[0.16 , 0.004, 0.229],
       [0.034, 0.004, 0.037],
       [0.207, 0.008, 0.313]])

Consider the penalty game as a zero-sum game: if player $1$ plays $i \in I$ and player 2 plays $j \in J$, then:

  • the payoff to player 1 is $A_{ij}$,
  • the payoff to player 2 is $-A_{ij}$.

Hence zero-sum games can be represented using a single matrix $A$: for this reason they are also known as matrix games. we define a Python class for these objects.

In [4]:
class Matrix_game:
    def __init__(self, A_i_j):
        self.nbi,self.nbj = A_i_j.shape
        self.A_i_j = A_i_j

penalty_game = Matrix_game(A_i_j)

Equilibrium in pure strategies¶

If player 1 plays $i$, then player 2's best response is $J(i) = \arg\min_j A_{ij}$.

If player 2 plays $j$, then player 1's best response is $I(j) = \arg\max_i A_{ij}$.

An equilibrium in pure strategies is a pair $(i^*,j^*)$ such that $i^* \in I(j^*)$ and $j^* \in J(i^*)$.

In [5]:
def Matrix_game_BRI(self,j):
    return np.argwhere(self.A_i_j[:,j] == np.max(self.A_i_j[:,j])).flatten()

def Matrix_game_BRJ(self,i):
    return np.argwhere(self.A_i_j[i,:] == np.min(self.A_i_j[i,:])).flatten()

Matrix_game.BRI = Matrix_game_BRI
Matrix_game.BRJ = Matrix_game_BRJ
In [6]:
penalty_game.BRI(1), penalty_game.BRJ(0)
Out[6]:
(array([2], dtype=int64), array([0], dtype=int64))

Look for equilibria in pure strategies using:

In [7]:
def Matrix_game_purestrat_solve(self):
    return [ (i,j) for j in range(self.nbj) for i in range(self.nbi)
            if ( (i in self.BRI(j)) and (j in self.BRJ(i)) ) ]

Matrix_game.purestrat_solve = Matrix_game_purestrat_solve

penalty_game.purestrat_solve()
Out[7]:
[]

We see that in this game, there is no equilibrium in pure strategies. In fact, it is possible to show that a game has an equilibrium in pure strategies if there is no advantage in playing first in the sequential version of the game, i.e. the value of the game is the same regardless of whether player 1 plays first or second. Clearly, this is not the case here: if the kicker plays first, then the goalkeeper can move to where the kicker kicked in order to decrease the probability of a goal. If the goalkeeper plays first, then the kicker can kick where the goalkeeper did not move.

Equilibrium in mixed strategies¶

Assume player 1 plays mixed strategy $p = (p_i) \in \Delta_I$, and player 2 plays mixed strategy $q = (q_j) \in \Delta_J$. Then:

  • the expected payoff to player 1 is $\sum_{ij} p_i q_ j A_{ij} = p^\top A q$.

  • the expected payoff to player 2 is minus the former.

If player 1 plays $p$, then player 2's best response is $Q(p) = \arg\min_{q \in \Delta_J} p^\top A q$.

If player 2 plays $q$, then player 1's best response is $P(q) = \arg\max_{p \in \Delta_I} p^\top A q$.

An equilibrium in mixed strategies is a pair $(p^*, q^*)$ such that $p^* \in P(q^*)$ and $q^* \in Q(p^*)$.

Equilibrium as a linear programming problem¶

Hence, at equilibrium, $p$ and $q$ are played in order to \begin{equation} \max_{p \in \Delta_I} \, \min_{q \in \Delta_J} ~ p^\top A q. \end{equation}

In general, we have \begin{equation} \max_{p \in \Delta_I} \, \min_{q \in \Delta_J} ~ p^\top A q \leq \min_{q \in \Delta_J} \, \max_{p \in \Delta_I} ~ p^\top A q \end{equation}

but here we have in fact equality. Indeed, we show below that both programs are in fact dual linear programs.

Player 1's problem¶

From the point of view of player 1, the problem is \begin{equation*} \max_{p \in \Delta_I} \, \min_{q \in \Delta_J} ~ p^\top A q. \end{equation*}

First, the problem of player 2 anticipating that player 1 will play $p$ is \begin{align} \min_{q \in \Delta_J} p^\top A q &= \min_{q \in \Delta_J} \sum_j q_j \left( \sum_i A_{ij} p_i \right) \\ &= \min_{j \in J} \sum_i A_{ij} p_i. \end{align}

Then, player 1 wants to \begin{equation} \max_{p \in \Delta_I, U} \left\{ U : U = \min_{j \in J} \sum_i A_{ij} p_i \right\} \end{equation} but this is equivalent with \begin{equation} \max_{p \in \Delta_I, U} \left\{ U : U \leq \min_{j \in J} \sum_i A_{ij} p_i \right\}. \end{equation}

Thus the program of player 1 is \begin{equation} \max_{p \in \Delta_I, U} \left\{ U : U \leq \sum_i A_{ij} p_i \text{ for all $j$} \right\}, \end{equation}

that is \begin{align} V_1 = \max_{ p_i \geq 0, U} ~ & U \\ \text{s.t.} ~ & U \leq \textstyle\sum_i A_{ij} p_i \quad (\forall j) \\ & \textstyle\sum_i p_i = 1. \end{align}

Introduce $x_i = p_i/U$. We can reformulate the previous problem as

\begin{align} V_1 = \max_{x_i \geq 0, U} ~ & U \\ \text{s.t.} ~ & U \leq \textstyle\sum_i A_{ij} x_i U \quad (\forall j) \\ &\textstyle\sum_i x_i U = 1 \end{align}

which, using $U = \frac{1}{\sum_i x_i}$, simplifies into \begin{align} V_1 = \max_{x_i \geq 0} ~ & \frac{1}{\sum_i x_i} \\ \text{s.t.} ~ & 1 \leq \textstyle\sum_i A_{ij} x_i \quad (\forall j) \end{align} and finally into the linear programming problem: \begin{align} \frac{1}{V_1} = \min_{x_i \geq 0} ~ &\sum_i x_i \\ \text{s.t.} ~ & \textstyle\sum_i A_{ij} x_i \geq 1 \quad (\forall j) \quad [y_j \geq 0]. \end{align}

Recall that $x_i = p_i/U$ and $U = \frac{1}{\sum_i x_i}$. Therefore \begin{equation} p_i = x_i U = \frac{x_i}{\sum_i x_i}. \end{equation}

Player 2's problem¶

From the point of view of player 2, the problem is \begin{equation} \min_{q \in \Delta_J} \, \max_{p \in \Delta_I} ~ p^\top A q. \end{equation}

If player 1 anticipates that player 2 will play $q$, then she does \begin{equation} \max_{p \in \Delta_I} ~ p^\top A q = \max_{i \in I} \sum_j A_{ij} q_j. \end{equation}

Then, player 2 wants to \begin{equation} \min_{q \in \Delta_J, V} \left\{ V : V \geq \max_{i \in I} \sum_j A_{ij} q_j \right\} \end{equation} which is also \begin{equation} \min_{q \in \Delta_J, V} \left\{ V : V \geq \sum_j A_{ij} q_j \text{ for all $i$} \right\} \end{equation} that is \begin{align} V_2 = \min_{q_j \geq 0, V} ~ & V \\ \text{s.t.} ~ & V \geq \textstyle\sum_j A_{ij} q_j \quad (\forall i) \\ & \textstyle\sum_j q_j = 1. \end{align}

Introducing $y_j = q_j/V$, we can again reformulate this problem as

\begin{align} \frac{1}{V_2} = \max_{y_j \geq 0} ~ & \sum_j y_j \\ \text{s.t.} ~ & \textstyle\sum_j A_{ij} y_j \leq 1 \quad (\forall i) \quad [x_i \geq 0] \end{align}

and we have \begin{equation} q_j = y_j V = \frac{y_j}{\sum_j y_j}. \end{equation}

Computation using Gurobi¶

We use player 2's point of view to solve for the equilibrium.

In [8]:
def Matrix_game_solve(self, verbose=0):
    model = grb.Model()
    model.Params.OutputFlag = 0
    y = model.addMVar(shape=self.nbj)
    model.setObjective(np.ones(self.nbj) @ y, grb.GRB.MAXIMIZE)
    model.addConstr(self.A_i_j @ y <= np.ones(self.nbi))
    model.optimize() 
    ystar = np.array(model.getAttr('x'))
    xstar = np.array(model.getAttr('pi'))
    V_2 = 1 / model.getAttr('ObjVal')
    p_i = V_2 * xstar
    q_j = V_2 * ystar
    if verbose > 0: print('p_i =', p_i, '\nq_j =', q_j)
    return {'p_i': p_i, 'q_j': q_j, 'val': V_2}

Matrix_game.solve = Matrix_game_solve
In [9]:
sol = penalty_game.solve(verbose=1)

Restricted license - for non-production use only - expires 2025-11-24
p_i = [0.3033884  0.15180727 0.54480433] 
q_j = [0.21908541 0.10161508 0.67929951]
In [10]:
p_i, q_j = sol['p_i'], sol['q_j']
p_i.reshape(-1,1) @ q_j.reshape(1,-1)
Out[10]:
array([[0.06646797, 0.03082884, 0.20609159],
       [0.03325876, 0.01542591, 0.1031226 ],
       [0.11935868, 0.05536033, 0.37008532]])

Compare this with the observed probabilties of playing $i$ and $j$:

In [11]:
π_i_j
Out[11]:
array([[0.16 , 0.004, 0.229],
       [0.034, 0.004, 0.037],
       [0.207, 0.008, 0.313]])

Higher consistency is obtained in the original paper by merging the actions $C$ and $R$.

Computation using the simplex algorithm¶

We use the simplex algorithm that we implemented in the lectures on linear programming, still from player 2's point of view.

Dictionary¶

In [12]:
import mec.lp
from mec.lp import Dictionary
from sympy import *

def Matrix_game_simplex_solve(self, verbose=0):
    dictionary = Dictionary(A_i_j = self.A_i_j, b_i = np.ones(self.nbi), c_j = np.ones(self.nbj),
                            decision_var_names_j = ['y_'+str(j) for j in range(self.nbj)])
    ystar, _, ystar_sum = dictionary.simplex_solve() # this returns the decision and slack variables
    q_j = ystar / ystar_sum
    expr_obj = dictionary.base[Symbol('obj')] # dual variables are coefficients in the objective
    xstar = -np.array([float(expr_obj.coeff(var)) for var in dictionary.nonbasic])
    p_i = xstar / ystar_sum
    if verbose > 0: print('p_i =', p_i, '\nq_j =', q_j)
    return {'p_i': p_i, 'q_j': q_j, 'val': 1/ystar_sum}

Matrix_game.simplex_solve = Matrix_game_simplex_solve
In [13]:
penalty_game.simplex_solve()

Optimal solution found.
=======================
Out[13]:
{'p_i': array([0.3033884 , 0.15180727, 0.54480433]),
 'q_j': array([0.21908541, 0.10161508, 0.67929951]),
 'val': 82.62606457928055}

Tableau¶

In [14]:
from mec.lp import Tableau

def Matrix_game_simplex_solve(self, verbose=0):
    tableau = Tableau(A_i_j = self.A_i_j, b_i = np.ones(self.nbi), c_j = np.ones(self.nbj),
                      decision_var_names_j = ['y_'+str(j) for j in range(self.nbj)])
    ystar, xstar, ystar_sum = tableau.simplex_solve()
    p_i = xstar / ystar_sum
    q_j = ystar / ystar_sum
    if verbose > 0: print('p_i =', p_i, '\nq_j =', q_j)
    return {'p_i': p_i, 'q_j': q_j, 'val': 1/ystar_sum}

Matrix_game.simplex_solve = Matrix_game_simplex_solve
In [15]:
penalty_game.simplex_solve()
Out[15]:
{'p_i': array([0.3033884 , 0.15180727, 0.54480433]),
 'q_j': array([0.21908541, 0.10161508, 0.67929951]),
 'val': 82.62606457928057}

Computation using Chambolle–Pock¶

In [16]:
def Matrix_game_chambolle_pock_solve(self, tol=10e-6, max_iter=10000):
    L1 = np.max(np.abs(self.A_i_j))
    sigma, tau = 1/L1, 1/L1

    p_i = np.ones(self.nbi) / self.nbi
    q_j = np.ones(self.nbi) / self.nbj
    q_prev = q_j.copy()

    gap = np.inf
    i=0
    while (gap >  tol) and (i < max_iter):
        q_tilde = 2*q_j - q_prev
        p_i *= np.exp(-sigma * self.A_i_j @ q_tilde)
        p_i /= p_i.sum()

        q_prev = q_j.copy()
        q_j *= np.exp(tau * self.A_i_j.T @ p_i)
        q_j /= q_j.sum()
        gap = np.max(self.A_i_j.T @ p_i) - np.min(self.A_i_j @ q_j)
        i += 1
    return p_i, q_j, gap, i

Matrix_game.chambolle_pock_solve = Matrix_game_chambolle_pock_solve
In [17]:
p_i, q_j ,_ ,_ = penalty_game.chambolle_pock_solve()
p_i, q_j
Out[17]:
(array([0.3033884 , 0.15180727, 0.54480433]),
 array([0.21908606, 0.10161432, 0.67929961]))

Exercises¶

Exchangeability of solutions. Show that if $(p,q)$ and $(p',q')$ are two Nash equilibria of a zero-sum game, then $(p',q)$ is also a Nash equilibrium.