1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

It is co-NP-hard to decide a a game has a unique equilibrium. See:

  • Gilboa, Itzhak, and Eitan Zemel. "Nash and correlated equilibria: Some complexity considerations." Games and Economic Behavior 1.1 (1989): 80-93.

  • Conitzer, Vincent, and Tuomas Sandholm. "New complexity results about Nash equilibria." Games and Economic Behavior 63.2 (2008): 621-641.

Thus you cannot even decide if a bimatrix game has one or more than one equilibrium in polynomial time, subject to the standard complexity theoretic assumption that co-NP != P.

Actually counting is #P-hard, as shown in Corollary 12 of the second paper above. Thus there is almost certainly no fast algorithm for the problem.

BTW, the Lemke-Howson algorithm does not enumerate all equilibria. In it's standard form, for an $m \times n$ game, it can find at most $m+n$ equilibria. In an extended form where one "concatenates" Lemke-Howson paths, it may still not find all equilibria as reported in Shapley (1974) who reports an example due to Robert Wilson:

  • Shapley, Lloyd S. "A note on the Lemke-Howson algorithm." Pivoting and Extension (1974): 175-189.

Your best approach for counting the number of equilibria exactly is to actually find them, for example with the algorithms we describe in:

  • Avis, D., Rosenberg, G. D., Savani, R., & Von Stengel, B. (2010). Enumeration of Nash equilibria for two-player games. Economic Theory, 42(1), 9-37.

That paper will also address some of your other questions/comments.

The best algorithm for enumeration for bimatrix games (from that paper) is also implemented via our web-based game solvers:

And in the lrs solver:

But only the web-based solvers will check for non-singleton equilibrium components (i.e., whether there are actually infinitely many equilibria).

For more than two players things get much harder and we don't have good tools for enumerating equilibria yet.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.