Zero-Sum Games

In some strategic interactions, every gain for one player comes at an equal cost to another. This chapter studies this important special case, showing how minimax optimisation and linear programming together characterise optimal play when interests are directly opposed.

Motivating Example¶

Consider the standard Rock-Paper-Scissors game The payoff matrix for the row player is:

We are going to modify the game to reflect the fact that the row player enjoys winning and hates losing with Paper more than any other action:

The column player feels equally strongly about Paper-related outcomes.

Is there a way for the row player to choose a strategy that guarantees a certain minimum expected payoff, regardless of how the column player responds?

Theory¶

This chapter will consider a specific subset of Normal Form Games.

Definition: Zero Sum Game¶

A two player normal form game with payoff matrices $(M_r, M_c) \in {\mathbb{R}^{m\times n}}^2$ is called zero sum if and only if:

In the case of a zero sum game we will use the convention of defining it with:

and implying $M_c=-M$.

Definition: the min-max and max-min strategies¶

Given a zero-sum game defined by a payoff matrix $M \in \mathbb{R}^{m \times n}$ and a strategy $y \in \mathbb{R}^n$ for the column player, the row player seeks a best response strategy $x \in \mathbb{R}^m$ that maximises their expected payoff:

This corresponds to choosing the rows of $M$ that yields the highest expected value under the strategy $y$, i.e.,

The column player, by selecting $y$, can influence the upper bound $v$ of this maximum. Since the game is zero-sum, the column player will aim to choose $y$ to make this upper bound $v$ as small as possible.

Hence,

The min-max strategy $y$ for the column player is the solution to the following optimisation problem (referred to as a linear program):

In this formulation, $v$ is the min-max value of the game.

The corresponding max-min strategy $x$ for the row player solves the following linear program:

In this case, $u$ is the max-min value of the game.

Example: Max-min strategy for modified Rock-Paper-Scissors¶

For (2), the max-min strategy $x$ for the row player satisfies the following linear program:

Example: Max-min strategy for Matching Pennies¶

For the matching pennies game with payoff matrix:

the max-min strategy $x$ for the row player satisfies the following linear program:

Given that $x_1 + x_2 = 1$, this linear program corresponds to:

These constraints can be rewritten as:

This implies:

which leads to:

This inequality holds only when $u = 0$. When $u = 0$, the constraints reduce to:

yielding the unique solution $x_1 = \frac{1}{2}$.

Thus, the max-min strategy is:

Theorem: The minimax theorem¶

The minimax theorem Neumann, 1928 states that if there exists optimal values of the:

1. max-min value $u$ and the max-min strategy $x$.

2. min-max value $v$ and the min-max strategy $y$.

then $u=v$.

The proof which uses the linear program duality theorem is omitted from this book but can be found in Vanderbei, 2010.

Note that this answers the question posed at the end of Motivating Example through a choice of strategy the row player can ensure they obtain the value of the game which is equal to the max-min value and the min-max value.

In the next section we will start to introduce practical tools with which to do that.

Definition: Standard Form Linear program¶

A standard form of the linear program can be written which more readily will allow us to use Integer Pivoting.

In a zero-sum game, given a row player payoff matrix $M$ with $m$ rows and $n$ columns, the following linear program yields the max-min strategy and the value of the game:

subject to:

The coefficients in this linear program are defined as:

Example: Standard form for the Modified Rock Paper Scissors Game¶

For the modified Rock-Paper-Scissors game, the corresponding coefficients are:

Definition: Tableau for Zero-Sum Game¶

Given a zero-sum game with payoff matrix $M\in \mathbb{R}{m\times n}$ the standard form linear program: can be represented by the following initial tableau:

Here, slack variables have been introduced to convert inequalities into equalities. The tableau is arranged with columns for the decision variables $x_1, \dots, x_m$, the game value variable $v$, slack variables $s_1, \dots, s_n$, and the right-hand side.

We proceed by performing integer pivoting to move from one basic feasible solution to another, reducing the objective function at each step until optimality is reached.

Example: Integer Pivoting for Modified Rock-Paper-Scissors¶

We now solve the modified Rock-Paper-Scissors game using tableaux. Recall that the standard form coefficients are:

To construct the tableau, we introduce slack variables $s_1, s_2, s_3$ for the inequality constraints, and denote the game value variable by $v = x_5$.

Initial Tableau¶

The initial tableau is:

The last row is the objective function: minimising $v$. We begin by identifying the entering variable with the most negative coefficient in the objective row, which is $v$.

Pivot 1: Entering variable $v$¶

To pivot on $v$, we look at the positive entries in the $v$ column (rows 1–3). All are 1, so we apply the ratio test:

• Row 1: $0 / 1 = 0$

• Row 2: $0 / 1 = 0$

• Row 3: $0 / 1 = 0$

Ties are broken arbitrarily. Suppose we choose row 1: we subtract appropriate multiples of this row from all others to eliminate $v$ from those rows:

• Row 2 $\gets$ Row 2 - Row 1

• Row 3 $\gets$ Row 3 - Row 1

• Objective row = Objective + Row 1

After row operations:

Pivot 2: Entering variable $x_2$¶

Next, inspect the objective row. The most negative coefficient is -2 for $x_2$.

Apply ratio test on rows with positive $x_2$ entries:

• Row 2: $0 / 2 = 0$

• Row 3: $0 / 4 = 0$

