## Can we efficiently compute a third Nash Equilibrium, given two?

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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?

-

1
Relevant reading: public.iastate.edu/~riczw/MEGliter/Book/… (see especially around Corollary 3.7 on pdf p.83/775) – Benjamin Dickman Nov 15 at 4:54
You might get more answers on cstheory.stackexchange – Josh Nov 19 at 15:06
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 8, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9097061157226562, "perplexity_flag": "middle"}