What is the quickest way to find Nash equilibria in two player bimatrix game?

Question

Suppose the cost/penalty matrix of a game is given as:

$$M = \begin{bmatrix} (-5,-5) & (0,0) \\ (0,0) & (-3,-3) \end{bmatrix}$$

Then the game as two equilibria $(u_{11},u_{21})$ and $(u_{12},u_{22})$ which have the lowest cost at $J(u_{11},u_{21}) = (-5,5)$ and $J(u_{12},u_{22}) = (-3,3)$

Based on how the equilibria is computed for this game, would it be reasonable to extend and general to all bimatrix games and say that to find the equilibria you need to (algorithmically speaking):

1. start with first column

2. find the strategy pair that is the minimum (element-wise), or conclude there doesn't exist a minimum (element-wise)

3. go to next column and repeat 2

Conclusion: to find the equilibrium is to find the minimum for each column.

Would there be any catch if I follow this rule and perform this algorithm every time I am given a bimatrix?

Answer 1

Computing Nash equilibria is not an easy business in general (if it were, then the world would be a weird place...). You may want to note the following facts:

• Nash equilibria may not exist in pure strategies. They're only guaranteed to exist in mixed strategies.

• In general, the problem of computing equilibria for bimatrix games is NP-hard (in fact, TFNP-hard).

For further reading, see this paper.