Computing Equilibria for Discrete-Choice Games

Why Equilibrium Computation Requires a Check

In a finite-action game, an equilibrium is a profile of choices at which no player can gain by changing their own choice alone. Finding such a profile computationally is not the same as verifying one. A solver can stop at a profile that is not an equilibrium, an iteration can cycle, and different starting values can lead to different fixed points. A reliable computation therefore combines a method for generating candidates with a direct check of the equilibrium conditions.

Two computational tasks are especially useful in structural models. For a small game with deterministic payoffs, enumerate action profiles and test every unilateral deviation. For a game with unobserved payoff shocks, calculate choice probabilities as functions of opponents’ probabilities and solve the resulting fixed-point equations. These tasks are related, but their equilibrium conditions are not interchangeable.

Definition: In a finite-action game, player $i$ chooses an action $a_i$ from a finite set $A_i$, and receives payoff $u_i(a_i,a_{-i})$, where $a_{-i}$ denotes the actions chosen by all other players. A pure-action profile $a^*=(a_1^*,\ldots,a_I^*)$ is a Nash equilibrium if $$ u_i(a_i^*,a_{-i}^*) \geq u_i(a_i,a_{-i}^*) \quad \text{for every player } i \text{ and every } a_i\in A_i. $$ The condition requires checking all unilateral deviations, holding the other players’ actions fixed.

Enumerating Pure-Action Profiles

If there are $I$ players and player $i$ has $|A_i|$ available actions, the number of pure profiles is $\prod_{i=1}^I |A_i|$. For each profile, calculate each player’s payoff from the prescribed action and compare it with the payoff from every alternative action. Retain the profile only if no player has a profitable deviation. Enumeration is finite and transparent, but the number of profiles grows quickly as the game gets larger.

List the profiles.
Form every combination of players’ actions, without omitting profiles that seem unlikely.

Calculate deviation payoffs.
At each profile, hold the opponents’ actions fixed and calculate the payoff from every action available to the player being checked.

Retain and verify candidates.
A profile is an equilibrium only if the prescribed action is payoff-maximizing for every player. Report all profiles that pass.

Worked Example: Enumerating a Two-Player Game

Two players each choose $A$ or $B$. The entries below are the payoffs to Player 1 and Player 2, in that order.

	Player 2: A	Player 2: B
Player 1: A	(2, 2)	(0, 0)
Player 1: B	(0, 0)	(1, 1)

At $(A,A)$, either player who switches alone receives $0$ rather than $2$. Neither has a profitable deviation, so $(A,A)$ is an equilibrium. At $(B,B)$, a unilateral switch gives $0$ rather than $1$, so $(B,B)$ is also an equilibrium.

At $(A,B)$, Player 1 receives $0$ and could switch to $B$, receiving $1$; the profile fails the condition. At $(B,A)$, Player 1 could switch to $A$ and increase their payoff from $0$ to $2$. Thus the complete enumeration finds exactly two pure-action equilibria: $(A,A)$ and $(B,B)$. The enumeration does not itself choose between them.

Mixed Strategies and Equilibrium Checks

A mixed strategy assigns a probability to each available action. To check a mixed-strategy equilibrium, calculate each action’s expected payoff against the opponents’ strategy probabilities. Every action used with positive probability must maximize expected payoff; any unused action must yield no more than that maximum. Probabilities must be nonnegative and sum to one for each player. These conditions provide a direct check after a numerical solver proposes a mixed equilibrium.

For a two-action player, let $p_i$ be the probability of choosing the first action. If both actions receive positive probability in equilibrium, their expected payoffs must be equal. This equality often gives equations that can be solved for the opponents’ probabilities. A computed probability outside $[0,1]$, or an action in the support that is not payoff-maximizing, signals an invalid candidate.

Worked Example: A Mixed Equilibrium and a Best-Response Cycle

In a matching-pennies game, Player 1 receives $1$ if the actions match and $-1$ otherwise. Player 2 receives the opposite payoff. Each chooses $H$ or $T$. Let $p$ be Player 1’s probability of $H$, and $r$ Player 2’s probability of $H$.

