Payoff Matrices and Minimax Values

From a Decision Problem to a Matrix

A finite decision problem can be written as a table of risks: each row represents a decision rule, and each column represents a possible state of nature. This representation makes the strategic roles visible. The decision maker chooses a row to control loss; an adversary chooses a column to make the decision maker’s outcome as unfavorable as possible. The two pure-strategy values answer different questions: what payoff can the decision maker guarantee, and what upper bound can the adversary impose?

The entries in the table are not necessarily the losses from one observed sample. They are typically risks, meaning expected losses under the sampling distribution at a specified parameter value. For a finite set of decision rules $\delta_1,\ldots,\delta_m$ and parameter values $\theta_1,\ldots,\theta_k$, let $R_{ij}$ be the risk of rule $\delta_i$ when the parameter is $\theta_j$.

Definition: The loss matrix $R=(R_{ij})$ has entry $R_{ij}=R(\theta_j,\delta_i)$, the risk of decision rule $\delta_i$ at parameter value $\theta_j$. The decision maker is the row player, who seeks low loss; the adversary is the column player, who seeks high loss. The corresponding payoff matrix to the decision maker is $A=-R$. The adversary’s payoff is $-A$, so the game is zero-sum.

For example, if the loss for an action $a$ at state $\theta$ is $L(\theta,a)$, then a rule $\delta_i$ based on data $X$ has risk $R(\theta,\delta_i)=E_\theta[L(\theta,\delta_i(X))]$, when this expectation exists. If the rules or state set are finite, these risks can be placed in a matrix. A randomized rule can also be represented by its risk, but the calculations below concern the pure rows and columns of the displayed matrix.

Two Values for a Payoff Matrix

Write $A_{ij}$ for the payoff to the decision maker when row $i$ and column $j$ are selected. If the decision maker chooses a row and then wants to guarantee as much payoff as possible, the worst column for row $i$ gives payoff $\min_j A_{ij}$. The decision maker chooses the row with the largest such guarantee. This is the maximin value.

The adversary’s corresponding calculation starts with a column. Against column $j$, the decision maker would choose the row with the largest payoff, $\max_i A_{ij}$. The adversary chooses the column that makes this largest payoff as small as possible. This is the minimax value for the decision maker’s payoff.

Definition: For a finite payoff matrix $A$, the pure-strategy maximin and minimax values to the decision maker are $$ \alpha=\max_i\min_j A_{ij}, \qquad \beta=\min_j\max_i A_{ij}. $$ The maximin is the decision maker’s guaranteed payoff from choosing a row. The minimax is the adversary’s smallest achievable upper bound on the decision maker’s payoff, obtained by choosing a column.

When the entries are losses $R_{ij}$, the same quantities can be expressed directly in loss units. A row’s worst loss is $\max_j R_{ij}$, so the decision maker’s smallest worst-case loss is $\min_i\max_j R_{ij}$. In a column, the decision maker can attain loss as low as $\min_i R_{ij}$; the adversary’s largest such minimum is $\max_j\min_i R_{ij}$. Since $A=-R$, the payoff values are the negatives of these loss quantities:

\alpha=-\min_i\max_j R_{ij}, \qquad \beta=-\max_j\min_i R_{ij}.

Thus, in loss language, the decision maker is minimizing a worst-case risk, while the adversary is maximizing the lowest risk the decision maker can achieve in a selected column. Do not call both of these quantities the “minimax value” without saying whether the matrix contains losses or payoffs.

Worked Examples

Worked Example: Squared-Error Estimation at Two Parameter Values

Suppose the parameter is either $\theta_1=0$ or $\theta_2=1$, and compare the two constant estimators $\delta_1(X)=0$ and $\delta_2(X)=1$ under squared-error loss $L(\theta,a)=(a-\theta)^2$. Because these rules are constant, their risks are just their squared errors.

At $\theta=0$, the risks are $(0-0)^2=0$ and $(1-0)^2=1$. At $\theta=1$, they are $(0-1)^2=1$ and $(1-1)^2=0$. Therefore

R= \begin{pmatrix} 0&1\\ 1&0 \end{pmatrix}, \qquad A=-R= \begin{pmatrix} 0&-1\\ -1&0 \end{pmatrix}.

For the payoff matrix, row 1 has minimum payoff $-1$ and row 2 also has minimum payoff $-1$. Hence $\alpha=\max(-1,-1)=-1$. In column 1 the maximum payoff is $0$; in column 2 it is also $0$, so $\beta=\min(0,0)=0$. Equivalently, the decision maker’s smallest worst-case risk is $1$, while the adversary’s largest columnwise best-achievable risk is $0$. Their negatives are $\alpha=-1$ and $\beta=0$.

Worked Example: A Strict Gap Between the Values

Consider a finite decision problem with loss matrix

R= \begin{pmatrix} 1&4\\ 3&2 \end{pmatrix}, \qquad A= \begin{pmatrix} -1&-4\\ -3&-2 \end{pmatrix}.

