Lexicographic minimum ratio test?
cpennington opened this issue · 2 comments
Is the lexicographic minimum ratio test (mentioned here) already being used by this implementation of Lemke-Howson? Would using it make it possible to use Lemke-Howson on degenerate games? (I ask mainly because LH seems to be much faster that the other solvers, but doesn't work on degenerate games that I'm encountering in the wild).
I looked into the code a bit, and the answer to "Is it being used?" seemed to be no, but I don't really understand the test or the code well enough to be sure.
The short answer is that no, the lexicographic minimum ratio test is not being used.
The minimum ratio test is implemented here https://github.com/drvinceknight/Nashpy/blob/master/src/nashpy/integer_pivoting/integer_pivoting.py#L23 and just does the basic min ratio test. Implementing the lexicographic test with the required perturbation would be a wonderful/welcome addition. When I get time (not for a while) I will look in to it.
I'll leave this issue up for ongoing discussion 👍 :)
@cpennington the lexicographic test is implemented by #71. There's still some work I'd like to do to refactor things before the next release (see #77) but if you're using the code from GitHub directly the master branch now has a lexicographic minimum ratio test.