Why is enumpoly_solve significantly slower than lcp_solve?

[fvz185]

Dear Community,

I am working on a benchmark of a range of methods for computing Nash equilibria (NEs). Two of these methods are pygambit.nash.enumpoly_solve() and pygambit.nash.lcp_solve().
During my initial tests, I realised that their computation times for returning the first NE found differ significantly. Both methods were asked to solve the same bimatrix game. However, the literature suggests that enumpoly, which is based on the Porter-Nudelman-Shoham algorithm for enumerating support profiles using a constraint programming approach, should be faster than lcp, which implements the Lemke-Howson algorithm. Right?

So, I wonder: do you share this experience? Have I missed anything?

Let me know if you need further specs or the precise setting for replication purposes.

[rahulsavani]

A few points:

1. Porter-Nudelman-Shoham claims are too strong I would say.
2. Implementation matters a lot and enumpoly works for any number of players -- for a bimatrix game one would want a purely "linear" implementation rather than using general polynomial equation solvers. While not linear, you can try with PHCpack (https://gambitproject.readthedocs.io/en/stable/tutorials/advanced_tutorials/pygambit.external_programs.html) which is likely faster than our internal implementation. For a purely linear implementation you may need to role your own.
3. You can also try https://github.com/gambitproject/lemke
4. Don't forget enummixed, again with the external lrs (https://cgm.cs.mcgill.ca/~avis/C/lrs.html) available if installed, rather than our very likely much slower internal implementation. And you can also try: https://github.com/rahulsavani/bimatrix_solver

[rahulsavani]

P.S. be very careful benchmarking -- using runtime makes no sense and there's every chance your results say nothing in general only about specific implementations. This is not work for a non-expert I am afraid to say. What type of academic project is this?

[fvz185]

Let me understand, what makes you think that we cannot use exact arithmetic for n>=3 player games?

And yes, I agree again: my priority is to go for two-player games for now. Is it still Lemke-Howson that is state of the art for this setting?

[rahulsavani]

Not think, I know. What exact arithmetic algorithm do you know to find such equilibria?

I can tell you how to find the exact Nash as solutions to polynomial systems, but if you want numbers not symbolic solutions, you need to approximate numerically. See e.g.

Kousha Etessami, Mihalis Yannakakis
On the Complexity of Nash Equilibria and Other Fixed Points. SIAM J. Comput. 39(6): 2531-2597 (2010)

[fvz185]

I don't know much :D But I want to understand.
As far as I've read, SMT solvers can use exact precision arithmetic. And if an SMT solver can be used to compute NEs, why should that then not be exact? That's why I'm asking.

[rahulsavani]

The simplest way to see this is the following:

There exist games (e.g. a 3-player poker game of Nash) where the only Nash equilibria use irrational probabilities.

These obviously cannot be solved in exact arithmetic -- the irrational probabilities can only be written down approximately as numbers. Read the paper I put above for more info.

[rahulsavani]

I wanted to clarify something:

My comments about exact arithmetic and not being able to use it for more than two players relates to the algorithms in Gambit, which are all numeric.

Your SMT solver approach is symbolic and can find the solutions as symbolic roots of polynomials.