FIXP

In computer science, FIXP is a complexity class introduced by Kousha Etessami and Mihalis Yannakakis at 2010.[1] 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:

Proving membership in FIXP

Filos-Ratsikas, Hansen, Høgh and Hollender[2] 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:

They also prove FIXP membership for Nash equilibrium computation and for the mechanism of Hylland and Zeckhauser[3] 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,[4] 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.[5]

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.[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

  1. ^ Etessami, Kousha; Yannakakis, Mihalis (January 2010). "On the Complexity of Nash Equilibria and Other Fixed Points". SIAM Journal on Computing. 39 (6): 2531–2597. doi:10.1137/080720826. hdl:20.500.11820/98752471-0a7a-4366-8871-b8f1984190ef. ISSN 0097-5397.
  2. ^ Filos-Ratsikas, Aris; Hansen, Kristoffer A.; Høgh, Kasper; Hollender, Alexandros (2023-04-04). "FIXP-Membership via Convex Optimization: Games, Cakes, and Markets". SIAM Journal on Computing: FOCS21–30. arXiv:2111.06878. doi:10.1137/22M1472656. ISSN 0097-5397.
  3. ^ Hylland, Aanund; Zeckhauser, Richard (1979). "The Efficient Allocation of Individuals to Positions". Journal of Political Economy. 87 (2): 293. doi:10.1086/260757. S2CID 154167284.
  4. ^ Fearnley, John; Goldberg, Paul; Hollender, Alexandros; Savani, Rahul (2022-12-19). "The Complexity of Gradient Descent: CLS = PPAD ∩ PLS". Journal of the ACM. 70 (1): 7:1–7:74. arXiv:2011.01929. doi:10.1145/3568163. ISSN 0004-5411. S2CID 263706261.
  5. ^ a b Garg, Jugal; Mehta, Ruta; Vazirani, Vijay V.; Yazdanbod, Sadra (2017-06-19). "Settling the complexity of Leontief and PLC exchange markets under exact and approximate equilibria". Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. STOC 2017. New York, NY, USA: Association for Computing Machinery. pp. 890–901. doi:10.1145/3055399.3055474. ISBN 978-1-4503-4528-6.
Stub icon

This computer science article is a stub. You can help Wikipedia by adding missing information.

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.