Mixed Strategies

Definition and basic idea

A mixed strategy for a player in a finite game is a probability distribution over that player's pure strategies. If player i has a finite set of pure actions A_i = {a_1, ..., a_m}, a mixed strategy is a vector p = (p_1, ..., p_m) with p_j >= 0 and \sum_j p_j = 1. A mixed-strategy profile is a tuple of such distributions, one per player. A mixed-strategy Nash equilibrium is a profile of mixed strategies such that no player can increase her expected payoff by unilaterally switching her distribution.

Why randomize? Motivation and examples

Randomization can be strategically necessary when no pure Nash equilibrium exists or when mixing raises a player's worst-case guarantee. Two canonical motivations:

1) Indifference and unpredictability. In zero-sum or adversarial environments, making yourself unpredictable prevents opponents from exploiting you. Matching Pennies has no pure Nash equilibrium, but mixing p = (1/2, 1/2) for both players is an equilibrium.

Numeric example: Matching Pennies. Payoff matrix to row player (column gets negative):

• •If row plays Heads (H) and column plays Heads (H): row gets +1.
• •H vs Tails (T): row gets -1.
• •T vs H: row gets -1.
• •T vs T: row gets +1.

If row plays H with probability p and column plays H with probability q, row's expected payoff is

(You can compute directly: u = p q 1 + p(1-q) (-1) + (1-p)q (-1) + (1-p)(1-q) 1.)

Setting p = q = 1/2 yields expected payoff 0 to both; unilateral deviation doesn't improve payoff, so it's a mixed Nash equilibrium.

2) Safety levels and maximin strategies. In competitive settings, mixing is used to maximize the minimum (safety) payoff, also called the maximin value. In zero-sum games the maximin strategy of a player coincides with the Nash strategy and is found by solving a minimax problem.

Support and the indifference principle: core intuitions

Two central concepts for mixed equilibria are support and the indifference principle. The support of a mixed strategy is the set of pure strategies assigned positive probability. In a mixed-strategy equilibrium, every pure strategy in a player's support must yield the same expected payoff against the opponents' mixed strategies; otherwise the player would shift probability mass to the better strategy. This is the indifference principle.

Concretely: suppose player 1 mixes over actions a and b with positive probabilities in equilibrium against opponents' mixed profile s_{-1}. Then

where v_1 is the equilibrium expected payoff to player 1. Any pure action outside the support must yield a payoff no greater than v_1; otherwise it would enter the support.

Formal existence (preview)

