Randomization and Convex Strategy Sets

Why Randomize Over Pure Strategies?

In a finite zero-sum game, each player may have only a small collection of available pure strategies. Yet choosing only one strategy can leave a player vulnerable: an opponent who observes or anticipates that choice may select a response that performs especially well against it. Randomization replaces a single choice with a probability distribution over choices. The resulting strategy sets have a useful geometric structure: they are convex.

That structure matters because a player’s expected payoff is linear in their own probabilities when the opponent’s strategy is held fixed. It lets us apply the finite minimax theorem to the enlarged strategy sets, even when the original pure-strategy choices have no saddle point. The conclusion is not that every problem becomes minimax simply by adding randomness: the finite-game result also relies on the bilinear expected-payoff form and the finite strategy sets.

Mixed Strategies as Convex Combinations

Consider a finite zero-sum game with row player strategies \(R_1,\ldots,R_m\), column player strategies \(C_1,\ldots,C_k\), and payoff matrix \(A=(a_{ij})\). The entry \(a_{ij}\) is the payoff to the row player, and the column player seeks to minimize that payoff. A pure strategy selects one row or one column.

The set of row mixtures is the probability simplex \(\Delta_m=\{p\in\mathbb{R}^m:p_i\geq 0,\ \sum_i p_i=1\}\), with an analogous set \(\Delta_k\) for the column player. Each pure strategy is represented by a unit vector: the vector with a 1 in its coordinate and 0 in every other coordinate. A mixed strategy is a convex combination of these vectors, with its probabilities as the combination weights.

Proof. Let \(p,p'\in\Delta_m\) and \(t\in[0,1]\). Each coordinate of \(tp+(1-t)p'\) is nonnegative, and its coordinates sum to \(t+(1-t)=1\). Thus \(tp+(1-t)p'\in\Delta_m\), proving convexity. The same calculation proves convexity of \(\Delta_k\). For fixed \(q\), \((tp+(1-t)p')^{\mathsf T}Aq=t p^{\mathsf T}Aq+(1-t)p'^{\mathsf T}Aq\). The corresponding identity holds when mixing \(q\) and \(q'\) while holding \(p\) fixed. These identities establish affinity in each player’s strategy. \(\square\)

The formula for expected payoff follows by considering the joint probability of each pair of pure strategies. Under independent randomization, that probability is \(p_iq_j\). Weighting each payoff \(a_{ij}\) by its probability gives \(\sum_{i=1}^m\sum_{j=1}^k p_iq_j a_{ij}=p^{\mathsf T}Aq\). In particular, holding one player’s mixture fixed, changing the other player’s mixture forms a convex combination of the payoffs from pure strategies.

Worked Examples of Convexification

Why Convex Strategy Sets Support Minimax Equality

For a finite payoff matrix, define the row player’s mixed maximin guarantee and the column player’s mixed minimax guarantee by

For any \(p\) and \(q\), the minimum over column mixtures is no greater than the payoff at that particular \(q\), and the maximum over row mixtures is no smaller than the payoff at that particular \(p\). Consequently, \(\underline{v}\leq\overline{v}\). The minimax equality is the stronger statement that the two guarantees are equal.

Justification. The finite-game form of von Neumann’s minimax theorem applies to every finite real payoff matrix with the row player maximizing and the column player minimizing. To apply it here, represent each pure strategy by its unit vector and each randomized strategy by its probability vector. The feasible sets are exactly \(\Delta_m\) and \(\Delta_k\), and the expected payoff of each pair of mixtures is exactly \(p^{\mathsf T}Aq\). The theorem therefore gives the stated equality for this randomized game. The convexity and affinity proved above explain the structure of the strategy sets and payoff that supports the result; they do not, by themselves, prove minimax equality for arbitrary strategy sets or payoffs. \(\square\)

The significance of randomization is not that it guarantees a better outcome in every game. Rather, it supplies a larger set of choices in which a player can balance performance across possible opponent responses. In matching pennies, neither pure strategy protects the row player from a payoff of \(-1\), but equal randomization guarantees 0. In the second example, the appropriate mixtures make each opponent’s pure options yield the same expected payoff, preventing a profitable response.

A Common Pitfall

Practical Interpretation

A mixed strategy can be understood as a lottery over complete pure strategies. The player commits to the probabilities, then uses randomization to select a pure strategy. The selected strategy is not necessarily a randomized action at every stage: when a pure strategy is a full plan for a multi-stage game, the lottery is over those plans. This distinction matters because the mixed strategy describes a distribution over pure strategies, while the payoff calculation averages over the resulting outcomes.

For a finite game, the main calculations are therefore concrete: list pure strategies, record their payoffs, represent mixtures as probability vectors, and calculate expected payoffs by \(p^{\mathsf T}Aq\). The probability constraints create convex strategy sets, and the affine payoff in each player’s mixture makes the finite minimax result relevant. In settings beyond finite matrix games, additional conditions are needed before a minimax interchange can be justified.