Nash Equilibrium and SPNE Solvers

Two small, dependency-light solvers for finite two-player games:

• nash_equilibrium.py — fully-mixed Nash equilibrium for an m × n normal-form game, by linear programming. See Limitations.
• spne_solver.py — subgame-perfect equilibrium for extensive-form games, by backward induction.

Mixed-strategy Nash

The idea is the standard one: at equilibrium each player's strategy makes the opponent indifferent between all of their pure strategies. That indifference condition is a linear program, so a two-player game takes two solves — one per side.

For a strategy vector x over our own pure strategies, with payoff[k][t] the opponent's payoff when they play k and we play t:

for every k:   sum_t payoff[k][t] · x_t  =  v
               sum_t x_t                 =  1
maximise v

Each equality becomes a pair of ≤ constraints, and v — the common payoff value — rides along as an extra variable. The row player's strategy is found from the column player's payoff matrix transposed, which is the same program with the game turned on its side.

from nash_equilibrium import find_nash_equilibrium

# Matching pennies
u1 = [[1, -1], [-1, 1]]
u2 = [[-1, 1], [1, -1]]

p, q = find_nash_equilibrium(u1, u2)
# p == [0.5, 0.5], q == [0.5, 0.5]

u1 and u2 are both m × n, indexed [row_player_strategy][column_player_strategy]. The returned vectors are length m and n respectively.

Limitations

The Nash solver finds equilibria in which each player randomises over all of their pure strategies — the indifference LP requires the opponent to be indifferent across their whole strategy set. Many games have no such equilibrium; their equilibria put zero weight on some strategies, and finding those needs support enumeration, which this does not do.

When the LP is infeasible the solver returns the uniform distribution, which is a placeholder and not an equilibrium. Pass strict=True to get an exception instead of a silently wrong answer:

from nash_equilibrium import find_nash_equilibrium, NoEqualisingEquilibrium

try:
    p, q = find_nash_equilibrium(u1, u2, strict=True)
except NoEqualisingEquilibrium:
    ...  # equilibrium has partial support; not handled here

Zero-sum games always have a fully-mixed equalising equilibrium when no saddle point exists, so matching pennies and rock-paper-scissors are solved exactly.

Subgame-perfect equilibrium

solve_spne(nodes, root_id) walks an extensive-form game tree bottom-up. Each decision node picks the child maximising its own player's payoff; each terminal node carries a payoff vector. It returns the actions along the equilibrium path and the payoffs reached.

from spne_solver import solve_spne

nodes = [
    {"id": 0, "player": 1, "actions": [{"action": "L", "child": 1},
                                       {"action": "R", "child": 2}]},
    {"id": 1, "payoffs": [3, 1]},
    {"id": 2, "payoffs": [2, 4]},
]

actions, payoffs = solve_spne(nodes, root_id=0)
# actions == ["L"], payoffs == [3, 1]

Command line

Both solvers read a game on stdin. For Nash, that is the dimensions m n, then m rows of n integers for the row player, then m rows for the column player:

echo "2 2
1 -1
-1 1
-1 1
1 -1" | python nash_equilibrium.py

Ready-made inputs are in examples/, with run_nash_examples.sh (and a PowerShell equivalent) to run them all.

Tests

pip install -r requirements.txt
python test_nash.py
python test_spne.py

The Nash suite covers matching pennies, a coordination game, arbitrary payoffs, a pure-strategy equilibrium, a 2×2 case checked against its closed-form solution, a non-square 3×2 game, and a game with no fully-mixed equilibrium (which must raise in strict mode). Each result is verified against the equilibrium conditions directly — probabilities sum to one, and no pure strategy played with positive probability is beaten by another. The SPNE suite checks four trees against hand-computed backward-induction results.

Third-party code

simplex.py and simplex.h are not part of this project's original work. They are the linear-programming solver from the Stanford ACM Notebook, MIT-licensed, vendored here so the solvers run without external LP dependencies. The C++ original retains its upstream header.

Everything else — the equilibrium formulations, the backward-induction solver, the tests and the examples — is original.

License

MIT. Third-party attribution is in NOTICE.

---

Originally written for a university game theory course.