In computer science, '''FIXP''' is a complexity class introduced by Kousha Etessami and Mihalis Yannakakis at 2010.<ref>{{Cite journal |last1=Etessami |first1=Kousha |last2=Yannakakis |first2=Mihalis |date=January 2010 |title=On the Complexity of Nash Equilibria and Other Fixed Points |url=https://epubs.siam.org/doi/abs/10.1137/080720826 |journal=SIAM Journal on Computing |volume=39 |issue=6 |pages=2531–2597 |doi=10.1137/080720826 |issn=0097-5397|url-access=subscription }}</ref> It represents problems that can be solved by computing a fixed point of a function that satisfies the conditions of Brouwer's fixed point theorem. More formally, FIXP contains search problems that can be cast as fixed point computation problems for functions represented by algebraic circuits over basis {+,*,-,/,max,min} with rational constants.
They prove that some fundamental problems in economics and game theory are complete for FIXP, in particular:
* Nash equilibrium computation - computing an exact or approximate mixed-strategy Nash equilibrium in a game with three or more players. * Market equilibrium computation - computing competitive-equilibrium prices for exchange economies with algebraic demand functions.
== Proving membership in FIXP == Filos-Ratsikas, Hansen, Høgh and Hollender<ref>{{Cite journal |last=Filos-Ratsikas |first=Aris |last2=Hansen |first2=Kristoffer A. |last3=Høgh |first3=Kasper |last4=Hollender |first4=Alexandros |date=2023-04-04 |title=FIXP-Membership via Convex Optimization: Games, Cakes, and Markets |url=https://epubs.siam.org/doi/abs/10.1137/22M1472656 |journal=SIAM Journal on Computing |pages=FOCS21–30 |doi=10.1137/22M1472656 |issn=0097-5397|arxiv=2111.06878 }}</ref> 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<ref name="hz79">{{cite journal |last1=Hylland |first1=Aanund |last2=Zeckhauser |first2=Richard |year=1979 |title=The Efficient Allocation of Individuals to Positions |journal=Journal of Political Economy |volume=87 |issue=2 |pages=293 |doi=10.1086/260757 |s2cid=154167284}}</ref> 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,<ref>{{Cite journal |last1=Fearnley |first1=John |last2=Goldberg |first2=Paul |last3=Hollender |first3=Alexandros |last4=Savani |first4=Rahul |date=2022-12-19 |title=The Complexity of Gradient Descent: CLS = PPAD ∩ PLS |url=https://doi.org/10.1145/3568163 |journal=Journal of the ACM |volume=70 |issue=1 |pages=7:1–7:74 |arxiv=2011.01929 |doi=10.1145/3568163 |issn=0004-5411 |s2cid=263706261}}</ref> 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.<ref name=":5">{{Cite book |last1=Garg |first1=Jugal |title=Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing |last2=Mehta |first2=Ruta |last3=Vazirani |first3=Vijay V. |last4=Yazdanbod |first4=Sadra |date=2017-06-19 |publisher=Association for Computing Machinery |isbn=978-1-4503-4528-6 |series=STOC 2017 |location=New York, NY, USA |pages=890–901 |chapter=Settling the complexity of Leontief and PLC exchange markets under exact and approximate equilibria |doi=10.1145/3055399.3055474 |chapter-url=https://dl.acm.org/doi/10.1145/3055399.3055474}}</ref>
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.<ref name=":5" />
=== 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 == {{Reflist}}{{Comp-sci-stub}} Category:Complexity classes