In [1]:
import gambit
The situation with games with three (or more) players is a bit more complex. There are several methods which can be used to compute equilibria for games with three or more players, but all have some limitations, whether theoretical, practical, or both.
We will use a three-player game as our example, in which each player has exactly two strategies each. This game has nine Nash equilibria, which is the maximum number of isolated equilibria a game of this dimension can have. It is also well-behaved in that the game continues to have nine equilibria even if payoffs are perturbed slightly.
In [2]:
g = gambit.Game.read_game("2x2x2.nfg")
import IPython.display; IPython.display.HTML(g.write('html'))
Out[2]:
For this example, I will run the various methods using the command-line tools via the shell. Several of these tools optionally print out some useful status information when run on the command-line, which is not (yet) logged and returned by the Python calls.
First up is simplicial subdivision, gambit-simpdiv. This operates essentially like the proof of the Brouwer fixed point theorem: It divides up the space of mixed strategies into a "grid" of simplices, and follows a path along that grid. The grid is then refined, and the process repeated.
Each run of the algorithm requires a starting point in the space of mixed strategy profiles. Which equilibrium you find depends on your starting point, and there's no guarantee the equilibrium you find bears any clear relationship to your starting point (it could in principle be arbitrarily far away in the space of mixed strategy profiles).
In [3]:
!gambit-simpdiv 2x2x2.nfg
In [4]:
!gambit-simpdiv -h
In [5]:
!gambit-simpdiv -n 5 -r 16 -V 2x2x2.nfg
The next two methods were proposed by Govindan and Wilson, and this implementation is based on the Gametracer package by Blum and Shelton. The global Newton method gambit-gnm uses the idea of the structure theorem (as we encountered in Bagwell's example). It picks a perturbation vector of the payoffs of the game, goes far out enough in that "direction" in payoff space such that the game has a unique equilibrium, and then traces backwards towards the original game. As the path of equilibria is followed, it may cross the original game more than once, so it is possible that this method will find more than one equilibrium - but it will not necessarily find all of them, and which equilibria are found depends on the choice of the perturbation vector.
In [6]:
!gambit-gnm 2x2x2.nfg
In [7]:
!gambit-gnm -h
We can use the -V switch to understand a bit more how the equilibria are found. Each intermediate step shows, in the first column, the homotopy parameter (how much the perturbation vector is multiplied by). Each entry shows a "turning point" in the path.
In [8]:
!gambit-gnm -V 2x2x2.nfg
Closely related (and also proposed by Govindan and Wilson and implemented in Gametracer by Blum and Shelton) is iterated polymatrix approximation, which speeds up the homotopy calculation by approximating the game as a polymatrix game (i.e., one where each player, in effect, plays a two-player game against each other player).
In [9]:
!gambit-ipa -h
In [10]:
!gambit-ipa 2x2x2.nfg
Another path-following approach uses quantal response equilibria, as proposed by McKelvey and Palfrey (1995) and implemented by Turocy (2005). Instead of perturbing the payoffs of the game, QRE perturbs the accuracy of the best response. Turocy (2005) showed that using the logit form of the accuracy of the best response has nice computational properties. The method starts from uniform randomisation across all strategies, and in the limit computes a Nash equilibrium. As instrumented here, this computes one Nash equilibrium (which McKelvey-Palfrey called the "logit solution"), but there do exist other branches of the QRE correspondence which can be used to compute equilibria (if you can find them, which is the tricky part...)
This is at present the best and most reliable way to compute one equilibrium of a game with three or more players. This is not a theoretical claim; this is simply because I invested a lot of time implementing it carefully for the 2005 GEB paper (and subsequent use in experimental game theory), so it has received rather more love and attention than other methods to date.
In [11]:
!gambit-logit 2x2x2.nfg
All methods so far compute one, or possibly many, equilibria, but none are guaranteed to find all equilibria in all games. There is exactly one such method, which operates by enumerating all of the subsets of supports in the game, and, for each of them, asks whether there is a totally mixed equilibrium on that support. The latter question amounts to a collection of polynomial equations. The number of possible supports grows quickly (but searching them is embarrassingly parallelizable!), but finding all solutions to a system of polynomial equations does take a bit of work in practice.
In Gambit, we have one implementation of this, done in the mid-1990s by Andrew McLennan, which currently ships as gambit-enumpoly. It uses the Pelican library by Birk Huber, which dates from the early 1990s, which I believe was translated from FORTRAN (and which is the bane of my existence in terms of maintenance with each new compiler version...)
If you give the -V switch, you can see each candidate support reported as it is inspected. In the case of this example, it works great on most of the supports, but has a problem with the full support (on which there are two totally mixed equilibria).
In [12]:
!gambit-enumpoly -V 2x2x2.nfg
This example comes from Nau et al (IJGT 2004) On the geometry of Nash equilibria and correlated equilibria. It is a very useful example case for computing Nash equilibria, in that there is an equilibrium component which is one-dimensional, and also spans three different supports. If you think of the set of mixed strategy profiles of this 2x2x2 game as a cube, this component starts along one edge (corresponding to incompletely-mixed equilibria), then curves across through the centre of the cube until it reaches the edge catercorner from the first, then continues along that edge (corresponding to more incompletely-mixed equilibria).
In [18]:
g = gambit.Game.read_game("2x2x2-nau.nfg")
import IPython.display; IPython.display.HTML(g.write('html'))
Out[18]:
None of the existing implementations do very well at giving the naive user much insight into the equilibrium structure.
In [19]:
!gambit-gnm -V 2x2x2-nau.nfg
In [20]:
!gambit-ipa 2x2x2-nau.nfg
gambit-logit does successfully pick out one of the totally-mixed equilibria at least, but doesn't (on its own) warn you about the one-dimensional component.
Interesting observation: This is the equilibrium in that component that has the highest entropy. I have a conjecture that any limiting QRE is either a local max or local min of entropy over the set of Nash equilibria. Anyone interested in having a go at trying to prove this, chat to me! I have no idea what use such a result would be however... ;)
In [21]:
!gambit-logit 2x2x2-nau.nfg
The performance of gambit-enumpoly on this game is a bit of a mixed bag. It fails to find anything but the pure equilibria. However, it does provide interesting diagnostic information, that some of the supports are "singular." Actually, this mostly just means that something went wrong and it gave up - but often this happens because the set of equations has a positive-dimensional set of solutions. So at least it provides some diagnostics that one might want to inspect those supports more closely.
In [22]:
!gambit-enumpoly -V 2x2x2-nau.nfg
There is however some hope on the horizon. Both PHCpack http://homepages.math.uic.edu/~jan/download.html and Bertini https://bertini.nd.edu are polynomial system solvers that deal with positive-dimensional sets of solutions. There is a Python script in the contrib/ directory of the Gambit repository which interfaces with these (but the script needs updating to the current version of the Python interface).
In [ ]: