To find the mixed NE for a 2-player 2x2 game, one can write the well-known formulation where each of the players makes another one indifference between its actions. But even in the case of a 2x2 game, this approach does not find all the equilibria of the game. For example, let's assume the actions of player 1 and 2 are $A_1=\{U,D\}$, $A_2=\{L,R\}$ and the utility matrix of the game is
$$\begin{array}{c|cc} &\text{L}&\text{R} \\ \hline \text{U}&A,E&B,F \\ \text{D}&C,G&D,H \\ \end{array}$$
Let's further assume that the mixed strategy of player 1 and 2 are $(q_1,1-q_1)$ and $(q_2,1-q_2)$, respectively. Now, player 2, to make player 1 indifference between its action writes $Aq_2 + B(1-q_2) = C(q_2) + D(1-q_2)$ and this gives: $$ q_2 = \frac{D-B}{A-B-C+D} $$
Now, applying the similar procedure for the following matrix gives $q_1=q_2= 0$. $$\begin{array}{c|cc} &\text{L}&\text{R} \\ \hline \text{U}&5,5&0,0 \\ \text{D}&0,0&0,0 \\ \end{array}$$
This means that it finds the NE $(D, R)$ and cannot find the NE $(U,L)$ which is a much better NE than the former one. As far as I know, Lemke-Howson algorithm generalizes the above procedure for $n \times n$ game, but similar to the example above, it cannot find all the NEs.
I wondered if there is a mathematical program like the Lemke-Howson algorithm, regardless of its complexity, to find all the NEs of the game (considering pure NEs as special cases of mixed NEs)?
Many thanks.
P.S: An algorithm is available here: http://banach.lse.ac.uk/, based on the paper of Avis, et al., but I think implementing that algorithm takes very long time.
The "well-known formulation" you describe is simply wrong. It is not sufficient for a player to be indifferent between some pure strategies to be able to mix between them in equilibrium; they must also be best response, i.e., give the best possible payoff among all pure strategies.
Finding all equilibria is harder for "degenerate games", where there be infinitely many equilibria, but if you are content with just finding the extreme equilibria (i.e., essentially equilibria which are not convex combinations of other equilibria) then the simplest approach is to do support enumeration.
Definition: the support of a mixed strategy is the set of pure strategies that it plays with positive probability.
Now given a pair of supports, you first check can each player make the other player indifferent between his support strategies using only her support strategies and, if this is possible, are the resulting mixed strategies that do this are best responses (i.e. give higher payoff than all things outside the support).
Pure equilibria have support size 1 for both players. When checking for the indifference part is trivial, since there is a single strategy, and you just need to check if the pure strategies are best responses against each other. For larger supports, you need to do both parts: see if indifference is even possible given the candidate support of the other player, and if it is possible for both players, see if the payoffs of the pure strategies in the supports (which will now all be the same for a given player since we achieved indifference) are the best possible.
In some sense, we are taking what you know about finding pure equilibria, and finding 2x2 mixed equilibria in 2x2 games, and combining them into a general algorithm.)
This is described as Algorithm 1 in the paper you refer to:
David Avis, Gabriel D. Rosenberg, Rahul Savani, and Bernhard von Stengel. Enumeration of Nash equilibria for two-player games. Economic Theory, 42(1):9–37.
It is not the algorithm used on banach.lse.ac.uk, which is indeed more complicated.
P.S. I wrote banach.lse.ac.uk and am a co-author on the Avis et al. paper.