Game Theory, Saddle Points, Mixed Strategies & Minimax Linear Programming Equivalence

Mathematical Game Theory, founded as a rigorous axiomatic discipline by John von Neumann in his landmark 1928 paper Zur Theorie der Gesellschaftsspiele and expanded in the monumental 1944 treatise Theory of Games and Economic Behavior co-authored with Oskar Morgenstern, analyzes multiperson decision situations in which the payoff received by each rational decision-maker depends not only on their own chosen action and exogenous stochastic states, but also on the strategic actions selected by competing rational agents with conflicting or partially aligned objectives. Within Operations Research and Mathematical Statistics (Course Stat H-205), Two-Person Zero-Sum Matrix Games occupy a foundational position for two intertwined reasons: first, as established by George Dantzig and John von Neumann in 1947, solving any finite two-person zero-sum matrix game is mathematically isomorphic to solving a pair of Primal-Dual Linear Programming Problems; second, as proven by Abraham Wald in Statistical Decision Functions (1950), frequentist minimax statistical estimation and Neyman–Pearson hypothesis testing are formally equivalent to a two-person zero-sum game played between the Statistician (who selects a measurable decision rule $\delta(\mathbf{X})$ to minimize risk) and Nature (who selects an adversarial prior distribution $\pi(\theta)$ over the parameter space $\Theta$ to maximize expected risk).

Strategic Normal Form and the Zero-Sum Payoff Identity

A finite two-person zero-sum game in strategic (normal) form is defined by a triplet $(\mathcal{S}_I, \mathcal{S}_{II}, \mathbf{A})$:

1. Row Player $I$ (The Maximizer): Possesses a finite set of $m$ pure strategies $\mathcal{S}_I = \{\alpha_1, \alpha_2, \dots, \alpha_m\}$, corresponding to the $m$ rows of an $m \times n$ matrix.

2. Column Player $II$ (The Minimizer): Possesses a finite set of $n$ pure strategies $\mathcal{S}_{II} = \{\beta_1, \beta_2, \dots, \beta_n\}$, corresponding to the $n$ columns of the matrix.

