La teoría algorítmica de juegos (AGT) es un área en la intersección de la teoría de juegos y la informática , con el objetivo de comprender y diseñar algoritmos en entornos estratégicos .
Normalmente, en los problemas de teoría algorítmica de juegos, la entrada a un algoritmo dado se distribuye entre muchos jugadores que tienen un interés personal en la salida. En esas situaciones, es posible que los agentes no informen la entrada con sinceridad debido a sus propios intereses personales. Podemos ver la teoría algorítmica de juegos desde dos perspectivas:
- Análisis : dados los algoritmos implementados actualmente, analícelos usando herramientas de teoría de juegos (por ejemplo, calcule y pruebe las propiedades de sus equilibrios de Nash , el precio de la anarquía y la dinámica de mejor respuesta)
- Diseño : diseñar juegos que tengan buenas propiedades tanto teóricas como algorítmicas. Esta área se denomina diseño de mecanismos algorítmicos .
Además de los requisitos habituales en el diseño de algoritmos clásicos (por ejemplo, tiempo de ejecución de tiempo polinómico , buena relación de aproximación), el diseñador también debe preocuparse por las restricciones de incentivos.
Historia
Nisan-Ronen: un nuevo marco para estudiar algoritmos
En 1999, el artículo fundamental de Nisan y Ronen [1] llamó la atención de la comunidad de Ciencias de la Computación Teórica sobre el diseño de algoritmos para usuarios egoístas (estratégicos). Como afirman en abstracto:
Consideramos un problema algorítmico en un entorno distribuido donde no se puede suponer que los participantes sigan el algoritmo sino más bien su propio interés. Como dichos participantes, denominados agentes, son capaces de manipular el algoritmo, el diseñador del algoritmo debe asegurarse de antemano de que los intereses de los agentes se sirven mejor si se comportan correctamente. Siguiendo nociones del campo del diseño de mecanismos, sugerimos un marco para estudiar dichos algoritmos. En este modelo, la solución algorítmica se adorna con pagos a los participantes y se denomina mecanismo. Los pagos deben elegirse cuidadosamente para motivar a todos los participantes a actuar como desee el diseñador del algoritmo. Aplicamos las herramientas estándar de diseño de mecanismos a problemas algorítmicos y en particular al problema de la ruta más corta.
Este artículo acuñó el término diseño de mecanismo algorítmico y fue reconocido por el comité del Premio Gödel 2012 como uno de los "tres artículos que sientan las bases del crecimiento en la teoría de juegos algorítmicos". [2]
Precio de la anarquía
Los otros dos artículos citados en el Premio Gödel 2012 por sus contribuciones fundamentales a la teoría algorítmica de juegos introdujeron y desarrollaron el concepto de "Precio de la anarquía". En su artículo de 1999 "Equilibrios del peor caso", [3] Koutsoupias y Papadimitriou propusieron una nueva medida de la degradación de la eficiencia del sistema debido al comportamiento egoísta de sus agentes: la relación entre la eficiencia del sistema en una configuración óptima y su eficiencia en el peor equilibrio de Nash. (El término "Precio de la anarquía" apareció solo un par de años después. [4] )
Internet como catalizador
Internet creó una nueva economía, tanto como base para el intercambio y el comercio, como por derecho propio. La naturaleza computacional de Internet permitió el uso de herramientas computacionales en esta nueva economía emergente. Por otro lado, Internet en sí es el resultado de las acciones de muchos. Esto era nuevo en el enfoque clásico de computación "de arriba hacia abajo" que se mantuvo hasta entonces. Por lo tanto, la teoría de juegos es una forma natural de ver Internet y las interacciones dentro de ella, tanto humanas como mecánicas.
La teoría de juegos estudia los equilibrios (como el equilibrio de Nash ). Un equilibrio se define generalmente como un estado en el que ningún jugador tiene un incentivo para cambiar su estrategia. Los equilibrios se encuentran en varios campos relacionados con Internet, por ejemplo, las interacciones financieras y el equilibrio de carga de comunicación [ cita requerida ] . La teoría de juegos proporciona herramientas para analizar los equilibrios, y un enfoque común es entonces "encontrar el juego", es decir, formalizar interacciones específicas de Internet como un juego y derivar los equilibrios asociados.
Reformular los problemas en términos de juegos permite el análisis de interacciones basadas en Internet y la construcción de mecanismos para satisfacer demandas específicas. Si se puede demostrar que existen los equilibrios, debe responderse una pregunta adicional: ¿se puede encontrar un equilibrio en un tiempo razonable? Esto conduce al análisis de algoritmos para encontrar equilibrios. De especial importancia es la clase de complejidad PPAD , que incluye muchos problemas en la teoría algorítmica de juegos.
Áreas de investigación
Diseño de mecanismo algorítmico
El diseño de mecanismos es la subárea de la economía que se ocupa de la optimización bajo restricciones de incentivos. El diseño de mecanismos algorítmicos considera la optimización de sistemas económicos bajo requisitos de eficiencia computacional. Los objetivos típicos estudiados incluyen la maximización de ingresos y la maximización del bienestar social.
Ineficiencia de equilibrios
Los conceptos de precio de la anarquía y precio de la estabilidad se introdujeron para capturar la pérdida de rendimiento de un sistema debido al comportamiento egoísta de sus participantes. El precio de la anarquía captura el desempeño del sistema en el peor de los casos en equilibrio en relación con el desempeño óptimo posible. [5] El precio de la estabilidad , por otro lado, captura el desempeño relativo del mejor equilibrio del sistema. [6] Estos conceptos son contrapartes de la noción de relación de aproximación en el diseño de algoritmos.
Complejidad de encontrar equilibrios
La existencia de un equilibrio en un juego se establece típicamente utilizando teoremas de punto fijo no constructivos . No se conocen algoritmos eficientes para calcular los equilibrios de Nash . El problema es completo para la clase de complejidad PPAD incluso en juegos de 2 jugadores. [7] Por el contrario, los equilibrios correlacionados se pueden calcular de manera eficiente utilizando la programación lineal, [8] así como aprender a través de estrategias sin arrepentimiento. [9]
Elección social computacional
La elección social computacional estudia los aspectos computacionales de la elección social , la agregación de las preferencias de los agentes individuales. Los ejemplos incluyen algoritmos y complejidad computacional de reglas de votación y formación de coaliciones. [10]
Otros temas incluyen:
- Algoritmos para calcular los equilibrios del mercado
- División justa
- Sistemas multiagente
Y el área cuenta con diversas aplicaciones prácticas: [11] [12]
- Subastas de búsqueda patrocinadas
- Subastas de espectro
- CRIPTOMONEDAS
- Mercados de predicción
- Sistemas de reputación
- Compartiendo economía
- Mercados coincidentes como el intercambio de riñones y la elección de escuelas
- Crowdsourcing y evaluación por pares
- Economía de la nube
Revistas y boletines
- Transacciones ACM sobre economía y computación (TEAC) [13]
- Intercambios SIGEcom [14]
Los artículos de la teoría algorítmica de juegos a menudo también se publican en revistas de teoría de juegos como GEB , [15] revistas de economía como Econometrica y revistas de informática como SICOMP . [dieciséis]
Ver también
- Teoría de la subasta
- Elección social computacional
- Equilibrio de carga (informática)
- Diseño de mecanismo
- Sistema de agentes múltiples
- Votar en teoría de juegos
Referencias
- ^ Nisan, Noam ; Ronen, Amir (1999), "Diseño de mecanismos algorítmicos", Actas del 31º Simposio ACM sobre Teoría de la Computación (STOC '99) , págs. 129–140, doi : 10.1145 / 301250.301287 , ISBN 978-1581130676, S2CID 8316937
- ^ "ACM SIGACT presenta el premio Gödel a la investigación que ilumina los efectos del uso egoísta de Internet" (Comunicado de prensa). Nueva York. Asociación para Maquinaria de Computación. 2012-05-16. Archivado desde el original el 18 de julio de 2013 . Consultado el 8 de enero de 2018 .
- ^ Koutsoupias, Elias; Papadimitriou, Christos (mayo de 2009). "Equilibrios en el peor de los casos" . Revisión de Ciencias de la Computación . 3 (2): 65–69. doi : 10.1016 / j.cosrev.2009.04.003 . Archivado desde el original el 13 de marzo de 2016 . Consultado el 8 de enero de 2018 .
- ^ Papadimitriou, Christos (2001), "Algoritmos, juegos e Internet", Actas del 33º Simposio ACM sobre Teoría de la Computación (STOC '01) , págs. 749–753, CiteSeerX 10.1.1.70.8836 , doi : 10.1145 / 380752.380883 , ISBN 978-1581133493, S2CID 207594967
- ^ Tim Roughgarden (2005). Enrutamiento egoísta y el precio de la anarquía . Prensa del MIT . ISBN 0-262-18243-2.
- ^ * Anshelevich, Elliot; Dasgupta, Anirban; Kleinberg, Jon; Tardos, Éva; Wexler, Tom; Roughgarden, Tim (2008). "El precio de la estabilidad para el diseño de redes con asignación justa de costos". SIAM J. Comput . 38 (4): 1602-1623. doi : 10.1137 / 070680096 . S2CID 2839399 .
- ^ * Chen, Xi; Deng, Xiaotie (2006). Resolver la complejidad del equilibrio de Nash de dos jugadores . Proc. 47th Symp. Fundamentos de la informática. págs. 261-271. doi : 10.1109 / FOCS.2006.69 . ECCC TR05-140 ..
- ^ Papadimitriou, Christos H .; Roughgarden, Tim (2008). "Computación de equilibrios correlacionados en juegos multijugador". J. ACM . 55 (3): 14: 1–14: 29. CiteSeerX 10.1.1.335.2634 . doi : 10.1145 / 1379759.1379762 . S2CID 53224027 .
- ^ Foster, Dean P .; Vohra, Rakesh V. (1996). "Aprendizaje calibrado y equilibrio correlacionado" . Juegos y comportamiento económico .
- ^ Felix Brandt; Vincent Conitzer; Ulle Endriss; Jérôme Lang; Ariel D. Procaccia, eds. (2016), Manual de elección social computacional (PDF)
- ^ Tim Roughgarden (2016). Veinte conferencias sobre teoría algorítmica de juegos . Prensa de la Universidad de Cambridge . ISBN 9781316624791.
- ^ "EC'19 || XX Congreso ACM sobre Economía y Computación" .
- ^ TEAC
- ^ Intercambios SIGEcom
- ^ Chawla, Shuchi; Fleischer, Lisa; Hartline, Jason; Tim Roughgarden (2015), "Introducción al número especial - Teoría algorítmica de juegos - STOC / FOCS / SODA 2011", Games and Economic Behavior , 92 : 228-231, doi : 10.1016 / j.geb.2015.02.011
- ^ SICOMP
- John von Neumann , Oskar Morgenstern (1944) Teoría de los juegos y comportamiento económico . Universidad de Princeton Prensa. Edición 2007: ISBN 978-0-691-13061-3
- Vazirani, Vijay V .; Nisan, Noam ; Roughgarden, Tim ; Tardos, Éva (2007), Teoría algorítmica de juegos (PDF) , Cambridge, Reino Unido: Cambridge University Press, ISBN 978-0-521-87282-9.
enlaces externos
- gambit.sourceforge.net - una biblioteca de software y herramientas de teoría de juegos para la construcción y análisis de juegos finitos extensivos y estratégicos.
- gamut.stanford.edu : un conjunto de generadores de juegos diseñados para probar algoritmos de teoría de juegos.