FIXP

Filos-Ratsikas, Hansen, Høgh and Hollender present a general method for proving membership in FIXP. Their method constructs a black-box that they call “OPT-gate”, which can solve most convex optimization problems. Using their technique, they prove FIXP membership of: • Market equilibrium computation in Arrow-Debreu markets with general concave utilities; • Computing an envy-free cake cutting with very general valuations is FIXP-complete. They also prove FIXP membership for Nash equilibrium computation and for the mechanism of Hylland and Zeckhauser for fair random assignment. == Relations to other classes ==

Relation to PPAD Etessami and Yannakakis describe the relation succinctly by saying that "The piecewise-linear fragment of FIXP equals PPAD". In other words, the problems in PPAD are the problems in FIXP in which the input function is piecewise-linear. Solutions to problems in PPAD are rational numbers, whereas solutions to problems in FIXP are algebraic numbers. PPAD is contained in function classes that are in the intersection of NP and co-NP, whereas FIXP is conjectured to be much harder, and lie in the "harder" end of PSPACE. Relation to SRS Computing an approximate Nash equilibrium to any factor smaller than 1/2 is at least as hard as the square-root sum problem. == References ==