The first decision has worst-case loss $\max(1,4)=4$; the second has worst-case loss $\max(3,2)=3$. The decision maker therefore has smallest worst-case loss $\min(4,3)=3$, attained by the second decision. In payoff units, the row minima are $-4$ and $-3$, so $\alpha=\max(-4,-3)=-3$.

Now examine each column. In the first column, the decision maker can attain loss $\min(1,3)=1$; in the second, the attainable minimum is $\min(4,2)=2$. The adversary’s largest such minimum is $\max(1,2)=2$, whose negative is $\beta=-2$. Directly from the payoff matrix, the column maxima are $-1$ and $-2$, giving $\beta=\min(-1,-2)=-2$. The two values differ: $-3<-2$. The matrix alone does not justify replacing either value by the other.

Worked Example: Equal Values in a Loss Matrix

Suppose two actions and two states have loss matrix

R= \begin{pmatrix} 1&4\\ 2&5 \end{pmatrix}.

The actions have worst-case losses $\max(1,4)=4$ and $\max(2,5)=5$, so the decision maker’s minimum worst-case loss is $4$. The statewise best-achievable losses are $\min(1,2)=1$ and $\min(4,5)=4$; their maximum is also $4$. Thus the corresponding payoff values are both $-4$. This calculation shows equality for this particular matrix; equality must be checked, not presumed for every matrix.

The Weak Minimax Inequality

The two payoff values always satisfy $\alpha\leq\beta$. This is an elementary but important guarantee: the decision maker’s payoff guarantee cannot exceed the adversary’s upper bound. It does not say that there is a single pure row and column that achieve a common value, or that equality holds.

Theorem: For every finite real payoff matrix $A$, its pure-strategy values satisfy $$ \max_i\min_j A_{ij}\leq \min_j\max_i A_{ij}. $$ Equivalently, for every finite loss matrix $R$, $$ \max_j\min_i R_{ij}\leq \min_i\max_j R_{ij}. $$

Proof. Fix any row $i$ and column $j$. The smallest entry in row $i$ cannot exceed $A_{ij}$, and $A_{ij}$ cannot exceed the largest entry in column $j$. Therefore

\min_{j'}A_{ij'}\leq A_{ij}\leq\max_{i'}A_{i'j}.

For each fixed column $j$, the first term is at most $\max_i A_{ij}$ for every row $i$. Taking the maximum over $i$ on the first term gives $\max_i\min_{j'}A_{ij'}\leq\max_i A_{ij}$. This holds for every column $j$; taking the minimum over $j$ on the right proves $\alpha\leq\beta$. Substituting $A_{ij}=-R_{ij}$ gives the stated loss inequality. $\square$

The inequality is also visible in Example 2: the decision maker’s maximin payoff is $-3$, no greater than the adversary’s minimax payoff $-2$. In loss units, the adversary’s maximin loss $2$ is no greater than the decision maker’s minimax loss $3$.

How to Build and Read the Matrix

A reliable translation keeps the statistical and strategic steps separate. First specify the finite rules and parameter values. Next calculate each risk using the model and loss function. Only then negate the risks if the game is to be stated as payoff to the decision maker. The row and column calculations follow from the chosen orientation, not from the word “minimax” alone.

Choose rows and columns.
List the decision rules as rows and the possible parameter values or states as columns.

Fill in risks.
For each rule and state, compute the expected loss $R_{ij}$. Check that each entry uses the same loss scale.

Choose an orientation.
For a loss matrix use low values as favorable to the decision maker. For a payoff matrix set $A=-R$, so high values are favorable to the decision maker.

Calculate both bounds.
For payoffs, take row minima then their maximum for $\alpha$, and column maxima then their minimum for $\beta$. For losses, use the equivalent formulas above.

A common mistake is to compute the row minima of a loss matrix and call their maximum the decision maker’s maximin payoff. That operation treats smaller loss as if it were a larger payoff, reversing the preference direction. The correction is to either keep the loss orientation—calculate $\min_i\max_j R_{ij}$ for the decision maker’s worst-case risk—or negate the entire matrix first and use the payoff formulas consistently.

These matrix calculations matter because they distinguish a decision maker’s security guarantee from an adversary’s bound, even when both are described informally as “worst case.” In a finite decision problem, each number can be computed directly from the risk table. A strict gap is possible, as Example 2 demonstrates; the weak inequality alone does not establish equality.

Check Your Understanding

Use the stated orientation in each question, and show the row or column calculations.

For a payoff matrix, explain in words what $\max_i\min_j A_{ij}$ measures and why the minimum is taken first.
For a loss matrix, write the decision maker’s smallest worst-case risk and the adversary’s largest columnwise best-achievable risk.
Negate the loss matrix $\begin{pmatrix}2&5\\4&1\end{pmatrix}$, then calculate its payoff maximin and minimax values.
Why does the weak minimax inequality not imply that the two pure-strategy values are equal?
A risk table has one row per estimator and one column per parameter value. What must an entry represent if the table is being used as a statistical decision matrix?