Existence and Support of Mixed-Strategy Equilibria

Why Mixed Strategies Matter

In a finite game, players may have no pure-strategy Nash equilibrium: each player’s best action can depend on what the other player chooses, producing a cycle of incentives. Allowing players to randomize changes the set of possible strategies. A mixed strategy assigns probabilities to a player’s pure actions, and a mixed-strategy equilibrium is a profile of such probability distributions at which no player can gain by changing their distribution alone.

Randomization is not a claim that a player is necessarily indecisive. It is a strategic description of choices whose probabilities make the other players willing to use the strategies they do. The key calculation is payoff indifference: when a player assigns positive probability to multiple actions, those actions must give the same expected payoff against the opponents’ equilibrium strategies. That equality identifies possible supports, but it must be paired with checks that actions outside the support do not pay more.

Mixed Strategies and Equilibrium

Definition: A finite normal-form game has a finite set of players $i=1,\ldots,N$, a finite set of pure actions $A_i$ for each player, and a payoff $u_i(a_1,\ldots,a_N)$ for each player at every action profile. A mixed strategy $\sigma_i$ for player $i$ is a probability distribution over $A_i$. Players’ randomizations are independent, so the probability of a pure-action profile $a$ under $\sigma=(\sigma_1,\ldots,\sigma_N)$ is $\prod_j \sigma_j(a_j)$. The expected payoff is $$ u_i(\sigma)=\sum_{a_1\in A_1,\ldots,a_N\in A_N} \left(\prod_{j=1}^N \sigma_j(a_j)\right)u_i(a_1,\ldots,a_N). $$ A mixed-strategy Nash equilibrium is a profile $\sigma^*$ such that, for every player $i$ and every alternative mixed strategy $\tau_i$, $$ u_i(\sigma_i^*,\sigma_{-i}^*)\geq u_i(\tau_i,\sigma_{-i}^*). $$

The support of $\sigma_i$, written $\operatorname{supp}(\sigma_i)$, is the set of pure actions assigned strictly positive probability. An action outside the support has probability zero. Given the opponents’ strategies, a pure action $a_i$ is a best response if it maximizes the expected payoff $u_i(a_i,\sigma_{-i})$. Because expected payoff is linear in a player’s own probabilities, a mixed strategy is a best response exactly when it assigns positive probability only to pure best responses.

Consequently, in equilibrium every action in a player’s support must yield the same payoff, and no action outside the support can yield a higher payoff. The equality identifies a candidate mixture; the inequality is essential for confirming that the proposed support is actually an equilibrium.

Existence for Every Finite Game

Theorem: Every finite normal-form game has at least one mixed-strategy Nash equilibrium. The equilibrium may assign probability one to a pure action profile, or may involve randomization by one or more players.

The result follows from a fixed-point argument. Let $\Delta(A_i)$ denote the set of all probability distributions over player $i$’s finite action set. This is a nonempty, compact, convex simplex. The set of all mixed-strategy profiles is the product $K=\prod_i\Delta(A_i)$, also a nonempty, compact, convex subset of a finite-dimensional Euclidean space.

For each profile of opponents’ strategies $\sigma_{-i}$, let $BR_i(\sigma_{-i})$ be player $i$’s set of best-response mixed strategies. Consider the correspondence $F:K\to K$ defined by $F(\sigma)=\prod_i BR_i(\sigma_{-i})$. A fixed point of $F$ is precisely a profile in which every player is best responding to the others.

Best responses exist.
Against any fixed opponents’ strategies, expected payoff is a continuous function on the compact simplex $\Delta(A_i)$. It attains a maximum, so $BR_i(\sigma_{-i})$ is nonempty. It is also compact because it is the set of maximizers of a continuous function.

Best-response sets are convex.
Expected payoff is linear in $\sigma_i$. If two mixed strategies maximize it, every probability mixture of those strategies gives the same maximal payoff. Thus $BR_i(\sigma_{-i})$, and therefore the product set $F(\sigma)$, is convex.

The correspondence has a closed graph.
Suppose $\sigma^k\to\sigma$ and $r^k\to r$, with $r^k\in F(\sigma^k)$. For each player $i$, best response means $u_i(r_i^k,\sigma_{-i}^k)\geq u_i(t_i,\sigma_{-i}^k)$ for every mixed strategy $t_i$. Continuity of expected payoffs implies $u_i(r_i,\sigma_{-i})\geq u_i(t_i,\sigma_{-i})$ in the limit. Hence $r\in F(\sigma)$.

Apply Kakutani’s fixed-point theorem.
Kakutani’s theorem states that a correspondence from a nonempty, compact, convex subset of Euclidean space into itself has a fixed point if it is upper hemicontinuous and has nonempty, compact, convex values. Here the values have those properties; the closed-graph property, together with compact domain and range, gives upper hemicontinuity. Thus some $\sigma^*\in K$ satisfies $\sigma^*\in F(\sigma^*)$, which means every player best responds. This is a mixed-strategy Nash equilibrium.

This argument establishes existence, not uniqueness. It also does not prescribe a numerical method for finding an equilibrium. In a two-player example, support conditions often make the calculation direct.

Payoff Indifference in Two-Player Games

For a two-player game, write $p$ for the probability that the row player chooses $U$, and $q$ for the probability that the column player chooses $L$. If the row player’s payoffs in the $U$ row are $a_{UL}$ and $a_{UR}$, then the expected payoff from choosing $U$ against $q$ is $q a_{UL}+(1-q)a_{UR}$. The row player’s payoff from $D$ is calculated in the same way. If both $U$ and $D$ are in the row player’s support, indifference requires these two expected payoffs to be equal. For the column player, the corresponding condition compares the expected payoffs from $L$ and $R$ against $p$.

