Skip to content
Tutorials Center
My learning

Topics

Lesson 17 of 37 ยท Mixed Strategies

Mixed Equilibria in Larger Games: Support Enumeration

Solve any bimatrix game by support enumeration: guess which actions are played, solve the indifference equations with NumPy linear algebra, and keep the profiles with no profitable deviation.

The formulas of the previous lesson only cover 2x2 games. For a game with three, four or more actions, we need a method that scales. The idea behind it is the one you already know: in a mixed equilibrium, every action in a player's support gives the same expected payoff. If we guess the supports, the equilibrium probabilities are the solution of a small system of linear equations. Then we check that no action outside the support would be better. Trying all supports gives every equilibrium. This is support enumeration.

Support enumeration is exponential in the number of actions, so real software uses cleverer algorithms (Lemke-Howson, for instance). But for the games in this course, and for understanding what a Nash equilibrium really is, it is exactly the right tool: short, exact, and easy to trust.

The idea in three steps

Let Ann have actions I (a chosen subset of her rows) and Bob a subset J of his columns, both of the same size k. (In a non-degenerate game equilibrium supports have equal size.)

  1. Bob's mix makes Ann indifferent on I. Find y supported on J and a number v with A[I, J] @ y_J = v for every row in I, and sum(y_J) = 1. That is k + 1 linear equations in k + 1 unknowns (y_J and v).
  2. Ann's mix makes Bob indifferent on J. Find x supported on I and w with x_I @ B[I, J] = w for every column in J, and sum(x_I) = 1.
  3. Check. All probabilities must be positive, and no action outside the support may be better: A @ y <= v for all rows, x @ B <= w for all columns.
flowchart TD
    S["Pick supports I (rows), J (columns)"] --> L1["Solve for y:<br/>A[I,J] y = v, sum y = 1"]
    S --> L2["Solve for x:<br/>x B[I,J] = w, sum x = 1"]
    L1 --> C["Probabilities positive?<br/>No outside action better?"]
    L2 --> C
    C -->|"yes"| E["Equilibrium found"]
    C -->|"no"| N["Try the next supports"]

Guess the supports, solve linear equations, then verify.

The algorithm in code

The linear system for y has the block form

Text
[ A[I,J]  -1 ] [ y ]   [ 0 ]
[ 1...1    0 ] [ v ] = [ 1 ]

and similarly for x with the transpose of B[I,J]. We solve with np.linalg.solve and skip supports that give a singular system.

Python Support enumeration for bimatrix games

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

We get three equilibria: the two pure ones (supports of size 1) and the mixed one with x = (0.6, 0.4) and y = (0.4, 0.6). This matches the 2x2 formula.

Rock-paper-scissors and a 3x3 game

Let us run the solver on bigger games. Rock-paper-scissors has exactly one equilibrium, the uniform mix. A less symmetric 3x3 game can have several equilibria, with supports of different sizes.

Python Equilibria of 3x3 games

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The second game has seven equilibria: three pure ones on the diagonal, three mixed ones on two actions each, and one fully mixed equilibrium using all three actions. It follows from a deep theorem that a non-degenerate game has an odd number of equilibria. You can use the count as a sanity check on your results: if your solver found an even number, either the game is degenerate or something is missing.

Degenerate games

In a degenerate game, some action has the same payoff as a mixture of others in an unlucky way, so there can be continuums of equilibria or supports of different sizes (a player mixes over two actions while the opponent mixes over three). Support enumeration with equal-size supports then misses some. The fix is to try all pairs of supports of any sizes and solve a least-squares or linear programming problem. Such cases arise with ties, for example in games with many zero payoffs. If your game has ties, double-check with another method, such as the linear programming approach for zero-sum games.

Verifying and using the equilibria

Once you have the equilibria you can compute their properties: payoffs, welfare, and whether they are Pareto efficient. Because of the multiplicity you may need the selection criteria from Multiple Equilibria and Selection.

Python Compare the equilibria of a game

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Chicken has three equilibria: two asymmetric pure ones with welfare 6, and the symmetric mixed one with welfare 5. The mixed one is the worst for the group, because with probability 1/4 both drivers go straight and crash.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the key condition used to compute y for a chosen support pair (I, J)?

    Ann is willing to mix over the rows in I only if they all give her the same expected payoff, so Bob's y must make them equal.
  2. 2. After solving the equations, which checks remain?

    A guessed support can give negative probabilities, and an outside action may be a profitable deviation. Both must be ruled out.
  3. 3. A non-degenerate bimatrix game has how many Nash equilibria (counting pure and mixed)?

    A classical theorem states that non-degenerate finite games have an odd number of equilibria, which is a good sanity check.
  4. 4. Why does support enumeration become impractical for large games?

    There are 2^m subsets of rows and 2^n of columns, so the search space explodes; real solvers use smarter algorithms.

Summary

  • In a mixed equilibrium each player's support actions give equal payoffs, so supports determine the probabilities through linear equations.
  • Support enumeration tries every pair of equal-size supports, solves two small linear systems and keeps the profiles with positive probabilities and no profitable outside deviation.
  • It finds all equilibria of a non-degenerate bimatrix game, and the number found should be odd.
  • Degenerate games (ties) may need unequal supports or another method.
  • The search is exponential, so large games call for dedicated algorithms.

Next: The Minimax Theorem and Linear Programming