# FIXP
> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/FIXP
> Markdown URL: https://mediated.wiki/source/FIXP.md
> Source: https://en.wikipedia.org/wiki/FIXP
> Source revision: 1318822432
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)
In [computer science](/source/computer_science), '''FIXP''' is a [complexity class](/source/complexity_class) introduced by [Kousha Etessami](/source/Kousha_Etessami) and [Mihalis Yannakakis](/source/Mihalis_Yannakakis) at 2010.[{{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 }}] It represents problems that can be solved by computing a [fixed point](/source/fixed_point_(mathematics)) of a function that satisfies the conditions of [Brouwer's fixed point theorem](/source/Brouwer's_fixed_point_theorem). More formally, FIXP contains [search problem](/source/search_problem)s 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](/source/Nash_equilibrium_computation) - computing an exact or approximate mixed-strategy Nash equilibrium in a game with three or more players.
* [Market equilibrium computation](/source/Market_equilibrium_computation) - computing competitive-equilibrium prices for exchange economies with algebraic [demand function](/source/demand_function)s.
== Proving membership in FIXP ==
Filos-Ratsikas, Hansen, Høgh and Hollender[{{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 }}] 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](/source/convex_optimization) problems. Using their technique, they prove FIXP membership of:
* [Market equilibrium computation](/source/Market_equilibrium_computation) in Arrow-Debreu markets with general concave utilities;
* Computing an [envy-free cake cutting](/source/Envy-free_cake-cutting) with very general valuations is FIXP-complete.
They also prove FIXP membership for [Nash equilibrium computation](/source/Nash_equilibrium_computation) and for the mechanism of Hylland and Zeckhauser[{{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}}] for [fair random assignment](/source/fair_random_assignment).
== Relations to other classes ==
=== Relation to PPAD ===
Etessami and Yannakakis describe the relation succinctly by saying that "The [piecewise-linear](/source/Piecewise_linear_function) fragment of FIXP equals [PPAD](/source/PPAD_(complexity))". In other words,[{{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}}] 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](/source/Rational_number), whereas solutions to problems in FIXP are [algebraic number](/source/algebraic_number)s.[{{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}}]
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](/source/PSPACE).