Zero-Sum Games

Why this concept exists

Game theory has many types of interaction: cooperation, coordination, bargaining, and pure competition. Zero-sum games isolate the pure competition part.

In a zero-sum game, the players’ interests are perfectly opposed: whatever Row gains, Column loses by the same amount. That makes the analysis unusually clean: there is a single notion of “the payoff,” and strategic reasoning becomes a search for guarantees rather than compromise.

Formal definition (matrix form)

A finite two-player zero-sum game is specified by a payoff matrix A ∈ ℝ^(m×n).

• •Row chooses an action i ∈ {1,…,m}
• •Column chooses an action j ∈ {1,…,n}
• •Row’s payoff is Aᵢⱼ
• •Column’s payoff is −Aᵢⱼ

So the game is “captured by one matrix.” If you know A, you know both players’ payoffs.

Pure strategies vs mixed strategies

A pure strategy is a single action (choose i deterministically).

A mixed strategy is a probability distribution over actions:

• •Row’s mixed strategy: p ∈ ℝ^m with pᵢ ≥ 0 and ∑ᵢ pᵢ = 1
• •Column’s mixed strategy: q ∈ ℝ^n with qⱼ ≥ 0 and ∑ⱼ qⱼ = 1

We’ll write these sets as simplices:

• •Δ_m = { p : p ≥ 0, ∑ᵢ pᵢ = 1 }
• •Δ_n = { q : q ≥ 0, ∑ⱼ qⱼ = 1 }

Expected payoff under randomization

If Row plays p and Column plays q, the expected payoff to Row is

E[payoff] = ∑ᵢ ∑ⱼ pᵢ Aᵢⱼ qⱼ = pᵀAq.

This bilinear form pᵀAq is the central object of zero-sum theory.

Intuition: adversarial uncertainty

A key mindset shift is this:

• •In probabilistic modeling, uncertainty might be “nature.”
• •In zero-sum games, uncertainty is often an opponent trying to hurt you.

So instead of maximizing expected value against a fixed distribution, you often maximize a worst-case expected value.

That leads directly to minimax reasoning.

Why randomize at all?

If you play deterministically in an adversarial setting, you can become predictable—and predictability can be exploited.

Classic example: Rock–Paper–Scissors has no good pure strategy. Any pure move can be countered for a loss. Randomization is not “noise”; it is a strategic tool.

Expected payoff as a weighted average

Fix Row’s mixed strategy p. Consider what happens against each pure column j. The expected payoff if Column plays pure j is

uⱼ(p) = ∑ᵢ pᵢ Aᵢⱼ.

This can be seen as the j-th component of the vector pᵀA.

Similarly, fix Column’s mixed strategy q. Against Row’s pure i, the expected payoff is

wᵢ(q) = ∑ⱼ Aᵢⱼ qⱼ,

i.e., the i-th component of Aq.

Now if both mix, the expected payoff is the average of these:

pᵀAq = ∑ⱼ qⱼ (∑ᵢ pᵢ Aᵢⱼ) = ∑ⱼ qⱼ uⱼ(p).

Best responses in a zero-sum setting

Given Column plays q, Row chooses p to maximize pᵀAq.

But for any fixed q, the function p ↦ pᵀAq is linear in p. Linear functions over a simplex achieve maxima at extreme points. That means:

• •A best response to q is always achievable by a pure row i that maximizes (Aq)ᵢ.

Similarly, a best response to p for Column (who wants to minimize Row’s payoff) can be taken as a pure column j that minimizes (pᵀA)ⱼ.

So why do we need mixed strategies if best responses are pure? Because the equilibrium concept is not “best response to a fixed opponent strategy,” but “mutually stable.” The stability can require mixing so that the opponent becomes indifferent among multiple pure best responses.

Dominated strategies (a quick pruning tool)

A row i is strictly dominated by row k if

Aᵢⱼ < A_kⱼ for all j.

Then Row should never play i (it is worse regardless of Column’s choice). Similarly, Column can delete dominated columns.

This matters because it can reduce the game size before you do heavier computation (LP or solving equations).

Geometric intuition: mixing as hedging

Think of each pure row i as a vector of payoffs across columns: (Aᵢ1, …, Aᵢn). When Row mixes, p forms a convex combination of these vectors.

