Computational hardness of constructing Type III dynamics for games
Computational hardness of constructing Type III dynamics for games
Let be a normal-form game. A game is degenerate if it has a non-isolated set of Nash equilibria, and a dynamical system is of Type III as defined in the paper. Computational hardness conjecture. The computational task of finding, from the description of , either a degeneracy of or an algorithm producing the direction of motion and speed of a dynamical system of Type III is PPAD-hard (and FIXP-hard for three or more players). This question lies at the boundary between computation, game theory, and the topology of dynamical systems; resolving it is expected to require new complexity-theoretic techniques for dynamical systems.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Jason Milionis, Christos Papadimitriou, Georgios Piliouras and Kelly Spendlove, “Nash, Conley, and Computation: Impossibility and Incompleteness in Game Dynamics”, arXiv:2203.14129 (2022).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.