Player 1’s expected payoff from $H$ is $r-(1-r)=2r-1$; from $T$ it is $(1-r)-r=1-2r$. For Player 1 to use both actions with positive probability, these payoffs must be equal: $2r-1=1-2r$, giving $r=0.5$. Player 2’s expected payoff from $H$ is $p-(1-p)=2p-1$, and from $T$ it is $(1-p)-p=1-2p$. Indifference requires $p=0.5$. Thus each player choosing $H$ and $T$ with probability $0.5$ is a mixed equilibrium. Against these probabilities, each action gives each player expected payoff $0$, so neither player can gain by changing their mixture.

A procedure that repeatedly makes both players choose a pure best response need not converge here. If the current profile is $(H,H)$, Player 2 switches to $T$, giving $(H,T)$. Player 1 then switches to $T$, giving $(T,T)$; Player 2 switches to $H$, giving $(T,H)$; and Player 1 switches to $H$, returning to $(H,H)$. The procedure cycles. This is not evidence that no equilibrium exists: it shows that this particular iteration does not find the mixed equilibrium.

Choice-Probability Fixed Points

In a game with payoff shocks, the object computed may instead be a vector of choice probabilities. For example, each firm may choose whether to enter after receiving a private payoff shock. Given the other firms’ entry probabilities, a firm can calculate the probability that entry yields the highest payoff. An equilibrium choice-probability vector is one in which those calculated probabilities equal the probabilities used to form beliefs about opponents’ choices.

Definition: Let $p_i$ be player $i$’s choice-probability vector over their finite action set. Let $T_i(p_{-i})$ give the probabilities implied by player $i$’s best choices, integrating over the model’s payoff shocks and the opponents’ action probabilities. A choice-probability equilibrium satisfies $$ p_i=T_i(p_{-i}) \quad \text{for every } i. $$ This fixed-point condition is specific to the stated payoff-shock model. It is not the same as a mixed-strategy equilibrium in a deterministic game: the probabilities here can reflect unobserved payoff variation, not only deliberate randomization among equally good actions.

A common numerical method starts with a probability vector $p^{(0)}$ and repeatedly applies the mapping: $p^{(k+1)}=T(p^{(k)})$. For two-action entry games, each player’s probability is a single number in $[0,1]$. A returned value is only a candidate until its residual, the difference between the proposed probability and the probability implied by the mapping, is checked. For example, a numerical tolerance $\varepsilon$ can require $\max_i |p_i-T_i(p_{-i})|<\varepsilon$.

Worked Example: Solving a Two-Firm Entry Fixed Point

Suppose each of two firms chooses enter or stay out. Let $q_j$ be firm $j$’s entry probability. Firm $i$’s payoff difference between entering and staying out is $-1+2q_j+\epsilon_i$, where $\epsilon_i$ has a standard logistic distribution, independently across firms. The standard logistic cumulative distribution function is $\Lambda(z)=1/(1+\exp(-z))$. Since the shock difference is included in the payoff comparison, firm $i$’s entry probability is $$ q_i=\Lambda(-1+2q_j). $$ In a symmetric equilibrium, $q_i=q_j=q$, so the fixed-point equation is $q=\Lambda(-1+2q)$.

The value $q=0.5$ satisfies the equation: $-1+2(0.5)=0$, and $\Lambda(0)=0.5$. To check whether simple iteration approaches this value, start at $q^{(0)}=0$. The successive calculations are $$ q^{(1)}=\Lambda(-1)=0.2689,\qquad q^{(2)}=\Lambda(-1+2(0.2689))=\Lambda(-0.4622)=0.3865, $$ $$ q^{(3)}=\Lambda(-1+2(0.3865))=\Lambda(-0.2270)=0.4435. $$ The iterates move toward $0.5$. At the proposed solution, the residual is $ |0.5-\Lambda(0)|=0$, so it satisfies the fixed-point equation. The calculation is conditional on the stated logistic-shock specification; it is not a deterministic pure-action profile.

Convergence, Starting Values, and Multiple Solutions

A fixed point is a solution to an equation; it does not guarantee that a particular iterative algorithm will find that solution from every starting value. A useful sufficient condition is contraction: if the mapping sends a closed set into itself and changes distances by at most a constant factor $c<1$, then repeated application converges to a unique fixed point in that set. In one dimension, a differentiable mapping with $|T'(q)|<1$ near a fixed point is locally stable under iteration. A derivative larger than one in absolute value indicates local instability, not that the fixed point fails the equilibrium equation.

