Nash Equilibrium Solver

A simple Nash Equilibrium solver for two-player zero-sum games implemented in python.

Usage

Please install requirements after cloning the repo:

pip3 install -e .

We include some simple games in examples (e.g., Rock-Paper-Scissor, Matching-Pennies, Presidential-Election-Game). For example, if you want to try Rock-Paper-Scissor example, please run

python3 main.py --example rock_paper_scissor

You are welcome to contribute more fun games via pull-requests!

How to solve

The Nash equilibrium problem for two-player zero-sum games (2p0s) can be expressed as a linear program (LP), which means that equilibria can be computed in polynomial time. However, the problem of finding a sample Nash equilibrium of a general-sum finite game with two or more players is PPAD-complete.

For 2p0s such as $G=({p1, p2}, A_1\times A_2, (u_1, u_2))$, where $A_1$ ($A_2$) is the action set for player 1 (player 2), and $u_1$ ($u_2$) is the utility function for player 1 (player 2), we can formulate and solve the following LP to obtain the expected utility $U_1^*$ for player 1 and player 2's action probabilities $s_2^k$ at the Nash Equilibrium profile (player 1's strategy can be solved similarly):

Why does the above formulation can give us a NE? The main reason is the well-known Minmax Theorem (von Neumann, 1928). Intuitively,

• the minmax strategy for player 1 against player 2 is a strategy that keeps the maximum payoff of player 2 at a minimum;
• the maxmin strategy for player 1 against player 2 is a strategy that maximizes player 1's worst-case payoff assuming player 2 is playing the strategies which cause the greatest harm to player 1.

John von Neumann tells us that for any finite 2p0s, any NE profile gives player a payoff which equals to both his minmax value and his maxmin value :)

TODO

The current version use Gurobi as the LP solver, which requires license though. We plan to implement a cvxpy version as solver as well.

References

Shoham, Yoav, and Kevin Leyton-Brown. Multiagent systems: Algorithmic, game-theoretic, and logical foundations. Cambridge University Press, 2008.