Gambit: Software Tools for Game Theory
Gambit: Software Tools for Game Theory
For developers: Building Gambit from source
Enter search terms or a module, class or function name.
Research on doing computation on finite games, and using numerical and algorithmic methods to analyze games, are areas of quite active research. There are a number of opportunities for programmers of all skill levels and backgrounds to contribute to improving and extending Gambit.
A number of such ideas are outlined in this section. Each project includes the required implementation environment, and a summary of the background prerequisites someone should have in order to take on the project successfully, in terms of mathematics, game theory, and software engineering.
For beginning contibutors - especially those who are interested in potentially applying to work on Gambit projects in future Google Summer of Code editions - there are a number of issues in the Gambit issue tracker tagged as “easy”. These are excellent ways to get familiar with the Gambit codebase. Contributors who have completed one or more such easy tasks will have a significantly greater chance of being considered for possible GSoC work.
The Gambit source tree is managed using git. It is recommended to have some familiarity with how git works, or to be willing to learn. (It’s not that hard, and once you do learn it, you’ll wonder how you ever lived without it.)
Here is the main system architecture and some terminology, useful for understanding how the various projects fit into the greater whole:
GTE is implemented in Java on the server and Flash (Action Script) on the client side. So far, all equilibrium-finding algorithms have been ported into Java. These should be replaced by better performing original algorithms, such as lrs in C, by invoking them via system calls. These should be the same modules that are invoked from the Gambit command line.
There are a number of outstanding issues in the GTE interface, including:
The initial implementation of GTE is in Flash. There is interest in porting this implementation to JavaScript for greater portability.
Web frameworks offer standard functionality of storage of user data, including user identification via login. The project is to create such a framework and webpages to retrieve typically used games, and store games created by the user.
Possible extension: Record-keeping and display of results for computational experiments. If games are generated systematically with various parameters, running times and computational results should be recorded systematically.
The basic library (in src/libgambit) for representing games was written in the mid-1990s. As such, it predates many modern C++ features (including templates, STL, exceptions, Boost, and so on). This project involves carrying out a thorough review of the basic library code. Tasks will/may include:
All tasks will involve coordination with the Python API to ensure this does not break as changes are made, so a working knowledge of Python/Cython is indicated.
Through the work of Albert Jiang and the research group of Prof Kevin Leyton-Brown at University of British Columbia, there is an implementation of support for the Action Graph Games representation structure. See
Jiang, A. X., Leyton-Brown, K., and Bhat, N. A. R. (2011) Action-graph games. Games and Economic Behavior 71(1): 141-173. http://dx.doi.org/10.1016/j.geb.2010.10.012
A preliminary integration of the work has been done in the agg branch in the Gambit git repository.
This project would involve completing the integration of their work for distribution. The primary tasks will involve code refactoring, documentation, and the construction of a test suite.
Each of the following are separate ideas for open projects on computing equilibria and other interesting quantities on games. Each of these is a single project For GSoC applications, you should select exactly one of these, as each is easily a full summer’s worth of work (no matter how easy some of them may seem at first read!)
The task is to implement the EEE algorithm, which is a published algorithm to enumerate all extreme equilibria of a bimatrix game.
Fuller details:
The task is to implement the EEE algorithm, which is a published algorithm to enumerate all extreme equilibria of a bimatrix game.
The most up-to-date version can be found in Sections 7 and 8 of
D. Avis, G. Rosenberg, R. Savani, and B. von Stengel (2010), Enumeration of Nash equilibria for two-player games. Economic Theory 42, 9-37.
http://www.maths.lse.ac.uk/Personal/stengel/ETissue/ARSvS.pdf
Extra information, including some code, is provided in the following report:
G. Rosenberg (2004), Enumeration of All Extreme Equilibria of Bimatrix Games with Integer Pivoting and Improved Degeneracy Check. CDAM Research Report LSE-CDAM-2004-18.
The original algorithm was described in the following paper:
C. Audet, P. Hansen, B. Jaumard, and G. Savard (2001), Enumeration of all extreme equilibria of bimatrix games. SIAM Journal on Scientific Computing 23, 323–338.
The implementation should include a feature to compare the algorithm’s output (a list of extreme equilibria) with the ouput of other algorithms for the same task (e.g. lrsnash).
In addition a framework that compares running times (and the number of recursive calls, calls to pivoting methods, and other crucial operations) should be provided. The output should record and document the computational experiments so that they can be reproduced, in a general setup - sufficiently documented - that can be used for similar comparisons.
Gambit incorporates the Gametracer package to provide implementations of two methods for computing equilibria, gambit-gnm and gambit-ipa. The integration is rather crude, as internally the program converts the game from native Gambit representation into Gametracer’s representation, and the converts the output back. Using Gametracer’s implementations as a starting point, refactor the implementation to use Gambit’s native classes directly, and carry out experiments on the reliability and performance of the algorithms.
Gambit’s gambit-enummixed tool computes all extreme Nash equilibria of a two-player game. There is another package, lrslib by David Avis, which implements the same algorithm more efficiently and robustly. There is a partial interface with an older version of lrslib in the Gambit source tree, which has proven not to be very reliable. The project is to complete the integration and testing of the lrslib integration.
Related to the Lemke-Howson method above, but with a slightly different algorithm that has an extra parameter, called the “covering vector”. That parameter can serve a randomly selected starting point of the computation and potentially reach many more equilibria.
The task is to implement a published algorithm to compute the so-called index of an equilibrium component in a bimatrix game. This component is the output to an existing enumeration algorithm.
Fuller details:
The aim of this project is to implement an existing algorithm that finds the index of an equilibrium component. The relevant description of this is chapter 2 of
Anne Balthasar, Geometry and Equilibria in Bimatrix Games, PhD Thesis, London School of Economics, 2009.
The mathematics in this chapter are pretty scary (in particular section 2.2, which is however not needed) but the final page 41 which describes the algorithm is less scary.
Nevertheless, this is rather advanced material because it builds on several different existing algorithms (for finding extreme equilibria in bimatrix games, and “cliques” that define convex sets of equilibria, and their non-disjoint unions that define “components”). It requires the understanding of what equilibria in bimatrix games are about. These algorithms are described in
D. Avis, G. Rosenberg, R. Savani, and B. von Stengel (2010), Enumeration of Nash equilibria for two-player games. Economic Theory 42, 9-37.
http://www.maths.lse.ac.uk/Personal/stengel/ETissue/ARSvS.pdf
and students who do not eventually understand that text should not work on this project. For this reason, at least senior-level (= third year) mathematics is required in terms of mathematical maturity. In the Avis et al. (2010) paper, pages 19-21 describe the lexicographic method for pivoting as it is used in the simplex method for linear programming. A variant of this lexicographic method is used in the chapter by Anne Balthasar. Understanding this is a requirement to work on this project (and a good test of how accessible all this is).
We give here two brief examples that supplement the above literature. Consider the following bimatrix game. It is very simple, and students of game theory may find it useful to first find out on their own what the equilibria of this game are:
2 x 2 Payoff matrix A:
1 1
0 1
2 x 2 Payoff matrix B:
1 1
0 1
EE = Extreme Equilibrium, EP = Expected Payoff
EE 1 P1: (1) 1 0 EP= 1 P2: (1) 1 0 EP= 1
EE 2 P1: (1) 1 0 EP= 1 P2: (2) 0 1 EP= 1
EE 3 P1: (2) 0 1 EP= 1 P2: (2) 0 1 EP= 1
Connected component 1:
{1, 2} x {2}
{1} x {1, 2}
This shows the following: there are 3 Nash equilibria, which partly use the same strategies of the two players, which are numbered (1), (2) for each player. It will take a bit of time to understand the above output. For our purposes, the bottom “component” is most relevant: It has two lines, and {1, 2} x {2} means that equilibrium (1),(2) - which is according to the previous list the strategy pair (1,0), (1,0) as well as (2),(2), which is (0,1), (1,0) are “extreme equilibria”, and moreover any convex combination of (1) and (2) of player 1 - this is the first {1, 2} - can be combined with strategy (2) of player 2. This is part of the “clique” output of Algorithm 2 on page 19 of Avis et al. (2010). There is a second such convex set of equilibria in the second line, indicated by {1} x {1, 2}. Moreover, these two convex sets intersect (in the equilibrium (1),(2)) and form therefore a “component” of equilibria. For such a component, the index has to be found, which happens to be the integer 1 in this case.
The following bimatrix game has also two convex sets of Nash equilibria, but they are disjoint and therefore listed as separate components on their own:
3 x 2 Payoff matrix A:
1 1
0 1
1 0
3 x 2 Payoff matrix B:
2 1
0 1
0 1
EE = Extreme Equilibrium, EP = Expected Payoff
Rational Output
EE 1 P1: (1) 1 0 0 EP= 1 P2: (1) 1 0 EP= 2
EE 2 P1: (2) 1/2 1/2 0 EP= 1 P2: (2) 0 1 EP= 1
EE 3 P1: (3) 1/2 0 1/2 EP= 1 P2: (1) 1 0 EP= 1
EE 4 P1: (4) 0 1 0 EP= 1 P2: (2) 0 1 EP= 1
Connected component 1:
{1, 3} x {1}
Connected component 2:
{2, 4} x {2}
Here the first component has index 1 and the second has index 0. One reason for the latter is that if the game is slightly perturbed, for example by giving a slightly lower payoff than 1 in row 2 of the game, then the second strategy of player 1 is strictly dominated and the equilibria (2) and (4) of player 1, and thus the entire component 2, disappear altogether. This can only happen if the index is zero, so the index gives some useful information as to whether an equilibrium component is “robust” or “stable” when payoffs are slightly perturbed.
Extension of an existing algorithm for enumerating all equilibria of a bimatrix game to game trees with imperfect information using the so-called “sequence form”. The method is described in abstract form but not implemented.
The set of Nash equilibrium conditions can be expressed as a system of polynomial equations and inequalities. The field of algebraic geometry has been developing packages to compute all solutions to a system of polynomial equations. Two such packages are PHCpack and Bertini. Gambit has an experimental interface, written in Python, to build the required systems of equations, call out to the solvers, and identify solutions corresponding to Nash equilibria. Refactor the implementation to be more flexible and Pythonic, and carry out experiments on the reliability and performance of the algorithms.
Herings and Peeters (Economic Theory, 18(1), 159-185, 2001) have proposed a homotopy algorithm to compute Nash equilibria. They have created a first implementation of the method in Fortran, using hompack. Create a Gambit implementation of this method, and carry out experiments on the reliability and performance of the algorithms.