MAP: Resolve future of enumpoly_solve/gambit-enumpoly

[tturocy]

Background

Gambit has offered the enumpoly_solve method since the late 1990s. This is a somewhat misleadingly named method, as the implementation combines two operations which are in some sense logically distinct.

One aspect - from which it gets its name - is that it finds equilibria by attempting to solve the systems of polynomial equations defining a totally-mixed Nash equilibrium on a given support profile of a game. If a solution to that system of equations yields valid probabilities, and further there are no strategies (or actions) outside the support which give a higher payoff, then a Nash equilibrium has been found.

Because the equations being solved are for a totally-mixed equilibrium, to make this a useful method it's necessary to enumerate the possible supports that could in principle harbour a totally-mixed equilibrium (on that support). Therefore, there is also a support enumeration aspect to the implementation. Further, it is possible to take different approaches to support enumeration - and indeed Gambit also offers some heuristic methods for prioritising certain supports, which have been contributed in the past.

At present, this support enumeration is largely embedded in the method, but it is worth noting that support enumeration could be useful in other contexts as well, and there is no necessity that, given a support profile of interest, equilibria need to be found using the polynomial solver method.

Turning focus specifically to the polynomial solver, Gambit's implementation was written principally by Andrew McLennan. It makes use of the pelican library written by Birk Huber circa 1995. Over the years we have done what we can to keep it compiling, especially as it is C code. The advent of 64-bit compilers have exposed issues with type declarations which appear possibly insurmountable - and at the moment enumpoly is not compiling or made available on Windows. (See #288.)

Discussion

This is an important method, because it is at the moment the only method that can find all Nash equilibria in a game with more than two players, and some users have reported that it works well for them in practice. On the other hand, there are known problems with it, such as #198. Given the state of the code, and how long ago it was written (both the Gambit layer and the underlying pelican implementation), it is probably not tenable to try to refactor and debug it.

PHCPack (https://homepages.math.uic.edu/~jan/PHCpack/phcpack.html) is an excellent piece of software for solving polynomial systems, and in the past we have had experimental Python codes that interface with it. These are currently in the contrib directory of the repository, and getting it back integrated has been on the wish list for some time (see #165).

The methods for solving polynomial systems are quite specialised, and have applications outside of game theory, so this is clearly an area where Gambit should be interfacing with other tools and letting those tools do the solving. However, doing so creates some additional burden as far as packaging, and, as usual, especially on Windows.

Certainly, at a minimum, what should be done is to refactor support enumeration out into an algorithm (or more accurately set of algorithms) in its own right. If we do this, then we have a lot more flexibility in plugging in different backends to solve the games defined by the subsets of strategies in the generated support profiles. This is already envisaged in the support-related roadmap issue in #341.

To-do list actions

• ENH: Remove enumpoly references from graphical interface and disable build by default #392
• Add maximum iterations in enumpoly to avoid infinite loop