Zero-Sum Games

Announce your row and lose

Rowan and Cole play a game. Rowan picks a row, Cole picks a column, both at the same moment, and Cole pays Rowan the entry where they meet. A negative entry means Rowan pays Cole.

The game repeats every evening, and Cole is good at reading people. If Rowan has a favourite row, he will find it. Row 0 promises 3 when Cole picks column 0, but Cole won't: he answers row 0 with column 1 and takes 1 from her. Row 1 is worse: he answers with column 0 and takes 2.

So what is this game worth to Rowan, and what should each of them actually do? The answer will be exact: $2/3$ per evening, from a precise coin. By the end you'll also have a tool that has nothing to do with evenings: a way to prove that no randomized algorithm can beat a bound.

A game like this, where one player's gain is the other's loss, is a two-player zero-sum game. It is nothing more than a matrix $M$: rows are the row player's pure strategies, columns are the column player's, and $M_{ij}$ is what the column player pays the row player.

The naive approach: the best worst case over rows

The cautious plan is to pick the row whose worst entry is best. The row minima of $H$ are $-1$ and $-2$, so Rowan plays row 0 and is guaranteed $-1$: a loss of 1 per evening, but never more.

Cole can do the same from his side. The column maxima are $3,4,1$, so column 2 caps what he pays at 1.

These two numbers are the pure lower and upper values, and the lower one never exceeds the upper one:

$${max}_i{min}_j{M}_{ij}\le {min}_j{max}_i{M}_{ij}.$$

(Take Rowan's best row $i$ and Cole's best column $j$. The entry $M_{ij}$ is at least row $i$'s minimum and at most column $j$'s maximum.) For $H$ there is a gap from $-1$ to $1$, and the pure plans say nothing about where in that gap the truth lies.

Sometimes there is no gap. In

the entry 3 at row 1, column 1 is the minimum of its row and the maximum of its column. Such an entry is a saddle point. Row 1 guarantees Rowan at least 3, column 1 holds her to at most 3, and neither player gains by doing anything else. A saddle point exists exactly when the pure lower and upper values are equal, and then the game is solved without any coins.

from fractions import Fraction as F

H = [[3, -1, 1], [-2, 4, 0]]
S = [[4, 2, 5], [6, 3, 7], [1, 0, 8]]

def pure_values(M):
    lower = max(min(row) for row in M)
    upper = min(max(row[j] for row in M) for j in range(len(M[0])))
    return lower, upper

assert pure_values(H) == (-1, 1)          # a gap: no saddle point
assert pure_values(S) == (3, 3)           # a saddle point, value 3

Mixed strategies, and what a known plan is worth

$H$ has no saddle point, so any fixed row is exploited. The way out is a mixed strategy: a probability vector $p$ over rows, with the coin flipped fresh every evening. Cole may know $p$ (he has watched for months) but not tonight's flip. With Cole mixing by $q$, the expected payoff is

$$p^{\mathsf{T}}Mq=\sum _{i,j}{p}_i{M}_{ij}{q}_j.$$

What does $p$ guarantee? Once $p$ is fixed, the expected payoff is linear in $q$: an average of the column payoffs $(p^{\mathsf{T}}M{)}_j$, weighted by $q_j$. An average is never below its smallest term, so Cole's best answer to a known $p$ is a pure column, and

$$g(p)={min}_j(p^{\mathsf{T}}M{)}_j.$$

That one fact shrinks the problem enormously: to evaluate a plan, check it against each pure reply, never against the infinitely many mixed ones.

Now Rowan's choice has one number in it. Write $p$ for the probability of row 0. Against column $j$ she earns the line

$$f_j(p)=M_{1j}+(M_{0j}-M_{1j})p,$$

which for $H$ is $f_0=5p-2$, $f_1=4-5p$ and $f_2=p$.

The naive search tries a grid of values of $p$. On the tenths $0,0.1,\dots ,1$ the best guarantee is $3/5$, at $p=3/5$. That beats the pure $-1$ by a lot. But it is not the answer, and a finer grid won't fix that. The grid can only report points it happens to try, it can't say whether a better one lies between them, and it says nothing about what Cole should do.

def f(M, j, p):                       # Rowan's expected payoff against column j
    return M[1][j] + (M[0][j] - M[1][j]) * p

tenths = [F(k, 10) for k in range(11)]
best = max(tenths, key=lambda p: min(f(H, j, p) for j in range(3)))
assert best == F(3, 5) and min(f(H, j, best) for j in range(3)) == F(3, 5)

The lower envelope

