I am exploring a large number of 2-player games. The Lemke-Howson algorithm is computationally very reasonable, and is able to find many equilibria. On the other hand, I know that there are equilibria such that the algorithm cannot find in principle.
I was wondering if there was any way, upon inspection of the payoff matrices, to find out whether the game in question is one for which L-H will give incomplete results, so that I could then try more computationally intensive algorithms on those.
I think this might be an open problem. The closest remark that I could find is by Shapley in 1981. I haven't found much thereafter, but, of course, I could have overlooked something. (Naturally, I am excluding the trivial "inspection" of using a computationally less reasonable algorithm first, and see whether they differ in their solutions.)
Related: Gilboa and Zemel (1989). I know next to nothing about (average) complexity, but perhaps somebody else can comment on whether this means you're in bad luck.