Mixed Strategy · aiwiki.page

A mixed strategy in game theory is a probability distribution over a player’s available pure strategies. Rather than selecting one strategy with certainty, the player assigns probabilities to alternatives. Pure strategies are included as the special case in which one alternative receives probability 1. Mixed strategies extend the set of possible choices and are essential to analyzing games that have no equilibrium in pure strategies. (mit.edu)

Mathematical definition

Suppose player $i$ has a finite pure-strategy set

S_i=\{s_{i1},\ldots,s_{im_i}\}.

A mixed strategy is a vector

\sigma_i=(p_{i1},\ldots,p_{im_i}), \qquad p_{ik}\geq 0,\qquad \sum_{k=1}^{m_i}p_{ik}=1,

where $p_{ik}$ is the probability of choosing $s_{ik}$ . The set of all such vectors, conventionally denoted $\Delta(S_i)$ , is a probability simplex. Its vertices represent pure strategies. The support of $\sigma_i$ consists of the pure strategies assigned positive probability; a strategy is fully mixed if every available pure strategy belongs to its support. (mit.edu)

Mixing means random selection among complete alternatives, not taking an average of their physical actions. A lottery between two choices need not be equivalent to choosing an intermediate action, even when such an action exists. This distinction follows from defining the mixture over strategies rather than over their numerical descriptions. (mit.edu)

Expected payoffs

Payoffs under mixed strategies are evaluated by their expected value. In the standard mixed-strategy model, players’ random selections satisfy statistical independence. For a profile $\sigma=(\sigma_1,\ldots,\sigma_n)$ ,

U_i(\sigma)= \sum_{s\in S_1\times\cdots\times S_n} u_i(s)\prod_{j=1}^{n}\sigma_j(s_j),

where $u_i(s)$ is player $i$ ’s payoff at pure-strategy profile $s$ . (mit.edu)

For a two-player game with row-player payoff matrix $A$ , this becomes

U_1(x,y)=x^{\mathsf T}Ay.

Holding opponents’ strategies fixed, expected payoff is linear in a player’s own probabilities. Consequently, randomization cannot yield more than the best pure response to those fixed opponents, though it can tie that response. (mit.edu)

Mixed-strategy Nash equilibrium

A mixed-strategy profile $\sigma^*$ is a Nash equilibrium if no player can improve expected payoff by changing their strategy alone:

U_i(\sigma_i^*,\sigma_{-i}^*) \geq U_i(\sigma_i,\sigma_{-i}^*) \quad \text{for every player }i \text{ and every }\sigma_i\in\Delta(S_i).

Here $\sigma_{-i}^*$ denotes the other players’ strategies. A mixed strategy is an individual choice rule; a mixed-strategy equilibrium is a profile satisfying this mutual optimality condition. (ocw.mit.edu)

Nash’s existence theorem guarantees at least one equilibrium in mixed strategies for every game with finitely many players and finitely many pure strategies per player. This does not imply that equilibrium is unique, that all players randomize, or that every available strategy receives positive probability. Pure-strategy equilibria are included in the guarantee. (mit.edu)

Indifference and computation

A mixed strategy is a best response precisely when every pure strategy in its support maximizes payoff against the opponents’ strategies. Thus, at equilibrium:

all strategies in a player’s support yield the same expected payoff;
strategies outside the support yield no greater payoff;
probabilities are nonnegative and sum to 1.

The equal-payoff condition is often called the indifference principle. Importantly, a player’s mixing probabilities make the other player indifferent between the alternatives that the other player uses. Equalizing supported payoffs is not sufficient unless excluded strategies are also checked. (ocw.mit.edu)

For finite two-player games, support enumeration searches possible pairs of supports and solves the associated payoff and probability constraints. Given supports, these constraints can be formulated using linear programming, although the number of candidate support pairs grows exponentially with the numbers of strategies. (mit.edu)

Example: matching pennies

Consider matching pennies, a two-player zero-sum game. Each player chooses heads or tails. The row player receives $+1$ if the choices match and $-1$ otherwise; the column player receives the opposite payoff:

A= \begin{pmatrix} 1&-1\\ -1&1 \end{pmatrix}.

If the column player chooses heads with probability $q$ , the row player’s payoffs from heads and tails are respectively

2q-1 \quad\text{and}\quad 1-2q.

Equating them gives $q=\tfrac12$ . Applying the same calculation to the column player gives $p=\tfrac12$ . Hence both players choosing each side with equal probability is an equilibrium, with expected payoff zero. These results follow directly from the expected-payoff and indifference conditions above. (mit.edu)

Behavioral strategies and correlation

In an extensive-form game, a pure strategy specifies a complete contingent plan, including choices at decision points that may never be reached. A mixed strategy randomizes over these complete plans. A behavioral strategy, by contrast, specifies a probability distribution over actions at each information set. In finite games with perfect recall, Kuhn’s theorem establishes their realization equivalence: each has a counterpart inducing the same outcome probabilities against opponents’ strategies. This equivalence need not hold without perfect recall. (cs.cmu.edu)

Independent mixing also differs from correlated equilibrium, where players’ choices can depend on correlated signals. A mixed-strategy Nash equilibrium induces a product distribution over players’ strategies and is a special case of correlated equilibrium; a correlated equilibrium need not have that product structure. (ocw.mit.edu)

References

MIT 6.7980 · Lecture 1 · Setting and equilibria: the Nash equilibriummit.edu
Game Theory, Lecture Notesocw.mit.edu
MIT 6.7980 · Supplementary reading S1 · Centralized algorithms for Nash equilibrium computationmit.edu
No Slide Titlecs.cmu.edu
Lecture5-Slidescs.cmu.edu
Behavior strategies and Kuhn's Theorem (Chapter 6) - Game Theorycambridge.org