Is there a "fast" algorithm or other methodology to determine the number of nash equilibria in a bimatrix game? I know of several algorithms to enumerate equilibria such as Lemke-Howson, but I'm only interested in the number of equilibria.
I've thought about a couple of things, but I don't have much. It's fairly simple to find all pure strategy equilibria in $O(nm)$ time, which is fast enough. We just find the best responses for both players and check for matches.
So, then, we just need to find the number of mixed strategy equilibria. This is harder. I know that one can consider the expected payoff function, and one knows that for all probabilities from which player one chooses, the partial derivative of player two's payoff must be zero, whence we get $n$ equations on $m$ variables and $m$ equations on variables. There will be an infinite number of mixed strategy equilibria if either system is underconstrained, and no mixed strategy equilibria if either is overconstrained, but I don't know how to solve that problem quickly.
I think that since these are linear equations, there can only be zero, one, or infinitely many solutions mostly considering the low-dimensional cases, but I don't know how to prove this.
I am also pretty sure this can be found be considering in some way by finding the rank of the payoff matrix, but I don't know linear algebra all that well, and I don't know how that would have to be used or how to quickly find it.
I would greatly appreciate any help you may be able to provide on this problem.
Also, If you happen to know anything about it, how does this problem expand to arbitrarily many players, if the solutions are similar.