Rowan's guarantee $g(p)={min}_j{f}_j(p)$ is the lower envelope of the lines: the lowest line at every $p$. Draw them.

Read it from left to right. At $p=0$ (always row 1) the lowest line is column 0's, at $-2$. Column 0's line rises steeply and meets column 2's at $p=1/2$, height $1/2$. From there column 2 is lowest and still rising, but slowly, until it meets column 1's falling line at $p=2/3$, height $2/3$. After that the envelope follows column 1 down to $-1$ at $p=1$.

A minimum of lines is concave and piecewise linear, so its maximum sits at an end ($p=0$ or $1$) or at a corner, and every corner is a crossing of two lines. That gives an exact method: evaluate $g$ at $0$, at $1$ and at every crossing inside $(0,1)$, and keep the best. For $H$ the candidates give $g=-2,1/2,2/3,-1$, and a third crossing, $f_0=f_1$ at $p=3/5$, gives $g(3/5)=3/5$ because column 2 is lower there. So Rowan plays row 0 with probability $p^{*}=2/3$, row 1 with probability $1/3$, and is guaranteed

$$v=\frac{2}{3}$$

per evening against anything Cole does, including anything he learns.

def g(M, p):
    return min(f(M, j, p) for j in range(len(M[0])))

assert [g(H, p) for p in (0, F(1, 2), F(3, 5), F(2, 3), 1)] == [-2, F(1, 2), F(3, 5), F(2, 3), -1]
assert max(g(H, F(k, 60)) for k in range(61)) == F(2, 3)      # sixtieths contain 2/3
assert g(H, F(1, 2)) == F(1, 2) == f(H, 0, F(1, 2)) == f(H, 2, F(1, 2))
uniform = sum(H[i][j] for i in range(2) for j in range(3)) * F(1, 6)
assert uniform == F(5, 6)                                     # uniform against uniform

Cole's answer, and the invariant

Is $2/3$ the most Rowan can get, or only the most this picture found? Cole answers that. At the peak two lines are tight: column 2's, rising with slope $+1$, and column 1's, falling with slope $-5$. If Cole plays column 1 with probability $q_1$ and column 2 with probability $q_2=1-q_1$, Rowan's payoff is the line $q_1{f}_1+q_2{f}_2$, with slope $-5q_1+q_2$. Choose the weights so that the slope is zero:

$$q_1=\frac{1}{1+5}=\frac{1}{6},q_2=\frac{5}{6}.$$

Against $q^{*}=(0,1/6,5/6)$ both of Rowan's rows pay exactly $2/3$, so no $p$ gets her more. Her $p^{*}$ guarantees $2/3$ and his $q^{*}$ holds her to $2/3$: the two certificates meet, and $2/3$ is the value of the game. Column 0 is never used. At $p^{*}=2/3$ it would pay Rowan $4/3$, more than he needs to concede.

Proof of the tightness half. Suppose $q^{*}$ holds Rowan to $v$, $p^{*}$ guarantees $v$, and Cole puts weight $q_j^{*}>0$ on a column with $(p^{*\mathsf{T}}M{)}_j>v$. Every column pays at least $v$ against $p^{*}$ and this one pays more, so the average $p^{*\mathsf{T}}M{q}^{*}>v$. But $q^{*}$ holds every row, and so every mix of rows, to at most $v$. That's a contradiction. The same argument works with the players swapped. (Module 16 meets this as complementary slackness.)

The step not to skip: the two tight lines Cole mixes must slope in opposite directions. Two rising lines mix into a rising line, and Rowan simply moves right.

p = [F(2, 3), F(1, 3)]
q = [0, F(1, 6), F(5, 6)]
against_columns = [sum(p[i] * H[i][j] for i in range(2)) for j in range(3)]
against_rows = [sum(H[i][j] * q[j] for j in range(3)) for i in range(2)]
assert against_columns == [F(4, 3), F(2, 3), F(2, 3)]    # p guarantees 2/3; column 0 is slack
assert against_rows == [F(2, 3), F(2, 3)]                # q holds both rows to exactly 2/3

These four lines are a complete proof that $v=2/3$, and anyone can check it without trusting how the strategies were found.

The minimax theorem

For any $p$ and $q$,

$${min}_j(p^{\mathsf{T}}M{)}_j\le p^{\mathsf{T}}Mq\le {max}_i(Mq{)}_i,$$

because an average lies between its smallest and largest terms. So every guarantee is at most every hold-down, and ${max}_p{min}_q{p}^{\mathsf{T}}Mq\le {min}_q{max}_p{p}^{\mathsf{T}}Mq$. That inequality is the easy direction.