For a vector mapping, the Jacobian matrix summarizes how small changes in current probabilities affect the next iterate. A spectral radius below one is a sufficient local condition for convergence near a fixed point. These conditions are diagnostics, not substitutes for checking the equation itself. In particular, if there are multiple fixed points, a solver’s convergence from one starting value establishes neither uniqueness nor which other solutions exist.

Worked Example: Starting Values Reveal Different Fixed Points

Consider a symmetric entry-probability mapping $T(q)=\Lambda(-3+6q)$. Fixed points solve $q=T(q)$. Direct substitution shows $q=0.5$ is a fixed point. Numerical solution also gives two additional fixed points, approximately $0.0707$ and $0.9293$. The symmetry follows from $\Lambda(-z)=1-\Lambda(z)$: if $q$ is a fixed point, then $1-q$ is also one.

The derivative is $T'(q)=6\Lambda(-3+6q)[1-\Lambda(-3+6q)]$. At a fixed point this becomes $6q(1-q)$. At $q=0.5$, it equals $1.5$, so iteration is locally unstable there. At either outer fixed point it is approximately $6(0.0707)(0.9293)=0.394$, so each is locally stable. For example, starting at $q^{(0)}=0.05$ gives $q^{(1)}=\Lambda(-2.7)=0.0630$, moving toward the lower fixed point. Starting at $q^{(0)}=0.95$ gives $q^{(1)}=\Lambda(2.7)=0.9370$, moving toward the upper one. A start exactly at $0.5$ remains there in exact arithmetic, although small perturbations move away. Therefore, the converged result depends on the starting value, and one run would not reveal all three solutions.

Implementation and Verification

For small deterministic games, enumeration is often preferable to an iterative best-response routine because it checks every pure profile directly. For larger games or payoff-shock models, fixed-point iteration can be convenient, but the implementation should preserve valid probability vectors and report convergence diagnostics. Useful practice includes running several starting values, recording the stopping rule and residual, and checking each returned candidate against the original equilibrium conditions.

If an update uses simultaneous best responses, it may cycle, as matching pennies demonstrates. Replacing a full update with a damped update such as $p^{(k+1)}=\lambda T(p^{(k)})+(1-\lambda)p^{(k)}$, for $0<\lambda<1$, can sometimes improve stability, but does not guarantee convergence or identify every equilibrium. A damped output still needs a residual check using the original mapping $T$, not just the damped update.

The calculation also depends on how expected payoffs or choice probabilities are evaluated. If numerical integration or simulation approximates them, approximation error can make an apparent fixed point differ from the exact model’s solution. Use sufficiently accurate integration, assess whether results change with increased simulation precision, and distinguish numerical tolerance from sampling or model uncertainty. These are separate sources of uncertainty.

Common Mistakes

Checking only the selected actions. A profile is not verified until every player’s payoff from every unilateral deviation has been compared with the prescribed payoff.
Treating convergence as proof of uniqueness. An iteration can find one fixed point while other solutions exist. Use multiple starts or a more exhaustive method when finding all solutions matters.
Treating a small update as an equilibrium check. Iterates can move only slightly because of damping or numerical precision. Evaluate the residual in the original fixed-point equation.
Confusing a cycle with nonexistence. An algorithm that cycles has failed to converge; its behavior alone says nothing about whether an equilibrium exists.
Calling every choice probability a mixed strategy. In a payoff-shock model, probabilities can arise from unobserved heterogeneity. State which model’s equilibrium condition is being solved.

Key takeaway: Generate equilibrium candidates with a method suited to the model, then check them against the original payoff-maximization or fixed-point conditions. Record convergence, residuals, and sensitivity to starting values; do not treat a solver’s output as self-verifying.

Check Your Understanding

Use the equilibrium conditions and numerical diagnostics, not the behavior of an algorithm alone.

In a finite game, what payoff comparisons must hold for a pure profile to be a Nash equilibrium?
Why can enumerating pure profiles fail to find a mixed-strategy equilibrium?
For a choice-probability iteration, what residual would you calculate to verify a returned vector?
What does a derivative with absolute value greater than one at a scalar fixed point imply for local fixed-point iteration?
Why should a computation be repeated from multiple starting values when multiple equilibria may exist?