• •The set { pᵀA : p ∈ Δ_m } is the convex hull of the row payoff vectors.

Row can choose a point in this convex set; Column then picks the coordinate (a column) that hurts Row most. Row’s problem becomes: pick a convex combination that maximizes the minimum coordinate.

That is already “minimax” in geometric clothing.

Why “value” matters

In many non-zero-sum games, equilibrium can mean multiple outcomes, negotiation, and mutual gain. In a zero-sum game, optimal play has a sharper promise:

• •Row can guarantee a certain payoff no matter what Column does.
• •Column can guarantee Row does not exceed a certain payoff no matter what Row does.

If these guarantees meet, the meeting point is the value of the game.

Maximin and minimax quantities

Define Row’s guaranteed payoff (maximin):

v_maximin = max_{p∈Δ_m} min_{q∈Δ_n} pᵀAq.

Interpretation:

1) Row chooses p first.

2) Column, knowing p, chooses q to minimize Row’s payoff.

3) Row selects p to maximize the resulting worst-case.

Define Column’s guaranteed bound (minimax):

v_minimax = min_{q∈Δ_n} max_{p∈Δ_m} pᵀAq.

Interpretation:

1) Column chooses q first.

2) Row responds to maximize payoff.

3) Column chooses q to make that best-case as small as possible.

A general inequality always holds:

max_{p} min_{q} pᵀAq ≤ min_{q} max_{p} pᵀAq.

Why? Because for any fixed (p, q):

min_{q} pᵀAq ≤ pᵀAq ≤ max_{p} pᵀAq

and taking max on the left expression and min on the right preserves the inequality.

So Row’s guarantee can’t exceed Column’s guarantee. The miracle is that in finite zero-sum games, they are actually equal.

Saddle points (pure and mixed)

A saddle point is a strategy pair (p⋆, q⋆) such that

pᵀAq⋆ ≤ (p⋆)ᵀAq⋆ ≤ (p⋆)ᵀAq

for all p ∈ Δ_m and q ∈ Δ_n.

Interpretation:

• •Given q⋆, Row cannot improve by deviating from p⋆.
• •Given p⋆, Column cannot reduce Row’s payoff by deviating from q⋆.

In a zero-sum game, a saddle point is exactly a Nash equilibrium (for the two-player zero-sum setting) because one player’s utility is the negative of the other’s.

If the saddle point occurs at pure strategies (i⋆, j⋆), then A_{i⋆j⋆} is simultaneously:

• •the minimum in Row i⋆ across columns
• •the maximum in Column j⋆ across rows

This is sometimes called a pure saddle point.

The minimax theorem (von Neumann)

For finite two-player zero-sum games:

max_{p∈Δ_m} min_{q∈Δ_n} pᵀAq = min_{q∈Δ_n} max_{p∈Δ_m} pᵀAq = v.

Moreover, there exist optimal mixed strategies (p⋆, q⋆) achieving this value v.

This theorem does three jobs at once:

1) Existence: an equilibrium in mixed strategies exists.

2) Equality of guarantees: the order of max and min can be swapped.

3) Operational meaning: v is the payoff under optimal play.

Interpreting v

• •If v > 0, Row has an advantage: Row can force positive expected payoff.
• •If v < 0, Column has an advantage: Column can force Row’s payoff negative.
• •If v = 0, the game is “fair” under optimal play.

Indifference principle (useful equilibrium property)

At equilibrium, any pure strategy used with positive probability must be a best response.

Concretely:

• •If Row’s equilibrium mix p⋆ assigns pᵢ⋆ > 0 to row i, then that row must achieve the same expected payoff v against q⋆ (otherwise Row would shift probability mass).
• •If Column’s equilibrium mix q⋆ assigns qⱼ⋆ > 0 to column j, then that column must yield the same expected payoff v against p⋆ (otherwise Column would shift mass).

This gives a practical method for small games: set certain expected payoffs equal and solve.

Why LP shows up here

The minimax theorem is not only about existence—it’s computational.

Row’s problem is:

maximize_{p∈Δ_m} min_{j} ∑ᵢ pᵢ Aᵢⱼ

because Column’s best response to p can be taken as a pure column j that minimizes (pᵀA)ⱼ.