• Row 4: $1 / 1 = 1$

Choose Row 2 (arbitrary tie-break).

Pivot on entry in row 2, column $x_2$ and eliminate $x_2$ from other rows. After computations, we get:

Pivot 3: Entering variable $x_3$¶

Continue inspecting the objective row. The most negative is now -2 for $x_3$, so it enters. Apply ratio test among positive entries in column $x_3$.

• Row 3: $0 / 6 = 0$

There is a single candidate: pivot on row 3. Eliminate $x_3$ from other rows. After computations we get:

We now set the non-basic variables to 0 and read the equations for the non-basic variables:

This gives:

Thus, the max-min strategy is:

Exercises¶

Programming¶

Solve linear programs using Scipy¶

The scipy library provides functionality to solve a linear program in standard form.

We begin by creating the various matrices and vectors: $M_{ub}$, $M_{eq}$, $b_{ub}$, $b_{eq}$, and $c$:

import numpy as np

M = np.array(
    [
        [0, -1, 1],
        [2, 0, -2],
        [-1, 1, 0],
    ]
)
M_ub = np.hstack((-M.T, [[1], [1], [1]]))
M_eq = np.array(([[1, 1, 1, 0]]))
b_ub = np.array(
    [
        [0],
        [0],
        [0],
    ]
)
b_eq = 1
c = np.array([0, 0, 0, -1])

Now we can pass these to scipy.optimize.linprog:

import scipy.optimize

res = scipy.optimize.linprog(
    c=c,
    A_ub=M_ub,
    b_ub=b_ub,
    A_eq=M_eq,
    b_eq=b_eq,
)
print(res)

        message: Optimization terminated successfully. (HiGHS Status 7: Optimal)
        success: True
         status: 0
            fun: 0.0
              x: [ 4.000e-01  2.000e-01  4.000e-01 -0.000e+00]
            nit: 0
          lower:  residual: [ 4.000e-01  2.000e-01  4.000e-01 -0.000e+00]
                 marginals: [ 0.000e+00  0.000e+00  0.000e+00  0.000e+00]
          upper:  residual: [       inf        inf        inf        inf]
                 marginals: [ 0.000e+00  0.000e+00  0.000e+00  0.000e+00]
          eqlin:  residual: [ 0.000e+00]
                 marginals: [-0.000e+00]
        ineqlin:  residual: [ 0.000e+00  0.000e+00  0.000e+00]
                 marginals: [-3.333e-01 -3.333e-01 -3.333e-01]
 mip_node_count: 0
 mip_dual_bound: 0.0
        mip_gap: 0.0

This returns the full output of the optimisation. The min-max strategy is contained in all but the last entry of res.x:

print(f"Min-max strategy: {res.x[:-1]}")

Min-max strategy: [0.4 0.2 0.4]

The last entry of res.x gives the value of the game:

print(f"Value of the game: {res.x[-1]}")

Value of the game: -0.0

Obtain min-max and max-min strategies using Nashpy¶

nashpy can be used to directly obtain the min-max and max-min strategies:

import nashpy as nash

game = nash.Game(M, -M)
print(game.linear_program())

(array([0.4, 0.2, 0.4]), array([0.33333333, 0.33333333, 0.33333333]))

Obtain min-max and max-min strategies using Gambit¶

Gambit can be used to directly obtain the min-max and max-min strategies. We start by creating a pygambit game from arrays:

import pygambit as gbt

game = gbt.Game.from_arrays(M, -M)
print(game)

Game(title='Untitled strategic game')

Now we can solve the underlying linear program:

print(gbt.nash.lp_solve(game))

NashComputationResult(method='lp', rational=True, use_strategic=False, equilibria=[[[Rational(2, 5), Rational(1, 5), Rational(2, 5)], [Rational(1, 3), Rational(1, 3), Rational(1, 3)]]], parameters={})

Notable Research¶

The foundations of zero-sum game theory and its connection to linear programming emerged from a convergence of ideas in mathematics, economics, and operations research during the mid-20th century.

The minimax theorem was first proven by John von Neumann in 1928 Neumann, 1928. This landmark result, stating that every finite, two-player zero-sum game has a value and optimal strategies, was later generalised in 1944 Neumann & Morgenstern, 1944.

The minimax theorem does not necessarily only apply to zero-sum games but in fact applies to any constant sum game where $M_r + M_c = K$ for some constant $K$. An example of this is shown in Chiappori et al., 2002 where penalty kicks are modelled and the payoff matrices correspond to the probability of scoring (or for the column player saving) a penalty.

Until the work of Nash Jr, 1950 the minimax theorem was the main solution concept in game theory. For his foundational work on equilibrium in non-cooperative games, John Nash was awarded the Nobel Prize in Economic Sciences in 1994, shared with John Harsanyi and Reinhard Selten. His contributions form the cornerstone of non-cooperative game theory.

Conclusion¶

This chapter introduced zero-sum games, where one player’s gain is precisely balanced by the other’s loss. We explored the foundational minimax theorem, the max-min and min-max strategies, and showed how linear programming provides a practical and elegant way to compute optimal strategies.

The central insight of this chapter is the equivalence between solving a zero-sum game and solving a pair of dual linear programs. This connection allows us to apply tools from optimisation, such as tableau methods and integer pivoting, to find equilibrium strategies.

Table 1 summarises the two central linear programs seen in this chapter.

Solutions¶