Hispanopedia WikiEn informática , FIXP es una clase de complejidad introducida por Kousha Etessami y Mihalis Yannakakis en 2010. [ 1 ] Representa problemas que pueden resolverse calculando un punto fijo de una función que satisface las condiciones del teorema del punto fijo de Brouwer . Más formalmente, FIXP contiene problemas de búsqueda que pueden plantearse como problemas de cálculo de punto fijo para funciones representadas por circuitos algebraicos sobre la base {+,*,-,/,max,min} con constantes racionales.
Demuestran que algunos problemas fundamentales de la economía y la teoría de juegos están resueltos para FIXP, en particular:
- Cálculo del equilibrio de Nash : cálculo de un equilibrio de Nash de estrategia mixta, exacto o aproximado, en un juego con tres o más jugadores.
- Cálculo del equilibrio de mercado : cálculo de los precios de equilibrio competitivo para economías de intercambio con funciones de demanda algebraicas .
Demostración de pertenencia a FIXP
Filos-Ratsikas, Hansen, Høgh y Hollender [ 2 ] presentan un método general para demostrar la pertenencia a FIXP. Su método construye una caja negra que denominan “OPT-gate”, la cual puede resolver la mayoría de los problemas de optimización convexa . Utilizando su técnica, demuestran la pertenencia a FIXP de:
- Cálculo del equilibrio de mercado en mercados de Arrow-Debreu con utilidades cóncavas generales;
- Calcular un reparto de pastel sin envidia con valoraciones muy generales es FIXP-completo.
También demuestran la pertenencia a FIXP para el cálculo del equilibrio de Nash y para el mecanismo de Hylland y Zeckhauser [ 3 ] para la asignación aleatoria justa .
Relaciones con otras clases
Relación con PPAD
Etessami y Yannakakis describen la relación sucintamente diciendo que "El fragmento lineal a trozos de FIXP es igual a PPAD ". En otras palabras, [ 4 ] los problemas en PPAD son los problemas en FIXP en los que la función de entrada es lineal a trozos.
Las soluciones a los problemas en PPAD son números racionales , mientras que las soluciones a los problemas en FIXP son números algebraicos . [ 5 ]
PPAD está contenido en clases de funciones que se encuentran en la intersección de NP y co-NP, mientras que se conjetura que FIXP es mucho más difícil y se ubica en el extremo "más difícil" de PSPACE . [ 5 ]
Relación con SRS
Calcular un equilibrio de Nash aproximado para cualquier factor menor que 1/2 es al menos tan difícil como el problema de la suma de raíces cuadradas .
Referencias
- ^ Etessami, Kousha; Yannakakis, Mihalis (enero de 2010). "Sobre la complejidad de los equilibrios de Nash y otros puntos fijos" . Revista SIAM de Computación . 39 (6): 2531–2597.doi : 10.1137 / 080720826 . hdl : 20.500.11820/98752471-0a7a-4366-8871-b8f1984190ef . ISSN 0097-5397 .
- ^ Filos-Ratsikas, Aris; Hansen, Kristoffer A.; Høgh, Kasper; Hollender, Alexandros (4 de abril de 2023). "Membresía FIXP mediante optimización convexa: juegos, pasteles y mercados" . Revista SIAM de Informática : FOCS21–30. arXiv : 2111.06878 . doi : 10.1137/22M1472656 . ISSN 0097-5397 .
- ↑ Hylland, Aanund; Zeckhauser, Richard (1979). "La asignación eficiente de individuos a puestos". Journal of Political Economy . 87 (2): 293. doi : 10.1086/260757 . S2CID 154167284 .
- ↑ Fearnley, John; Goldberg, Paul; Hollender, Alexandros; Savani, Rahul (2022-12-19). "La complejidad del descenso de gradiente: 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 .
- 1 2 Garg, Jugal; Mehta, Ruta; Vazirani, Vijay V.; Yazdanbod, Sadra (19 de junio de 2017). "Resolviendo la complejidad de los mercados de intercambio de Leontief y PLC bajo equilibrios exactos y aproximados" . Actas del 49.º Simposio Anual ACM SIGACT sobre Teoría de la Computación . STOC 2017. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 890–901 . doi : 10.1145/3055399.3055474 . ISBN 978-1-4503-4528-6.
- esbozos de informática
- Clases de complejidad