Computational hardness of constructing Type III dynamics for games
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.