That “maximize a minimum of linear functions” can be converted into an LP by introducing a variable v representing the guaranteed payoff.

Row player LP (primal)

Row wants the largest v such that every column j gives expected payoff ≥ v.

Variables: p ∈ ℝ^m, v ∈ ℝ

LP:

maximize v

subject to

• •∑ᵢ pᵢ Aᵢⱼ ≥ v for all columns j = 1,…,n
• •∑ᵢ pᵢ = 1
• •pᵢ ≥ 0 for all i

This is linear because v appears linearly and constraints are linear inequalities.

Column player LP (dual perspective)

Similarly, Column wants to minimize Row’s payoff. Column chooses q to make every row’s expected payoff ≤ v.

Variables: q ∈ ℝ^n, v ∈ ℝ

minimize v

subject to

• •∑ⱼ Aᵢⱼ qⱼ ≤ v for all rows i = 1,…,m
• •∑ⱼ qⱼ = 1
• •qⱼ ≥ 0 for all j

The minimax theorem corresponds to strong duality: both LPs share the same optimal value v.

Making the LP look “standard”

Some textbooks require A to be strictly positive to avoid sign issues when transforming to canonical forms. Practically, you can always shift payoffs by a constant c:

A' = A + c·1·1ᵀ

where 1 is the all-ones vector. Then

pᵀA'q = pᵀAq + c

So the optimal strategies (p⋆, q⋆) do not change, and the value shifts by +c.

This is a useful trick when converting to alternative LP formulations (like minimizing ∑ xᵢ subject to Aᵀx ≥ 1).

Complementary slackness = equilibrium structure

At optimality:

• •If Column assigns qⱼ⋆ > 0, then the corresponding constraint for Row is tight:

∑ᵢ pᵢ⋆ Aᵢⱼ = v.

• •If Row assigns pᵢ⋆ > 0, then the corresponding constraint for Column is tight:

∑ⱼ Aᵢⱼ qⱼ⋆ = v.

This matches the indifference principle: actions in the support of a mixed strategy yield equal expected payoff.

Practical comparison: methods to solve

Since you already know LP, the key conceptual leap is: “optimal play” is an LP feasibility + optimization problem.

Why this matters beyond game theory

Zero-sum games formalize adversarial optimization: one side tries to minimize a quantity while the other tries to maximize it. That pattern appears in:

• •Robust optimization (model vs worst-case perturbation)
• •Security (defender vs attacker)
• •Online learning (learner vs adversary)
• •Generative Adversarial Networks (generator vs discriminator)

GANs as a minimax game (high-level)

In a vanilla GAN, we have two models:

• •Generator G: produces fake samples
• •Discriminator D: tries to distinguish real from fake

Training is often written as

min_G max_D V(D, G)

This is not always a strict zero-sum game in the clean matrix sense (continuous strategies, non-convex objectives, approximation, etc.), but the conceptual backbone is minimax: one player improves by making the other worse.

What transfers directly from zero-sum theory

1) Value thinking: Instead of “did my loss go down,” ask “what can I guarantee against an improving opponent?”

2) Mixed strategies as distributions: In GANs, stochasticity and diversity in generation can be understood as mixing over outputs; in more theoretical treatments, one may consider mixed strategies over model parameters.

3) No-regret dynamics → equilibrium (preview idea): In many zero-sum settings, if both sides use algorithms with vanishing regret, the time-averaged strategies converge to minimax equilibrium. This is a bridge to modern ML training dynamics.

What does not transfer cleanly

• •Finite matrix games are convex–concave; deep networks are not.
• •Minimax theorem relies on compactness/convexity assumptions that fail in many ML parameterizations.

Still, the zero-sum framework gives you the correct mental model for adversarial objectives: equilibrium is about balance, not unilateral improvement.

A useful habit: write the payoff explicitly

Whenever you see “minimize a loss that depends on an adversary,” try to rewrite it as:

payoff = pᵀAq (finite case)

or more generally as an expectation under two distributions. Then ask:

• •What is the maximizing player’s best response?
• •What is the minimizing player’s best response?
• •Is there a value v? Under what assumptions?

That’s the zero-sum mindset you’ll reuse in GANs and robust ML.