The hard direction says there is never a gap once mixing is allowed. It is proved in module 16 from linear-programming duality, and this lesson only states it. For $2\times n$ games you have just seen why it holds: the envelope's peak is either an end or a crossing, and at an interior crossing that isn't flat, a rising and a falling tight line give the opponent a flat mix. (At an end, or where a tight line is flat, one tight column already holds Rowan to $v$.)

Complexity

$2\times n$ games. There are $n$ lines, so at most $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ crossings plus the two ends. Evaluating the envelope at each candidate costs $n$ comparisons, which is $O(n^3)$ exact arithmetic operations in the worst case. That is fast enough for the sizes in this lesson. It can be done in $O(n\log n)$: sort the lines by slope and sweep to build the envelope, then walk its $O(n)$ corners.

General $m\times n$ games. Rowan's problem is: maximize $v$ such that $(p^{\mathsf{T}}M{)}_j\ge v$ for every column and $p$ is a probability vector. That is a linear program with $m+1$ variables and $n$ inequality constraints (plus $p\ge 0$ and ${\sum }_i{p}_i=1$), and module 15 shows how to solve it exactly. So every finite zero-sum game can be solved exactly, and in polynomial time (module 17).

What the grid costs. A grid of $N$ points needs $Nn$ evaluations and never certifies its answer. On $H$ the tenths report $3/5$. A grid of sixtieths lands on $2/3$ only because 60 is a multiple of 3.

Yao's principle: games against algorithms

Here is the use that matters most in algorithm design. Fix a problem size. Let the rows be the possible inputs and the columns the deterministic algorithms, and let the entry be the cost of that algorithm on that input. The algorithm designer is the column player and wants low cost. The adversary picks the input. A randomized algorithm is exactly a mixed column strategy: a probability distribution over deterministic algorithms.

Proof. The worst input costs at least the average input, so the left side is at least ${\mathbb{E}}_{x~D}{\mathbb{E}}_{A~R}[\mathrm{c}\mathrm{o}\mathrm{s}\mathrm{t}(A,x)]$. Swap the two expectations to get ${\mathbb{E}}_{A~R}{\mathbb{E}}_{x~D}[\mathrm{c}\mathrm{o}\mathrm{s}\mathrm{t}(A,x)]$, an average over deterministic algorithms, which is at least the best of them. $◻$

This is the easy direction of the minimax theorem, and it gives a recipe. To prove that every randomized algorithm has expected cost at least $b$ on some input, find one input distribution on which every deterministic algorithm averages at least $b$. Averaging over a distribution is often much easier to reason about than the worst case of an algorithm you can't see. "Expected" here means over the algorithm's coins, on the worst input, as everywhere in this course.

An instance. An array of $n$ cells holds exactly one marked cell. A probe reads one cell, and the cost is the number of probes. A deterministic algorithm is an order of probing, and after $n-1$ misses the last cell must be the mark, so it needs no probe. On the uniform distribution over the mark's position, every order costs $1,2,\dots ,n-1$ for the first $n-1$ positions it probes and $n-1$ for the last, so every order averages

$$\frac{n(n+1)/2-1}{n}.$$

For $n=5$ that is $14/5$, and all 120 orders give exactly $14/5$. By Yao, every randomized algorithm needs at least $14/5$ expected probes on some input. Probing in a uniformly random order achieves $14/5$ on every input, so it is optimal. The left-to-right scan is deterministic and pays $4$ when the mark is last.

from itertools import permutations

def probes(order, mark):                    # the cost model: a stand-in for any probing code
    return min(order.index(mark) + 1, len(order) - 1)

n = 5
averages = {F(sum(probes(o, m) for m in range(n)), n) for o in permutations(range(n))}
assert averages == {F(14, 5)} and F(n * (n + 1), 2) - 1 == 14 * n // 5
assert probes(list(range(n)), n - 1) == 4   # the scan's worst case

Measure the claim

The random order's expected cost on any input is $(n+1)/2-1/n$ probes, about half of $n$. Measured on the scan's worst input (mark in the last cell), 1,000 runs each with random.Random(451):

import random

table = []
for n in (50, 100, 200, 400):
    rng, total = random.Random(451), 0
    for _ in range(1000):
        order = list(range(n))
        rng.shuffle(order)
        total += probes(order, n - 1)
    table.append((n, round(total / 1000, 1), round(total / 1000 / n, 3)))
assert table == [(50, 25.1, 0.503), (100, 50.9, 0.509), (200, 98.8, 0.494), (400, 200.2, 0.5)]
assert [float(F(n * (n + 1), 2) - 1) / n for n in (50, 100, 200, 400)] == [25.48, 50.49, 100.495, 200.4975]

