Skip to content

Instantly share code, notes, and snippets.

@scheibo
Last active February 7, 2026 03:54
Show Gist options
  • Select an option

  • Save scheibo/1dd2111db184e059084af2de961b69f2 to your computer and use it in GitHub Desktop.

Select an option

Save scheibo/1dd2111db184e059084af2de961b69f2 to your computer and use it in GitHub Desktop.
Nash Equilibrium using Linear Programming Solvers

Problem

$$\begin{pmatrix} 3 & 2 & 5\\ 1 & 4 & 2\\ 4 & 3 & 3 \end{pmatrix} $$

lrsnash

3 3

3 2 5
1 4 2
4 3 3

-3 -2 -5
-1 -4 -2
-4 -3 -3

GLPK

Note the strategies are reversed as is the sign on the expected payoff - P1 is min player and is computing the minimum payoff for the max player P2

P1

var v;
var x1 >= 0;
var x2 >= 0;
var x3 >= 0;

minimize z:     v;

subject to c11: -3*x1 + -1*x2 + -4*x3 <= v;
subject to c12: -2*x1 + -4*x2 + -3*x3 <= v;
subject to c13: -5*x1 + -2*x2 + -3*x3 <= v;
subject to c14: x1 + x2 + x3 = 1;

end;

P2

var v;
var x1 >= 0;
var x2 >= 0;
var x3 >= 0;

maximize z:     v;

subject to c11: 3*x1 + 1*x2 + 4*x3 >= v;
subject to c12: 2*x1 + 4*x2 + 3*x3 >= v;
subject to c13: 5*x1 + 2*x2 + 3*x3 >= v;
subject to c14: x1 + x2 + x3 = 1;

end;  

Gambit

NFG 1 R "Game"
{ "P1" "P2" } { 3 3 }

3 -3 1 -1 4 -4 2 -2 4 -4 3 -3 5 -5 2 -2 3 -3
@scheibo
Copy link
Copy Markdown
Author

scheibo commented Feb 7, 2026

the Pokémon use case involves solving zero sum games on exclusively small dimension matrices and the AI use case can often afford to trade accuracy for speed (an ε-Nash equilibrium is sufficient for small enough ε).

lrsnash

  • all equilibria
  • exact precision
  • arbitrary sum
  • arbitrary matrix size

want: fast nash equlibrium solver

  • assume zero sum (only need one matrix)
  • assume matrix is at most 9x9
  • just return first equilibria (might be worse off if playing imperfect opponent)
  • approximate precision (using floats behind the scenes = need to worry about number stability, will have less accurate answer)
  • optionally: have different modes for one vs. all equilibria & BigRational vs. fixed precision rational (no allocs) vs. double

when calling, quantized floats quantized (if all are assumed to be int values out of 128 then can just use plain ints and no fractions, howeber, under hood needs to use something...)

COMPARE AGAINST lrsnash as oracle

  • arbitrary integers (1-128)
  • all weights need to sum to 1 (or whatever quantity is being used to quantize) - not really if things round poorly?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment