Teoría de juegos algorítmicos

La teoría algorítmica de juegos (AGT) es un campo interdisciplinario que se encuentra en la intersección de la teoría de juegos y la informática, centrado en la comprensión y el diseño de algoritmos para entornos donde interactúan múltiples agentes estratégicos. Esta área de investigación combina el pensamiento computacional con principios económicos para abordar los desafíos que surgen cuando las entradas algorítmicas provienen de participantes interesados.En el diseño tradicional de algoritmos, se asume que las entradas son fijas y fiables. Sin embargo, en muchas aplicaciones del mundo real —como subastas en línea, enrutamiento por internet, publicidad digital y sistemas de asignación de recursos— las entradas son proporcionadas por múltiples agentes independientes que pueden falsear estratégicamente la información para manipular los resultados a su favor. La AGT proporciona marcos para analizar y diseñar sistemas que se mantengan eficaces a pesar de dicho comportamiento estratégico.El campo puede abordarse desde dos perspectivas complementarias:

• Análisis: Evaluar los algoritmos y sistemas existentes a través de herramientas teóricas para entender sus propiedades estratégicas. Esto incluye calcular y probar propiedades de Nash equilibria (estables estados donde ningún participante puede beneficiarse cambiando sólo su propia estrategia), medir el precio de la anarquía (pérdida de eficiencia debido al comportamiento egoísta), y analizar la dinámica de mejor respuesta (cómo evolucionan los sistemas cuando los jugadores optimizan sus estrategias secuencialmente).
• Diseño: Creación de mecanismos y algoritmos con propiedades computacionales deseables y robustez teórica del juego. Este subcampo, conocido como diseño de mecanismo algorítmico, desarrolla sistemas que incentivan el comportamiento veraz manteniendo la eficiencia computacional.

Los diseñadores de algoritmos en este ámbito deben satisfacer los requisitos algorítmicos tradicionales (como el tiempo de ejecución polinomial y una buena relación de aproximación) y, al mismo tiempo, abordar las restricciones de incentivos que garantizan que los participantes actúen de acuerdo con el diseño previsto del sistema.En 1999, el artículo fundamental de Noam Nisan y Amir Ronen llamó la atención de la comunidad de la informática teórica sobre el diseño de algoritmos para usuarios egoístas (estratégicos). Como afirman en el resumen:

Consideramos problemas algorítmicos en un entorno distribuido donde no se puede suponer que los participantes sigan el algoritmo sino más bien su propio interés propio. Como tales participantes, llamados agentes, son capaces de manipular el algoritmo, el diseñador de algoritmos debe asegurarse de antemano que los intereses de los agentes son mejor servidos por comportarse correctamente. Siguiendo nociones del campo de diseño de mecanismos, sugerimos un marco para estudiar tales algoritmos. En este modelo la solución algoritmo está adornada con pagos a los participantes y se denomina un mecanismo. Los pagos deben ser cuidadosamente elegidos como para motivar a todos los participantes a actuar como el algoritmo de diseño desea. Aplicamos las herramientas estándar de diseño de mecanismos a problemas algorítmicos y, en particular, al problema de trayectoria más corto.

Este artículo acuñó el término "diseño de mecanismos algorítmicos" y fue reconocido por el comité del Premio Gödel 2012 como uno de los "tres artículos que sientan las bases para el crecimiento de la teoría de juegos algorítmicos".Los otros dos artículos citados en el Premio Gödel de 2012 por sus contribuciones fundamentales a la Teoría de Juegos Algorítmicos introdujeron y desarrollaron el concepto de «Precio de la Anarquía». En su artículo de 1999, «Equilibrios en el Peor Caso», 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ó un par de años después).Internet creó una nueva economía, tanto como base para el intercambio y el comercio como por sí misma. Su naturaleza computacional permitió el uso de herramientas computacionales en esta nueva economía emergente. Por otro lado, Internet en sí misma es el resultado de las acciones de muchos. Esto era nuevo para el enfoque clásico, descendente, de la computación vigente hasta entonces. Por lo tanto, la teoría de juegos es una forma natural de ver Internet y las interacciones que se dan en 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 incentivos para cambiar su estrategia. Los equilibrios se encuentran en varios campos relacionados con Internet, por ejemplo, las interacciones financieras y el equilibrio de carga en las comunicaciones. La teoría de juegos proporciona herramientas para analizar los equilibrios, y un enfoque común consiste en "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 analizar las interacciones en internet y construir mecanismos para satisfacer demandas específicas. Si se demuestra la existencia de equilibrios, se debe responder a otra pregunta: ¿es posible encontrar un equilibrio en un tiempo razonable? Esto conduce al análisis de algoritmos para encontrar equilibrios. La clase de complejidad PPAD es especialmente importante, ya que incluye muchos problemas de la teoría de juegos algorítmica.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 algorítmico de mecanismos 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.Los conceptos de precio de la anarquía y precio de la estabilidad se introdujeron para reflejar la pérdida de rendimiento de un sistema debido al comportamiento egoísta de sus participantes. El precio de la anarquía refleja el peor rendimiento del sistema en equilibrio en relación con el rendimiento óptimo posible. El precio de la estabilidad, por otro lado, refleja el rendimiento relativo del mejor equilibrio del sistema. Estos conceptos son equivalentes a la noción de razón de aproximación en el diseño de algoritmos.La existencia de un equilibrio en un juego se establece típicamente mediante teoremas de punto fijo no constructivos. No se conocen algoritmos eficientes para calcular equilibrios de Nash. El problema es completo para la clase de complejidad PPAD, incluso en juegos de dos jugadores. En cambio, los equilibrios correlacionados pueden calcularse eficientemente mediante programación lineal, así como aprenderse mediante estrategias de no arrepentimiento.La elección social computacional estudia los aspectos computacionales de la elección social, es decir, la agregación de las preferencias de los agentes individuales. Algunos ejemplos incluyen algoritmos y la complejidad computacional de las reglas de votación y la formación de coaliciones.Otros temas incluyen:

• Algorithms for computing Market equilibria
• División justa
• Sistemas multiagent

Y el área cuenta con diversas aplicaciones prácticas:

• subastas de búsqueda patrocinadas
• subastas de espectro
• Criptomonedas
• Mercados de predicción
• Sistemas de reputación
• Compartir la economía
• Mercados coincidentes como el intercambio renal y la elección escolar
• Crowdsourcing y clasificación entre pares
• Economía de la nube

• ACM Transactions on Economics and Computation (TEAC)
• SIGEcom Exchanges

Los artículos sobre teoría de juegos algorítmica también suelen publicarse en revistas especializadas en teoría de juegos como GEB, revistas económicas como Econométrica y revistas informáticas como SICOMP.

• Auction Theory
• Elección social computacional
• Gamification
• Equilibrio de carga (computación)
• Diseño del mecanismo
• Sistema multiagente
• Voto en la teoría del juego

• John von Neumann, Oskar Morgenstern (1944) Teoría de Juegos y Comportamiento Económico. Princeton Univ. Press. 2007 edición: ISBN 978-0-691-13061-3
• Vazirani, Vijay V.; Nisan, Noam; Roughgarden, Tim; Tardos, Éva (2007), Teoría del Juego Algorítmico (PDF), Cambridge, UK: Cambridge University Press, ISBN 978-0-521-87282-9.

• gambit.sourceforge.net - una biblioteca de software de teoría del juego y herramientas para la construcción y análisis de juegos amplios y estratégicos finitos.
• gamut.stanford.edu - una suite de generadores de juego designados para probar algoritmos teóricos del juego.