ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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.

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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.