Applied and computational mathematics

Game theory

The mathematics of strategic decisions among rational agents, with concepts like Nash equilibrium.

IntuitionWhen your best move depends on someone else's move

Two food trucks must each choose where to park on a street before seeing where the other parks. Choosing the busy end is best if the other truck picks the quiet end — but worst if both pick the busy end and split the same crowd. Optimization alone cannot solve this: there is no single best choice, only a best choice given what the other player does. Game theory is the mathematics of exactly this kind of interdependent decision.

z = x^2 - y^2

: a saddle payoff surface. It curves upward in

x

(a minimizing player's choice) and downward in

y

(a maximizing player's choice); the flat point at the center is where neither player can gain by moving alone — the value of the game.

This shape is not a coincidence. In many two-player competitive games, one player's payoff is exactly the negative of the other's — a zero-sum game — and the payoff, viewed as a function of both players' choices, is convex in the minimizer's strategy and concave in the maximizer's: exactly the saddle shape above. The flat point at the center is a saddle point, and it turns out to correspond precisely to rational play by both sides.

UndergraduateNormal-form games

Definition: Normal-form game

A normal-form game consists of a finite set of players $1, \dots, n$ ; for each player $i$ , a finite set of pure strategies $S_i$ ; and for each player $i$ , a payoff function $u_i : S_1 \times \cdots \times S_n \to \mathbb{R}$ giving player $i$ 's payoff for every combination of strategies chosen by all players simultaneously.

A two-player game is often written as a payoff matrix. In the classic Prisoner's Dilemma, two suspects independently choose to stay Silent or Confess; entries show (row player's years in prison, column player's years in prison) — smaller is better for each:

Prisoner's Dilemma payoff matrix (years in prison; lower is better)
Row \ Column	Column: Silent	Column: Confess
Row: Silent	$(1, 1)$	$(5, 0)$
Row: Confess	$(0, 5)$	$(3, 3)$

UndergraduateMixed strategies and von Neumann's minimax theorem

Definition: Mixed strategy

A mixed strategy for player $i$ is a probability distribution $x_i$ over $S_i$ : instead of committing to one pure strategy, the player randomizes. This matters most in games without a stable pure-strategy outcome — like Matching Pennies, where any predictable pure choice can be exploited by the opponent.

u_i(x_1, \dots, x_n) = \sum_{s_1 \in S_1} \cdots \sum_{s_n \in S_n} \left(\prod_{k=1}^n x_k(s_k)\right) u_i(s_1, \dots, s_n)

For a two-player zero-sum game, the row player's payoff matrix $A$ (an $m \times n$ matrix of real numbers) is exactly the negative of the column player's, so the row player wants to maximize $x^\top A y$ and the column player wants to minimize it, where $x$ and $y$ are the players' mixed strategies (probability vectors).

Theorem: Von Neumann's minimax theorem

For every $m \times n$ real matrix $A$ , $\max_{x \in \Delta_m} \min_{y \in \Delta_n} x^\top A y = \min_{y \in \Delta_n} \max_{x \in \Delta_m} x^\top A y$ , where $\Delta_m$ and $\Delta_n$ are the sets of probability vectors of length $m$ and $n$ . This common value $v$ is the value of the game.

Why is it true?

Without randomization, whoever moves "second" (choosing after learning the opponent's strategy) has an advantage, so maximin (row commits first) is generally at most minimax (column commits first). The surprising content of the theorem is that with mixed strategies this gap closes completely: randomizing removes any advantage from acting second, because the opponent can no longer predict — and exploit — a fixed choice.

Proof

Weak duality. For any fixed $x_0 \in \Delta_m$ and $y_0 \in \Delta_n$ : $\min_y x_0^\top A y \le x_0^\top A y_0 \le \max_x x^\top A y_0$ . Taking $\max_{x_0}$ of the left side and $\min_{y_0}$ of the right side preserves the inequality: $\max_x \min_y x^\top A y \le \min_y \max_x x^\top A y$ . This direction needs no randomization argument at all.

Reduction to a linear program. Since $y \mapsto x^\top A y$ is linear, its minimum over the simplex $\Delta_n$ is attained at a vertex, i.e. at some pure strategy $j$ : $\min_y x^\top A y = \min_{j} \sum_{i=1}^m x_i A_{ij}$ . So the row player's problem $\max_x \min_y x^\top A y$ is the linear program: maximize $v$ subject to $\sum_{i=1}^m A_{ij} x_i \ge v$ for every $j = 1, \dots, n$ , and $x \in \Delta_m$ .

The dual program. By the standard theory of linear programming duality, the dual of this LP is: minimize $w$ subject to $\sum_{j=1}^n A_{ij} y_j \le w$ for every $i = 1, \dots, m$ , and $y \in \Delta_n$ — which is exactly the linear-programming formulation of the column player's problem $\min_y \max_x x^\top A y$ .

Strong duality. Both the primal and dual feasible regions ( $\Delta_m$ and $\Delta_n$ ) are nonempty and compact, so the linear program is feasible and bounded; the strong duality theorem for linear programming then guarantees the primal and dual optimal values coincide: $\max_x \min_y x^\top A y = \min_y \max_x x^\top A y$ . Combined with weak duality, which already gave $\le$ in this direction, equality holds, proving the theorem.

UndergraduateNash equilibrium and its existence

Definition: Nash equilibrium

A strategy profile $x^\star = (x_1^\star, \dots, x_n^\star)$ is a Nash equilibrium if no player can improve their payoff by unilaterally switching to a different strategy while every other player's strategy stays fixed: for every player $i$ and every pure strategy $s_i \in S_i$ , $u_i(x_i^\star, x_{-i}^\star) \ge u_i(s_i, x_{-i}^\star)$ , where $x_{-i}^\star$ denotes the strategies of all players other than $i$ .

u_i(x_i^\star, x_{-i}^\star) \ge u_i(s_i, x_{-i}^\star) \quad \text{for every } i \text{ and every } s_i \in S_i

In the Prisoner's Dilemma above, (Confess, Confess) is the unique Nash equilibrium: Confess strictly beats Silent no matter what the other suspect does, so neither has any incentive to deviate — even though (Silent, Silent) gives both suspects a strictly better outcome. This gap between equilibrium and the best joint outcome is the heart of the "dilemma," and shows equilibria need not be efficient.

Theorem: Nash's existence theorem

Every finite normal-form game (any number of players $n$ , each with a finite pure-strategy set $S_i$ ) has at least one Nash equilibrium in mixed strategies.

Why is it true?

The proof builds a continuous "improve your strategy a little" map on the space of all strategy profiles: nudge probability toward any pure strategy currently doing better than average. Since the space of strategy profiles is compact and convex, Brouwer's fixed-point theorem guarantees this map has a fixed point — a profile that the map does not want to change. The proof's remaining work shows a fixed point is exactly a profile with no profitable deviation, i.e. a Nash equilibrium.

Proof

Let $\Delta = \Delta_1 \times \cdots \times \Delta_n$ , the product of the players' mixed-strategy simplices — a compact, convex subset of Euclidean space. For $x \in \Delta$ , player $i$ , and pure strategy $j \in S_i$ , define the gain function $g_{ij}(x) = \max\big(0,\, u_i(s_{ij}, x_{-i}) - u_i(x)\big)$ , the payoff player $i$ would gain by switching entirely to pure strategy $j$ , or $0$ if that switch would not help. Define $f : \Delta \to \Delta$ by $f_i(x)_j = \dfrac{x_{ij} + g_{ij}(x)}{1 + \sum_{k \in S_i} g_{ik}(x)}$ ; since $u_i$ is continuous (indeed multilinear) in $x$ , $g_{ij}$ is continuous, so $f$ is continuous, and each $f_i(x)$ is again a probability vector by construction.

By Brouwer's fixed-point theorem, the continuous map $f$ on the compact convex set $\Delta$ has a fixed point $x^\star$ with $f(x^\star) = x^\star$ . Write $S_i := \sum_{k \in S_i} g_{ik}(x^\star)$ ; the fixed-point equation for each $(i,j)$ reads $x_{ij}^\star (1 + S_i) = x_{ij}^\star + g_{ij}(x^\star)$ , i.e. $x_{ij}^\star S_i = g_{ij}(x^\star)$ .

Fix a player $i$ and let $d_{ij} := u_i(s_{ij}, x_{-i}^\star) - u_i(x^\star)$ , so $g_{ij}(x^\star) = \max(0, d_{ij})$ . Multiply the fixed-point equation by $d_{ij}$ and sum over $j \in S_i$ : on the left, $S_i \sum_j x_{ij}^\star d_{ij} = S_i\left(\sum_j x_{ij}^\star u_i(s_{ij}, x_{-i}^\star) - u_i(x^\star)\sum_j x_{ij}^\star\right) = S_i(u_i(x^\star) - u_i(x^\star)) = 0$ , using $\sum_j x_{ij}^\star u_i(s_{ij}, x_{-i}^\star) = u_i(x^\star)$ and $\sum_j x_{ij}^\star = 1$ .

On the right, $\sum_j g_{ij}(x^\star)\, d_{ij} = \sum_j \max(0,d_{ij})\, d_{ij} = \sum_{j:\, d_{ij} > 0} d_{ij}^2 \ge 0$ . Equating both sides, $\sum_{j:\, d_{ij}>0} d_{ij}^2 = 0$ , a sum of squares equal to zero, so every term vanishes: there is no $j$ with $d_{ij} > 0$ . Since $i$ was arbitrary, $u_i(s_{ij}, x_{-i}^\star) \le u_i(x^\star)$ for every player $i$ and every pure strategy $j$ — precisely the Nash equilibrium condition. Hence $x^\star$ is a Nash equilibrium.

UndergraduateReal-World Applications and Worked Examples

Game theory shapes how economists model competition and pricing, how security engineers reason about attackers and defenders, how biologists explain animal behavior through evolutionary stable strategies, and how auction designers (including for online ad markets) construct mechanisms where truthful bidding is each participant's best response.

Example: Mixed-strategy equilibrium in a network-defense game

An attacker chooses to attack Server A or Server B; a defender chooses which one to monitor. If the attacker targets the monitored server, the attack is caught (attacker payoff $-4$ ); if it targets the unmonitored one, it succeeds, earning $2$ against Server A or $6$ against Server B (more valuable). This is zero-sum with attacker payoff matrix (rows: attack A, attack B; columns: monitor A, monitor B) $A = \begin{pmatrix} -4 & 2 \\ 6 & -4 \end{pmatrix}$ . Find the attacker's optimal mixed strategy and the value of the game.

Solution

Check for a pure saddle point first: row minima are $\min(-4,2)=-4$ and $\min(6,-4)=-4$ , so maximin $=-4$ ; column maxima are $\max(-4,6)=6$ and $\max(2,-4)=2$ , so minimax $=2$ . Since $-4 \ne 2$ , there is no pure-strategy saddle, so a mixed strategy is required.

Let the attacker attack A with probability $p$ (and B with probability $1-p$ ). The expected payoff if the defender monitors A is $-4p + 6(1-p) = 6 - 10p$ ; if the defender monitors B, it is $2p - 4(1-p) = 6p - 4$ . An optimal $p$ must make these equal — otherwise the defender would always pick whichever is smaller for the attacker, and the attacker could do better by adjusting $p$ .

Solving $6 - 10p = 6p - 4$ : $10 = 16p$ , so $p = 10/16 = 5/8$ . The attacker should attack Server A with probability $5/8$ and Server B with probability $3/8$ .

The value of the game is $v = 6 - 10(5/8) = 6 - 6.25 = -0.25$ : even playing optimally, the attacker's expected payoff is slightly negative, meaning the defender's monitoring strategy holds a slight edge overall.

Example: Multiple pure Nash equilibria in a standards-adoption game

Two smartphone makers must each choose charging Standard A or Standard B; profits are highest when both choose the same standard, thanks to network effects and shared accessories. Payoffs (Firm 1, Firm 2) are: $(A,A){=}(8,8)$ , $(A,B){=}(2,3)$ , $(B,A){=}(3,2)$ , $(B,B){=}(6,6)$ . Find all pure-strategy Nash equilibria.

Solution

Check each of the four cells for a profitable unilateral deviation. At $(A,A)$ : Firm 1 switching to B (with Firm 2 fixed at A) gives $3 < 8$ , no gain; by symmetry Firm 2 has no gain either. So $(A,A)$ is a Nash equilibrium.

At $(B,B)$ : Firm 1 switching to A (Firm 2 fixed at B) gives $2 < 6$ , no gain; symmetric for Firm 2. So $(B,B)$ is also a Nash equilibrium.

At $(A,B)$ : Firm 1 gets $2$ ; switching to B (Firm 2 stays at B) gives $6 > 2$ , a strict improvement, so Firm 1 deviates — $(A,B)$ is not an equilibrium. By the same logic $(B,A)$ is not an equilibrium either.

So this game has two pure Nash equilibria, $(A,A)$ and $(B,B)$ — both stable in the sense that neither firm wants to deviate alone, yet the theory alone does not say which one the market will settle on; this equilibrium selection problem (matching the historical VHS-versus-Betamax standards battle) is a genuine subtlety beyond existence.

Research frontier as of 2026

As of 2026, computing a Nash equilibrium is understood to be computationally hard in general: Daskalakis, Goldberg and Papadimitriou (2009) proved that finding a Nash equilibrium of a normal-form game is PPAD-complete, a complexity class believed to sit strictly between polynomial time and NP-hardness, by reducing the problem to a discretized version of Brouwer's fixed-point theorem itself. This has pushed research toward equilibrium notions that can be computed efficiently and that arise naturally from repeated play: no-regret learning dynamics, where each player adapts their strategy over many rounds using only their own realized payoffs, are known to converge to the value of a two-player zero-sum game and, more generally, to broader equilibrium-like sets (coarse correlated equilibria) in general games — an active area connecting game theory to online learning, multi-agent reinforcement learning, and the design of markets and auctions where algorithms play both roles.

A zero-sum game has payoff matrix (to the row player) $A = \begin{pmatrix} 4 & 1 \\ 2 & 3 \end{pmatrix}$ . There is no pure-strategy saddle point. What is the value of the game?

Which condition correctly defines a Nash equilibrium $x^\star$ ?

Two suspects each choose Silent or Confess. Both Silent: 1 year each. Both Confess: 3 years each. One Confesses while the other stays Silent: the confessor goes free (0 years), the silent one gets 5 years. Confessing gives a strictly better outcome than Silent no matter what the other suspect does. What is the Nash equilibrium of this game?

A tennis server can aim Left or Right; the returner guesses Left or Right. The server wins the point with probability $80\%$ when the returner guesses the wrong direction, and only $50\%$ when the returner guesses correctly — symmetric for both directions. At the mixed-strategy Nash equilibrium, what probability should the server assign to aiming Left?

References

John von Neumann, Oskar Morgenstern (1944). Theory of Games and Economic Behavior
John F. Nash Jr. (1950). Equilibrium points in n-person games · DOI:10.1073/pnas.36.1.48
John F. Nash Jr. (1951). Non-Cooperative Games · DOI:10.2307/1969529
Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou (2009). The Complexity of Computing a Nash Equilibrium · DOI:10.1137/070699652