The ratio is flat at $1/2$, as the bound predicts. Three of the four means are slightly below the bound. That isn't a broken theorem: these are sample means over 1,000 runs, and the theorem is about the expectation.

Beyond zero-sum

When the players' payoffs don't cancel, each has her own matrix. A Nash equilibrium is a pair of mixed strategies from which neither player gains by changing her own strategy alone. Nash proved in 1950 that every finite game has one. Much of what made zero-sum games clean is lost. Two firms choosing a shared standard, where firm 1 earns 2 on standard A and 1 on B, firm 2 the reverse, and both earn 0 on a mismatch, have three equilibria: both choose A, payoffs $(2,1)$; both choose B, payoffs $(1,2)$; and a mixed one, firm 1 choosing A with probability $2/3$ and firm 2 with probability $1/3$, where each earns only $2/3$. There's no single value, an equilibrium strategy guarantees nothing if the other side deviates, and finding an equilibrium is PPAD-complete even with two players, while zero-sum games reduce to a linear program.

A1 = [[2, 0], [0, 1]]                  # firm 1's payoffs: rows = its choice A, B
A2 = [[1, 0], [0, 2]]                  # firm 2's payoffs, same cells: columns = its choice
x, y = [F(2, 3), F(1, 3)], [F(1, 3), F(2, 3)]
row_pay = [sum(A1[i][j] * y[j] for j in range(2)) for i in range(2)]
col_pay = [sum(x[i] * A2[i][j] for i in range(2)) for j in range(2)]
assert row_pay == [F(2, 3)] * 2 and col_pay == [F(2, 3)] * 2   # both indifferent: an equilibrium

A problem that looks different

A city has one ticket inspector who can ride one of two tram lines each morning. A fare dodger chooses among three routes to work, and a table gives the fine collected for every pair of line and route. The inspector's rota is published in the union contract, so the dodger knows the probabilities; only this morning's draw is secret. How should the city set the rota, and how much can it count on collecting? The lab's last problem is a different one.

Practise

In the lab you work out what a known mix guarantees against every reply and draw it, frame by frame. Then you predict the lower envelope of a new $2\times 4$ game before tracing it piece by piece. After that you solve $2\times n$ games exactly, with both players' strategies, and check them against an exact linear-programming solver. You count probes to watch Yao's bound in your own code, and you finish with a problem that doesn't say what it is.

Recap

You can now: find a game's pure lower and upper values and its saddle points; say what a mixed strategy guarantees by checking only pure replies; solve a $2\times n$ game exactly from the lower envelope, with the opponent's strategy as a certificate; and prove lower bounds on randomized algorithms with Yao's principle.

Invariant: an optimal mix earns at least the value against every pure reply, and every reply the opponent actually uses earns exactly the value.

Complexity achieved: an exact $2\times n$ solution in $O(n^3)$ arithmetic as described ($O(n\log n)$ with a sweep), and any $m\times n$ game by one linear program. A grid search is inexact and names no strategy for the opponent.

Failure mode: maximizing the average payoff instead of the worst case over the opponent's replies. The uniform mix $p=(1/2,1/2)$ earns $5/6$ against a uniform Cole, but Cole answers with column 0 (or 2) and holds it to $1/2$.

In real software: randomized security schedules computed from game models have been deployed. The ARMOR system scheduled checkpoints and canine patrols at Los Angeles International Airport from 2007, using a Bayesian Stackelberg game, a general-sum relative of this lesson's games. Solving a zero-sum game is one linear program, which SciPy's scipy.optimize.linprog solves with the HiGHS solvers by default.

Retrieval (module 02): why does every deterministic comparison algorithm need $n-1$ comparisons to find the minimum of $n$ elements, and what would it take to turn that into a bound on randomized algorithms?

Check yourself

1. Why is Cole's strategy $(0,1/6,5/6)$ optimal in $H$, and why is column 0 never used?
2. Change $H_{0,2}$ from 1 to 3. What are the new value and strategies, and which column now goes unused?
3. For finding one marked cell among $n=5$, compare the left-to-right scan with the random order. What does Yao's principle prove about every other randomized algorithm, and what does it not prove?

Topic list modeled on the public schedule of CMU 15-451/651 Algorithm Design and Analysis (Fall 2025). All lecture text, proofs, examples, code, and exercises are original to SciMigo; no CMU course materials are reproduced. This course is independent and not affiliated with or endorsed by Carnegie Mellon University.