The drop-down menu for game solvers should be improved:
- Automatic choice of most informative output (all equilibrium components) for small games
- Enumerating all equilibria of a two-player game tree, as implemented by Wan Huang.
- Default for zero-sum games: Simplex algorithm with subsequent enumeration of extreme optimal strategies using linear programming.
- Display of Lemke-Howson path network.
- Varying starting vector using Elzen/Talman.
This is being pursued by Christian Pelissier as part of his MSc dissertation under the supervision of Bernhard von Stengel and was sponsored by GSoC 2014. It is a substantial project,
- Allow more than two players in extensive form
- For strategic-form input, three players choose row/column/panel with intuitive interface, to be designed.
- easy way to swap/rotate players (needs implementation for two players, too)
- For small games, complete description of all equilibria using polynomial algebra.
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.
- Languages: C
- Prerequisites: Senior-level mathematics, interest in game theory and some basic topology.
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.
- which are pages 21-41 of
- http://www.maths.lse.ac.uk/Personal/stengel/phds/anne-final.pdf
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.
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.
- Languages: Python
- Prerequisites: Experience with text processing to pass data to and from the external solvers.