Welcome to Gambit#
Gambit is a library of game theory software and tools for the construction and analysis of finite extensive and strategic games. Gambit is fully-cross platform, and is supported on Linux, Mac OS X, and Microsoft Windows.
Key features of Gambit include:
A graphical user interface, which uses wxWidgets to provide a common interface with native look-and-feel across platforms.
All equilibrium-computing algorithms are available as command-line tools, callable from scripts and other programs.
A Python API for developing scripting applications.
Gambit is Free/Open Source software, released under the terms of the GNU General Public License, Version 2.
We hope you will find Gambit useful for both teaching and research applications. If you do use Gambit in a class, or in a paper, we would like to hear about it. We are especially interested in finding out what you like about Gambit, and where you think improvements could be made.
If you are citing Gambit in a paper, we suggest a citation of the form:
Savani, Rahul and Turocy, Theodore L. (2024) Gambit: The package for computation in game theory, Version 16.2.0. http://www.gambit-project.org.
Replace the version number and year as appropriate if you use a different release.
All Gambit’s methods for equilibrium computation are available via command-line programs.
Gambit’s graphical interface lets you interactively create, explore, and find equilibria of games.
An overview of Gambit#
What is Gambit?#
Gambit is a set of software tools for doing computation on finite, noncooperative games. These comprise a graphical interface for interactively building and analyzing general games in extensive or strategy form; a number of command-line tools for computing Nash equilibria and other solution concepts in games; and, a set of file formats for storing and communicating games to external tools.
A brief history of Gambit#
The Gambit Project was founded in the mid-1980s by Richard McKelvey at the California Institute of Technology. The original implementation was written in BASIC, with a simple graphical interface. This code was ported to C around 1990 with the help of Bruce Bell, and was distributed publicly as version 0.13 in 1991 and 1992.
A major step in the evolution of Gambit took place with the awarding of the NSF grants in 1994, with McKelvey and Andrew McLennan as principal investigators, and Theodore Turocy as the head programmer. The grants sponsored a complete rewrite of Gambit in C++. The graphical interface was made portable across platforms through the use of the wxWidgets library (http://www.wxwidgets.org). Version 0.94 of Gambit was released in the late summer of 1994, version 0.96 followed in 1999, and version 0.97 in 2002. During this time, many students at Caltech and Minnesota contributed to the effort by programming, testing, and/or documenting. These include, alphabetically, Bruce Bell, Anand Chelian, Matthew Derer, Nelson Escobar, Ben Freeman, Eugene Grayver, Todd Kaplan, Geoff Matters, Brian Trotter, Michael Vanier, Roberto Weber, and Gary Wu.
Over the same period, Bernhard von Stengel, of the London School of Economics, made significant contributions in the implementation of the sequence form methods for two-player extensive games, and for contributing his “clique” code for identification of equilibrium components in two-player strategic games, as well as other advice regarding Gambit’s implementation and architecture.
Development since the mid-2000s has focused on two objectives. First, the graphical interface was reimplemented and modernized, with the goal of following good interaction design principles, especially in regards to easing the learning curve for users new to Gambit and new to game theory. Second, the internal architecture of Gambit was refactored to increase interoperability between the tools provided by Gambit and those written independently.
Gambit is proud to have participated in the Google Summer of Code program in the summers of 2011 and 2012 as a mentoring organization. The Python API, which became part of Gambit from Gambit 13, was developed during these summers, thanks in particular to the work of Stephen Kunath and Alessandro Andrioni.
Key features of Gambit#
Gambit has a number of features useful both for the researcher and the instructor:
Interactive, cross-platform graphical interface. All Gambit features are available through the use of a graphical interface, which runs under multiple operating systems: Windows, various flavors of Un*x (including Linux), and Mac OS X. The interface offers flexible methods for creating extensive and strategic games. It offers an interface for running algorithms to compute Nash equilibria, and for visualizing the resulting profiles on the game tree or table, as well as an interactive tool for analyzing the dominance structure of actions or strategies in the game. The interface is useful for the advanced researcher, but is intended to be accessible for students taking a first course in game theory as well.
Command-line tools for computing equilibria. More advanced applications often require extensive computing time and/or the ability to script computations. All algorithms in Gambit are packaged as individual, command-line programs, whose operation and output are configurable.
Extensibility and interoperability. The Gambit tools read and write file formats which are textual and documented, making them portable across systems and able to interact with external tools. It is therefore straightforward to extend the capabilities of Gambit by, for example, implementing a new method for computing equilibria, reimplementing an existing one more efficiently, or creating tools to programmatically create, manipulate, and transform games, or for econometric analysis on games.
Limitations of Gambit#
Gambit has a few limitations that may be important in some applications. We outline them here.
Gambit is for finite games only. Because of the mathematical structure of finite games, it is possible to write many general- purpose routines for analyzing these games. Thus, Gambit can be used in a wide variety of applications of game theory. However, games that are not finite, that is, games in which players may choose from a continuum of actions, or in which players may have a continuum of types, do not admit the same general-purpose methods.
Gambit is for noncooperative game theory only. Gambit focuses on the branch of game theory in which the rules of the game are written down explicitly, and in which players choose their actions independently. Gambit’s analytical tools center primarily around Nash equilibrium, and related concepts of bounded rationality such as quantal response equilibrium. Gambit does not at this time provide any representations of, or methods for, analyzing games written in cooperative form. (It should be noted that some problems in cooperative game theory do not suffer from the computational complexity that the Nash equilibrium problem does, and thus cooperative concepts could be an interesting future direction of development.)
Analyzing large games may become infeasible surprisingly quickly. While the specific formal complexity classes of computing Nash equilibria and related concepts are still an area of active research, it is clear that, in the typical case, the amount of time required to compute equilibria increases rapidly in the size of the game. In other words, it is quite easy to write down games which will take Gambit an unacceptably long amount time to compute the equilibria of. There are two ways to deal with this problem in practice. One way is to better identify good heuristic approaches for guiding the equilibrium computation process. Another way is to take advantage of known features of the game to guide the process. Both of these approaches are now becoming areas of active interest. While it will certainly not be possible to analyze every game that one would like to, it is hoped that Gambit will both contribute to these two areas of research, as well as make the resulting methods available to both students and practitioners.
Developers#
The principal developers of Gambit are:
Theodore Turocy, University of East Anglia: director.
Richard D. McKelvey, California Institute of Technology: project founder.
Andrew McLennan, University of Queensland: co-PI during main development, developer and maintainer of polynomial-based algorithms for equilibrium computation.
Much of the development of the main Gambit codebase took place in 1994-1996, under a grant from the National Science Foundation to the California Institute of Technology and the University of Minnesota (McKelvey and McLennan, principal investigators).
Others contributing to the development and distribution of Gambit include:
Bernhard von Stengel provided advice on implementation of sequence form code, and contributed clique code
Eugene Grayver developed the first version of the graphical user interface.
Gary Wu implemented an early scripting language interface for Gambit (since superseded by the Python API).
Stephen Kunath and Alessandro Andrioni did extensive work to create the first release of the Python API.
From Gambit 14, Gambit contains support for Action Graph Games [Jiang11]. This has been contributed by Navin Bhat, Albert Jiang, Kevin Leyton-Brown, and David Thompson, with funding support provided by a University Graduate Fellowship of the University of British Columbia, the NSERC Canada Graduate Scholarship, and a Google Research Award to Leyton-Brown.
Downloading Gambit#
Gambit source code and built binaries can be downloaded from the project `GitHub repository releases section`<gambitproject/gambit>.
Older versions of Gambit can be downloaded from http://sourceforge.net/projects/gambit/files.
Bug reports#
In the first instance, bug reports or feature requests should be posted to the Gambit issue tracker, located at gambitproject/gambit#issues.
When reporting a bug, please be sure to include the following:
The version(s) of Gambit you are using. (If possible, it is helpful to know whether a bug exists in both the current stable/teaching and the current development/research versions.)
The operating system(s) on which you encountered the bug.
A detailed list of steps to reproduce the bug. Be sure to include a sample game file or files if appropriate; it is often helpful to simplify the game if possible.
Command-line tools#
Gambit provides command-line interfaces for each method for computing Nash equilibria. These are suitable for scripting or calling from other programs. This chapter describes the use of these programs. For a general overview of methods for computing equilibria, see the survey of [McKMcL96].
The graphical interface also provides a frontend for calling these programs and evaluating their output. Direct use of the command-line programs is intended for advanced users and applications.
These programs take an extensive or strategic game file, which can be specified on the command line or piped via standard input, and output a list of equilibria computed. The default output format is to present equilibria computed as a list of comma-separated probabilities, preceded by the tag NE. For mixed strategy profiles, the probabilities are sorted lexicographically by player, then by strategy. For behavior strategy profiles, the probabilities are sorted by player, then information set, then action number, where the information sets for a player are sorted by the order in which they are encountered in a depth-first traversal of the game tree. Many programs take an option -D, which, if specified, instead prints a more verbose, human-friendly description of each strategy profile computed.
Many of the programs optionally output additional information about the operation of the algorithm. These outputs have other, program-specific tags, described in the individual program documentation.
gambit-enumpure: Enumerate pure-strategy equilibria of a game#
gambit-enumpure reads a game on standard input and searches for pure-strategy Nash equilibria.
Changed in version 14.0.2: The effect of the -S switch is now purely cosmetic, determining how the equilibria computed are represented in the output. Previously, -S computed using the strategic game; if this was not specified for an extensive game, the agent form equilibria were returned.
- -S#
Report equilibria in reduced strategic form strategies, even if the game is an extensive game. By default, if passed an extensive game, the output will be in behavior strategies. Specifying this switch does not imply any change in operation internally, as pure-strategy equilibria are defined in terms of reduced strategic form strategies.
- -D#
New in version 14.0.2.
The default output format for computed equilibria is a comma-separated list of strategy or action probabilities, suitable for postprocessing by automated tools. Specifying -D instead causes the program to output greater detail on each equilbrium profile computed.
- -A#
New in version 14.0.2.
Report agent form equilibria, that is, equilibria which consider only deviations at one information set. Only has an effect for extensive games, as strategic games have only one information set per player.
- -P#
By default, the program computes all pure-strategy Nash equilibria in an extensive game. This switch instructs the program to find only pure-strategy Nash equilibria which are subgame perfect. (This has no effect for strategic games, since there are no proper subgames of a strategic game.)
- -h#
Prints a help message listing the available options.
- -q#
Suppresses printing of the banner at program launch.
Computing the pure-strategy equilibria of extensive game e02.efg, the example in Figure 2 of Selten
(International Journal of Game Theory, 1975):
$ gambit-enumpure e02.efg
Search for Nash equilibria in pure strategies
Gambit version 16.2.0, Copyright (C) 1994-2024, The Gambit Project
This is free software, distributed under the GNU GPL
NE,1,0,0,0,1,0
With the -S switch, the set of equilibria returned is the same, except expressed in strategic game strategies rather than behavior strategies:
$ gambit-enumpure -S e02.efg
Search for Nash equilibria in pure strategies
Gambit version 16.2.0, Copyright (C) 1994-2024, The Gambit Project
This is free software, distributed under the GNU GPL
NE,1,0,0,1,0
The -A switch considers only behavior strategy profiles where there is no way for a player to improve his payoff by changing action at only one information set; therefore the set of solutions is larger:
$ gambit-enumpure -A e02.efg
Search for Nash equilibria in pure strategies
Gambit version 16.2.0, Copyright (C) 1994-2024, The Gambit Project
This is free software, distributed under the GNU GPL
NE,1,0,1,0,1,0
NE,1,0,1,0,0,1
NE,1,0,0,1,1,0
gambit-enummixed: Enumerate equilibria in a two-player game#
gambit-enummixed reads a two-player game on standard input and 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 gambit-lcp: Compute equilibria in a two-player game via linear complementarity). It was shown by Shapley [Sha74] that there are equilibria not accessible via the method in gambit-lcp: Compute equilibria in a two-player game via linear complementarity, whereas the output of gambit-enummixed is guaranteed to return all the extreme points.
- -d#
By default, this program computes using exact rational arithmetic. Since the extreme points computed by this method are guaranteed to be rational when the payoffs in the game are rational, this permits exact computation of the equilibrium set. Computation using rational arithmetic is in general slow, however. For most games, acceptable results can be obtained by computing using the computer’s native floating-point arithmetic. Using this flag enables computation in floating-point, and expresses all output using decimal representations with the specified number of digits.
- -D#
Since all Nash equilibria involve only strategies which survive iterative elimination of strictly dominated strategies, the program carries out the elimination automatically prior to computation. This is recommended, since it almost always results in superior performance. Specifying -D skips the elimination step and performs the enumeration on the full game.
- -c#
The program outputs the extreme equilibria as it finds them, prefixed by the tag NE . If this option is specified, once all extreme equilbria are identified, the program computes the convex sets which make up the set of equilibria. The program then additionally outputs each convex set, prefixed by convex-N , where N indexes the set. The set of all equilibria, then, is the union of these convex sets.
- -h#
Prints a help message listing the available options.
- -q#
Suppresses printing of the banner at program launch.
- -L#
Use lrslib by David Avis to carry out the enumeration process. This is an experimental feature that has not been widely tested.
Computing the equilibria, in mixed strategies, of e02.nfg, the reduced strategic form of the example
in Figure 2 of Selten (International Journal of Game Theory,
1975):
$ gambit-enummixed e02.nfg
Compute Nash equilibria by enumerating extreme points
Gambit version 16.2.0, Copyright (C) 1994-2024, The Gambit Project
Enumeration code based on lrslib 4.2b,
Copyright (C) 1995-2005 by David Avis (avis@cs.mcgill.ca)
This is free software, distributed under the GNU GPL
NE,1,0,0,1,0
NE,1,0,0,1/2,1/2
In fact, the game e02.nfg has a one-dimensional continuum of equilibria. This fact can be observed by examining the connectedness information using the -c switch:
$ gambit-enummixed -c e02.nfg
Compute Nash equilibria by enumerating extreme points
Gambit version 16.2.0, Copyright (C) 1994-2024, The Gambit Project
Enumeration code based on lrslib 4.2b,
Copyright (C) 1995-2005 by David Avis (avis@cs.mcgill.ca)
This is free software, distributed under the GNU GPL
NE,1,0,0,1,0
NE,1,0,0,1/2,1/2
convex-1,1,0,0,1/2,1/2
convex-1,1,0,0,1,0
gambit-lcp: Compute equilibria in a two-player game via linear complementarity#
gambit-lcp reads a two-player game on standard input and computes Nash equilibria 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 using the method of Lemke and Howson [LemHow64]. There exist strategic games for which some equilibria cannot be located by this method; 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 gambit-enummixed: Enumerate equilibria in a two-player game for a method which is guaranteed to find all the extreme points for a strategic game.
- -d#
By default, this program computes using exact rational arithmetic. Since the extreme points computed by this method are guaranteed to be rational when the payoffs in the game are rational, this permits exact computation of the equilibrium set. Computation using rational arithmetic is in general slow, however. For most games, acceptable results can be obtained by computing using the computer’s native floating-point arithmetic. Using this flag enables computation in floating-point, and expresses all output using decimal representations with the specified number of digits.
- -S#
By default, the program uses behavior strategies for extensive games; this switch instructs the program to use reduced strategic game strategies for extensive games. (This has no effect for strategic games, since a strategic game is its own reduced strategic game.)
- -D#
New in version 14.0.2.
The default output format for computed equilibria is a comma-separated list of strategy or action probabilities, suitable for postprocessing by automated tools. Specifying -D instead causes the program to output greater detail on each equilbrium profile computed.
- -P#
By default, the program computes Nash equilibria in an extensive game. This switch instructs the program to find only equilibria which are subgame perfect. (This has no effect for strategic games, since there are no proper subgames of a strategic game.)
- -h#
Prints a help message listing the available options.
- -q#
Suppresses printing of the banner at program launch.
Computing an equilibrium of extensive game e02.efg, the example in Figure 2 of Selten
(International Journal of Game Theory, 1975):
$ gambit-lcp e02.efg
Compute Nash equilibria by solving a linear complementarity program
Gambit version 16.2.0, Copyright (C) 1994-2024, The Gambit Project
This is free software, distributed under the GNU GPL
NE,1,0,1/2,1/2,1/2,1/2
gambit-lp: Compute equilibria in a two-player constant-sum game via linear programming#
gambit-lp reads a two-player constant-sum game on standard input and computes a Nash equilibrium by solving a linear program. The program uses the sequence form formulation of Koller, Megiddo, and von Stengel [KolMegSte94] for extensive games.
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.
- -d#
By default, this program computes using exact rational arithmetic. Since the extreme points computed by this method are guaranteed to be rational when the payoffs in the game are rational, this permits exact computation of an equilibrium. Computation using rational arithmetic is in general slow, however. For most games, acceptable results can be obtained by computing using the computer’s native floating-point arithmetic. Using this flag enables computation in floating-point, and expresses all output using decimal representations with the specified number of digits.
- -S#
By default, the program uses behavior strategies for extensive games; this switch instructs the program to use reduced strategic game strategies for extensive games. (This has no effect for strategic games, since a strategic game is its own reduced strategic game.)
- -D#
New in version 14.0.3.
The default output format for computed equilibria is a comma-separated list of strategy or action probabilities, suitable for postprocessing by automated tools. Specifying -D instead causes the program to output greater detail on each equilbrium profile computed.
- -P#
By default, the program computes Nash equilibria in an extensive game. This switch instructs the program to find only equilibria which are subgame perfect. (This has no effect for strategic games, since there are no proper subgames of a strategic game.)
- -h#
Prints a help message listing the available options.
- -q#
Suppresses printing of the banner at program launch.
Computing an equilibrium of the game 2x2const.nfg, a game with two players with two
strategies each, with a unique equilibrium in mixed strategies:
$ gambit-lp 2x2const.nfg
Compute Nash equilibria by solving a linear program
Gambit version 16.2.0, Copyright (C) 1994-2024, The Gambit Project
This is free software, distributed under the GNU GPL
NE,1/3,2/3,1/3,2/3
gambit-liap: Compute Nash equilibria using function minimization#
gambit-liap reads a game on standard input and 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.
Changed in version 16.2.0: The Lyapunov function is now normalized to be independent of the scale of the payoffs of the game; therefore multiplying or dividing all payoffs by a common factor will not affect the output of the algorithm.
The criterion for accepting whether a local constrained minimizer of the Lyanunov function is an approximate Nash equilibrium is specified in terms of the maximum regret. This regret is interpreted as a fraction of the difference between the maximum and minimum payoffs in the game.
- -d#
Express all output using decimal representations with the specified number of digits.
- -n#
Specify the number of starting points to randomly generate.
- -i#
New in version 16.1.1.
Specify the maximum number of iterations in function minimization (default is 1000).
- -m#
New in version 16.2.0.
Specify the maximum regret criterion for acceptance as an approximate Nash equilibrium (default is 1e-4). See Acceptance criteria for Nash equilibria for interpretation and guidance.
- -h#
Prints a help message listing the available options.
- -q#
Suppresses printing of the banner at program launch.
- -s#
Specifies a file containing a list of starting points for the algorithm. The format of the file is comma-separated values, one mixed strategy profile per line, in the same format used for output of equilibria (excluding the initial NE tag).
- -S#
By default, the program uses behavior strategies for extensive games; this switch instructs the program to use reduced strategic game strategies for extensive games. (This has no effect for strategic games, since a strategic game is its own reduced strategic game.)
- -v#
Sets verbose mode. In verbose mode, initial points, as well as points at which the minimization fails at a constrained local minimum that is not a Nash equilibrium, are all output, in addition to any equilibria found.
Computing an equilibrium in mixed strategies of e02.efg, the example in Figure 2 of Selten
(International Journal of Game Theory, 1975):
$ gambit-liap e02.nfg
Compute Nash equilibria by minimizing the Lyapunov function
Gambit version 16.2.0, Copyright (C) 1994-2024, The Gambit Project
This is free software, distributed under the GNU GPL
NE, 0.998701, 0.000229, 0.001070, 0.618833, 0.381167
gambit-simpdiv: Compute equilibria via simplicial subdivision#
gambit-simpdiv reads a game on standard input and 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.
The algorithm begins with any mixed strategy profile consisting of
rational numbers as probabilities. Without any options, the algorithm
begins with the centroid, and computes one Nash equilibrium. To
attempt to compute other equilibria that may exist, use the
gambit-simpdiv -r or gambit-simpdiv -s
options to specify additional starting points for the algorithm.
- -g#
Sets the granularity of the grid refinement. By default, when the grid is refined, the stepsize is cut in half, which corresponds to specifying -g 2. If this parameter is specified, the grid is refined at each step by a multiple of MULT .
- -h#
Prints a help message listing the available options.
- -n#
Randomly generate COUNT starting points. Only applicable if option
gambit-simpdiv -ris also specified.
- -q#
Suppresses printing of the banner at program launch.
- -r#
Generate random starting points with denominator DENOM. Since this algorithm operates on a grid, by its nature the probabilities it works with are always rational numbers. If this parameter is specified, starting points for the procedure are generated randomly using the uniform distribution over strategy profiles with probabilities having denominator DENOM.
- -s#
Specifies a file containing a list of starting points for the algorithm. The format of the file is comma-separated values, one mixed strategy profile per line, in the same format used for output of equilibria (excluding the initial NE tag).
- -m#
New in version 16.2.0.
Specify the maximum regret criterion for acceptance as an approximate Nash equilibrium (default is 1e-8). See Acceptance criteria for Nash equilibria for interpretation and guidance.
- -d DECIMALS#
New in version 16.2.0.
Simplicial subdivision operates on a triangulation grid in the set of mixed strategy profiles. Therefore, it produces output in which all probabilities are expressed as rational numbers, and by default the output reports these. By specifying this option, instead probabilities are expressed as floating-point numbers with the specified number of decimal places. Specifying this option sacrifices some precision in reporting the output of the method, in exchange for probabilities which are more human-readable.
- -v#
Sets verbose mode. In verbose mode, initial points, as well as the approximations computed at each grid refinement, are all output, in addition to the approximate equilibrium profile found.
Computing an equilibrium in mixed strategies of e02.efg, the example in Figure 2 of Selten
(International Journal of Game Theory, 1975):
$ gambit-simpdiv e02.nfg
Compute Nash equilibria using simplicial subdivision
Gambit version 16.2.0, Copyright (C) 1994-2024, The Gambit Project
This is free software, distributed under the GNU GPL
NE,1,0,0,1,0
gambit-logit: Compute quantal response equilbria#
gambit-logit reads a game on standard input and 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 option -s sets the 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 option -a sets the maximum acceleration (or deceleration). 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.
Changed in version 16.2.0: The criterion for accepting whether a point is sufficiently close to a Nash equilibrium to terminate the path-following is specified in terms of the maximum regret. This regret is interpreted as a fraction of the difference between the maximum and minimum payoffs in the game.
- -d#
Express all output using decimal representations with the specified number of digits. The default is -d 6.
- -s#
Sets the initial step size for the predictor phase of the tracing procedure. The default value is .03. The step size is specified in terms of the arclength along the branch of the correspondence, and not the size of the step measured in terms of lambda. So, for example, if the step size is currently .03, but the position of the strategy profile on the branch is changing rapidly with lambda, then lambda will change by much less then .03 between points reported by the program.
- -a#
Sets the maximum acceleration of the step size during the tracing procedure. This is interpreted as a multiplier. The default is 1.1, which means the step size is increased or decreased by no more than ten percent of its current value at every step. A value close to one would keep the step size (almost) constant at every step.
- -m#
New in version 16.2.0.
Specify the maximum regret criterion for acceptance as an approximate Nash equilibrium (default is 1e-8). See Acceptance criteria for Nash equilibria for interpretation and guidance.
- -l#
While tracing, compute the logit equilibrium points with parameter LAMBDA accurately.
- -S#
By default, the program uses behavior strategies for extensive games; this switch instructs the program to use reduced strategic game strategies for extensive games. (This has no effect for strategic games, since a strategic game is its own reduced strategic game.)
- -h#
Prints a help message listing the available options.
- -e#
By default, all points computed are output by the program. If this switch is specified, only the approximation to the Nash equilibrium at the end of the branch is output.
Computing the principal branch, in mixed strategies, of e02.nfg, the reduced strategic form of the example
in Figure 2 of Selten (International Journal of Game Theory,
1975):
$ gambit-logit e02.nfg
Compute a branch of the logit equilibrium correspondence
Gambit version 16.2.0, Copyright (C) 1994-2024, The Gambit Project
This is free software, distributed under the GNU GPL
0.000000,0.333333,0.333333,0.333333,0.5,0.5
0.022853,0.335873,0.328284,0.335843,0.501962,0.498038
0.047978,0.338668,0.322803,0.33853,0.504249,0.495751
0.075600,0.341747,0.316863,0.34139,0.506915,0.493085
0.105965,0.345145,0.310443,0.344413,0.510023,0.489977
0.139346,0.348902,0.303519,0.347578,0.51364,0.48636
...
735614.794714,1,0,4.40659e-11,0.500016,0.499984
809176.283787,1,0,3.66976e-11,0.500015,0.499985
890093.921767,1,0,3.05596e-11,0.500014,0.499986
979103.323545,1,0,2.54469e-11,0.500012,0.499988
1077013.665501,1,0,2.11883e-11,0.500011,0.499989
gambit-gnm: Compute Nash equilibria in a strategic game using a global Newton method#
gambit-gnm reads a game on standard input and 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.
The algorithm finds a subset of equilibria starting from any given profile. Multiple starting profiles may be generated via the -n option or specified via the -s option; different starting profiles may result in different subsets of equilibria being found.
- -d#
Express all output using decimal representations with the specified number of digits.
- -h#
Prints a help message listing the available options.
- -n#
Randomly generate the specified number of perturbation vectors.
- -q#
Suppresses printing of the banner at program launch.
- -s#
Specifies a file containing a list of starting points for the algorithm. The format of the file is comma-separated values, one mixed strategy profile per line, in the same format used for output of equilibria (excluding the initial NE tag).
- -m LAMBDA#
New in version 16.2.0.
Specifies the value of lambda at which to assume no more equilibria are accessible via the specified ray, and terminate tracing. Must be a negative number; default is -10.
- -f FREQ#
New in version 16.2.0.
Specifies the frequency to run a local Newton method step. This is a correction step that reduces accumulated errors in the path-following. Default is 3.
- -i MAXITS#
New in version 16.2.0.
Specifies the maximum number of iterations in a local Newton method step. Default is 10.
- -c STEPS#
New in version 16.2.0.
Specifies the number of steps to take within a support cell. Larger values trade off speed for security in tracing the path. Default is 100.
- -v#
Show intermediate output of the algorithm. If this option is not specified, only the equilibria found are reported.
Computing an equilibrium of e02.nfg,
the reduced strategic form of the example in Figure 2 of Selten
(International Journal of Game Theory, 1975):
$ gambit-gnm e02.nfg
Compute Nash equilibria using a global Newton method
Gametracer version 0.2, Copyright (C) 2002, Ben Blum and Christian Shelton
Gambit version 16.2.0, Copyright (C) 1994-2024, The Gambit Project
This is free software, distributed under the GNU GPL
NE,1,0,2.99905e-12,0.5,0.5
gambit-ipa: Compute Nash equilibria in a strategic game using iterated polymatrix approximation#
gambit-ipa reads a game on standard input and 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.
The algorithm finds at most one equilibrium starting from any given profile. Multiple starting profiles may be generated via the -n option or specified via the -s option; different starting profiles may result in different equilibria being found.
- -d#
Express all output using decimal representations with the specified number of digits.
- -h#
Prints a help message listing the available options.
- -n#
Randomly generate the specified number of perturbation vectors.
- -q#
Suppresses printing of the banner at program launch.
- -s#
Specifies a file containing a list of starting points for the algorithm. The format of the file is comma-separated values, one mixed strategy profile per line, in the same format used for output of equilibria (excluding the initial NE tag).
Computing an equilibrium of e02.nfg,
the reduced strategic form of the example in Figure 2 of Selten
(International Journal of Game Theory, 1975):
$ gambit-ipa e02.nfg
Compute Nash equilibria using iterated polymatrix approximation
Gametracer version 0.2, Copyright (C) 2002, Ben Blum and Christian Shelton
Gambit version 16.2.0, Copyright (C) 1994-2024, The Gambit Project
This is free software, distributed under the GNU GPL
NE,1.000000,0.000000,0.000000,1.000000,0.000000
gambit-convert: Convert games among various representations#
gambit-convert reads a game on standard input in any supported format and converts it to another text representation. Currently, this tool supports outputting the strategic form of the game in one of these formats:
A standard HTML table.
A LaTeX fragment in the format of Martin Osborne’s sgame macros (see http://www.economics.utoronto.ca/osborne/latex/index.html).
- -O FORMAT#
Required. Specifies the output format. Supported options for FORMAT are html or sgame.
- -r PLAYER#
Specifies the player number to place on the rows of the tables. The default if not specified is to place player 1 on the rows.
- -c PLAYER#
Specifies the player number to place on the columns of the tables. The default if not specified is to place player 2 on the columns.
- -h#
Prints a help message listing the available options.
- -q#
Suppresses printing of the banner at program launch.
Example invocation for HTML output:
$ gambit-convert -O html 2x2.nfg
Convert games among various file formats
Gambit version 16.2.0, Copyright (C) 1994-2024, The Gambit Project
This is free software, distributed under the GNU GPL
<center><h1>Two person 2 x 2 game with unique mixed equilibrium</h1></center>
<table><tr><td></td><td align=center><b>1</b></td><td
align=center><b>2</b></td></tr><tr><td align=center><b>1</b></td><td
align=center>2,0</td><td align=center>0,1</td></tr><tr><td
align=center><b>2</b></td><td align=center>0,1</td><td
align=center>1,0</td></tr></table>
Example invocation for LaTeX output:
$ gambit-convert -O sgame 2x2.nfg
Convert games among various file formats
Gambit version 16.2.0, Copyright (C) 1994-2024, The Gambit Project
This is free software, distributed under the GNU GPL
\begin{game}{2}{2}[Player 1][Player 2]
&1 & 2\\
1 & $2,0$ & $0,1$ \\
2 & $0,1$ & $1,0$
\end{game}
pygambit Python package#
Gambit provides a Python package, pygambit, which provides access to
Gambit’s features. pygambit is available on PyPI
(https://pypi.org/project/pygambit/), and can be installed via pip.
User guide#
Example: One-shot trust game with binary actions#
[Kre90] introduced a game commonly referred to as the trust game.
We will build a one-shot version of this game using pygambit’s game transformation
operations.
There are two players, a Buyer and a Seller. The Buyer moves first and has two actions, Trust or Not trust. If the Buyer chooses Not trust, then the game ends, and both players receive payoffs of 0. If the Buyer chooses Trust, then the Seller has a choice with two actions, Honor or Abuse. If the Seller chooses Honor, both players receive payoffs of 1; if the Seller chooses Abuse, the Buyer receives a payoff of -1 and the Seller receives a payoff of 2.
We create a game with an extensive representation using Game.new_tree():
In [1]: import pygambit as gbt
In [2]: g = gbt.Game.new_tree(players=["Buyer", "Seller"],
...: title="One-shot trust game, after Kreps (1990)")
...:
The tree of the game contains just a root node, with no children:
In [3]: g.root
Out[3]: Node(game=Game(title='One-shot trust game, after Kreps (1990)'), path=[])
In [4]: g.root.children
Out[4]: NodeChildren(parent=Node(game=Game(title='One-shot trust game, after Kreps (1990)'), path=[]))
To extend a game from an existing terminal node, use Game.append_move():
In [5]: g.append_move(g.root, "Buyer", ["Trust", "Not trust"])
In [6]: g.root.children
Out[6]: NodeChildren(parent=Node(game=Game(title='One-shot trust game, after Kreps (1990)'), path=[]))
We can then also add the Seller’s move in the situation after the Buyer chooses Trust:
In [7]: g.append_move(g.root.children[0], "Seller", ["Honor", "Abuse"])
Now that we have the moves of the game defined, we add payoffs. Payoffs are associated with
an Outcome; each Outcome has a vector of payoffs, one for each player,
and optionally an identifying text label. First we add the outcome associated with the
Seller proving themselves trustworthy:
In [8]: g.set_outcome(g.root.children[0].children[0], g.add_outcome([1, 1], label="Trustworthy"))
Next, the outcome associated with the scenario where the Buyer trusts but the Seller does not return the trust:
In [9]: g.set_outcome(g.root.children[0].children[1], g.add_outcome([-1, 2], label="Untrustworthy"))
And, finally the outcome associated with the Buyer opting out of the interaction:
In [10]: g.set_outcome(g.root.children[1], g.add_outcome([0, 0], label="Opt-out"))
Nodes without an outcome attached are assumed to have payoffs of zero for all players. Therefore, adding the outcome to this latter terminal node is not strictly necessary in Gambit, but it is useful to be explicit for readability.
Kreps, D. (1990) “Corporate Culture and Economic Theory.” In J. Alt and K. Shepsle, eds., Perspectives on Positive Political Economy, Cambridge University Press.
Example: A one-card poker game with private information#
To illustrate games in extensive form, [Mye91] presents a one-card poker game. A version of this game also appears in [RUW08], as a classroom game under the name “stripped-down poker”. This is perhaps the simplest interesting game with imperfect information.
In our version of the game, there are two players, Alice and Bob. There is a deck of cards, with equal numbers of King and Queen cards. The game begins with each player putting $1 in the pot. One card is dealt at random to Alice; Alice observes her card but Bob does not. After Alice observes her card, she can choose either to Raise or to Fold. If she chooses to Fold, Bob wins the pot and the game ends. If she chooses to Raise, she adds another $1 to the pot. Bob then chooses either to Meet or Pass. If he chooses to Pass, Alice wins the pot and the game ends. If he chooses to Meet, he adds another $1 to the pot. There is then a showdown, in which Alice reveals her card. If she has a King, then she wins the pot; if she has a Queen, then Bob wins the pot.
We can build this game using the following script:
g = gbt.Game.new_tree(players=["Alice", "Bob"],
title="One card poker game, after Myerson (1991)")
g.append_move(g.root, g.players.chance, ["King", "Queen"])
for node in g.root.children:
g.append_move(node, "Alice", ["Raise", "Fold"])
g.append_move(g.root.children[0].children[0], "Bob", ["Meet", "Pass"])
g.append_infoset(g.root.children[1].children[0],
g.root.children[0].children[0].infoset)
alice_winsbig = g.add_outcome([2, -2], label="Alice wins big")
alice_wins = g.add_outcome([1, -1], label="Alice wins")
bob_winsbig = g.add_outcome([-2, 2], label="Bob wins big")
bob_wins = g.add_outcome([-1, 1], label="Bob wins")
g.set_outcome(g.root.children[0].children[0].children[0], alice_winsbig)
g.set_outcome(g.root.children[0].children[0].children[1], alice_wins)
g.set_outcome(g.root.children[0].children[1], bob_wins)
g.set_outcome(g.root.children[1].children[0].children[0], bob_winsbig)
g.set_outcome(g.root.children[1].children[0].children[1], alice_wins)
g.set_outcome(g.root.children[1].children[1], bob_wins)
All extensive games have a chance (or nature) player, accessible as
.Game.players.chance. Moves belonging to the chance player can be added in the same
way as to personal players. At any new move created for the chance player, the action
probabilities default to uniform randomization over the actions at the move.
In this game, information structure is important. Alice knows her card, so the two nodes at which she has the move are part of different information sets. The loop:
for node in g.root.children:
g.append_move(node, "Alice", ["Raise", "Fold"])
causes each of the newly-appended moves to be in new information sets. In contrast, Bob does not know Alice’s card, and therefore cannot distinguish between the two nodes at which he has the decision. This is implemented in the following lines:
g.append_move(g.root.children[0].children[0], "Bob", ["Meet", "Pass"])
g.append_infoset(g.root.children[1].children[0],
g.root.children[0].children[0].infoset)
The call Game.append_infoset() adds a move at a terminal node as part of
an existing information set (represented in pygambit as an Infoset).
Building a strategic game#
Games in strategic form, also referred to as normal form, are represented solely
by a collection of payoff tables, one per player. The most direct way to create
a strategic game is via Game.from_arrays(). This function takes one
n-dimensional array per player, where n is the number of players in the game.
The arrays can be any object that can be indexed like an n-times-nested Python list;
so, for example, numpy arrays can be used directly.
For example, to create a standard prisoner’s dilemma game in which the cooperative payoff is 8, the betrayal payoff is 10, the sucker payoff is 2, and the noncooperative payoff is 5:
In [11]: import numpy as np
In [12]: m = np.array([[8, 2], [10, 5]])
In [13]: g = gbt.Game.from_arrays(m, np.transpose(m))
In [14]: g
Out[14]: Game(title='Untitled strategic game')
The arrays passed to Game.from_arrays() are all indexed in the same sense, that is,
the top level index is the choice of the first player, the second level index of the second player,
and so on. Therefore, to create a two-player symmetric game, as in this example, the payoff matrix
for the second player is transposed before passing to Game.from_arrays().
Representation of numerical data of a game#
Payoffs to players and probabilities of actions at chance information sets are specified as numbers. Gambit represents the numerical values in a game in exact precision, using either decimal or rational representations.
To illustrate, we consider a trivial game which just has one move for the chance player:
In [15]: import pygambit as gbt
In [16]: g = gbt.Game.new_tree()
In [17]: g.append_move(g.root, g.players.chance, ["a", "b", "c"])
In [18]: [act.prob for act in g.root.infoset.actions]
Out[18]: [Rational(1, 3), Rational(1, 3), Rational(1, 3)]
The default when creating a new move for chance is that all actions are chosen with
equal probability. These probabilities are represented as rational numbers,
using pygambit’s Rational class, which is derived from Python’s
fractions.Fraction. Numerical data can be set as rational numbers:
In [19]: g.set_chance_probs(g.root.infoset,
....: [gbt.Rational(1, 4), gbt.Rational(1, 2), gbt.Rational(1, 4)])
....:
In [20]: [act.prob for act in g.root.infoset.actions]
Out[20]: [Rational(1, 4), Rational(1, 2), Rational(1, 4)]
They can also be explicitly specified as decimal numbers:
In [21]: g.set_chance_probs(g.root.infoset,
....: [gbt.Decimal(".25"), gbt.Decimal(".50"), gbt.Decimal(".25")])
....:
In [22]: [act.prob for act in g.root.infoset.actions]
Out[22]: [Decimal('0.25'), Decimal('0.50'), Decimal('0.25')]
Although the two representations above are mathematically equivalent, pygambit
remembers the format in which the values were specified.
Expressing rational or decimal numbers as above is verbose and tedious.
pygambit offers a more concise way to express numerical data in games:
when setting numerical game data, pygambit will attempt to convert text strings to
their rational or decimal representation. The above can therefore be written
more compactly using string representations:
In [23]: g.set_chance_probs(g.root.infoset, ["1/4", "1/2", "1/4"])
In [24]: [act.prob for act in g.root.infoset.actions]
Out[24]: [Rational(1, 4), Rational(1, 2), Rational(1, 4)]
In [25]: g.set_chance_probs(g.root.infoset, [".25", ".50", ".25"])
In [26]: [act.prob for act in g.root.infoset.actions]
Out[26]: [Decimal('0.25'), Decimal('0.50'), Decimal('0.25')]
As a further convenience, pygambit will accept Python int and float values.
int values are always interpreted as Rational values.
pygambit attempts to render float values in an appropriate Decimal
equivalent. In the majority of cases, this creates no problems.
For example,
In [27]: g.set_chance_probs(g.root.infoset, [.25, .50, .25])
In [28]: [act.prob for act in g.root.infoset.actions]
Out[28]: [Decimal('0.25'), Decimal('0.5'), Decimal('0.25')]
However, rounding can cause difficulties when attempting to use float values to represent values which do not have an exact decimal representation
In [29]: g.set_chance_probs(g.root.infoset, [1/3, 1/3, 1/3])
---------------------------------------------------------------------------
ValueError Traceback (most recent call last)
Cell In[29], line 1
----> 1 g.set_chance_probs(g.root.infoset, [1/3, 1/3, 1/3])
File src/pygambit/game.pxi:632, in pygambit.gambit.Game.set_chance_probs()
ValueError: set_chance_probs(): must specify non-negative probabilities that sum to one
This behavior can be slightly surprising, especially in light of the fact that in Python,
In [30]: 1/3 + 1/3 + 1/3
Out[30]: 1.0
In checking whether these probabilities sum to one, pygambit first converts each
of the probabilitiesto a Decimal representation, via the following method
In [31]: gbt.Decimal(str(1/3))
Out[31]: Decimal('0.3333333333333333')
and the sum-to-one check then fails because
In [32]: gbt.Decimal(str(1/3)) + gbt.Decimal(str(1/3)) + gbt.Decimal(str(1/3))
Out[32]: Decimal('0.9999999999999999')
Setting payoffs for players also follows the same rules. Representing probabilities
and payoffs exactly is essential, because pygambit offers (in particular for two-player
games) the possibility of computation of equilibria exactly, because the Nash equilibria
of any two-player game with rational payoffs and chance probabilities can be expressed exactly
in terms of rational numbers.
It is therefore advisable always to specify the numerical data of games either in terms
of Decimal or Rational values, or their string equivalents.
It is safe to use int values, but float values should be used with some care to ensure
the values are recorded as intended.
Reading a game from a file#
Games stored in existing Gambit savefiles can be loaded using Game.read_game():
In [33]: g = gbt.Game.read_game("e02.nfg")
In [34]: g
Out[34]: Game(title='Selten (IJGT, 75), Figure 2, normal form')
Computing Nash equilibria#
Interfaces to algorithms for computing Nash equilibria are provided in pygambit.nash.
Method |
Python function |
|---|---|
We take as an example the one-card poker game. This is a two-player, constant sum game, and so all of the equilibrium-finding methods can be applied to it.
For two-player games, lcp_solve() can compute Nash equilibria directly using
the extensive representation. Assuming that g refers to the game
In [35]: result = gbt.nash.lcp_solve(g)
In [36]: result
Out[36]: NashComputationResult(method='lcp', rational=True, use_strategic=False, equilibria=[[[[Rational(1, 1), Rational(0, 1)], [Rational(1, 3), Rational(2, 3)]], [[Rational(2, 3), Rational(1, 3)]]]], parameters={'stop_after': 0, 'max_depth': 0})
In [37]: len(result.equilibria)
Out[37]: 1
The result of the calculation is returned as a NashComputationResult object.
The set of equilibria found is reported in NashComputationResult.equilibria;
in this case, this is a list of mixed behavior profiles.
A mixed behavior profile specifies, for each information set, the probability distribution over
actions at that information set.
Indexing a MixedBehaviorProfile by a player gives a MixedBehavior,
which specifies probability distributions at each of the player’s information sets:
In [38]: eqm = result.equilibria[0]
In [39]: eqm["Alice"]
Out[39]: [[Rational(1, 1), Rational(0, 1)], [Rational(1, 3), Rational(2, 3)]]
In this case, at Alice’s first information set, the one at which she has the King, she always raises.
At her second information set, where she has the Queen, she sometimes bluffs, raising with
probability one-third.
The probability distribution at an information set is represented by a MixedAction.
MixedBehavior.mixed_actions() iterates over these for the player:
In [40]: for infoset, mixed_action in eqm["Alice"].mixed_actions():
....: print(infoset)
....: print(mixed_action)
....:
Infoset(player=Player(game=Game(title='One card poker game, after Myerson (1991)'), label='Alice'), number=0)
[Rational(1, 1), Rational(0, 1)]
Infoset(player=Player(game=Game(title='One card poker game, after Myerson (1991)'), label='Alice'), number=1)
[Rational(1, 3), Rational(2, 3)]
So we could extract Alice’s probabilities of raising at her respective information sets like this:
In [41]: {infoset: mixed_action["Raise"] for infoset, mixed_action in eqm["Alice"].mixed_actions()}
Out[41]:
{Infoset(player=Player(game=Game(title='One card poker game, after Myerson (1991)'), label='Alice'), number=0): Rational(1, 1),
Infoset(player=Player(game=Game(title='One card poker game, after Myerson (1991)'), label='Alice'), number=1): Rational(1, 3)}
In larger games, labels may not always be the most convenient way to refer to specific
actions. We can also index profiles directly with Action objects.
So an alternative way to extract the probabilities of playing “Raise” would be by
iterating Alice’s list of actions:
In [42]: {action.infoset: eqm[action] for action in g.players["Alice"].actions if action.label == "Raise"}
Out[42]:
{Infoset(player=Player(game=Game(title='One card poker game, after Myerson (1991)'), label='Alice'), number=0): Rational(1, 1),
Infoset(player=Player(game=Game(title='One card poker game, after Myerson (1991)'), label='Alice'), number=1): Rational(1, 3)}
Looking at Bob’s strategy,
In [43]: eqm["Bob"]
Out[43]: [[Rational(2, 3), Rational(1, 3)]]
Bob meets Alice’s raise two-thirds of the time. The label “Raise” is used in more than one information set for Alice, so in the above we had to specify information sets when indexing. When there is no ambiguity, we can specify action labels directly. So for example, because Bob has only one action named “Meet” in the game, we can extract the probability that Bob plays “Meet” by:
In [44]: eqm["Bob"]["Meet"]
Out[44]: Rational(2, 3)
Moreover, this is the only action with that label in the game, so we can index the profile directly using the action label without any ambiguity:
In [45]: eqm["Meet"]
Out[45]: Rational(2, 3)
Because this is an equilibrium, the fact that Bob randomizes at his information set must mean he
is indifferent between the two actions at his information set. MixedBehaviorProfile.action_value()
returns the expected payoff of taking an action, conditional on reaching that action’s information set:
In [46]: {action: eqm.action_value(action) for action in g.players["Bob"].infosets[0].actions}
Out[46]:
{Action(infoset=Infoset(player=Player(game=Game(title='One card poker game, after Myerson (1991)'), label='Bob'), number=0), label='Meet'): Rational(-1, 1),
Action(infoset=Infoset(player=Player(game=Game(title='One card poker game, after Myerson (1991)'), label='Bob'), number=0), label='Pass'): Rational(-1, 1)}
Bob’s indifference between his actions arises because of his beliefs given Alice’s strategy.
MixedBehaviorProfile.belief() returns the probability of reaching a node, conditional on
its information set being reached:
In [47]: {node: eqm.belief(node) for node in g.players["Bob"].infosets[0].members}
Out[47]:
{Node(game=Game(title='One card poker game, after Myerson (1991)'), path=[0, 0]): Rational(3, 4),
Node(game=Game(title='One card poker game, after Myerson (1991)'), path=[0, 1]): Rational(1, 4)}
Bob believes that, conditional on Alice raising, there’s a 75% chance that she has the king;
therefore, the expected payoff to meeting is in fact -1 as computed.
MixedBehaviorProfile.infoset_prob() returns the probability that an information set is
reached:
In [48]: eqm.infoset_prob(g.players["Bob"].infosets[0])
Out[48]: Rational(2, 3)
The corresponding probability that a node is reached in the play of the game is given
by MixedBehaviorProfile.realiz_prob(), and the expected payoff to a player
conditional on reaching a node is given by MixedBehaviorProfile.node_value().
In [49]: {node: eqm.node_value("Bob", node) for node in g.players["Bob"].infosets[0].members}
Out[49]:
{Node(game=Game(title='One card poker game, after Myerson (1991)'), path=[0, 0]): Rational(-5, 3),
Node(game=Game(title='One card poker game, after Myerson (1991)'), path=[0, 1]): Rational(1, 1)}
The overall expected payoff to a player given the behavior profile is returned by
MixedBehaviorProfile.payoff():
In [50]: eqm.payoff("Alice")
Out[50]: Rational(1, 3)
In [51]: eqm.payoff("Bob")
Out[51]: Rational(-1, 3)
The equilibrium computed expresses probabilities in rational numbers. Because
the numerical data of games in Gambit are represented exactly,
methods which are specialized to two-player games, lp_solve(), lcp_solve(),
and enummixed_solve(), can report exact probabilities for equilibrium strategy
profiles. This is enabled by default for these methods.
When a game has an extensive representation, equilibrium finding methods default to computing
on that representation. It is also possible to compute using the strategic representation.
pygambit transparently computes the reduced strategic form representation of an extensive game
In [52]: [s.label for s in g.players["Alice"].strategies]
Out[52]: ['11', '12', '21', '22']
In the strategic form of this game, Alice has four strategies. The generated strategy labels list the action numbers taken at each information set. We can therefore apply a method which operates on a strategic game to any game with an extensive representation
In [53]: result = gbt.nash.gnm_solve(g)
In [54]: result
Out[54]: NashComputationResult(method='gnm', rational=False, use_strategic=True, equilibria=[[[0.33333333333866677, 0.6666666666613335, 0.0, 0.0], [0.6666666666559997, 0.3333333333440004]]], parameters={'perturbation': [[1.0, 0.0, 0.0, 0.0], [1.0, 0.0]], 'end_lambda': -10.0, 'steps': 100, 'local_newton_interval': 3, 'local_newton_maxits': 10})
gnm_solve() can be applied to any game with any number of players, and uses a path-following
process in floating-point arithmetic, so it returns profiles with probabilities expressed as
floating-point numbers. This method operates on the strategic representation of the game, so
the returned results are of type MixedStrategyProfile, and
specify, for each player, a probability distribution over that player’s strategies.
Indexing a MixedStrategyProfile by a player gives the probability distribution
over that player’s strategies only.
In [55]: eqm = result.equilibria[0]
In [56]: eqm["Alice"]
Out[56]: [0.33333333333866677, 0.6666666666613335, 0.0, 0.0]
In [57]: eqm["Bob"]
Out[57]: [0.6666666666559997, 0.3333333333440004]
The expected payoff to a strategy is provided by MixedStrategyProfile.strategy_value():
In [58]: {strategy: eqm.strategy_value(strategy) for strategy in g.players["Alice"].strategies}
Out[58]:
{Strategy(player=Player(game=Game(title='One card poker game, after Myerson (1991)'), label='Alice'), label='11'): 0.33333333334400045,
Strategy(player=Player(game=Game(title='One card poker game, after Myerson (1991)'), label='Alice'), label='12'): 0.33333333332799997,
Strategy(player=Player(game=Game(title='One card poker game, after Myerson (1991)'), label='Alice'), label='21'): -0.9999999999839995,
Strategy(player=Player(game=Game(title='One card poker game, after Myerson (1991)'), label='Alice'), label='22'): -1.0}
In [59]: {strategy: eqm.strategy_value(strategy) for strategy in g.players["Bob"].strategies}
Out[59]:
{Strategy(player=Player(game=Game(title='One card poker game, after Myerson (1991)'), label='Bob'), label='1'): -0.33333333333066656,
Strategy(player=Player(game=Game(title='One card poker game, after Myerson (1991)'), label='Bob'), label='2'): -0.3333333333386667}
The overall expected payoff to a player is returned by MixedStrategyProfile.payoff():
In [60]: eqm.payoff("Alice")
Out[60]: 0.33333333333333354
In [61]: eqm.payoff("Bob")
Out[61]: -0.33333333333333354
When a game has an extensive representation, we can convert freely between
MixedStrategyProfile and the corresponding
MixedBehaviorProfile representation of the same strategies
using MixedStrategyProfile.as_behavior() and MixedBehaviorProfile.as_strategy().
In [62]: eqm.as_behavior()
Out[62]: [[[1.0, 0.0], [0.3333333333386667, 0.6666666666613333]], [[0.6666666666559997, 0.3333333333440004]]]
In [63]: eqm.as_behavior().as_strategy()
Out[63]: [[0.3333333333386667, 0.6666666666613333, 0.0, 0.0], [0.6666666666559997, 0.3333333333440004]]
Acceptance criteria for Nash equilibria#
Some methods for computing Nash equilibria operate using floating-point arithmetic and/or generate candidate equilibrium profiles using methods which involve some form of successive approximations. The outputs of these methods therefore are in general \(\varepsilon\)-equilibria, for some positive \(\varepsilon\).
To provide a uniform interface across methods, where relevant Gambit provides a parameter maxregret, which specifies the acceptance criterion for labeling the output of the algorithm as an equilibrium. This parameter is interpreted proportionally to the range of payoffs in the game. Any profile returned as an equilibrium is guaranteed to be an \(\varepsilon\)-equilibrium, for \(\varepsilon\) no more than maxregret times the difference of the game’s maximum and minimum payoffs.
As an example, consider solving the standard one-card poker game using
logit_solve(). The range of the payoffs in this game is 4 (from +2 to -2).
In [64]: g = gbt.Game.read_game("poker.efg")
In [65]: g.max_payoff, g.min_payoff
Out[65]: (Rational(2, 1), Rational(-2, 1))
logit_solve() is a globally-convergent method, in that it computes a
sequence of profiles which is guaranteed to have a subsequence that converges to a
Nash equilibrium. The default value of maxregret for this method is set at
\(10^{-8}\):
In [66]: result = gbt.nash.logit_solve(g, maxregret=1e-8)
In [67]: result.equilibria
Out[67]: [[[[1.0, 0.0], [0.33333338649882943, 0.6666666135011707]], [[0.6666667065407631, 0.3333332934592369]]]]
In [68]: result.equilibria[0].max_regret()
Out[68]: 3.987411578698641e-08
The value of MixedBehaviorProfile.max_regret() of the computed profile exceeds
\(10^{-8}\) measured in payoffs of the game. However, when considered relative
to the scale of the game’s payoffs, we see it is less than \(10^{-8}\) of
the payoff range, as requested:
In [69]: result.equilibria[0].max_regret() / (g.max_payoff - g.min_payoff)
Out[69]: 9.968528946746602e-09
In general, for globally-convergent methods especially, there is a tradeoff between precision and running time. Some methods may be slow to converge on some games, and it may be useful instead to get a more coarse approximation to an equilibrium. We could instead ask only for an \(\varepsilon\)-equilibrium with a (scaled) \(\varepsilon\) of no more than \(10^{-4}\):
In [70]: result = gbt.nash.logit_solve(g, maxregret=1e-4)
In [71]: result.equilibria[0]
Out[71]: [[[1.0, 0.0], [0.3338351656285656, 0.666164834417892]], [[0.6670407651644306, 0.3329592348608147]]]
In [72]: result.equilibria[0].max_regret()
Out[72]: 0.00037581039824041707
In [73]: result.equilibria[0].max_regret() / (g.max_payoff - g.min_payoff)
Out[73]: 9.395259956010427e-05
The convention of expressing maxregret scaled by the game’s payoffs standardises the
behavior of methods across games. For example, consider solving the poker game instead
using liap_solve().
In [74]: result = gbt.nash.liap_solve(g.mixed_behavior_profile(), maxregret=1.0e-4)
In [75]: result.equilibria[0]
Out[75]: [[[0.9999979852809777, 2.0147190221904606e-06], [0.3333567614695495, 0.6666432385304505]], [[0.6668870457043463, 0.33311295429565374]]]
In [76]: result.equilibria[0].max_regret()
Out[76]: 0.00022039452688993322
In [77]: result.equilibria[0].max_regret() / (g.max_payoff - g.min_payoff)
Out[77]: 5.5098631722483304e-05
If, instead, we double all payoffs, the output of the method is unchanged.
In [78]: for outcome in g.outcomes:
....: outcome["Alice"] = outcome["Alice"] * 2
....: outcome["Bob"] = outcome["Bob"] * 2
....:
In [79]: result = gbt.nash.liap_solve(g.mixed_behavior_profile(), maxregret=1.0e-4)
In [80]: result.equilibria[0]
Out[80]: [[[0.9999979852809777, 2.0147190221904606e-06], [0.3333567614695495, 0.6666432385304505]], [[0.6668870457043463, 0.33311295429565374]]]
In [81]: result.equilibria[0].max_regret()
Out[81]: 0.00044078905377986644
In [82]: result.equilibria[0].max_regret() / (g.max_payoff - g.min_payoff)
Out[82]: 5.5098631722483304e-05
Generating starting points for algorithms#
Some methods for computation of Nash equilibria take as an initial condition a
MixedStrategyProfile or MixedBehaviorProfile which is used
as a starting point. The equilibria found will depend on which starting point is
selected. To facilitate generating starting points, Game provides
methods Game.random_strategy_profile() and Game.random_behavior_profile(),
to generate profiles which are drawn from the uniform distribution on the product
of simplices.
As an example, we consider a three-player game from McKelvey and McLennan (1997), in which each player has two strategies. This game has nine equilibria in total, and in particular has two totally mixed Nash equilibria, which is the maximum possible number of regular totally mixed equilbria in games of this size.
We first consider finding Nash equilibria in this game using liap_solve().
If we run this method starting from the centroid (uniform randomization across all
strategies for each player), liap_solve() finds one of the totally-mixed equilibria.
In [83]: g = gbt.Game.read_game("2x2x2.nfg")
In [84]: gbt.nash.liap_solve(g.mixed_strategy_profile())
Out[84]: NashComputationResult(method='liap', rational=False, use_strategic=True, equilibria=[[[0.4000000330601743, 0.5999999669398257], [0.499999791913678, 0.5000002080863221], [0.3333334438355959, 0.6666665561644041]]], parameters={'start': [[0.5, 0.5], [0.5, 0.5], [0.5, 0.5]], 'maxregret': 0.0001, 'maxiter': 1000})
Which equilibrium is found depends on the starting point. With a different starting point, we can find, for example, one of the pure-strategy equilibria.
In [85]: gbt.nash.liap_solve(g.mixed_strategy_profile([[.9, .1], [.9, .1], [.9, .1]]))
Out[85]: NashComputationResult(method='liap', rational=False, use_strategic=True, equilibria=[[[0.9999999952144591, 4.785540892853837e-09], [0.9999999998451463, 1.5485358776552024e-10], [0.9999999988047714, 1.1952285809728638e-09]]], parameters={'start': [[0.9, 0.1], [0.9, 0.1], [0.9, 0.1]], 'maxregret': 0.0001, 'maxiter': 1000})
To search for more equilibria, we can instead generate strategy profiles at random.
In [86]: gbt.nash.liap_solve(g.random_strategy_profile())
Out[86]: NashComputationResult(method='liap', rational=False, use_strategic=True, equilibria=[[[0.4000006115393901, 0.59999938846061], [0.49999873824756796, 0.5000012617524321], [0.3333336637527727, 0.6666663362472274]]], parameters={'start': [[0.5279265148370416, 0.4720734851629584], [0.39513832089736656, 0.6048616791026334], [0.5806139651431909, 0.4193860348568091]], 'maxregret': 0.0001, 'maxiter': 1000})
Note that methods which take starting points do record the starting points used in the
result object returned. However, the random profiles which are generated will differ
in different runs of a program. To support making the generation of random strategy
profiles reproducible, and for finer-grained control of the generation of these profiles
if desired, Game.random_strategy_profile() and Game.random_behavior_profile()
optionally take a numpy.random.Generator object, which is used as the source
of randomness for creating the profile.
In [87]: import numpy as np
In [88]: gen = np.random.default_rng(seed=1234567890)
In [89]: p1 = g.random_strategy_profile(gen=gen)
In [90]: p1
Out[90]: [[0.8359110871883912, 0.16408891281160876], [0.7422931336795922, 0.25770686632040796], [0.977833473596193, 0.02216652640380706]]
In [91]: gen = np.random.default_rng(seed=1234567890)
In [92]: p2 = g.random_strategy_profile(gen=gen)
In [93]: p2
Out[93]: [[0.8359110871883912, 0.16408891281160876], [0.7422931336795922, 0.25770686632040796], [0.977833473596193, 0.02216652640380706]]
In [94]: p1 == p2
Out[94]: True
When creating profiles in which probabilities are represented as floating-point numbers,
Game.random_strategy_profile() and Game.random_behavior_profile()
internally use the Dirichlet distribution for each simplex to generate correctly uniform
sampling over probabilities. However, in some applications generation of random profiles
with probabilities as rational numbers is desired. For example, simpdiv_solve()
takes such a starting point, because it operates by successively refining a triangulation
over the space of mixed strategy profiles.
Game.random_strategy_profile() and Game.random_behavior_profile()
both take an optional parameter denom which, if specified, generates a profile in which
probabilities are generated uniformly from the grid in each simplex in which all probabilities
have denominator denom.
In [95]: gen = np.random.default_rng(seed=1234567890)
In [96]: g.random_strategy_profile(denom=10, gen=gen)
Out[96]: [[Rational(1, 2), Rational(1, 2)], [Rational(7, 10), Rational(3, 10)], [Rational(0, 1), Rational(1, 1)]]
In [97]: g.random_strategy_profile(denom=10, gen=gen)
Out[97]: [[Rational(1, 10), Rational(9, 10)], [Rational(3, 5), Rational(2, 5)], [Rational(3, 5), Rational(2, 5)]]
These can then be used in conjunction with simpdiv_solve() to search for equilibria
from different starting points.
In [98]: gbt.nash.simpdiv_solve(g.random_strategy_profile(denom=10, gen=gen))
Out[98]: NashComputationResult(method='simpdiv', rational=True, use_strategic=True, equilibria=[[[Rational(1, 1), Rational(0, 1)], [Rational(1, 1), Rational(0, 1)], [Rational(1, 1), Rational(0, 1)]]], parameters={'start': [[Rational(7, 10), Rational(3, 10)], [Rational(4, 5), Rational(1, 5)], [Rational(0, 1), Rational(1, 1)]], 'maxregret': Rational(1, 10000000), 'refine': 2, 'leash': None})
In [99]: gbt.nash.simpdiv_solve(g.random_strategy_profile(denom=10, gen=gen))
Out[99]: NashComputationResult(method='simpdiv', rational=True, use_strategic=True, equilibria=[[[Rational(1, 1), Rational(0, 1)], [Rational(0, 1), Rational(1, 1)], [Rational(0, 1), Rational(1, 1)]]], parameters={'start': [[Rational(4, 5), Rational(1, 5)], [Rational(1, 5), Rational(4, 5)], [Rational(0, 1), Rational(1, 1)]], 'maxregret': Rational(1, 10000000), 'refine': 2, 'leash': None})
In [100]: gbt.nash.simpdiv_solve(g.random_strategy_profile(denom=10, gen=gen))
Out[100]: NashComputationResult(method='simpdiv', rational=True, use_strategic=True, equilibria=[[[Rational(1, 1), Rational(0, 1)], [Rational(1, 1), Rational(0, 1)], [Rational(1, 1), Rational(0, 1)]]], parameters={'start': [[Rational(1, 2), Rational(1, 2)], [Rational(1, 1), Rational(0, 1)], [Rational(1, 2), Rational(1, 2)]], 'maxregret': Rational(1, 10000000), 'refine': 2, 'leash': None})
Estimating quantal response equilibria#
Alongside computing quantal response equilibria, Gambit can also perform maximum likelihood estimation, computing the QRE which best fits an empirical distribution of play.
As an example we consider an asymmetric matching pennies game studied in [Och95], analysed in [McKPal95] using QRE.
In [101]: g = gbt.Game.from_arrays(
.....: [[1.1141, 0], [0, 0.2785]],
.....: [[0, 1.1141], [1.1141, 0]],
.....: title="Ochs (1995) asymmetric matching pennies as transformed in McKelvey-Palfrey (1995)"
.....: )
.....:
In [102]: data = g.mixed_strategy_profile([[128*0.527, 128*(1-0.527)], [128*0.366, 128*(1-0.366)]])
Estimation of QRE is done using fit_fixedpoint().
In [103]: fit = gbt.qre.fit_fixedpoint(data)
The returned LogitQREMixedStrategyFitResult object contains the results of the
estimation.
The results replicate those reported in [McKPal95], including the estimated value of lambda,
the QRE profile probabilities, and the log-likelihood.
Because data contains the empirical counts of play, and not just frequencies, the resulting
log-likelihood is correct for use in likelihoood-ratio tests. [1]
In [104]: print(fit.lam)
1.8456097536855864
In [105]: print(fit.profile)
[[0.615651314427859, 0.3843486855721409], [0.3832909400456291, 0.616709059954371]]
In [106]: print(fit.log_like)
-174.76453191087444
Footnotes
API documentation#
Representation of games#
A game, the fundamental unit of analysis in game theory. |
|
A player in a |
|
An outcome in a |
|
A node in a |
|
An information set in a |
|
A choice available at an |
|
A plan of action for a |
Creating, reading, and writing games#
|
Create a new |
|
Create a new |
|
Create a new |
|
Create a new |
|
Construct a game from its serialised representation in a file. |
|
Construct a game from its serialised representation in a string |
|
Produce a serialization of the game. |
Transforming game trees#
|
Add a move for player at terminal nodes. |
|
Add a move in information set infoset at terminal nodes. |
|
Insert a move for player prior to the node node, with actions actions. |
|
Insert a move in information set infoset prior to the node node. |
|
Copy the subtree rooted at 'src' to 'dest'. |
|
Move the subtree rooted at 'src' to 'dest'. |
|
Delete the parent node of node. |
|
Truncate the game tree at node, deleting the subtree beneath it. |
Transforming game information structure#
|
Set the player at an information set. |
|
Place node in the information set infoset. |
|
Remove this node from its information set. |
|
Reveals the move made at infoset to player. |
|
Set the action probabilities at chance information set infoset. |
Transforming game components#
|
Add a new player to the game. |
|
Add a new outcome to the game. |
|
Delete an outcome from the game. |
|
Set outcome to be the outcome at node. |
|
Add a new strategy to the set of strategies for player. |
|
Delete strategy from the game. |
Information about the game#
Get or set the title of the game. |
|
Get or set the comment of the game. |
|
Whether the game is constant sum. |
|
Return whether a game has a tree-based representation. |
|
Whether the game is perfect recall. |
|
The set of players in the game. |
|
The set of outcomes in the game. |
|
The minimum payoff in the game. |
|
The maximum payoff in the game. |
|
The set of strategies in the game. |
|
The root node of the game. |
|
The set of actions available in the game. |
|
The set of information sets in the game. |
|
|
Return a list of nodes in the game tree. |
An iterator over the contingencies in the game. |
Gets or sets the text label of the player. |
|
Returns the number of the player in its game. |
|
Gets the |
|
Returns the set of strategies belonging to the player. |
|
Returns the set of information sets at which the player has the decision. |
|
Returns the set of actions available to the player at some information set. |
|
Returns whether the player is the chance player. |
|
Returns the smallest payoff for the player in any outcome of the game. |
|
Returns the largest payoff for the player in any outcome of the game. |
|
Returns the set of strategies belonging to the player. |
The text label associated with this outcome. |
|
Returns the game with which this outcome is associated. |
The text label associated with the node. |
|
Gets the |
|
Returns the outcome attached to the node. |
|
The set of children of this node. |
|
The parent of this node. |
|
Returns whether the node is the root of a proper subgame. |
|
Returns whether this is a terminal node of the game. |
|
The action which leads to this node. |
|
The node which is immediately before this one in its parent's children. |
|
The node which is immediately after this one in its parent's children. |
|
The information set to which this node belongs. |
|
The player who makes the decision at this node. |
|
|
Returns whether this node is a successor of node. |
Get or set the text label of the information set. |
|
The |
|
Whether the information set belongs to the chance player. |
|
The player who has the move at this information set. |
|
The set of actions at the information set. |
|
The set of nodes which are members of the information set. |
|
|
Return whether this information set precedes node in the game tree. |
Get or set the text label of the action. |
|
Get the information set to which the action belongs. |
|
|
Returns whether node precedes this action in the extensive game. |
Get the probability a chance action is played. |
Get or set the text label associated with the strategy. |
|
The game to which the strategy belongs. |
|
The player to which the strategy belongs. |
|
The number of the strategy. |
Player behavior#
|
Create a mixed strategy profile over the game. |
|
Create a MixedStrategy on the game, with probabilities drawn from the uniform distribution over the set of mixed strategy profiles. |
|
Create a mixed behavior profile over the game. |
|
Create a MixedBehaviorProfile on the game, with probabilities drawn from the uniform distribution over the set of mixed behavior profiles. |
Representation of strategic behavior#
Probability distributions over strategies#
Represents a mixed strategy profile over the strategies in a |
|
The game on which this mixed strategy profile is defined. |
|
Iterate over the mixed strategies in the profile. |
|
Iterate over the probabilities assigned to strategies by the profile. |
|
Access a component of the mixed strategy profile specified by index. |
|
Sets a probability or a mixed strategy to value. |
|
|
Returns the expected payoff to a player if all players play according to the profile. |
|
Returns the expected payoff to playing the strategy, if all other players play according to the profile. |
|
Returns the regret to playing strategy, if all other players play according to the profile. |
Returns the regret of player for playing their mixed strategy, if all other players play according to the profile. |
|
Returns the maximum regret of any player. |
|
Returns the derivative of the payoff to playing strategy, with respect to the probability that other is played. |
|
Returns the Lyapunov value (see [McK91]) of the strategy profile. |
|
Creates a mixed behavior profile which is equivalent to this mixed strategy profile. |
|
Create a profile with the same strategy proportions as this one, but normalised so probabilities for each player sum to one. |
|
Creates a copy of the mixed strategy profile. |
|
|
A probability distribution over a player's strategies. |
Iterate over the probabilities assigned to strategies by the mixed strategy. |
|
|
Returns the probability that the strategy referred to by index is played. |
|
Sets the probability a strategy is played. |
Probability distributions over behavior#
Represents a mixed behavior profile over the actions in a |
|
The game on which this mixed behavior profile is defined. |
|
Iterate over the mixed behaviors in the profile. |
|
Iterate over the mixed actions specified by the profile. |
|
Iterate over the probabilities assigned to actions by the profile. |
|
Access a component of the mixed behavior specified by index. |
|
Sets a probability, mixed agent strategy, or mixed behavior strategy to value. |
|
|
Returns the expected payoff to a player if all players play according to the profile. |
Returns the regret to playing action, if all other players play according to the profile. |
|
Returns the expected payoff to the player of playing an action conditional on reaching its information set, if all players play according to the profile. |
|
|
Returns the expected payoff to the player conditional on reaching an information set, if all players play according to the profile. |
|
Returns the expected payoff to player conditional on play reaching node, if all players play according to the profile. |
Returns the probability with which a node is reached. |
|
|
Returns the probability with which an information set is reached. |
Returns the conditional probability that a node is reached, given that its information set is reached. |
|
|
Returns whether the profile has probabilities defined at the information set. |
Returns the Lyapunov value (see [McK91]) of the strategy profile. |
|
Returns a MixedStrategyProfile which is equivalent to the profile. |
|
Create a profile with the same action proportions as this one, but normalised so probabilities for each infoset sum to one. |
|
Creates a copy of the behavior strategy profile. |
|
|
A set of probability distributions describing a player's behavior. |
Iterate over the mixed actions specified by the mixed behavior. |
|
Iterate over the probabilities assigned to actions by the mixed behavior. |
|
|
Access a component of the mixed behavior specified by index. |
|
Sets a component of the mixed behavior to value. |
|
A probability distribution over a player's actions at an information set. |
Iterate over the probabilities assigned to actions by the mixed action. |
|
|
Returns the probability that the action referred to by index is played. |
|
Sets the probability an action is played. |
Computation on supports#
|
Return a support profile including only the strategies in profile which are not dominated by another pure strategy. |
Computation of Nash equilibria#
|
Represents the result of a method which computes Nash equilibria in a game. |
|
Compute all pure-strategy Nash equilibria of game. |
|
Compute all mixed-strategy Nash equilibria of a two-player game using the strategic representation. |
|
Compute Nash equilibria of a two-player constant-sum game using linear programming. |
|
Compute Nash equilibria of a two-player game using linear complementarity programming. |
|
Compute approximate Nash equilibria of a game using Lyapunov function minimization. |
|
Compute Nash equilibria of a game using the logit quantal response equilibrium correspondence. |
|
Compute Nash equilibria of a game using simplicial subdivision. |
|
Compute Nash equilibria of a game using iterated polymatrix approximation. |
|
Compute Nash equilibria of a game using a global Newton method. |
Computation of quantal response equilibria#
|
Use maximum likelihood estimation to estimate a quantal response equilibrium using the empirical payoff method. |
|
Use maximum likelihood estimation to find the logit quantal response equilibrium on the principal branch for a strategic game which best fits empirical frequencies of play. |
|
The result of fitting a QRE to a given probability distribution over strategies. |
The graphical interface#
Gambit’s graphical user interface provides an “integrated development environment” to help visually construct games and to investigate their main strategic features.
The graphical interface is largely intended for the interactive construction and analysis of small to medium games. Repeating the caution from the introduction of this manual, the computation time required for the equilibrium analysis of games increases rapidly in the size of the game. The graphical interface is ideal for students learning about the fundamentals of game theory, or for practitioners prototyping games of interest.
In graduating to larger applications, users are encouraged to make use of the underlying Gambit libraries and programs directly. For greater control over computing Nash and quantal response equilibria of a game, see the section on the command-line tools. To build larger games or to explore parameter spaces of a game systematically, it is recommended to use the Python package.
General concepts#
General layout of the main window#
The frame presenting a game consists of two principal panels. The main panel, to the right, displays the game graphically; in this case, showing the game tree of a simple one-card poker game. To the left is the player panel, which lists the players in the game; here, Fred and Alice are the players. Note that where applicable, information is color-coded to match the colors assigned to the players: Fred’s moves and payoffs are all presented in red, and Alice’s in blue. The color assigned to a player can be changed by clicking on the color icon located to the left of the player’s name on the player panel. Player names are edited by clicking on the player’s name, and editing the name in the text control that appears.
Two additional panels are available. Selecting toggles the display of an additional toolbar across the top of the window. This toolbar controls the indication and elimination of actions or strategies that are dominated. The use of this toolbar is discussed in Investigating dominated strategies and actions.
Selecting , or clicking the show profiles icon on the toolbar, toggles the display of the list of computed strategy profiles on the game. More on the way the interface handles the computation of Nash equilibria and other kinds of strategy profiles is presented in Computing Nash equilibria.
Payoffs and probabilities in Gambit#
Gambit stores all payoffs in games in an arbitrary-precision format. Payoffs may be entered as decimal numbers with arbitrarily many decimal places. In addition, Gambit supports representing payoffs using rational numbers. So, for example, in any place in which a payoff may appear, either an outcome of an extensive game or a payoff entry in a strategic game, the payoff one-tenth may be entered either as .1 or 1/10.
The advantage of this format is that, in certain circumstances, Gambit may be able to compute equilibria exactly. In addition, some methods for computing equilibria construct good numerical approximations to equilibrium points. For these methods, the computed equilibria are stored in floating-point format. To increase the number of decimal places shown for these profiles, click the increase decimals icon . To decrease the number of decimal places shown, click the decrease decimals icon .
Increasing or decreasing the number of decimals displayed in computed strategy profiles will not have any effect on the display of outcome payoffs in the game itself, since those are stored in arbitrary precision.
A word about file formats#
The graphical interface manipulates several different file formats for representing games. This section gives a quick overview of those formats.
Gambit has for many years supported two file formats for representing games, one for extensive games (typically using the filename extension .efg) and one for strategic games (typically using the filename extension .nfg). These file formats are recognized by all Gambit versions dating back to release 0.94 in 1995. (Users interested in the details of these file formats can consult Game representation formats for more information.)
Beginning with release 2005.12.xx, the graphical interface now reads and writes a new file format, which is referred to as a”Gambit workbook.” This extended file format stores not only the representation of the game, but also additional information, including parameters for laying out the game tree, the colors assigned to players, any equilibria or other analysis done on the game, and so forth. So, for example, the workbook file can be used to store the analysis of a game and then return to it. These files by convention end in the extension .gbt.
The graphical interface will read files in all three formats: .gbt, .efg, and .nfg. The “Save” and “Save as” commands, however, always save in the Gambit workbook (.gbt) format. To save the game itself as an extensive (.efg) or strategic (.nfg) game, use the items on the “Export” submenu of the “File” menu. This is useful in interfacing with older versions of Gambit, with other tools which read and write those formats, and in using the underlying Gambit analysis command- line tools directly, as those programs accept .efg or .nfg game files. Users primarily interested in using Gambit solely via the graphical interface are encouraged to use the workbook (.gbt) format.
As it is a new format, the Gambit workbook format is still under development and may change in details. It is intended that newer versions of the graphical interface will still be able to read workbook files written in older formats.
Extensive games#
The graphical interface provides a flexible set of operations for constructing and editing general extensive games. These are outlined below.
Creating a new extensive game#
To create a new extensive game, select , or click on the new extensive game icon . The extensive game created is a trivial game with two players, named by default Player 1 and Player 2, with one node, which is both the root and terminal node of the game. In addition, extensive games have a special player labeled Chance, which is used to represent random events not controlled by any of the strategic players in the game.
Adding moves#
There are two options for adding moves to a tree: drag-and-drop and the Insert move dialog.
Moves can be added to the tree using a drag-and-drop idiom. From the player list window, drag the player icon located to the left of the player who will have the move to any terminal node in the game tree. The tree will be extended with a new move for that player, with two actions at the new move. Adding a move for the chance player is done the same way, except the dice icon appearing to the left of the chance player in the player list window is used instead of the player icon. For the chance player, the two actions created will each be given a probability weight of one-half. If the desired move has more than two actions, additional actions can be added by dragging the same player’s icon to the move node; this will add one action to the move each time this is done.
Click on any terminal node in the tree, and select to display the insert move dialog. The dialog is intended to read like a sentence:
The first control specifies the player who will make the move. The move can be assigned to a new player by specifying Insert move for a new player here.
The second control selects the information set to which to add the move. To create the move in a new information set, select at a new information set for this control.
The third control sets the number of actions. This control is disabled unless the second control is set to at a new information set. Otherwise, it is set automatically to the number of actions at the selected information set.
The two methods can be useful in different contexts. The drag-and-drop approach is a bit quicker to use, especially when creating trees that have few actions at each move. The dialog approach is a bit more flexible, in that a move can be added for a new, as-yet-undefined player, a move can be added directly into an existing information set, and a move can be immediately given more than two actions.
Copying and moving subtrees#
Many extensive games have structures that appear in multiple parts of the tree. It is often efficient to create the structure once, and then copy it as needed elsewhere.
Gambit provides a convenient idiom for this. Clicking on any nonterminal node and dragging to any terminal node implements a move operation, which moves the entire subtree rooted at the original, nonterminal node to the terminal node.
To turn the operation into a copy operation:
On Windows and Linux systems, hold down the Ctrl key during the operation.
On OS X, hold down the Cmd key when starting the drag operation, then release prior to dropping.
The entire subtree rooted at the original node is copied, starting at the terminal node. In this copy operation, each node in the copied image is placed in the same information set as the corresponding node in the original subtree.
Copying a subtree to a terminal node in that subtree is also supported. In this case, the copying operation is halted when reaching the terminal node, to avoid an infinite loop. Thus, this feature can also be helpful in constructing multiple-stage games.
Removing parts of a game tree#
Two deletion operations are supported on extensive games. To delete the entire subtree rooted at a node, click on that node and select .
To delete an individual move from the game, click on one of the direct children of that node, and select . This operation deletes the parent node, as well as all the children of the parent other than the selected node. The selected child node now takes the place of the parent node in the tree.
Managing information sets#
Gambit provides several methods to help manage the information structure in an extensive game.
When building a tree, new moves can be placed in a given information set using the Insert move dialog. Additionally, new moves can be created using the drag-and-drop idiom by holding down the Shift key and dragging a node in the tree. During the drag operation, the cursor changes to the move icon . Dropping the move icon on another node places the target node in the same information set as the node where the drag operation began.
The information set to which a node belongs can also be set by selecting . This displays the node properties dialog. The Information set dropdown defaults to the current information set to which the node belongs, and contains a list of all other information sets in the game which are compatible with the node, that is, which have the same number of actions. Additionally, the node can be moved to a new, singleton information set by setting this dropdown to the New information set entry.
When building out a game tree using the drag-and-drop approach to copying portions of the tree, the nodes created in the copy of the subtree remain in the same information set as the corresponding nodes in the original subtree. In many cases, though, these trees differ in the information available to some or all of the players. To help speed the process of adjusting information sets in bulk, Gambit offers a “reveal” operation, which breaks information sets based on the action taken at a particular node. Click on a node at which the action taken is to be made known subsequently to other players, and select . This displays a dialog listing the players in the game. Check the boxes next to the players who observe the outcome of the move at the node, and click OK. The information sets at nodes below the selected one are adjusted based on the action selected at this node.
Note
The reveal operation only has an effect at the time it is done. In particular, it does not enforce the separation of information sets based on this information during subsequent editing of the game.
Outcomes and payoffs#
Gambit supports the specification of payoffs at any node in a game tree, whether terminal or not. Each node is created with no outcome attached; in this case, the payoff at each node is zero to all players. These are indicated in the game tree by the presence of a (u) in light grey to the right of a node.
To set the payoffs at a node, double-click on the (u) to the right of the node. This creates a new outcome at the node, with payoffs of zero for all players, and displays an editor to set the payoff of the first player.
The payoff to a player for an outcome can be edited by double-clicking on the payoff entry. This action creates a text edit control in which the payoff to that player can be modified. Edits to the payoff can be accepted by pressing the Enter key. In addition, accepting the payoff by pressing the Tab key both stores the changes to the player’s payoff, and advances the editor to the payoff for the next player at that outcome.
Outcomes may also be moved or copied using a drag-and-drop idiom. Left-clicking and dragging an outcome to another node moves the outcome from the original node to the target node. Copying an outcome may be accomplished by doing this same action while holding down the Control (Ctrl) key on the keyboard.
When using the copy idiom described above, the action assigns the same outcome to both the involved nodes. Therefore, if subsequently the payoffs of the outcome are edited, the payoffs at both nodes will be modified. To copy the outcome in such a way that the outcome at the target node is a different outcome from the one at the source, but with the same payoffs, hold down the Shift key instead of the Control key while dragging.
To remove an outcome from a node, click on the node, and select .
Formatting and labeling the tree#
Gambit offers some options for customizing the display of game trees.
Labels on nodes and branches#
The information displayed at the nodes and on the branches of the tree can be configured by selecting , which displays the tree labels dialog.
Above and below each node, the following information can be displayed:
- No label
The space is left blank.
- The node’s label
The text label assigned to the node. (This is the default labeling above each node.)
- The player’s name
The name of the player making the move at the node.
- The information set’s label
The name of the information set to which the node belongs.
- The information set’s number
A unique identifier of the information set, in the form player number:information set number. (This is the default labeling below each node.)
- The realization probability
The probability the node is reached. (Only displayed when a behavior strategy is selected to be displayed on the tree.)
- The belief probability
The probability a player assigns to being at the node, conditional on reaching the information set. (Only displayed when a behavior strategy is selected to be displayed on the tree.)
- The payoff of reaching the node
The expected payoff to the player making the choice at the node, conditional on reaching the node. (Only displayed when a behavior strategy is selected to be displayed on the tree.)
Above and below each branch, the following information can be displayed:
- No label
The space is left blank.
- The name of the action
The name of the action taken on the branch. (This it the default labeling above the branch.)
- The probability the action is played
For chance actions, the probability the branch is taken; this is always displayed. For player actions, the probability the action is taken in the selected profile (only displayed when a behavior strategy is selected to be displayed on the tree). In some cases, behavior strategies do not fully specify behavior sufficiently far off the equilibrium path; in such cases, an asterisk is shown for such action probabilities. (This is the default labeling below each branch.)
- The value of the action
The expected payoff to the player of taking the action, conditional on reaching the information set. (Only displayed when a behavior strategy is selected to be displayed on the tree.)
Controlling the layout of the tree#
Gambit implements an automatic system for layout out game trees, which provides generally good results for most games. These can be adjusted by selecting . The layout parameters are organized on three tabs.
The first tab, labeled Nodes, controls the size, location, and rendering of nodes in the tree. Nodes can be indicated using one of five tokens: a horizontal line (the “traditional” Gambit style from previous versions), a box, a diamond, an unfilled circle, and a filled circle). These can be set independently to distinguish chance and terminal nodes from player nodes.
The sizing of nodes can be configured for best results. Gambit styling from previous versions used the horizontal line tokens with relatively long lines; when using the other tokens, smaller node sizes often look better.
The layout algorithm is based upon identifying the location of terminal nodes. The vertical spacing between these nodes can be set; making this value larger will tend to give the tree a larger vertical extent.
The second tab, labeled Branches, controls the display of the branches of the tree. The traditional Gambit way of drawing branches is a “fork-tine” approach, in which there is a flat part at the end of each branch at which labels are displayed. Alternatively, branches can be drawn directly between nodes by setting Draw branches to using straight lines between nodes. With this setting, labels are now displayed at points along the (usually) diagonal branches. Labels are usually shown horizontally; however, they can be drawn rotated parallel to the branches by setting Draw labels to rotated.
The rotated label drawing is experimental, and does not always look good on screen.
The length used for branches and their tines, if drawn, can be configured. Longer branch and tine lengths give more space for longer labels to be drawn, at the cost of giving the tree a larger horizontal extent.
Finally, display of the information sets in the game is configured under the tab labeled Information sets. Members of information sets are by default connected using a “bubble” similar to that drawn in textbook diagrams of games. The can be modified to use a single line to connect nodes in the same information set. In conjunction with using lines for nodes, this can sometimes lead to a more compact representation of a tree where there are many information sets at the same horizontal location.
The layout of the tree may be such that members of the same information set appear at different horizontal locations in the tree. In such a case, by default, Gambit draws a horizontal arrow pointing rightward or leftward to indicate the continuation of the information set, as illustrated in the diagram nearby.
These connections can be disabled by setting Connect members of information sets to only when on the same level. In addition, drawing information set indicators can be disabled entirely by setting this to invisibly (don’t draw indicators).
Selecting fonts and colors#
To select the font used to draw the labels in the tree, select . The standard font selection dialog for the operating system is displayed, showing the fonts available on the system. Since available fonts vary across systems, when opening a workbook on a system different from the system on which it was saved, Gambit tries to match the font style as closely as possible when the original font is not available.
The color-coding for each player can be changed by clicking on the color icon to the left of the corresponding player.
Strategic games#
Gambit has full support for constructing and manipulating arbitrary N-player strategic (also known as normal form) games.
For extensive games, Gambit automatically computes the corresponding reduced strategic game. To view the reduced strategic game corresponding to an extensive game, select or click the strategic game table icon on the toolbar.
The strategic games computed by Gambit as the reduced strategic game of an extensive game cannot be modified directly. Instead, edit the original extensive game; Gambit automatically recomputes the strategic game after any changes to the extensive game.
Strategic games may also be input directly. To create a new strategic game, select , or click the new strategic game icon on the toolbar.
Navigating a strategic game#
Gambit displays a strategic game in table form. All players are assigned to be either row players or column players, and the payoffs for each entry in the strategic game table correspond to the payoffs corresponding to the situation in which all the row players play the strategy specified on that row for them, and all the column players play the strategy specified on that column for them.
For games with two players, this presentation is by default configured to be similar to the standard presenation of strategic games as tables, in which one player is assigned to be the “row” player and the other the “column” player. However, Gambit permits a more flexible assignment, in which multiple players can be assigned to the rows and multiple players to the columns. This is of particular use for games with more than two players. In print, a three-player strategic game is usually presented as a collection of tables, with one player choosing the row, the second the column, and the third the table. Gambit presents such games by hierarchially listing the strategies of one or more players on both rows and columns.
The hierarchical presentation of the table is similar to that of a contingency table in a spreadsheet application. Here, Alice, shown in red, has her strategies listed on the rows of the table, and Bob, shown in blue, has his strategies listed on the columns of the table.
The assignment of players to row and column roles is fully customizable. To change the assignment of a player, drag the person icon appearing to the left of the player’s name on the player toolbar to either of the areas in the payoff table displaying the strategy labels.
For example, dragging the player icon from the left of Bob’s name in the list of players and dropping it on the right side of Alice’s strategy label column changes the display of the game as in Here, the strategies are shown in a hierarchical format, enumerating the outcomes of the game first by Alice’s (red) strategy choice, then by Bob’s (blue) strategy choice.
Alternatively, the game can be displayed by listing the outcomes with Bob’s strategy choice first, then Alice’s. Drag Bob’s player icon and drop it on the left side of Alice’s strategy choices, and the game display changes to organize the outcomes first by Bob’s action, then by Alice’s.
The same dragging operation can be used to assign players to the columns. Assigning multiple players to the columns gives the same hierarchical presentation of those players’ strategies. Dropping a player above another player’s strategy labels assigns him to a higher level of the column player hierarchy; dropping a player below another player’s strategy labels assigns him to a lower level of the column player hierarchy.
As the assignment of players in the row and column hierarchies changes, the ordering of the payoffs in each cell of the table also changes. In all cases, the color-coding of the entries identifies the player to whom each payoff corresponds. The ordering convention is chosen so that for a two player game in which one player is a row player and the other a column player, the row player’s payoff is shown first, followed by the column player, which is the most common convention in print.
Adding players and strategies#
To add an additional player to the game, use the menu item , or the corresponding toolbar icon . The newly created player has one strategy, by default labeled with the number 1.
Gambit supports arbitrary numbers of strategies for each player. To add a new strategy for a player, click the new strategy icon located to the left of that player’s name.
To edit the names of strategies, click on any cell in the strategic game table where the strategy label appears, and edit the label using the edit control.
Editing payoffs#
Payoffs for each player are specified individually for each contingency, or collection of strategies, in the game. To edit any payoff in the table, click that cell in the table and edit the payoff. Pressing the Escape key (Esc) cancels any editing of the payoff and restores the previous value.
To speed entry of many payoffs, as is typical when creating a new game, accepting a payoff entry via the Tab key automatically moves the edit control to the next cell to the right. If the payoff is the last payoff listed in a row of the table, the edit control wraps around to the first payoff in the next row; if the payoff is in the last row, the edit control wraps around to the first payoff in the first row. So a strategic game payoff table can be quickly entered by clicking on the first payoff in the upper-left cell of the table, inputting the payoff for the first (row) player, pressing the Tab key, inputting the payoff for the second (column) player, pressing the Tab key, and so forth, until all the payoff entries in the table have been filled.
Investigating dominated strategies and actions#
Selecting toggles the appearance of a toolbar which can be used to investigate the structure of dominated strategies and actions.
Dominated actions in extensive game#
In extensive games, the dominance toolbar controls the elimination of actions which are conditionally dominated.
Actions may be eliminated based on two criteria:
- Strict dominance
The action is always worse than another, regardless of beliefs at the information set;
- Strict or weak dominance
There is another action at the information set that is always at least as good as the action, and strictly better in some cases.
For example, in the poker game, it is strictly dominated for Fred to choose Fold after Red. Clicking the next level icon removes the dominated action from the game display.
The tree layout remains unchanged, including nodes which can only be reached using actions which have been eliminated. To compress the tree to remove the unreachable nodes, check the box labeled Show only reachable nodes.
For this game, no further actions can be eliminated. In general, further steps of elimination can be done by again clicking the next level icon. The toolbar keeps track of the number of levels of elimination currently shown; the previous level icon moves up one level of elimination.
The elimination of multiple levels can be automated using the fast forward icon , which iteratively eliminates dominated actions until no further actions can be eliminated. The rewind icon restores the display to the full game.
Dominated strategies in strategic games#
The dominance toolbar operates in strategic games in the same way as the in the extensive game. Strategies can be eliminated iteratively based on whether they are strictly or weakly dominated.
When the dominance toolbar is shown, the strategic game table contains indicators of strategies that are dominated. In the prisoner’s dilemma, the Cooperate strategy is strictly dominated for both players. This strict dominance is indicated by the solid “X” drawn across the corresponding strategy labels for both players. In addition, the payoffs corresponding to the dominated strategies are also drawn with a solid “X” across them. Thus, any contingency in the table containing at least one “X” is a contingency that can only be reached by at least one player playing a strategy that is dominated.
Strategies that are weakly dominated are similarly indicated, except the “X” shape is drawn using a thinner, dashed line instead of the thick, solid line.
Clicking the next level icon removes the strictly dominated strategies from the display.
Computing Nash equilibria#
Gambit offers broad support for computing Nash equilibria in both extensive and strategic games. To access the provided algorithms for computing equilibria, select , or click on the calculate icon on the toolbar.
Selecting the method of computing equilibria#
The process of computing Nash equilibria in extensive and strategic games is similar. This section focuses on the case of extensive games; the process for strategic games is analogous, except the extensive game-specific features, such as displaying the profiles on the game tree, are not applicable.
Gambit provides guidance on the options for computing Nash equilibria in a dialog. The methods applicable to a particular game depend on three criteria: the number of equilibria to compute, whether the computation is to be done on the extensive or strategic games, and on details of the game, such as whether the game has two players or more, and whether the game is constant-sum.
The first step in finding equilibria is to specify how many equilibria are to be found. Some algorithms for computing equilibria are adapted to finding a single equilibrium, while others attempt to compute the whole equilibrium set. The first drop-down in the dialog specifies how many equilibria to compute. In this drop-down there are options for as many equilibria as possible and, for two-player games, all equilibria. For some games, there exist algorithms which will compute many equilibria (relatively) efficiently, but are not guaranteed to find all equilibria.
To simplify this process of choosing the method to compute equilibria in the second drop-down, Gambit provides for any game “recommended” methods for computing one, some, and all Nash equilibria, respectively. These methods are selected based on experience as to the efficiency and reliability of the methods, and should generally work well on most games. For more control over the process, the user can select from the second drop-down in the dialog one of the appropriate methods for computing equilibria. This list only shows the methods which are appropriate for the game, given the selection of how many equilibria to compute. More details on these methods are contained in Command-line tools.
Finally, for extensive games, there is an option of whether to use the extensive or strategic game for computation. In general, computation using the extensive game is preferred, since it is often a significantly more compact representation of the strategic characeteristics of the game than the reduced strategic game is.
For even moderate sized games, computation of equilibrium can be a time-intensive process. Gambit runs all computations in the background, and displays a dialog showing all equilibria computed so far. The computation can be cancelled at any time by clicking on the cancel icon , which terminates the computation but keeps any equilibria computed.
Viewing computed profiles in the game#
After computing equilibria, a panel showing the list of equilibria computed is displayed automatically. The display of this panel can be toggled by selecting , or clicking on the playing card icon on the toolbar.
This game has a unique equilibrium in which Fred raises after Red with probability one, and raises with probability one-third after Black. Alice, at her only information set, plays meet with probability two- thirds and raise with probability one-third.
This equilibrium is displayed in a table in the profiles panel. If more than one equilibrium is found, this panel lists all equilibria found. Equilibria computed are grouped by separate computational runs; computing equilibria using a different method (or different settings) will add a second list of profiles. The list of profiles displayed is selected using the drop-down at the top left of the profiles panel; in the screenshot, it is set to Profiles 1. A brief description of the method used to compute the equilibria is listed across the top of the profiles panel.
The currently selected equilibrium is shown in bold in the profiles listing, and information about this equilibrium is displayed in the extensive game. In the figure, the probabilities of selecting each action are displayed below each branch of the tree. (This is the default Gambit setting; see Controlling the layout of the tree for configuring the labeling of trees.) Each branch of the tree also shows a black line, the length of which is proportional to the probability with which the action is played.
Clicking on any node in the tree displays additional information about the profile at that node. The player panel displays information relevant to the selected node, including the payoff to all players conditional on reaching the node, as well as information about Alice’s beliefs at the node.
The computed profiles can also be viewed in the reduced strategic game. Clicking on the strategic game icon changes the view to the reduced strategic form of the game, and shows the equilibrium profiles converted to mixed strategies in the strategic game.
Computing quantal response equilibria#
Gambit provides methods for computing the logit quantal response equilibrium correspondence for extensive games [McKPal98] and strategic games [McKPal95], using the tracing method of [Tur05].
To compute the correspondence, select . If viewing an extensive game, the agent quantal response equilibrium correspondence is computed; if viewing a strategic game (including the reduced strategic game derived from an extensive game), the correspondence is computed in mixed strategies.
The computed correspondence values can be saved to a CSV (comma- separated values) file by clicking the button labeled Save correspondence to .csv file. This format is suitable for reading by a spreadsheet or graphing application.
Quantal response equilibria in strategic games (experimental)#
There is an experimental graphing interface for quantal response equilibria in strategic games. The graph by default plots the probabilities of all strategies, color- coded by player, as a function of the lambda parameter. The lambda values on the horizontal axis are plotted using a sigmoid transformation; the Graph scaling value controls the shape of this transformation. Lower values of the scaling give more graph space to lower values of lambda; higher values of the scaling give more space to higher values of lambda.
The strategies graphed are indicated in the panel at the left of the window. Clicking on the checkbox next to a strategy toggles whether it is displayed in the graph.
The data points computed in the correspondence can be viewed (as in the extensive game example above) by clicking on the show data icon on the toolbar. The data points can be saved to a CSV file by clicking on the .
To zoom in on a portion of the graph of interest, hold down the left mouse button and drag a rectangle on the graph. The plot window zooms in on the portion of the graph selected by that rectangle. To restore the graph view to the full graph, click on the zoom to fit icon .
To print the graph as shown, click on the print icon . Note that this is very experimental, and the output may not be very satisfactory yet.
Printing and exporting games#
Gambit supports (almost) WYSIWYG (what you see is what you get) output of both extensive and strategic games, both to a printer and to several graphical formats. For all of these operations, the game is drawn exactly as currently displayed on the screen, including whether the extensive or strategic representation is used, the layout, colors for players, dominance and probability indicators, and so forth.
Printing a game#
To print the game, press Ctrl-P, select , or click the printer icon on the toolbar. The game is scaled so that the printout fits on one page, while maintaining the same ratio of horizontal to vertical size; that is, the scaling factor is the same in both horizontal and vertical dimensions.
Note that especially for extensive games, one dimension of the tree is much larger than the other. Typically, the extent of the tree vertically is much greater than its horizontal extent. Because the printout is scaled to fit on one page, printing such a tree will generally result in what appears to be a thin line running vertically down the center of the page. This is in fact the tree, shrunk so the large vertical dimension fits on the page, meaning that the horizontal dimension, scaled at the same ratio, becomes very tiny.
Saving to a graphics file#
Gambit supports export to five graphical file formats:
Windows bitmaps ( .bmp )
JPEG, a lossy compressed format ( .jpg , .jpeg )
PNG, a lossless compressed format ( .png ); these are similar to GIFs
Encapsulated PostScript ( .ps )
Scalable vector graphics ( .svg )
To export a game to one of these formats, select , and select the corresponding menu entry.
The Windows bitmap and PNG formats are generally recommended for export, as they both are lossless formats, which will reproduce the game image exactly as in Gambit. PNG files use a lossless compression algorithm, so they are typically much smaller than the Windows bitmap for the same game. Not all image viewing and manipulation tools handle PNG files; in those cases, use the Windows bitmap output instead. JPEG files use a compression algorithm that only approximates the original version, which often makes it ill-suited for use in saving game images, since it often leads to “blocking” in the image file.
For all three of these formats, the dimensions of the exported graphic are determined by the dimensions of the game as drawn on screen. Image export is only supported for games which are less than about 65000 pixels in either the horizontal or vertical dimensions. This is unlikely to be a practical problem, since such games are so large they usually cannot be drawn in such a way that a human can make sense of them.
Encapsulated PostScript output is generally useful for inclusion in LaTeX and other scientific document preparation systems. This is a vector-based output, and thus can be rescaled much more effectively than the other output formats.
Sample games#
2x2x2.nfgA three-player normal form game with two strategies per player. This game has nine Nash equilibria, which is the maximal number of regular Nash equilibria possible for a game of this size. See McKelvey, Richard D. and McLennan, Andrew (1997). The maximal number of regular totally mixed Nash equilibria. Journal of Economic Theory 72(2): 411-425.
2x2x2-nau.nfgA three-player normal form game with two strategies per player. This game has three pure strategy equilibria, two equilibria which are incompletely mixed, and a continuum of completely mixed equilibria. This game appears as an example in Nau, Robert, Gomez Canovas, Sabrina, and Hansen, Pierre (2004). On the geometry of Nash equilibria and correlated equilibria. International Journal of Game Theory 32(4): 443-453.
bagwell.efgStackelberg leader game with imperfectly observed commitment, from Bagwell, Kyle (1993) Commitment and observability in games. Games and Economic Behavior 8: 271-280.
bayes2a.efgA twice-repeated Bayesian game, with two players, each having two types and two actions. This game also illustrates the use of payoffs at nonterminal nodes in Gambit, which can substantially simplify the representation of multi-stage games such as this.
cent3.efgA three-stage centipede game, featuring an exogenous probability that one player is an altruistic type, who always passes. See, for example, McKelvey, Richard D. and Palfrey, Thomas R. (1992) An experimental study of the centipede game. Econometrica 60(4): 803-836.
condjury.efgA three-person Condorcet jury game, after the analysis of Feddersen, Timothy and Pesendorfer, Wolfgang (1998) Convicting the innocent: The inferiority of unanimous jury verdicts under strategic voting. American Political Science Review 92(1): 23-35..
loopback.nfgA game due to McKelvey which illustrates that the logit quantal response equilibrium correspondence can have a “backward-bending” segment on the principal branch.
montyhal.efgThe famous Monty Hall problem: if Monty offers to let you switch doors, should you?
nim.efgThe classic game of Nim, which is a useful example of the value of backward induction. This version starts with five stones. An interesting experimental study of this class of games is McKinney, C. Nicholas and Van Huyck, John B. (2013) Eureka learning: Heuristics and response time in perfect information games. Games and Economic Behavior 79: 223-232.
pbride.efgA signaling game from Joel Watson’s Strategy textbook, modeling the confrontation in The Princess Bride between Humperdinck and Roberts in the bedchamber.
poker.efgA simple game of one-card poker introduced in Myerson, Roger (1991) Game Theory: Analysis of Conflict.. A bit unusually for poker, the “fold” action by a player with a strong hand counts for a win for that player, so folding is only weakly rather than strictly dominated in this case.
4cards.efgA slightly more complex poker example, contributed by Alix Martin.
spence.efgA version of Spence’s classic job-market signaling game. This version comes from Joel Watson’s Strategy textbook.
These games, and others, ship in the standard Gambit source distribution in the directory contrib/games.
For developers: Building Gambit from source#
This section covers instructions for building Gambit from source. This is for those who are interested in developing Gambit, or who want to play around with the latest features before they make it into a pre-compiled binary version.
This section requires at least some familiarity with programming. Most users will want to stick with binary distributions; see Downloading Gambit for how to get the current version for your operating system.
General information#
Gambit uses the standard autotools mechanism for configuring and building. This should be familiar to most users of Un*ces and MacOS X.
If you are building from a source tarball, you just need to unpack the sources, change directory to the top level of the sources (typically of the form gambit-xx.y.z), and do the usual
./configure
make
sudo make install
Command-line options are available to modify the configuration process; do ./configure –help for information. Of these, the option which may be most useful is to disable the build of the graphical interface
By default Gambit will be installed in /usr/local. You can change this by replacing configure step with one of the form
./configure --prefix=/your/path/here
Note
The graphical interface relies on external calls to other programs built in this process, especially for the computation of equilibria. It is strongly recommended that you install the Gambit executables to a directory in your path!
Building from git repository#
If you want to live on the bleeding edge, you can get the latest version of the Gambit sources from the Gambit repository on github.com, via
git clone https://github.com/gambitproject/gambit.git
cd gambit
After this, you will need to set up the build scripts by executing
aclocal
libtoolize
automake --add-missing
autoconf
For this, you will need to have automake, autoconf, and libtool2 installed on your system.
At this point, you can then continue with the configuration and build stages as in the previous section.
In the git repository, the branch master always points to the
latest development version. New development should in general always
be based off this branch. Branches labeled maintVV, where VV
is the version number, point to the latest commit on a stable
version.
For Windows users#
For Windows users wanting to compile Gambit on their own, you’ll need to use either the Cygwin or MinGW environments. We do compilation and testing of Gambit on Windows using MinGW.
For OS X users#
For building the command-line tools only, one should follow the instructions for Un*x/Linux platforms above.
The graphical interface and wxWidgets#
Gambit requires wxWidgets version 3.1.x or higher. See the wxWidgets website at http://www.wxwidgets.org to download this if you need it. Packages of this should be available for most Un*x users through their package managers (apt or rpm). Note that you’ll need the appropriate -dev package for wxWidgets to get the header files needed to build Gambit.
Un*x users, please note that Gambit at this time only supports the GTK port of wxWidgets.
If wxWidgets it isn’t installed in a standard place (e.g., /usr or /usr/local), you’ll need to tell configure where to find it with the –with-wx-prefix=PREFIX option, for example:
./configure --with-wx-prefix=/home/mylogin/wx
Finally, if you don’t want to build the graphical interface, you can either (a) simply not install wxWidgets, or (b) pass the argument –disable-gui to the configure step, for example,
./configure --disable-gui
This will just build the command-line tools, and will not require a wxWidgets installation.
For OS X users, after the usual make step, run
make osx-bundle
This produces an application Gambit.app in the current directory,
which can be run from its current location, or copied elsewhere in the
disk (such as /Applications). The application bundle includes the
command-line executables.
Building the Python extension#
The pygambit Python package is in src/pygambit
in the Gambit source tree.
Building the extension follows the standard approach.
From the root directory of the source tree execute
python -m pip install .
There is a set of test cases in src/pygambit/tests, which can be run using nose2.
Once installed, simply import pygambit in your Python shell or
script to get started.
Game representation formats#
This section documents the file formats recognized by Gambit. These file formats are text-based and designed to be readable and editable by hand by humans to the extent possible, although programmatic tools to generate and manipulate these files are almost certainly needed for all but the most trivial of games.
These formats can be viewed as being low-level. They define games explicitly in terms of their structure, and do not support any sort of parameterization, macros, and the like. Thus, they are adapted largely to the type of input required by the numerical methods for computing Nash equilibria, which only apply to a particular realization of a game’s parameters. Higher-level tools, whether the graphical interface or scripting applications, are indicated for doing parametric analysis and the like.
Conventions common to all file formats#
Several conventions are common to the interpretation of the file formats listed below.
Whitespace is not significant. In general, whitespace (carriage returns, horizontal and vertical tabs, and spaces) do not have an effect on the meaning of the file. The only exception is inside explicit double-quotes, where all characters are significant. The formatting shown here is the same as generated by the Gambit code and has been chosen for its readability; other formattings are possible (and legal).
Text labels. Most objects in an extensive game may be given textual labels. These are prominently used in the graphical interface, for example, and it is encouraged for users to assign nonempty text labels to objects if the game is going to be viewed in the graphical interface. In all cases, these labels are surrounded by the quotation character (“). The use of an explicit “ character within a text label can be accomplished by preceding the embedded “ characters with a backwards slash (). This is an alternate version of the first line of the example file, in which the title of the game contains the term Bayesian game in quotation marks:
EFG 2 R "An example of a \"Bayesian game\"" { "Player 1" "Player 2" }
Numerical data. Numerical data, namely, the payoffs at outcomes, and the action probabilities for chance nodes, may be expressed in integer, decimal, or rational formats. In all cases, numbers are understood by Gambit to be exact, and represented as such internally. For example, the numerical entries 0.1 and 1/10 represent the same quantity.
In versions 0.97 and prior, Gambit distinguished between floating point and rational data. In these versions, the quantity 0.1 was represented interally as a floating-point number. In this case, since 0.1 does not have an exact representation in binary floating point, the values 0.1 and 1/10 were not identical, and some methods for computing equilibria could give (slightly) different results for games using one versus the other. In particular, using rational-precision methods on games with the floating point numbers could give unexpected output, since the conversion of 0.1 first to floating-point then to rational would involve roundoff error. This is largely of technical concern, and the current Gambit implementation now behaves in such a way as to give the “expected” result when decimal numbers appear in the file format.
The extensive game (.efg) file format#
The extensive game (.efg) file format has been used by Gambit, with minor variations, to represent extensive games since circa 1994. It replaced an earlier format, which had no particular name but which had the conventional extension .dt1. It is intended that some new formats will be introduced in the future; however, this format will be supported by Gambit, possibly through the use of converter programs to those putative future formats, for the foreseeable future.
A sample file#
This is a sample file illustrating the general format of the file. This file is similar to the one distributed in the Gambit distribution under the name bayes1a.efg:
EFG 2 R "General Bayes game, one stage" { "Player 1" "Player 2" }
c "ROOT" 1 "(0,1)" { "1G" 0.500000 "1B" 0.500000 } 0
c "" 2 "(0,2)" { "2g" 0.500000 "2b" 0.500000 } 0
p "" 1 1 "(1,1)" { "H" "L" } 0
p "" 2 1 "(2,1)" { "h" "l" } 0
t "" 1 "Outcome 1" { 10.000000 2.000000 }
t "" 2 "Outcome 2" { 0.000000 10.000000 }
p "" 2 1 "(2,1)" { "h" "l" } 0
t "" 3 "Outcome 3" { 2.000000 4.000000 }
t "" 4 "Outcome 4" { 4.000000 0.000000 }
p "" 1 1 "(1,1)" { "H" "L" } 0
p "" 2 2 "(2,2)" { "h" "l" } 0
t "" 5 "Outcome 5" { 10.000000 2.000000 }
t "" 6 "Outcome 6" { 0.000000 10.000000 }
p "" 2 2 "(2,2)" { "h" "l" } 0
t "" 7 "Outcome 7" { 2.000000 4.000000 }
t "" 8 "Outcome 8" { 4.000000 0.000000 }
c "" 3 "(0,3)" { "2g" 0.500000 "2b" 0.500000 } 0
p "" 1 2 "(1,2)" { "H" "L" } 0
p "" 2 1 "(2,1)" { "h" "l" } 0
t "" 9 "Outcome 9" { 4.000000 2.000000 }
t "" 10 "Outcome 10" { 2.000000 10.000000 }
p "" 2 1 "(2,1)" { "h" "l" } 0
t "" 11 "Outcome 11" { 0.000000 4.000000 }
t "" 12 "Outcome 12" { 10.000000 2.000000 }
p "" 1 2 "(1,2)" { "H" "L" } 0
p "" 2 2 "(2,2)" { "h" "l" } 0
t "" 13 "Outcome 13" { 4.000000 2.000000 }
t "" 14 "Outcome 14" { 2.000000 10.000000 }
p "" 2 2 "(2,2)" { "h" "l" } 0
t "" 15 "Outcome 15" { 0.000000 4.000000 }
t "" 16 "Outcome 16" { 10.000000 0.000000 }
Structure of the prologue#
The extensive gamefile consists of two parts: the prologue, or header, and the list of nodes, or body. In the example file, the prologue is the first line. (Again, this is just a consequence of the formatting we have chosen and is not a requirement of the file structure itself.)
The prologue is constructed as follows. The file begins with the token EFG , identifying it as an extensive gamefile. Next is the digit 2 ; this digit is a version number. Since only version 2 files have been supported for more than a decade, all files have a 2 in this position. Next comes the letter R . The letter R used to distinguish files which had rational numbers for numerical data; this distinction is obsolete, so all new files should have R in this position.
The prologue continues with the title of the game. Following the title is a list of the names of the players defined in the game. This list follows the convention found elsewhere in the file of being surrounded by curly braces and delimited by whitespace (but not commas, semicolons, or any other character). The order of the players is significant; the first entry in the list will be numbered as player 1, the second entry as player 2, and so forth. At the end of the prologue is an optional text comment field.
Structure of the body (list of nodes)#
The body of the file lists the nodes which comprise the game tree. These nodes are listed in the prefix traversal of the tree. The prefix traversal for a subtree is defined as being the root node of the subtree, followed by the prefix traversal of the subtree rooted by each child, in order from first to last. Thus, for the whole tree, the root node appears first, followed by the prefix traversals of its child subtrees. For convenience, the game above follows the convention of one line per node.
Each node entry begins with an unquoted character indicating the type of the node. There are three node types:
c for a chance node
p for a personal player node
t for a terminal node
Each node type will be discussed individually below. There are three numbering conventions which are used to identify the information structure of the tree. Wherever a player number is called for, the integer specified corresponds to the index of the player in the player list from the prologue. The first player in the list is numbered 1, the second 2, and so on. Information sets are identified by an arbitrary positive integer which is unique within the player. Gambit generates these numbers as 1, 2, etc. as they appear first in the file, but there are no requirements other than uniqueness. The same integer may be used to specify information sets for different players; this is not ambiguous since the player number appears as well. Finally, outcomes are also arbitrarily numbered in the file format in the same way in which information sets are, except for the special number 0 which indicates the null outcome.
Information sets and outcomes may (and frequently will) appear multiple times within a game. By convention, the second and subsequent times an information set or outcome appears, the file may omit the descriptive information for that information set or outcome. Alternatively, the file may specify the descriptive information again; however, it must precisely match the original declaration of the information set or outcome. If any part of the description is omitted, the whole description must be omitted.
Outcomes may appear at nonterminal nodes. In these cases, payoffs are interepreted as incremental payoffs; the payoff to a player for a given path through the tree is interpreted as the sum of the payoffs at the outcomes encountered on that path (including at the terminal node). This is ideal for the representation of games with well- defined”stages”; see, for example, the file bayes2a.efg in the Gambit distribution for a two-stage example of the Bayesian game represented previously.
In the following lists, fields which are omittable according to the above rules are indicated by the label (optional).
Format of chance (nature) nodes. Entries for chance nodes begin with the character c . Following this, in order, are
a text string, giving the name of the node
a positive integer specifying the information set number
(optional) the name of the information set
(optional) a list of actions at the information set with their corresponding probabilities
a nonnegative integer specifying the outcome
(optional)the payoffs to each player for the outcome
Format of personal (player) nodes. Entries for personal player decision nodes begin with the character p . Following this, in order, are:
a text string, giving the name of the node
a positive integer specifying the player who owns the node
a positive integer specifying the information set
(optional) the name of the information set
(optional) a list of action names for the information set
a nonnegative integer specifying the outcome
(optional) the name of the outcome
the payoffs to each player for the outcome
Format of terminal nodes. Entries for terminal nodes begin with the character t . Following this, in order, are:
a text string, giving the name of the node
a nonnegative integer specifying the outcome
(optional) the name of the outcome
the payoffs to each player for the outcome
There is no explicit end-of-file delimiter for the file.
The strategic game (.nfg) file format, payoff version#
This file format defines a strategic N-player game. In this version, the payoffs are listed in a tabular format. See the next section for a version of this format in which outcomes can be used to identify an equivalence among multiple strategy profiles.
A sample file#
This is a sample file illustrating the general format of the file. This file is distributed in the Gambit distribution under the name e02.nfg:
NFG 1 R "Selten (IJGT, 75), Figure 2, normal form"
{ "Player 1" "Player 2" } { 3 2 }
1 1 0 2 0 2 1 1 0 3 2 0
Structure of the prologue#
The prologue is constructed as follows. The file begins with the token NFG , identifying it as a strategic gamefile. Next is the digit 1 ; this digit is a version number. Since only version 1 files have been supported for more than a decade, all files have a 1 in this position. Next comes the letter R . The letter R used to distinguish files which had rational numbers for numerical data; this distinction is obsolete, so all new files should have R in this position.
The prologue continues with the title of the game. Following the title is a list of the names of the players defined in the game. This list follows the convention found elsewhere in the file of being surrounded by curly braces and delimited by whitespace (but not commas, semicolons, or any other character). The order of the players is significant; the first entry in the list will be numbered as player 1, the second entry as player 2, and so forth.
Following the list of players is a list of positive integers. This list specifies the number of strategies available to each player, given in the same order as the players are listed in the list of players.
The prologue concludes with an optional text comment field.
Structure of the body (list of payoffs)#
The body of the format lists the payoffs in the game. This is a “flat” list, not surrounded by braces or other punctuation.
The assignment of the numeric data in this list to the entries in the strategic game table proceeds as follows. The list begins with the strategy profile in which each player plays their first strategy. The payoffs to all players in this contingency are listed in the same order as the players are given in the prologue. This, in the example file, the first two payoff entries are 1 1 , which means, when both players play their first strategy, player 1 receives a payoff of 1, and player 2 receives a payoff of 1.
Next, the strategy of the first player is incremented. Thus, player 1’s strategy is incremented to his second strategy. In this case, when player 1 plays his second strategy and player 2 his first strategy, the payoffs are 0 2 : a payoff of 0 to player 1 and a payoff of 2 to player 2.
Now the strategy of the first player is again incremented. Thus, the first player is playing his third strategy, and the second player his first strategy; the payoffs are again 0 2 .
Now, the strategy of the first player is incremented yet again. But, the first player was already playing strategy number 3 of 3. Thus, his strategy now “rolls over” to 1, and the strategy of the second player increments to 2. Then, the next entries 1 1 correspond to the payoffs of player 1 and player 2, respectively, in the case where player 1 plays his second strategy, and player 2 his first strategy.
In general, the ordering of contingencies is done in the same way that we count: incrementing the least-significant digit place in the number first, and then incrementing more significant digit places in the number as the lower ones “roll over.” The only differences are that the counting starts with the digit 1, instead of 0, and that the “base” used for each digit is not 10, but instead is the number of strategies that player has in the game.
The strategic game (.nfg) file format, outcome version#
This file format defines a strategic N-player game. In this version, the payoffs are defined by means of outcomes, which may appear more than one place in the game table. This may give a more compact means of representing a game where many different strategy combinations map to the same consequences for the players. For a version of this format in which payoffs are listed explicitly, without identification by outcomes, see the previous section.
A sample file#
This is a sample file illustrating the general format of the file. This file defines the same game as the example in the previous section:
NFG 1 R "Selten (IJGT, 75), Figure 2, normal form" { "Player 1" "Player 2" }
{
{ "1" "2" "3" }
{ "1" "2" }
}
{
{ "" 1, 1 }
{ "" 0, 2 }
{ "" 0, 2 }
{ "" 1, 1 }
{ "" 0, 3 }
{ "" 2, 0 }
}
1 2 3 4 5 6
Structure of the prologue#
The prologue is constructed as follows. The file begins with the token NFG , identifying it as a strategic gamefile. Next is the digit 1 ; this digit is a version number. Since only version 1 files have been supported for more than a decade, all files have a 1 in this position. Next comes the letter R . The letter R used to distinguish files which had rational numbers for numerical data; this distinction is obsolete, so all new files should have R in this position.
The prologue continues with the title of the game. Following the title is a list of the names of the players defined in the game. This list follows the convention found elsewhere in the file of being surrounded by curly braces and delimited by whitespace (but not commas, semicolons, or any other character). The order of the players is significant; the first entry in the list will be numbered as player 1, the second entry as player 2, and so forth.
Following the list of players is a list of strategies. This is a nested list; each player’s strategies are given as a list of text labels, surrounded by curly braces.
The nested strategy list is followed by an optional text comment field.
The prologue closes with a list of outcomes. This is also a nested list. Each outcome is specified by a text string, followed by a list of numerical payoffs, one for each player defined. The payoffs may optionally be separated by commas, as in the example file. The outcomes are implicitly numbered in the order they appear; the first outcome is given the number 1, the second 2, and so forth.
Structure of the body (list of outcomes)#
The body of the file is a list of outcome indices. These are presented in the same lexicographic order as the payoffs in the payoff file format; please see the documentation of that format for the description of the ordering. For each entry in the table, a nonnegative integer is given, corresponding to the outcome number assigned as described in the prologue section. The special outcome number 0 is reserved for the “null” outcome, which is defined as a payoff of zero to all players. The number of entries in this list, then, should be the same as the product of the number of strategies for all players in the game.
The action graph game (.agg) file format#
Action graph games (AGGs) are a compact representation of simultaneous-move games with structured utility functions. For more information on AGGs, the following paper gives a comprehensive discussion.
A.X. Jiang, K. Leyton-Brown and N. Bhat, Action-Graph Games, Games and Economic Behavior, Volume 71, Issue 1, January 2011, Pages 141-173.
Each file in this format describes an action graph game. In order for the file to be recognized as AGG by GAMBIT, the initial line of the file should be:
#AGG
The rest of the file consists of 8 sections, separated by whitespaces. Lines with starting ‘#’ are treated as comments and are allowed between sections.
The number of players, n.
The number of action nodes, |S|.
The number of function nodes, |P|.
Size of action set for each player. This is a row of n integers:
|S1| |S2| …. |Sn|
Each Player’s action set. We have N rows; row i has |Si| integers in ascending order, which are indices of Action nodes. Action nodes are indexed from 0 to |S|-1.
The Action Graph. We have |S| + |P| nodes, indexed from 0 to |S| + |P|-1. The function nodes are indexed after the action nodes. The graph is represented as (|S| + |P|) neighbor lists, one list per row. Rows 0 to |S| - 1 are for action nodes; rows |S| to |S| + |P|-1 are for function nodes. In each row, the first number |v| specifies the number of neighbors of the node. Then follows |v| numbers, corresponding to the indices of the neighbors.
We require that each function node has at least one neighbor, and the neighbors of function nodes are action nodes. The action graph restricted to the function nodes has to be a directed acyclic graph (DAG).
Signatures of functions. This is |P| rows, each specifying the mapping f_p that maps from the configuration of the function node p’s neighbors to an integer for p’s “action count”. Each function is specified by its “signature” consisting of an integer type, possibly followed by further parameters. Several types of mapping are implemented:
Types 0-3 require no further input.
Type 0: Sum. i.e. The action count of a function node p is the sum of the action counts of p’s neighbors.
Type 1: Existence: boolean for whether the sum of the counts of neighbors are positive.
Type 2: The index of the neighbor with the highest index that has non-zero counts, or |S| + |P| if none applies.
Type 3: The index of the neighbor with the lowest index that has non-zero counts, or |S| + |P| if none applies.
Types 10-13 are extended versions of type 0-3, each requiring further parameters of an integer default value and a list of weights, |S| integers enclosed in square brackets. Each action node is thus associated with an integer weight.
Type 10: Extended Sum. Each instance of an action in p’s neighborhood being chosen contributes the weight of that action to the sum. These are added to the default value.
Type 11: Extended Existence: boolean for whether the extended sum is positive. The input default value and weights are required to be nonnegative.
Type 12: The weight of the neighbor with the highest index that has non-zero counts, or the default value if none applies.
Type 13: The weight of the neighbor with the lowest index that has non-zero counts, or the default value if none applies.
The following is an example of the signatures for an AGG with three action nodes and two function nodes:
2 10 0 [2 3 4]
The payoff function for each action node. So we have |S| subblocks of numbers. Payoff function for action s is a mapping from configurations to real numbers. Configurations are represented as a tuple of integers; the size of the tuple is the size of the neighborhood of s. Each configuration specifies the action counts for the neighbors of s, in the same order as the neighbor list of s.
The first number of each subblock specifies the type of the payoff function. There are multiple ways of representing payoff functions; we (or other people) can extend the file format by defining new types of payoff functions. We define two basic types:
- Type 0
The complete representation. The set of possible configurations can be derived from the action graph. This set of configurations can also be sorted in lexicographical order. So we can just specify the payoffs without explicitly giving the configurations. So we just need to give one row of real numbers, which correspond to payoffs for the ordered set of configurations.
If action s is in multiple players’ action sets (say players i, j), then it is possible that the set of possible configurations given si is different from the set of possible configurations given sj. In such cases, we need to specify payoffs for the union of the sets of configurations (sorted in lexicographical order).
- Type 1
The mapping representation, in which we specify the configurations and the corresponding payoffs. For the payoff function of action s, first give Delta_s, the number of elements in the mapping. Then follows Delta_s rows. In each row, first specify the configuration, which is a tuple of integers, enclosed by a pair of brackets “[” and “]”, then the payoff. For example, the following specifies a payoff function of type 1, with two configurations:
1 2 [1 0] 2.5 [1 1] -1.2
The Bayesian action graph game (.bagg) format#
Bayesian action graph games (BAGGs) are a compact representation of Bayesian (i.e., incomplete-information) games. For more information on BAGGs, the following paper gives a detailed discussion.
A.X. Jiang and K. Leyton-Brown, Bayesian Action-Graph Games. NIPS, 2010.
Each file in this format describes a BAGG. In order for the file to be recognized as BAGG by GAMBIT, the initial line of the file should be:
#BAGG
The rest of the file consists of the following sections, separated by whitespaces. Lines with starting ‘#’ are treated as comments and are allowed between sections.
The number of Players, n.
The number of action nodes, |S|.
The number of function nodes, |P|.
The number of types for each player, as a row of n integers.
Type distribution for each player. The distributions are assumed to be independent. Each distribution is represented as a row of real numbers. The following example block gives the type distributions for a BAGG with two players and two types for each player:
0.5 0.5 0.2 0.8
Size of type-action set for each player’s each type.
Type-action set for each player’s each type. Each type-action set is represented as a row of integers in ascending order, which are indices of action nodes. Action nodes are indexed from 0 to |S|-1.
The action graph: same as in `the AGG format`_.
types of functions: same as in `the AGG format`_.
utility function for each action node: same as in `the AGG format`_.
Bibliography#
Articles on computation of Nash equilibria#
Bland, J. R. and Turocy, T. L., 2023. Quantal response equilibrium as a structural model for estimation: The missing manual. SSRN working paper 4425515.
B. C. Eaves, “The linear complementarity problem”, 612-634, Management Science , 17, 1971.
Govindan, Srihari and Robert Wilson. (2003) “A Global Newton Method to Compute Nash Equilibria.” Journal of Economic Theory 110(1): 65-86.
Govindan, Srihari and Robert Wilson. (2004) “Computing Nash Equilibria by Iterated Polymatrix Approximation.” Journal of Economic Dynamics and Control 28: 1229-1241.
A. X. Jiang, K. Leyton-Brown, and N. Bhat. (2011) “Action-Graph Games.” Games and Economic Behavior 71(1): 141-173.
Daphne Koller, Nimrod Megiddo, and Bernhard von Stengel (1996). “Efficient computation of equilibria for extensive two-person games.” Games and Economic Behavior 14: 247-259.
C. E. Lemke and J. T. Howson, “Equilibrium points of bimatrix games”, 413-423, Journal of the Society of Industrial and Applied Mathematics , 12, 1964.
O. Mangasarian, “Equilibrium points in bimatrix games”, 778-780, Journal of the Society for Industrial and Applied Mathematics, 12, 1964.
Richard McKelvey, A Liapunov function for Nash equilibria, 1991, California Institute of Technology.
Richard McKelvey and Andrew McLennan, “Computation of equilibria in finite games”, 87-142, Handbook of Computational Economics , Edited by H. Amman, D. Kendrick, J. Rust, Elsevier, 1996.
Ryan Porter, Eugene Nudelman, and Yoav Shoham. “Simple search methods for finding a Nash equilibrium.” Games and Economic Behavior 664-669, 2004.
J. Rosenmuller, “On a generalization of the Lemke-Howson Algorithm to noncooperative n-person games”, 73-79, SIAM Journal of Applied Mathematics, 21, 1971.
Lloyd Shapley, “A note on the Lemke-Howson algorithm”, 175-189, Mathematical Programming Study , 1, 1974.
Theodore L. Turocy, “A dynamic homotopy interpretation of the logistic quantal response equilibrium correspondence”, 243-263, Games and Economic Behavior, 51, 2005.
Theodore L. Turocy, “Using Quantal Response to Compute Nash and Sequential Equilibria.” Economic Theory 42(1): 255-269, 2010.
G. van der Laan, A. J. J. Talman, and L. van Der Heyden, “Simplicial variable dimension algorithms for solving the nonlinear complementarity problem on a product of unit simplices using a general labelling”, 377-397, Mathematics of Operations Research , 1987.
Robert Wilson, “Computing equilibria of n-person games”, 80-87, SIAM Applied Math, 21, 1971.
Y. Yamamoto, 1993, “A Path-Following Procedure to Find a Proper Equilibrium of Finite Games “, International Journal of Game Theory .
General game theory articles and texts#
John Harsanyi, “Games of Incomplete Information Played By Bayesian Players I”, 159-182, Management Science , 14, 1967.
John Harsanyi, “Games of Incomplete Information Played By Bayesian Players II”, 320-334, Management Science , 14, 1967.
John Harsanyi, “Games of Incomplete Information Played By Bayesian Players III”, 486-502, Management Science , 14, 1968.
David Kreps and Robert Wilson, “Sequential Equilibria”, 863-894, Econometrica , 50, 1982.
Richard McKelvey and Tom Palfrey, “Quantal response equilibria for normal form games”, 6-38, Games and Economic Behavior , 10, 1995.
Richard McKelvey and Tom Palfrey, “Quantal response equilibria for extensive form games”, 9-41, Experimental Economics , 1, 1998.
Roger Myerson, “Refinements of the Nash equilibrium concept”, 73-80, International Journal of Game Theory , 7, 1978.
John Nash, “Equilibrium points in n-person games”, 48-49, Proceedings of the National Academy of Sciences , 36, 1950.
Jack Ochs, “Games with unique, mixed strategy equilibria: An experimental study”, Games and Economic Behavior 10: 202-217, 1995.
Reinhard Selten, Reexamination of the perfectness concept for equilibrium points in extensive games , 25-55, International Journal of Game Theory , 4, 1975.
Eric van Damme, 1983, Stability and Perfection of Nash Equilibria , Springer-Verlag, Berlin.
Textbooks and general reference#
Roger Myerson, 1991, Game Theory : Analysis of Conflict , Harvard University Press.