Most matrix simultaneous games have odd number of equilibria. However, there are cases where this might not be true. How can I identify these cases? Do they have an specific property?
Consider for instance the following simultaneous move game with two players, each having 3 possible actions
The payoff matrix for player one is
$$ \begin{pmatrix} 5&0&3\\ 4&5&4\\ 3&0&5\\ \end{pmatrix}$$
The payoff matrix for player two is
$$ \begin{pmatrix} 3&4&5\\ 0&5&0\\ 5&4&3\\ \end{pmatrix} $$
The game has one pure strategy equilibrium at payoff 5 for each player and a mixed strategy equilibrium. That's two equilibria... how can we make sure this is one of those special cases where there are only two equilibria?
A game is called non-degenerate if for every mixed strategy with support size $k$ (where the support of a mixed strategy is the number of pure strategies used with positive probability), the number of pure best responses against the mixed strategy is at most $k$.
Non-degenerate games always have an odd number of equilibria. This can be proved, for example, using the Lemke-Howson algorithm.
A degenerate game can have any number of equilibria including infinitely many. Here are two examples:
$$ A = \left( \begin{array}{ccc} 0 & 0 \\ 0 & 1 \\ \end{array} \right) \quad B = \left( \begin{array}{ccc} 0 & 0 \\ 0 & 1 \\ \end{array} \right) $$ This game has exactly two equilibria, top left, and bottom right. $$ A = \left( \begin{array}{ccc} 1 & 0 \\ 0 & 1 \\ \end{array} \right) \quad B = \left( \begin{array}{ccc} 0 & 1 \\ 1 & 1 \\ \end{array} \right) $$ This game has one equilibrium component with infinitely many equilibria, where the row player with payoff matrix A plays the bottom row and the column player plays any mixture that puts at least probability $0.5$ on the right column.
In two by two games, degeneracy appears as weak dominance of a pure strategy, since it can only occur due to two best responses to a pure strategy. Here's a $3 \times 2$ example. $$ A = \left( \begin{array}{ccc} 2 & 0 \\ 0 & 2 \\ 1 & 1 \end{array} \right) \quad B = \left( \begin{array}{ccc} 0 & 1 \\ 1 & 2 \\ 1 & 0 \end{array} \right) $$ The game is degenerate because against the mixed strategy $q = (0.5,0.5)$ for the columns, the row player, with payoff matrix $A$, has $3 > \text{Support}(q) = 2$ pure best responses (all three rows). Here are the equilibria of that game, produced via the websolver http://banach.lse.ac.uk/. There are two equilibrium components, one is a singleton, the other is infinite (and occurs when the column player plays $q = (0.5,0.5)$).
3 x 2 Payoff matrix A: 2 0 0 2 1 1 3 x 2 Payoff matrix B: 0 1 1 2 1 0 EE = Extreme Equilibrium, EP = Expected Payoff Decimal Output EE 1 P1: (1) 0.5 0.0 0.5 EP= 1.0 P2: (1) 0.5 0.5 EP= 0.5 EE 2 P1: (2) 0.0 0.5 0.5 EP= 1.0 P2: (1) 0.5 0.5 EP= 1.0 EE 3 P1: (3) 0.0 1.0 0.0 EP= 2.0 P2: (2) 0.0 1.0 EP= 2.0 Rational Output EE 1 P1: (1) 1/2 0 1/2 EP= 1 P2: (1) 1/2 1/2 EP= 1/2 EE 2 P1: (2) 0 1/2 1/2 EP= 1 P2: (1) 1/2 1/2 EP= 1 EE 3 P1: (3) 0 1 0 EP= 2 P2: (2) 0 1 EP= 2 Connected component 1: {1, 2} x {1} Connected component 2: {3} x {2}To see that your example game is degenerate, consider the mixed strategy that plays rows 1 and 3 with probability $0.5$. Against this, all three columns are best responses. Likewise, when the column player plays the first and third columns with probability $0.5$, all three rows are best responses. Thus, you can see the similarity to the first example in this answer, where there are also exactly two equilibria (degeneracy for both players).
In general, it is NP-hard to decide if a game is degenerate. See
Ye Du (2013). On the complexity of deciding degeneracy in a bimatrix game with sparse payoff matrix. Theoretical Computer Science. 472 , 104-109.
It is $\#P$-hard to count the number of equilibria. See
V Conitzer, T Sandholm (2008). New complexity results about Nash equilibria. Games and Economic Behavior 63 (2), 621-641.