3. Payoff Matrix $\mathbf{A} = [a_{ij}] \in \mathbb{R}^{m \times n}$: By universal convention in Operations Research, the matrix $\mathbf{A}$ is written from the perspective of Player $I$. When Player $I$ selects row strategy $\alpha_i$ ($i \in \{1, \dots, m\}$) and Player $II$ simultaneously (and without prior knowledge of Player $I$'s choice) selects column strategy $\beta_j$ ($j \in \{1, \dots, n\}$), Player $I$ receives the scalar utility payoff $u_I(\alpha_i, \beta_j) = a_{ij}$ and Player $II$ receives the utility payoff $u_{II}(\alpha_i, \beta_j) = -a_{ij}$.

The game is zero-sum (or strictly competitive) because the algebraic sum of the payoffs to the two players equals zero identically across every possible outcome cell $(i, j)$:

Consequently, $a_{ij} > 0$ represents a net gain of $a_{ij}$ utility units paid by Player $II$ to Player $I$, whereas $a_{ij} < 0$ represents a net loss of $|a_{ij}|$ paid by Player $I$ to Player $II$. More generally, any constant-sum game in which $u_I(\alpha_i, \beta_j) + u_{II}(\alpha_i, \beta_j) = K$ for a fixed constant $K \in \mathbb{R}$ (such as two competing firms splitting a fixed $100\%$ market share) is strategically identical to a zero-sum game via the affine utility shift $\tilde{u}_{II} = u_{II} - K = -u_I$.

Wald's Conservative Security Levels: Maximin and Minimax Pure Criteria

How do two rational, mutually distrustful adversaries evaluate pure strategies in $\mathbf{A}$ when each assumes the opponent will act as intelligently and malevolently as possible?

• Player $I$'s Security Level and Maximin Pure Strategy: If Player $I$ selects row $i$, the worst-case (minimum) payoff Player $I$ could possibly receive across all columns $j \in \{1, \dots, n\}$ that Player $II$ might choose is the row minimum $\min_{1 \le j \le n} a_{ij}$. To guarantee the largest possible floor (security level) regardless of Player $II$'s response, a conservative Player $I$ maximizes this worst-case minimum over all rows $i \in \{1, \dots, m\}$, defining the Lower Value of the Game ($\underline{v}$):

Any row strategy $\alpha_{i^*}$ achieving $\underline{v}$ is called a maximin pure strategy for Player $I$; by playing $\alpha_{i^*}$, Player $I$ is guaranteed to win at least $\underline{v}$ no matter what column Player $II$ plays.

• Player $II$'s Security Ceiling and Minimax Pure Strategy: Symmetrically, if Player $II$ selects column $j$, the worst-case (maximum) loss Player $II$ could suffer across all rows $i \in \{1, \dots, m\}$ is the column maximum $\max_{1 \le i \le m} a_{ij}$. To ensure the smallest possible ceiling on maximum loss, Player $II$ minimizes this maximum loss over all columns $j \in \{1, \dots, n\}$, defining the Upper Value of the Game ($\overline{v}$):

Any column strategy $\beta_{j^*}$ achieving $\overline{v}$ is called a minimax pure strategy for Player $II$; by playing $\beta_{j^*}$, Player $II$ is guaranteed to lose at most $\overline{v}$ no matter what row Player $I$ plays.

Lemma 7.1 (The Fundamental Maximin–Minimax Inequality):

For any real $m \times n$ matrix $\mathbf{A} = [a_{ij}] \in \mathbb{R}^{m \times n}$, the lower value never exceeds the upper value:

Proof:

For every specific pair of indices $(i_0, j_0) \in \{1,\dots,m\} \times \{1,\dots,n\}$, the entry $a_{i_0 j_0}$ is at least the minimum of row $i_0$ and at most the maximum of column $j_0$:

Because the left-hand side depends only on $i_0$ and the right-hand side depends only on $j_0$, this inequality holds for every $i_0$ and every $j_0$. Taking the maximum over $i_0 \in \{1, \dots, m\}$ on the left and the minimum over $j_0 \in \{1, \dots, n\}$ on the right yields $\underline{v} = \max_{i_0} \min_j a_{i_0 j} \le \min_{j_0} \max_i a_{i j_0} = \overline{v}$.

When the weak inequality $\underline{v} \le \overline{v}$ of Lemma 7.1 holds with strict equality ($\underline{v} = \overline{v} = v$), the conservative security levels of Player $I$ and Player $II$ meet at a single common value $v$, and the game is said to be strictly determined (solvable in pure strategies).

Saddle Points of Payoff Matrices

An entry $(i^*, j^*)$ of the payoff matrix $\mathbf{A} = [a_{ij}]$ is defined as a saddle point (or pure-strategy Nash equilibrium) of $\mathbf{A}$ if $a_{i^* j^*}$ is simultaneously the minimum element in its row $i^*$ and the maximum element in its column $j^*$:

The metaphor of a horse's saddle (or hyperbolic paraboloid $z = y^2 - x^2$) is exact: along the north-south direction (changing rows $i$ within column $j^*$), $(i^*, j^*)$ sits at the highest peak of the pass, whereas along the east-west direction (changing columns $j$ within row $i^*$), $(i^*, j^*)$ sits at the lowest trough! Notice the stability of a saddle point against unilateral espionage: even if Player $I$ announces in advance that row $i^*$ will be played, Player $II$'s best response to minimize loss in row $i^*$ is still column $j^*$ ($a_{i^* j^*} = \min_j a_{i^* j}$); symmetrically, even if Player $II$ announces column $j^*$ in advance, Player $I$'s best response to maximize gain in column $j^*$ is still row $i^*$ ($a_{i^* j^*} = \max_i a_{i j^*}$). Neither player has any unilateral incentive to deviate!

Theorem 7.1 (Necessary and Sufficient Condition for Saddle Points and Rectangular Interchangeability):

1. A matrix $\mathbf{A} \in \mathbb{R}^{m \times n}$ possesses a saddle point $(i^*, j^*)$ if and only if its lower value equals its upper value: $\underline{v} = \overline{v} = v = a_{i^* j^*}$.
2. Rectangular (Interchangeability) Property of Multiple Saddle Points: If $(i_1, j_1)$ and $(i_2, j_2)$ are both saddle points of $\mathbf{A}$, then the cross-paired cells $(i_1, j_2)$ and $(i_2, j_1)$ are also saddle points of $\mathbf{A}$, and all four cells share the exact same game value:

Proof:

First, if $(i^*, j^*)$ is a saddle point, then $\overline{v} = \min_j \max_i a_{ij} \le \max_i a_{i j^*} = a_{i^* j^*} = \min_j a_{i^* j} \le \max_i \min_j a_{ij} = \underline{v}$; combining $\overline{v} \le \underline{v}$ with Lemma 7.1 ($\underline{v} \le \overline{v}$) forces $\underline{v} = \overline{v} = a_{i^* j^*}$. Conversely, if $\underline{v} = \overline{v} = v$, let $i^*$ achieve $\max_i \min_j a_{ij} = \underline{v}$ and let $j^*$ achieve $\min_j \max_i a_{ij} = \overline{v}$. Then for all $i$ and $j$: $a_{i j^*} \le \max_k a_{k j^*} = \overline{v} = \underline{v} = \min_l a_{i^* l} \le a_{i^* j}$. Setting $i = i^*$ and $j = j^*$ shows $a_{i^* j^*} = v$ and $a_{i j^*} \le a_{i^* j^*} \le a_{i^* j}$ for all $i, j$. Second, if $(i_1, j_1)$ and $(i_2, j_2)$ are both saddle points, then by row-minimality and column-maximality:

Since the first and last terms are identical ($a_{i_1 j_1}$), all four entries must be equal to $v$, and both $(i_1, j_2)$ and $(i_2, j_1)$ satisfy the saddle-point inequalities.

Iterative Elimination of Dominated Strategies (Dominance Reduction Rules)

Before solving a large $m \times n$ matrix game analytically or via Linear Programming, its dimension can frequently be reduced dramatically by deleting rows and columns that a rational player would never need to use—a procedure known as Iterative Elimination of Dominated Strategies (IEDS):

1. Row Dominance Rule (Player $I$ Maximizes): Row $r$ is dominated by row $i$ (or by a convex combination of rows $\sum_{k \ne r} \lambda_k \mathbf{a}_{k*}$ with $\lambda_k \ge 0, \sum \lambda_k = 1$) if every entry in row $r$ is less than or equal to the corresponding entry in row $i$:

Because Player $I$ seeks to maximize payoff, playing row $i$ (or the mixed combination $\boldsymbol{\lambda}$) yields at least as large a payoff as row $r$ in every column $j$. Therefore, dominated row $r$ can be deleted from $\mathbf{A}$ without altering the value of the game!

2. Column Dominance Rule (Player $II$ Minimizes): Column $s$ is dominated by column $j$ (or by a convex combination of columns $\sum_{l \ne s} \mu_l \mathbf{a}_{*l}$ with $\mu_l \ge 0, \sum \mu_l = 1$) if every entry in column $s$ is greater than or equal to the corresponding entry in column $j$:

Because Player $II$ seeks to minimize loss, column $s$ inflicts a loss at least as large as column $j$ in every row $i$. Therefore, dominated (high-loss) column $s$ can be deleted from $\mathbf{A}$! Notice that deleting a row may create a newly dominated column, and deleting a column may create a newly dominated row, allowing alternating row-and-column reductions.

What happens when the strict inequality $\underline{v} < \overline{v}$ holds, so that the payoff matrix $\mathbf{A}$ possesses no saddle point in pure strategies? Consider the classic $2 \times 2$ Matching Pennies game $\mathbf{A} = \begin{pmatrix} +1 & -1 \\ -1 & +1 \end{pmatrix}$, where $\underline{v} = -1 < +1 = \overline{v}$. If either player adopts any deterministic pure strategy, the opponent can exploit that predictability to inflict a loss of $-1$. To protect against exploitation while maximizing expected utility, each player must randomize their choice of pure strategies according to an optimal probability distribution—termed a Mixed Strategy.

Probability Simplices and the Expected Payoff Bilinear Form

• A mixed strategy for Player $I$ is a probability vector $\mathbf{x} = (x_1, x_2, \dots, x_m)^T$ residing in the $(m-1)$-dimensional unit probability simplex $\Delta_{m-1} \subseteq \mathbb{R}_+{}^m$:

where $x_i = \mathbb{P}(\text{Player } I \text{ selects row } \alpha_i)$. Notice that the $m$ pure strategies $\alpha_1, \dots, \alpha_m$ correspond exactly to the $m$ standard unit extreme vertices $\mathbf{e}_1, \dots, \mathbf{e}_m$ of the simplex $\Delta_{m-1}$.

• Symmetrically, a mixed strategy for Player $II$ is a probability vector $\mathbf{y} = (y_1, y_2, \dots, y_n)^T$ residing in the $(n-1)$-dimensional probability simplex $\Delta_{n-1} \subseteq \mathbb{R}_+{}^n$:

where $y_j = \mathbb{P}(\text{Player } II \text{ selects column } \beta_j)$.

Because Player $I$ and Player $II$ randomize independently, the joint probability that cell $(i, j)$ occurs is $x_i y_j$. Therefore, the Expected Payoff $E(\mathbf{x}, \mathbf{y})$ to Player $I$ (and expected loss to Player $II$) is the bilinear quadratic form:

Simplification of Worst-Case Mixed Security Levels to Finite Pure Responses

Suppose Player $I$ commits to a mixed strategy $\mathbf{x} \in \Delta_{m-1}$. What is the worst-case (minimum) expected payoff $\min_{\mathbf{y} \in \Delta_{n-1}} \mathbf{x}^T\mathbf{A}\mathbf{y}$ that Player $II$ can force upon Player $I$? Notice that for fixed $\mathbf{x}$, $E(\mathbf{x}, \mathbf{y}) = \sum_{j=1}^n (\mathbf{x}^T \mathbf{a}_{*j}) y_j$ is a linear function (convex combination) of the $n$ pure-column expected payoffs $\mathbf{x}^T\mathbf{a}_{*j}$ over the simplex $\mathbf{y} \in \Delta_{n-1}$! By the Fundamental Theorem of Linear Programming (Unit 1), the minimum of a linear function over the probability simplex $\Delta_{n-1}$ occurs at one of its $n$ extreme vertices $\mathbf{y} = \mathbf{e}_j$ (pure column strategies $j \in \{1,\dots,n\}$):

and symmetrically, for fixed $\mathbf{y} \in \Delta_{n-1}$, Player $II$'s maximum expected loss occurs against one of Player $I$'s $m$ pure row strategies $i \in \{1, \dots, m\}$:

Theorem 7.2 (John von Neumann's Fundamental Minimax Theorem, 1928):

For every finite $m \times n$ matrix $\mathbf{A} \in \mathbb{R}^{m \times n}$, the mixed-strategy maximin value for Player $I$ and the mixed-strategy minimax value for Player $II$ both exist (since $\Delta_{m-1}$ and $\Delta_{n-1}$ are non-empty compact convex polytopes and $\mathbf{x} \mapsto \min_j \mathbf{x}^T\mathbf{a}_{*j}$ is continuous) and are strictly equal:

That is, there exists a saddle-point pair of optimal mixed strategies $(\mathbf{x}^*, \mathbf{y}^*) \in \Delta_{m-1} \times \Delta_{n-1}$ and a unique real number $v \in [\underline{v}, \overline{v}]$, called the Value of the Game, such that:

A game with $v = 0$ is called a fair game; a game with $\mathbf{A}^T = -\mathbf{A}$ ($m = n$, skew-symmetric payoff matrix) is called a symmetric game, which always has value $v = 0$ and identical optimal strategy sets ($\mathbf{x}^* = \mathbf{y}^*$).

Theorem 7.3 (Complementary Slackness / Equalizing Property of Active Pure Strategies):

At any optimal mixed-strategy pair $(\mathbf{x}^*, \mathbf{y}^*)$ with game value $v$:

1. Every pure column $j \in \{1, \dots, n\}$ played with strictly positive probability ($y_j^* > 0$) by Player $II$ must yield an expected payoff against $\mathbf{x}^*$ strictly equal to $v$: $\sum_{i=1}^m a_{ij} x_i^* = v$. Conversely, if $\sum_{i=1}^m a_{ij} x_i^* > v$, then $y_j^* = 0$.
2. Every pure row $i \in \{1, \dots, m\}$ played with strictly positive probability ($x_i^* > 0$) by Player $I$ must yield an expected payoff against $\mathbf{y}^*$ strictly equal to $v$: $\sum_{j=1}^n a_{ij} y_j^* = v$. Conversely, if $\sum_{j=1}^n a_{ij} y_j^* < v$, then $x_i^* = 0$.

When at least one player possesses only two pure strategies (or after dominance reduction leaves a $2 \times 2$, $2 \times n$, or $m \times 2$ matrix without a pure saddle point), the optimal mixed strategies $(\mathbf{x}^*, \mathbf{y}^*)$ and game value $v$ can be derived in exact closed form without executing the full Simplex Algorithm.

1. Closed-Form Algebraic Formulas and the Method of Oddments for $2 \times 2$ Games

Consider a $2 \times 2$ matrix game $\mathbf{A} = \begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix}$ that has no pure saddle point (which occurs if and only if the two diagonal elements strictly bracket the two off-diagonal elements: either $a_{11}, a_{22} > a_{12}, a_{21}$ or $a_{11}, a_{22} < a_{12}, a_{21}$). Because no pure saddle point exists, both pure strategies must be active ($0 < x_1^*, x_2^* < 1$ with $x_2^* = 1 - x_1^*$, and $0 < y_1^*, y_2^* < 1$ with $y_2^* = 1 - y_1^*$). By the Equalizing Property (Theorem 7.3), Player $I$ chooses $(x_1^*, 1 - x_1^*)$ so that Player $II$'s expected loss is identical whether Player $II$ plays Column 1 or Column 2:

Solving this linear equation for $x_1^*$, $x_2^* = 1 - x_1^*$, and symmetrically solving $E(\alpha_1, \mathbf{y}^*) = E(\alpha_2, \mathbf{y}^*)$ for $y_1^*, y_2^*$ and $v$ yields the Exact $2 \times 2$ Mixed-Strategy Formulas:

Notice the rapid mnemonic known as Williams' Method of Oddments:

• The unnormalized odds (oddments) $(|a_{22} - a_{21}| : |a_{11} - a_{12}|)$ for Row 1 and Row 2 equal the absolute row differences swapped across the two rows!
• The unnormalized odds $(|a_{22} - a_{12}| : |a_{11} - a_{21}|)$ for Column 1 and Column 2 equal the absolute column differences swapped across the two columns!

2. Graphical Envelope Solution of $2 \times n$ and $m \times 2$ Matrix Games

When Player $I$ has $m = 2$ rows and Player $II$ has $n \ge 3$ columns ($2 \times n$ game), Player $I$'s mixed strategy $\mathbf{x} = (x_1, 1 - x_1)^T$ depends on a single scalar probability parameter $x_1 \in [0, 1]$!

• Against each pure column $j \in \{1, 2, \dots, n\}$ of Player $II$, Player $I$'s expected payoff is a linear function of $x_1 \in [0, 1]$:

Plotted on two vertical parallel axes at $x_1 = 0$ (height $a_{2j}$) and $x_1 = 1$ (height $a_{1j}$), each column $j$ is a straight line segment connecting $(0, a_{2j})$ to $(1, a_{1j})$.

• Because Player $I$ seeks to maximize the minimum expected payoff over all $n$ columns:

the pointwise minimum $\underline{E}(x_1) = \min_{1 \le j \le n} E_j(x_1)$ forms a piecewise-linear concave lower envelope across $x_1 \in [0, 1]$! The global maximum $v$ of this lower envelope occurs at its highest peak vertex $x_1^*$, which is the intersection of two active column lines $j_1$ and $j_2$! Thus, any $2 \times n$ game reduces to a $2 \times 2$ subgame on the two columns $(j_1, j_2)$ intersecting at the peak of the lower envelope (with $y_j^* = 0$ for all other $n - 2$ columns!).

• Symmetrically, in an $m \times 2$ game where Player $II$ has $2$ columns $\mathbf{y} = (y_1, 1 - y_1)^T$ and Player $I$ has $m \ge 3$ rows, each row $i \in \{1, \dots, m\}$ plots as a line $E_i(y_1) = a_{i1} y_1 + a_{i2}(1 - y_1)$ for $y_1 \in [0, 1]$. Because Player $II$ seeks to minimize the maximum expected loss:

the pointwise maximum $\overline{E}(y_1) = \max_{1 \le i \le m} E_i(y_1)$ forms a piecewise-linear convex upper envelope, and the game value $v$ occurs at the lowest trough vertex $y_1^*$ of the upper envelope, reducing the $m \times 2$ game to a $2 \times 2$ subgame on the two active rows $(i_1, i_2)$ intersecting at that lowest vertex!

For general $m \times n$ matrix games where $\min(m, n) \ge 3$, graphical envelope methods are no longer applicable. Here we establish one of the most celebrated theorems of twentieth-century applied mathematics: every finite two-person zero-sum matrix game is completely equivalent to a pair of mutually dual Linear Programming Problems, and conversely, any primal-dual pair of Linear Programs can be embedded into a single skew-symmetric zero-sum matrix game!

Step 1: Ensuring Strict Positivity of the Game Value ($v > 0$)

To transform Player $I$'s maximin problem and Player $II$'s minimax problem into standard-form Linear Programs by dividing through by the game value $v$, we must ensure that $v > 0$ (strictly positive). Suppose the payoff matrix $\mathbf{A} = [a_{ij}]$ contains negative or zero entries so that its lower value $\underline{v} \le 0$. By adding a fixed positive shift constant $k > |\min_{i,j} a_{ij}|$ (for instance, $k = 1 - \min_{i,j} a_{ij} > 0$ whenever $\min_{i,j} a_{ij} \le 0$) to every entry of $\mathbf{A}$ to form the shifted matrix $\tilde{\mathbf{A}} = [a_{ij} + k] > \mathbf{0}$, for any mixed strategies $\mathbf{x} \in \Delta_{m-1}$ and $\mathbf{y} \in \Delta_{n-1}$:

Thus adding a constant $k$ to every entry of $\mathbf{A}$ leaves the optimal mixed strategies $(\mathbf{x}^*, \mathbf{y}^*)$ completely invariant and simply shifts the game value from $v$ to $\tilde{v} = v + k > 0$! Once $\tilde{v}$ is found, the original game value is recovered via $v = \tilde{v} - k$. Henceforth we assume without loss of generality that $a_{ij} > 0$ and $v > 0$.

Step 2: Deriving the Primal-Dual Linear Programs via Change of Variables

1. Player $I$'s Maximin Problem: Player $I$ seeks $\mathbf{x} \in \Delta_{m-1}$ and the largest scalar floor $v > 0$ such that every column's expected payoff is at least $v$:

Because $v > 0$, divide every constraint by $v$ and define the scaled non-negative variables $X_i = \frac{x_i}{v} \ge 0$ for $i = 1, \dots, m$. Notice that summing $X_i$ over all $i=1,\dots,m$ yields:

Because $v > 0$, maximizing $v$ is strictly equivalent to minimizing $\frac{1}{v} = \sum_{i=1}^m X_i$! Thus Player $I$'s problem becomes the standard-form Minimization Linear Program (Dual LP):

2. Player $II$'s Minimax Problem: Symmetrically, Player $II$ seeks $\mathbf{y} \in \Delta_{n-1}$ and the smallest scalar ceiling $v > 0$ such that every row's expected loss is at most $v$:

Dividing by $v > 0$, defining $Y_j = \frac{y_j}{v} \ge 0$ for $j = 1, \dots, n$, and noting that minimizing $v > 0$ is equivalent to maximizing $\frac{1}{v} = \sum_{j=1}^n Y_j$, Player $II$'s problem becomes the canonical Maximization Linear Program (Primal LP):

Theorem 7.4 (Primal-Dual Identity of Matrix Games and Proof of the Minimax Theorem):

Player $II$'s Maximization LP ($\max Z = \mathbf{1}_n^T \mathbf{Y}$ s.t. $\mathbf{A}\mathbf{Y} \le \mathbf{1}_m, \mathbf{Y} \ge \mathbf{0}$) and Player $I$'s Minimization LP ($\min W = \mathbf{1}_m^T \mathbf{X}$ s.t. $\mathbf{A}^T\mathbf{X} \ge \mathbf{1}_n, \mathbf{X} \ge \mathbf{0}$) are exact Symmetric Primal-Dual Linear Programs! Because $a_{ij} > 0$, $\mathbf{Y} = \mathbf{0}$ is primal feasible and $\mathbf{X}$ is bounded below by $\mathbf{0}$ (and dual feasible for large $\mathbf{X}$), so by the Strong Duality Theorem of Linear Programming (Theorem 3.2), both LPs possess finite optimal solutions $(\mathbf{Y}^*, \mathbf{X}^*)$ with:

Thus Strong Duality of Linear Programming provides an immediate, constructive algebraic proof of John von Neumann's Minimax Theorem! Furthermore, by solving just one of the two LPs (typically Player $II$'s Maximization LP via the standard Simplex Algorithm with slack variables $s_1, \dots, s_m \ge 0$ and zero artificial variables!), we read off $\mathbf{Y}^*$ from the optimal RHS column and read off Player $I$'s optimal scaled vector $\mathbf{X}^*$ directly from the optimal $z_j - c_j$ row under the $m$ slack variables!

