Computational hardness of constructing Type III dynamics for games

From papers

Let gg 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 gg, either a degeneracy of gg 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

No solutions have been posted yet.