Can we efficiently compute a third Nash Equilibrium, given two? A finite, two-player, nondegenerate, symmetric game is defined by a nondegenerate $n \times n$ payoff matrix $A$.  If player 1 plays strategy $i$ and player 2 plays strategy $j$, then player 1's payoff is $A_{ij}$ and player 2's payoff is $A_{ji}$.  It is well known that the problem of computing a symmetric Nash Equillibrium in such a game is PPAD-complete (PPAD lies between P and NP but is probably intractable).
Wilson's Oddness Theorem states that there are an odd number of symmetric Nash Equilibria in such games.  This gives rise to my question.  Suppose we have found two equilibria of $A$.  Given these, what is the computational complexity of computing one more?
Or, more generally - given $2k$ equilibria, what is the complexity of computing another?
 A: In a two-by-two symmetric game, there are two possible symmetric equilibria in pure strategies.  Suppose we know that these are both in fact equilibria.  All this tells us is that 
 $A_{11}>A_{21}$ and $A_{22}>A_{12}$.  
Then there is exactly one additional equilibrium, determined by the equation $${p\over 1-p}={A_{22}-A_{12}\over A_{11}-A_{21}}$$
which means that $p$ can take any value at all between $0$ and $1$.  So at least in this case, knowing two equilibria is of absolutely no help in finding the third.  (And one can easily extend this example to $n$ by $n$ games.)
(The above assumes all $A_{ij}$ are distinct but you need something like this to apply Wilson's theorem in the first place.)
A: Elaborating on Steven's answer, consider the Chicken game, that is the two-by-two symmetric game where each player can either cooperate (C) or defect (D). The payoff for mutual cooperation is $R$, the one for mutual defection is $P$, and, if one player cooperates and the other defects, then the cooperator gets $S$ and the defector gets $T$. Payoffs are subject to the conditions $T>R>S>P$.
This game has always two pure Nash equilibria, $(C,D)$ and $(D,C)$, independently of the exact values of the payoffs. But the other Nash equilibrium may be any mixed strategies depending on the particular payoffs. To see this observe that the extremal situation $T=R$ (resp. $S=P$) gives rise to the two degenerate equilibria $(C,C)$ (resp. $(D,D)$).
So, again, if you are given only two Nash equilibria, there is no way to know the third one. This suggests that the problem remains PPAD complete.  
A: Computational complexity of knowing if more than one equilibrium exists in NP-Hard (complete)
http://www.sciencedirect.com/science/article/pii/S0899825609001973
There we look at very simple two player games called imitation games and the proofs are prety simple. Further, the payoff matrix is a symmetric. So even in that special case, knowing if another equilibrium exists is NP-Hard.
Of course, if you have found one equilibrium, then finding another is not in the class of PPAD because that other one may not exist. 
Now given two, it is still not clear to me that finding a third is PPAD. I don't know of a path following algorithm that does this. 
