.. _algorithms: Equilibrium computation ======================= The table below summarizes the available PyGambit functions and corresponding Gambit CLI programs for algorithms for computing Nash equilibria. ================ =========================================================================== ======================================== ========================================== Algorithm Description PyGambit function CLI command ================ =========================================================================== ======================================== ========================================== :ref:`enumpure` Enumerate pure-strategy equilibria of a game :py:func:`pygambit.nash.enumpure_solve` :ref:`gambit-enumpure ` :ref:`enummixed` Enumerate equilibria in a two-player game :py:func:`pygambit.nash.enummixed_solve` :ref:`gambit-enummixed ` :ref:`enumpoly` Compute equilibria of a game using polynomial systems of equations :py:func:`pygambit.nash.enumpoly_solve` :ref:`gambit-enumpoly ` :ref:`lp` Compute equilibria in a two-player constant-sum game via linear programming :py:func:`pygambit.nash.lp_solve` :ref:`gambit-lp ` :ref:`lcp` Compute equilibria in a two-player game via linear complementarity :py:func:`pygambit.nash.lcp_solve` :ref:`gambit-lcp ` :ref:`liap` Compute equilibria using function minimization :py:func:`pygambit.nash.liap_solve` :ref:`gambit-liap ` :ref:`logit` Compute quantal response equilibria :py:func:`pygambit.nash.logit_solve` :ref:`gambit-logit ` :ref:`simpdiv` Compute equilibria via simplicial subdivision :py:func:`pygambit.nash.simpdiv_solve` :ref:`gambit-simpdiv ` :ref:`ipa` Compute equilibria using iterated polymatrix approximation :py:func:`pygambit.nash.ipa_solve` :ref:`gambit-ipa ` :ref:`gnm` Compute equilibria using a global Newton method :py:func:`pygambit.nash.gnm_solve` :ref:`gambit-gnm ` ================ =========================================================================== ======================================== ========================================== .. _enumpure: enumpure -------- Searches for pure-strategy Nash or agent Nash equilibria. .. _enummixed: enummixed --------- Computes Nash equilibria using extreme point enumeration. In a two-player strategic game, the set of Nash equilibria can be expressed as the union of convex sets. This program generates all the extreme points of those convex sets. (Mangasarian [Man64]_) This is a superset of the points generated by the path-following procedure of Lemke and Howson (see :ref:`lcp`). It was shown by Shapley [Sha74]_ that there are equilibria not accessible via the method in :ref:`lcp`, whereas the output of :program:`enummixed` is guaranteed to return all the extreme points. .. _enumpoly: enumpoly -------- Computes Nash equilibria by solving systems of polynomial equations and inequalities. This program searches for all Nash equilibria in a strategic game using a support enumeration approach. This approach computes all the supports which could, in principle, be the support of a Nash equilibrium. For each candidate support, it attempts to compute totally mixed equilibria on that support by successively subdividing the space of mixed strategy profiles or mixed behavior profiles (as appropriate). By using the fact that the equilibrium conditions imply a collection of equations and inequalities which can be expressed as multilinear polynomials, the subdivision constructed is such that each cell contains either no equilibria or exactly one equilibrium. For strategic games, the program searches supports in the order proposed by Porter, Nudelman, and Shoham [PNS04]_. For two-player games, this prioritises supports for which both players have the same number of strategies. For games with three or more players, this prioritises supports which have the fewest strategies in total. For many classes of games, this will tend to lower the average time until finding one equilibrium, as well as finding the second equilibrium (if one exists). For extensive games, a support of actions equates to allowing positive probabilities over a subset of terminal nodes. The indifference conditions used are those for the sequence form defined on the projection of the game to that support of actions. A solution to these equations implies a probability distribution over terminal nodes. The algorithm then searches for a profile that is a Nash equilibrium that implements that probability distribution. If there exists at least one such profile, a sample one is returned. Note that for probability distributions which assign zero probability to some terminal nodes, it is generally the case that there are (infinitely) many such profiles. Subsequent analysis of unreached information sets can yield alternative profiles that specify different choices at unreached information sets while still satisfying the Nash equilibrium conditions. .. _lp: lp --- Computes a Nash equilibrium in a two-player game by solving a linear program. For extensive games, the program uses the sequence form formulation of Koller, Megiddo, and von Stengel [KolMegSte94]_. While the set of equilibria in a two-player constant-sum strategic game is convex, this method will only identify one of the extreme points of that set. .. _lcp: lcp --- Computes Nash equilibria of a two-player game by finding solutions to a linear complementarity problem. For extensive games, the program uses the sequence form representation of the extensive game, as defined by Koller, Megiddo, and von Stengel [KolMegSte94]_, and applies the algorithm developed by Lemke. For strategic games, the program uses the method of Lemke and Howson [LemHow64]_. In this case, the method will find all "accessible" equilibria, i.e., those that can be found as concatenations of Lemke-Howson paths that start at the artificial equilibrium. There exist strategic-form games for which some equilibria cannot be found by this method, i.e., some equilibria are inaccessible; see Shapley [Sha74]_. In a two-player strategic game, the set of Nash equilibria can be expressed as the union of convex sets. This program will find extreme points of those convex sets. See :ref:`enummixed` for a method which is guaranteed to find all the extreme points for a strategic game. .. _liap: liap ---- Computes approximate Nash equilibria using a function minimization approach. This procedure searches for equilibria by generating random starting points and using conjugate gradient descent to minimize the Lyapunov function of the game. This is a nonnegative function which is zero exactly at strategy profiles which are Nash equilibria. Note that this procedure is not globally convergent. That is, it is not guaranteed to find all, or even any, Nash equilibria. .. _logit: logit ----- Computes the principal branch of the (logit) quantal response correspondence. The method is based on the procedure described in Turocy [Tur05]_ for strategic games and Turocy [Tur10]_ for extensive games. It uses standard path-following methods (as described in Allgower and Georg's "Numerical Continuation Methods") to adaptively trace the principal branch of the correspondence efficiently and securely. The method used is a predictor-corrector method, which first generates a prediction using the differential equations describing the branch of the correspondence, followed by a corrector step which refines the prediction using Newton's method for finding a zero of a function. Two parameters control the operation of this tracing. The algorithm accepts an initial step size for the predictor phase of the tracing. This step size is then dynamically adjusted based on the rate of convergence of Newton's method in the corrector step. If the convergence is fast, the step size is adjusted upward (accelerated); if it is slow, the step size is decreased (decelerated). The maximum acceleration (or deceleration) can be set as an argument. As described in Turocy [Tur05]_, this acceleration helps to efficiently trace the correspondence when it reaches its asymptotic phase for large values of the precision parameter lambda. In extensive games, logit quantal response equilibria are not well-defined if an information set is not reached due to being the successor of chance moves with zero probability. In such games, the implementation treats the beliefs at such information sets as being uniform across all member nodes. .. _simpdiv: simpdiv -------- Computes approximations to Nash equilibria using a simplicial subdivision approach. This program implements the algorithm of van der Laan, Talman, and van Der Heyden [VTH87]_. The algorithm proceeds by constructing a triangulated grid over the space of mixed strategy profiles, and uses a path-following method to compute an approximate fixed point. This approximate fixed point can then be used as a starting point on a refinement of the grid. The program continues this process with finer and finer grids until locating a mixed strategy profile at which the maximum regret is small. .. _ipa: ipa --- Computes Nash equilibria using an iterated polymatrix approximation approach developed by Govindan and Wilson [GovWil04]_. This program is based on the `Gametracer 0.2 `_ implementation by Ben Blum and Christian Shelton. The algorithm takes as a parameter a mixed strategy profile. This profile is interpreted as defining a ray in the space of games. The profile must have the property that, for each player, the most frequently played strategy must be unique. .. _gnm: gnm --- Computes Nash equilibria using a global Newton method approach developed by Govindan and Wilson [GovWil03]_. This program is based on the `Gametracer 0.2 `_ implementation by Ben Blum and Christian Shelton. The algorithm takes as a parameter a mixed strategy profile. This profile is interpreted as defining a ray in the space of games. The profile must have the property that, for each player, the most frequently played strategy must be unique.