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?



Can we efficiently compute a third Nash Equilibrium, given two?
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.)