More generally, let $S_i$ be a proposed support. Each action in $S_i$ must yield the same maximal payoff against the opponents’ proposed strategies. Every action outside $S_i$ must yield a payoff no greater than that maximum. When these conditions hold for each player, the proposed profile is an equilibrium: any mixed deviation is a probability-weighted average of pure-action payoffs and therefore cannot exceed the maximum.

Worked Example: Matching Pennies

Suppose the row player receives $1$ when the actions match and $-1$ otherwise; the column player receives the opposite payoff. In the order $U,D$ for rows and $L,R$ for columns, the payoff pairs are $$ \begin{array}{c|cc} & L & R\\ \hline U & (1,-1) & (-1,1)\\ D & (-1,1) & (1,-1) \end{array} $$ Let $p=P(U)$ and $q=P(L)$. To have both row actions in the support, make their expected payoffs equal: $$ u_{\text{row}}(U)=q(1)+(1-q)(-1)=2q-1, \qquad u_{\text{row}}(D)=q(-1)+(1-q)(1)=1-2q. $$ Equating gives $2q-1=1-2q$, so $q=1/2$. For the column player, $$ u_{\text{col}}(L)=p(-1)+(1-p)(1)=1-2p, \qquad u_{\text{col}}(R)=p(1)+(1-p)(-1)=2p-1. $$ Indifference requires $1-2p=2p-1$, so $p=1/2$. At these probabilities, each player’s two actions give expected payoff $0$. The probabilities are strictly between zero and one, so both actions are indeed in each support. Neither player can gain by changing actions or by mixing differently. Thus $p=q=1/2$ is a mixed-strategy equilibrium.

Worked Example: A Coordination Game with Unequal Payoffs

Consider a game in which both players prefer to coordinate, but have different preferred coordinated outcomes: $$ \begin{array}{c|cc} & A & B\\ \hline A & (2,1) & (0,0)\\ B & (0,0) & (1,2) \end{array} $$ Let $p$ be the row player’s probability of choosing $A$, and $q$ the column player’s probability of choosing $A$. If the row player uses both actions, their payoffs must be equal: $$ u_{\text{row}}(A)=2q,\qquad u_{\text{row}}(B)=1-q,\qquad 2q=1-q. $$ Therefore $q=1/3$, and each row action yields $2/3$. For the column player, $$ u_{\text{col}}(A)=p,\qquad u_{\text{col}}(B)=2(1-p),\qquad p=2(1-p). $$ Solving gives $3p=2$, so $p=2/3$; each column action yields $2/3$ for the column player. Both probabilities lie strictly between zero and one, so the proposed supports are consistent with the calculation. Each player is indifferent between the two actions, and no pure or mixed deviation can improve on the common payoff. The profile $p=2/3,\ q=1/3$ is therefore a mixed-strategy equilibrium.

Worked Example: Checking an Action Outside the Support

The row player has actions $A,B,C$, and the column player has actions $L,R$. The payoff pairs are $$ \begin{array}{c|cc} & L & R\\ \hline A & (2,1) & (0,0)\\ B & (0,0) & (1,1)\\ C & (-1,0) & (-1,0) \end{array} $$ Test the proposed support $\{A,B\}$ for the row player and $\{L,R\}$ for the column player. Let $p=P(A)$ and $q=P(L)$. Row indifference requires $$ u_{\text{row}}(A)=2q,\qquad u_{\text{row}}(B)=1-q,\qquad 2q=1-q, $$ so $q=1/3$. At this value, both supported row actions yield $2/3$. The excluded action $C$ yields $-1$, which is strictly below $2/3$; it is not profitable for the row player to add $C$ to the support.

For the column player, the expected payoff from $L$ is $p(1)+(1-p)(0)=p$, and the payoff from $R$ is $p(0)+(1-p)(1)=1-p$. Indifference gives $p=1-p$, hence $p=1/2$. Both column actions are assigned positive probability and yield $1/2$. Every player’s supported actions are best responses, and the row player’s only excluded action yields less. Thus $p=1/2,\ q=1/3$ is an equilibrium. This check matters: indifference among $A$ and $B$ alone would not rule out a profitable deviation to $C$.

Common Pitfall: Indifference Is Not Enough

A frequent error is to solve the indifference equations for a proposed support and stop. Those equations only ensure that the actions assigned positive probability give equal payoffs. They do not show that those actions are better than every excluded action. In the last example, if $C$ had yielded $1$ rather than $-1$, the same equalities between $A$ and $B$, and between $L$ and $R$, would still hold at the calculated probabilities. But the row player would then prefer $C$, so the candidate would not be an equilibrium.

The reverse mistake is to impose indifference on an action that receives probability zero. An excluded action need not yield the same payoff as the supported actions; it may yield less. The correct procedure is to equate payoffs only among actions in each proposed support, then compare every excluded action’s payoff with the common supported payoff. Finally, check that each proposed probability is valid and that every action designated as supported receives strictly positive probability.

Key takeaway: A finite game always has at least one mixed-strategy Nash equilibrium. To identify an equilibrium by supports, impose payoff equality on actions used with positive probability and payoff inequalities on actions left out.

Check Your Understanding

Use payoff indifference to analyze the proposed supports, and remember to check actions outside them.

In matching pennies, why must the column player use $L$ and $R$ with equal probabilities in equilibrium?
In the coordination example, what expected payoff does each player receive at the mixed-strategy equilibrium?
State the payoff condition that an action outside a player’s proposed support must satisfy.
In the three-action example, what would happen to the proposed profile if the row payoff from $C$ were $1$ against both $L$ and $R$?
Why does a mixed strategy that assigns positive probability only to pure best responses also constitute a best response?