Reference: Algorithms to Compute Nash Equilibria

This appendix is an overview of the literature on computing Nash equilibria in finite games. The focus here is on detailing the essentials of the theory for the user who wants to compute equilibria, and to document the implementations of the algorithms provided in Gambit. The interested user should consult McKelvey and McLennan's survey article [McKMcL96], plus the references therein and the bibliography of this manual for more information.

Tips on getting started

Gambit has a number of algorithms to find Nash equilibria. The appropriate algorithm to use depends on a number of factors, most importantly, the number of players in the game, and the number of equilibria you want to find.

Before computing equilibria, you may wish to eliminate dominated strategies. The smaller the number of strategies the algorithm must consider, the faster any algorithm will run. However, dominance elimination can itself be computationally intensive, especially if domination by mixed strategies (for the normal form) is considered, or if dominance elimination is done on a large extensive form.

Common algorithm parameters

There are a few parameters which are common among several algorithms.

Pure strategy equilibria

The EnumPureSolve algorithm can be used to enumerate all of the pure strategy equilibria for both extensive and normal form games.

Two Person Constant Sum Games

For two person constant sum normal form games, the minimax theorem applies. The set of Nash equilibria is a convex set, and the problem of finding Nash equilibria can be formulated as a linear program. The LpSolve algorithm will solve a constant sum game using this approach.

Two Person Games

For two person nonzero sum games, the problem of finding Nash equilibria can be formulated as a linear complementarity problem, and exact solutions can be found as long as computations are done in rationals. The LcpSolve algorithm solves a two person game using this approach. Note that this algorithm can also be used directly on an extensive form game, where it implements the Koller, Megiddo, von Stengel sequence form [KolMegSte94].

For a two person game the EnumMixedSolve algorithm will enumerate all of the extreme points of the components of the set of Nash equilibria, and hence can be used to find all Nash equilibria.

Games With More Than Two Players

For n-person normal form games, with n greater than two, the PolEnumSolve algorithm will find all Nash equilibria. The PolEnum algorithm may be computationally infeasible on large games. Thus other algorithms are also available for finding one or a sample of Nash equilibria. Since Nash equilibria can be irrational, the algorithms to locate one equilibrium will only find approximations (to machine accuracy) of Nash equilibria.

SimpDivSolveSimpDivSolve is guaranteed to locate one equilibrium for an n-person normal form game. This algorithm can be very slow on some games. Hence two other algorithms are also implemented, QreSolve and LiapSolve. These algorithms can also be used to search for multiple equilibria (with no guarantee that all have been found), and to search for equilibria close to a given starting point.

Sequential Equilibria

Sequential equilibria are equilibria that prescribe optimal behavior at any information set of the extensive form, given a consistent assessment of beliefs. See [KreWil82]. QreSolve on extensive form games is guaranteed to converge to a sequential equilibrium.