In finite games, mixed-strategy Nash equilibria always exist (Nash's theorem). The existence proof constructs a continuous best-response map on the compact, convex set of mixed profiles and applies Brouwer or Kakutani fixed-point theorems. A consequence: even when pure equilibria fail, mixing salvages equilibrium.

What this section prepares you to do

After this section you should: (i) know the definition of a mixed strategy and mixed Nash equilibrium, (ii) understand why supports and indifference matter, and (iii) appreciate the role of mixed strategies in guaranteeing safety levels in adversarial settings. In the next sections we will convert these intuitive statements into algebraic conditions you can solve to find equilibria and maximin strategies.

Connection with prerequisites

In "Nash Equilibrium (d3)" we learned the idea that no player benefits from unilateral deviation; here we extend that to probability distributions over actions. In "Common Distributions (d2)" you have the calculus of probability distributions — we will use discrete distributions for finite games and continuous distributions for auctions/examples.

Statement of the indifference principle

Let player i have k pure strategies indexed 1..k and let the opponents' mixed profile be s_{-i}. If player i places positive probability on a subset S (the support), then for all a in S,

for some constant V_i (player i's equilibrium payoff). For any a \notin S, we must have

Thus the support yields linear equalities and inequalities that pin down the opponents' probabilities.

Solving two-player games: linear equations

In two-player finite games, solving for a mixed equilibrium reduces to solving linear equations that enforce indifference across the support. Consider a 2x2 game where row has actions R1,R2 and column has actions C1,C2. Let row mix with probability p on R1 (so 1-p on R2), and column mix with q on C1 (1-q on C2). Suppose both players mix (support includes both pure actions). Then indifference gives two linear equations:

Row indifferent: u_row(R1, q) = u_row(R2, q)

Column indifferent: u_col(p, C1) = u_col(p, C2)

Example: Battle of the Sexes

Payoff matrix (row, column), numbers listed as (row payoff, column payoff):

• •(Opera, Opera): (2,1)
• •(Opera, Football): (0,0)
• •(Football, Opera): (0,0)
• •(Football, Football): (1,2)

Let row play Opera with probability p, column play Opera with probability q. Compute expected payoffs.

Row's expected payoff of Opera: u_row(Opera,q) = 2q + 0(1-q) = 2q.

Row's expected payoff of Football: u_row(Football,q) = 0 q + 1(1-q) = 1 - q.

Indifference for Row (if mixing both): 2q = 1 - q => 3q = 1 => q = 1/3. Numeric example: q = 1/3 means Column plays Opera with probability 1/3.

Column's expected payoff of Opera: u_col(p, Opera) = 1 p + 0 (1-p) = p.

Column's expected payoff of Football: u_col(p, Football) = 0 p + 2 (1-p) = 2(1 - p).

Indifference for Column: p = 2(1 - p) => 3p = 2 => p = 2/3. Numeric example: Row plays Opera with probability p = 2/3.

So the unique mixed-strategy Nash equilibrium (where both mix) is p = 2/3, q = 1/3, giving expected payoffs V_row = 2q = 2/3 and V_col = p = 2/3.

Support enumeration and elimination

A systematic method to find mixed equilibria in small games is support enumeration: enumerate candidate supports (combinations of actions with positive probability), solve indifference equalities to obtain probability distributions, and check inequality constraints for excluded actions. For an n-action player, a support of size s yields s-1 independent equalities (normalization provides the last equation), so unknown probabilities are determined by solving linear systems. This is why algorithmic equilibrium solvers like Lemke-Howson enumerate supports.

Concrete algebraic worked mini-example: Matching Pennies (again, 2x2 zero-sum)

Row payoff matrix (same as section 1): +1 on matching, -1 on mismatch. Suppose row mixes p on Heads; column mixes q on Heads. Row's expected payoff of Heads is

Maximin strategies and safety levels (definitions)

For player i, a maximin strategy maximizes the player's minimum payoff against any opponents' strategies. Formally, for a two-player game with row player R and column player C, R's maximin value is

A strategy p^ achieving this value is a maximin strategy and guarantees the safety level V_R = \min_q u_R(p^,q).

In zero-sum games, u_C = -u_R, and von Neumann's minimax theorem states:

Thus the maximin equals the minimax, and furthermore both players have mixed strategies achieving those values.

Numeric example: simple zero-sum 2x2

Payoff to row:

\begin{array}{c|cc}

& C1 & C2 \\

\hline

R1 & 2 & -1 \\

R2 & 0 & 1 \\

\end{array}

Find row's maximin strategy. Let row mix p on R1. For a given column pure C1, row's expected payoff is 2p + 0(1-p) = 2p. Against C2 it's -1 p + 1(1-p) = 1 - 2p. The worst-case payoff (as column can pick best response to minimize row's payoff) is

Auctions: bidding strategies as mixed equilibria

In many auction formats, especially first-price sealed-bid auctions with symmetric private values, bidders randomize in equilibrium. Consider n bidders, each with value v drawn independently from Uniform[0,1]. A symmetric Bayes–Nash equilibrium bidding function in the first-price auction is

Numeric example: for n=2, b(v) = v/2. If a bidder's valuation is v = 0.6, she bids b = 0.3.

Derivation sketch (why this is a mixed-continuous equilibrium): A bidder choosing a bid b given value v trades off increasing bid (raising chance to win) and paying more if she wins. Symmetric equilibrium leads to an ODE solved by straightforward calculus; the solution for uniform [0,1] yields the closed-form above. The continuous bidding function induces a distribution over bids (a continuous mixed strategy).

Security games and patrols

Defenders in security settings often randomize patrols across locations to avoid being predictable. Suppose there are two targets T1 and T2 with values x1 and x2 to the attacker; defender chooses a probability p to cover T1. The attacker then chooses the less-protected target. The defender's indifference condition sets p so that attacker is indifferent. Numeric example: if targets worth (10,6) and defender's coverage prevents attack, defender sets p so expected value of attacking either target is equal — yielding a specific p computed from those numbers.

Evolutionary dynamics and mixed equilibria

In evolutionary game theory, mixed Nash equilibria correspond to population states in which strategies co-exist in stable proportions. The indifference principle appears as equal average fitness across strategies in the support. Rock-Paper-Scissors (RPS) has a symmetric mixed NE p = (1/3, 1/3, 1/3). Numeric example: payoffs for RPS standard are 0 for ties, +1 for wins, -1 for losses. The symmetric uniform mix yields expected payoff 0 for every pure strategy, satisfying indifference.

Mechanism design and implementation

Mixed strategies feature in equilibrium constructs for mechanism design: designers must account for the possibility that agents randomize (e.g., mixed-strategy equilibria in matching markets, entry deterrence via mixed strategies). Knowledge of mixed-equilibrium existence is crucial when checking implementability.

Algorithmic game theory and complexity

From a computational perspective, computing a mixed Nash equilibrium for two-player games can be reduced to solving a linear complementarity problem; the Lemke–Howson algorithm finds one for bimatrix games. More broadly, finding Nash equilibria is PPAD-complete for games with >2 players or general bimatrix games — so while existence is guaranteed, computation can be hard.

Correlated equilibrium and refinement

Correlated equilibria generalize mixed equilibria by allowing a mediator to correlate players' strategies. Mixed equilibria are a subset of correlated equilibria. Mixed strategies set the stage: understanding support and indifference helps when analyzing correlated signals that induce the same indifference conditions.

Learning in games: fictitious play and regret minimization

Learning dynamics often converge to mixed equilibria or to sets that contain them. In two-player zero-sum games, no-regret algorithms converge (in average play) to the set of minimax strategies. Practical systems employing online learning (e.g., in security resource allocation) therefore effectively play mixed strategies.

Concrete applied example: network security patrol

Suppose a defender must patrol two segments of a network; attacks yield losses L1 = 100 and L2 = 40. If coverage prevents attack completely, defender chooses p to cover segment 1 with probability p so that attacker's expected payoff from attacking either segment is equal:

Attacker payoff when attacking 1: (1 - p) * 100.

Attacker payoff when attacking 2: (1 - (1 - p)) 40 = p 40.

Indifference (if attacker is indifferent): (1 - p) 100 = p 40 => 100 - 100 p = 40 p => 140 p = 100 => p = 100/140 = 5/7 ≈ 0.714. Numeric result: defender covers segment 1 ~71.4% of the time.

Where this leads you next

Mastering mixed strategies opens the door to Bayesian games (private information and continuous mixed strategies), auctions (bidding functions and equilibrium distributions), evolutionary stability (ESS vs mixed NE), correlated equilibria, learning algorithms and their convergence properties, and computational complexity of equilibrium computation (PPAD). Each of those directions depends on support/indifference reasoning and maximin thinking cultivated here.