The mathematical equivalence between zero-sum games and linear programming extends directly into the foundations of Statistical Decision Theory, as formulated by Abraham Wald (1945, 1950), David Blackwell, and Meyer Girshick (1954).

Wald's Statistical Game against Nature: Minimax Risk and Least Favorable Priors

In a parametric statistical decision problem, a statistician observes a random sample $\mathbf{X} \sim P_\theta$, where the unknown true parameter $\theta$ belongs to a finite parameter space $\Theta = \{\theta_1, \theta_2, \dots, \theta_m\}$ (the pure strategies of Nature, Player $I$), and must select a decision rule $d_j$ from a finite set of non-randomized estimators or hypothesis tests $\mathcal{D} = \{d_1, d_2, \dots, d_n\}$ (the pure strategies of the Statistician, Player $II$). If the true state of nature is $\theta_i$ and the statistician employs decision rule $d_j$, the statistician incurs expected statistical loss (risk) $R(\theta_i, d_j) = \mathbb{E}_{\theta_i}[L(\theta_i, d_j(\mathbf{X}))] = a_{ij}$.

• A randomized decision rule for the Statistician is a probability vector $\mathbf{y} = (y_1, \dots, y_n)^T \in \Delta_{n-1}$ over $\mathcal{D}$.
• A prior probability distribution selected by Nature is a probability vector $\boldsymbol{\pi} = (\pi_1, \dots, \pi_m)^T \in \Delta_{m-1}$ over the parameter space $\Theta$.
• For any prior $\boldsymbol{\pi} \in \Delta_{m-1}$ and randomized decision rule $\mathbf{y} \in \Delta_{n-1}$, the Bayes Risk is the bilinear form $r(\boldsymbol{\pi}, \mathbf{y}) = \boldsymbol{\pi}^T \mathbf{R} \mathbf{y} = \sum_{i=1}^m \sum_{j=1}^n \pi_i R(\theta_i, d_j) y_j$.

