ENH: Develop implementation of LCP solvers

[tturocy]

Historical background

The implementation of the linear complementarity solvers (using Lemke-Howson for strategic games and Lemke for extensive games) is some of the oldest Nash-finding code in Gambit. Developments over the intervening ca. 25 years suggest that a review of this implementation is in order, especially given the importance of these methods.

Some notes for historical context include:

• The implementation is templated, and uses the same code to implement floating-point and rational precision calculations. The rational precision calculations are inefficient as each value is represented as its own rational number, not taking advantage of common remainders, and the arbitrary-precision integer implementation underlying the rational numbers is likely also not very efficient.
• It is far from clear that the OOP design of the tableaux concepts is appropriate, in terms of the benefits that abstraction brings relative to the use of tableaux across these two methods (as well as the LP solver).

Proposed action

There are various C codes written by von Stengel, Savani, and Igwe, which implement both methods in exact arithmetic. They are almost surely in every way superior to the rational-precision implementation currently in Gambit. At the moment, they are not yet packaged and instrumented to be easy to integrate into other software.

• Confirm whether the functionality of the library fully supersedes what is offered by the existing Gambit implementations for rational-precision arithmetic.
• Consider how to integrate this library. Does it make sense simply to embed the code? Or, does it make sense to package it as its own library for working with linear complementary problems? These algorithms do have applications outside of equilibrium computation (cf. lrslib). Therefore there could be benefits to packaging this as a separate library, at a small cost of creating a bit of complexity in the build process for Gambit itself.
• Evaluate whether there are legitimate use cases for providing LCP solvers that do arithmetic in floating-point precision. Historically, Gambit allowed payoffs and chance probabilities to be stored as floating-point numbers. When that was the case, trying to solve a game in rational precision using the existing implementation performed extremely poorly, because the resulting rational numbers had many digits. Now, Gambit stores all payoffs exactly, which partially addresses that problem. Nevertheless, there could be applications involving drawing games randomly according to some distribution over payoff functions, or games with payoffs that are truly real numbers because of e.g. utilities arising from risk aversion. In these applications, the rounding problems that exact arithmetic addresses, should not be an issue. How performant is the exact implementation with these kind of games as input data? Does it imply that providing a floating-point implementation is a good idea?

Related issues

This discussion potentially extends or supersedes part or all of several previous issues:

• Allow using other LP/LCP solvers #301
• Modernise the LCP solver implementation #192
• Clean up algorithm working data in gambit-lcp #138