Clean up algorithm working data in gambit-lcp

[tturocy]

Both the strategic and sequence form LCP implementations in src/nash/lcp carry around a Solution class (defined as a nested class inside the LCP algorithm driver) object, which includes working data on the current run of the algorithm. In refactoring LCP to use the new Nash equilibrium computation framework in Gambit 14, just enough was done to remove all algorithm state from the algorithm classes themselves. However, more could be done to encapsulate properly the algorithm state, including:

• Move some operations to be operations on the Solution class, rather than being done inline in the algorithm.
• Consider incorporating other working data, such as the Tableau classes. If possible, it might make sense to have the internal private member function calls passing around mostly just the game being solved, and the Solution class; possibly, the game itself should be part of that.

In addition, the filling of the Tableau in both implementations - but especially the sequence form version - is very awkwardly done. This could do with some proper encapsulation, rather than the current rather opaque indexing calculations.

Note that eventually something like the Solution class might be passed back to the caller (rather than just a list of computed equilibrium profiles), with the idea being that richer data on the running of the algorithm might be interesting. Design of this class should be done with that in mind.

[tturocy]

Assigning this to myself for now, as carrying out this work requires a bit of experience with understanding the LCP setup. Others are quite welcome to have a go at this, but would do well to consult with me first before trying it. Newcomers to Gambit or game theory should definitely not be thinking about taking this one on!

[stengel]

Hi Ted,

would you like to use some of the C libraries from

https://github.com/stengel/ecta2002

for your Lemke re-implementation?

It has the following features:

• an implementation of Lemke's algorithm with arbitrary
  precision arithmetic, and lexicographic degeneracy
  resolution. It will never have problems with numerical
  inaccuracy because all pivots are exact. Moreover, they
  use integer (rather than rational) arithmetic which is 10
  times faster (and even more for larger LCPs) because
  fractions do not have to be cancelled, with a lot of
  wasteful GCD computations. It also has various debugging
  options, such output of tableaux or the entering and
  leaving variables. This is high-quality code.
• There are separate setup routines for filling the tableau
  from LCP data M,q,d
• Additional setup routines generate M from strategic or
  sequence form payoff matrices, the latter with the
  separate constraint matrices.
• I have not yet implemented it, but I have a complete spec
  for the REDUCED SEQUENCE FORM where intermediate sequences
  that do not lead to leaves, only to information sets, are
  eliminated in a straightforward substitution, which cuts a
  lot (typically 1/2) of the auxiliary constraints while
  keeping the system still readable because the payoff
  matrix stays the same, only its all-zero rows and columns
  are taken out.

I am happy to comment in detail what needs to be done here
if you are interested.

--Bernhard

• Ted Turocy notifications@github.com [29-05-2014 06:41:53 -0700]:

Both the strategic and sequence form LCP implementations
in src/nash/lcp carry around a Solution class (defined as
a nested class inside the LCP algorithm driver) object,
which includes working data on the current run of the
algorithm. In refactoring LCP to use the new Nash
equilibrium computation framework in Gambit 14, just
enough was done to remove all algorithm state from the
algorithm classes themselves. However, more could be done
to encapsulate properly the algorithm state, including:

• Move some operations to be operations on the Solution
  class, rather than being done inline in the algorithm. *
  Consider incorporating other working data, such as the
  Tableau classes. If possible, it might make sense to have
  the internal private member function calls passing around
  mostly just the game being solved, and the Solution class;
  possibly, the game itself should be part of that.

In addition, the filling of the Tableau in both
implementations - but especially the sequence form version

• is very awkwardly done. This could do with some proper
  encapsulation, rather than the current rather opaque
  indexing calculations.

Note that eventually something like the Solution class
might be passed back to the caller (rather than just a
list of computed equilibrium profiles), with the idea
being that richer data on the running of the algorithm
might be interesting. Design of this class should be done
with that in mind.

Please access the attached hyperlink for an important electronic communications disclaimer: http://lse.ac.uk/emailDisclaimer

[tturocy]

That is an interesting idea. The main point of this issue wasn't the Lemke implementation per se, but rather the setup of the tableaux. However, I have also wanted to get rid of the old tableau implementation entirely as it is indeed unnecessarily slow, especially with the use of rational numbers. I think it would be entirely too aggressive to try to do this for Gambit 14, but it could be something we would start work on for an early development release of Gambit 15.

[stengel]

Very good. For the tableaux setup, I have a simple routine
that just copies a small matrix (such as payoff or
constraint matrix) into a larger LCP matrix with 4
parameters: the dimensions of the small matrix and the
offset in the bigger matrix, and an extra Boolean toggle
whether the small matrix is to be transposed. This is
obviously not something difficult to program but has proved
useful - all you need to do is to concentrate on setting the
offsets right. In addition, there are of course the
generations of these small matrices themselves from the
game. Let's keep this mind.

--Bernhard

• Ted Turocy notifications@github.com [02-06-2014 01:56:59 -0700]:

That is an interesting idea. The main point of this issue
wasn't the Lemke implementation per se, but rather the
setup of the tableaux. However, I have also wanted to get
rid of the old tableau implementation entirely as it is
indeed unnecessarily slow, especially with the use of
rational numbers. I think it would be entirely too
aggressive to try to do this for Gambit 14, but it could
be something we would start work on for an early
development release of Gambit 15.

Please access the attached hyperlink for an important electronic communications disclaimer: http://lse.ac.uk/emailDisclaimer

[tturocy]

Commit 15347b8 revises the implementation of the sequence form LP and LCP solvers to be roughly parallel, largely fulfilling the main goal of this issue.