By von Neumann's Minimax Theorem (Theorem 7.2) applied to the risk matrix $\mathbf{R} = [R(\theta_i, d_j)]$:

This yields Wald's Fundamental Theorem of Minimax Statistical Inference:

1. The Statistician's optimal mixed strategy $\mathbf{y}^* \in \Delta_{n-1}$ is the Minimax Randomized Decision Rule, which minimizes the worst-case frequentist risk $\max_{1 \le i \le m} R(\theta_i, \mathbf{y})$ across the entire parameter space $\Theta$.
2. Nature's optimal mixed strategy $\boldsymbol{\pi}^* \in \Delta_{m-1}$ is the Least Favorable Prior Distribution, which maximizes the minimum achievable Bayes risk $r^*(\boldsymbol{\pi}) = \min_{\mathbf{y}} \boldsymbol{\pi}^T\mathbf{R}\mathbf{y}$.
3. By Complementary Slackness (Theorem 7.3), every minimax decision rule $\mathbf{y}^*$ is a Bayes rule with respect to the least favorable prior $\boldsymbol{\pi}^*$, and achieves a constant risk $R(\theta_i, \mathbf{y}^*) = v$ across all parameter states $\theta_i$ in the support of $\boldsymbol{\pi}^*$ ($\pi_i^* > 0$)—the celebrated Equalizer Rule Theorem of mathematical statistics!

Iterative Learning in Games: George Brown's Fictitious Play and Robinson's Convergence Theorem

Besides exact Simplex pivoting, George W. Brown (1951) proposed an intuitive statistical learning algorithm for solving $m \times n$ matrix games known as Fictitious Play (the direct precursor to modern online regret-minimization and reinforcement learning). In Fictitious Play, the two players play the game repeatedly over discrete rounds $t = 1, 2, \dots, T$. In round $t+1$, Player $I$ forms the empirical frequency distribution $\hat{\mathbf{y}}^{(t)} = \frac{1}{t}\sum_{s=1}^t \mathbf{e}_{j_s} \in \Delta_{n-1}$ of Player $II$'s historical column choices over the first $t$ rounds and plays a pure row $i_{t+1} \in \arg\max_i (\mathbf{A}\hat{\mathbf{y}}^{(t)})_i$ that maximizes expected payoff against $\hat{\mathbf{y}}^{(t)}$; simultaneously, Player $II$ tracks the empirical frequency distribution $\hat{\mathbf{x}}^{(t)} = \frac{1}{t}\sum_{s=1}^t \mathbf{e}_{i_s} \in \Delta_{m-1}$ of Player $I$'s past row choices and plays a pure column $j_{t+1} \in \arg\min_j ((\hat{\mathbf{x}}^{(t)})^T\mathbf{A})_j$ that minimizes expected loss against $\hat{\mathbf{x}}^{(t)}$. Notice that at every step $t$, the empirical strategies provide rigorous two-sided bounds on the true game value $v$:

In a celebrated 1951 paper in the Annals of Mathematics, Julia Robinson proved that as $t \to \infty$, the upper and lower bounds converge to $v$ and the empirical frequency vectors $(\hat{\mathbf{x}}^{(t)}, \hat{\mathbf{y}}^{(t)})$ converge to the set of optimal minimax mixed strategies $(\mathbf{x}^*, \mathbf{y}^*)$ for any finite zero-sum matrix game!