You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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:
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:
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.
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.Related issues
This discussion potentially extends or supersedes part or all of several previous issues:
The text was updated successfully, but these errors were encountered: