La teoría de juegos algorítmica ( TGA ) 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. Este área de investigación combina el pensamiento computacional con principios económicos para abordar los desafíos que surgen cuando las entradas de los algoritmos provienen de participantes con intereses propios.

En el diseño tradicional de algoritmos, se asume que las entradas serán 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 TGA proporciona marcos para analizar y diseñar sistemas que se mantengan eficaces a pesar de dicho sesgo de los comportamientos estratégicos.

El campo puede abordarse desde dos perspectivas complementarias:

Análisis: Evaluación de algoritmos y sistemas existentes mediante herramientas de teoría de juegos para comprender sus propiedades estratégicas. Esto incluye el cálculo y la comprobación de las propiedades de los equilibrios de Nash (estados estables donde ningún participante se beneficia modificando únicamente su propia estrategia), la medición del precio de la anarquía (pérdida de eficiencia debido al comportamiento egoísta) y el análisis de la dinámica de mejor respuesta (cómo evolucionan los sistemas cuando los jugadores optimizan secuencialmente sus respectivas estrategias). Diseño: Creación de algoritmos con propiedades deseables y robustez en teoría de juegos. Este subcampo, conocido como diseño de mecanismos algorítmicos, desarrolla sistemas que incentivan el comportamiento veraz de los agentes manteniendo la eficiencia computacional.

Los diseñadores de algoritmos en este dominio deben satisfacer los requisitos algorítmicos tradicionales (como el tiempo de ejecución en tiempo polinomial y una buena relación de aproximación) y al mismo tiempo abordar las restricciones de incentivos que garantizan que los agentes actúen de acuerdo con el diseño previsto del algoritmo.

Historia

Nisan-Ronen: un nuevo marco para el estudio de algoritmos En 1999, un 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 agentes egoístas. 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 sentaron las bases del crecimiento de la Teoría de Juegos Algorítmica".

El 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 de Juegos Algorítmica introdujeron y desarrollaron el concepto del Precio de la Anarquía. En su artículo de 1999, Equilibrios en el Peor de los Casos, Koutsoupias y Papadimitriou propusieron una nueva medida de la degradación de la eficiencia del sistema debido al comportamiento egoísta de los 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. )

Internet como catalizador Resulta evidente que Internet creó una nueva economía, tanto como base para el intercambio y el comercio como por sí misma. Su naturaleza computacional permite el uso de herramientas computacionales en esta nuevo tipo de economía. Por otro lado, Internet en sí misma es el resultado de las acciones de muchos. Esto supuso una novedad respecto al enfoque clásico, descendente, de la computación vigente hasta entonces. Por lo tanto, la teoría de juegos es una forma natural de comprender Internet y las interacciones que se dan en ella, tanto las humanas como las computacionales.

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 agente tiene incentivos para cambiar su estrategia. Los equilibrios se encuentran en diversos campos relacionados con Internet, por ejemplo, las interacciones financieras y el balanceo de las comunicaciones. La teoría de juegos proporciona herramientas para analizar estos equilibrios, y un enfoque común consiste en «encontrar el juego»; es decir, formalizar las interacciones específicas de Internet como un juego y derivar los equilibrios asociados.

Reformular estos problemas en términos de juegos permite analizar las interacciones en internet y construir mecanismos para satisfacer las demandas necesarias. Si se encuentra la existencia de equilibrios, hace falta responder a una pregunta adicional: ¿es posible alcanzar un equilibrio en un tiempo razonable? Esto conduce al análisis de algoritmos para la búsqueda de equilibrios. La clase de complejidad PPAD es especialmente importante, ya que abarca numerosos problemas de la Teoría de Juegos Algorítmica.

Áreas de investigación

Diseño de mecanismos algorítmicos El diseño de mecanismos es la subárea que se ocupa de la optimización bajo restricciones de incentivos. El diseño algorítmico de mecanismos considera la optimización de los sistemas bajo requisitos de eficiencia computacional. Los objetivos típicos estudiados incluyen la maximización de ingresos y del bienestar social.

Ineficiencia de los equilibrios Los conceptos de precio de la anarquía y precio de la estabilidad se introdujeron para captar la pérdida de rendimiento de un sistema debido al comportamiento egoísta de los agentes. El precio de la anarquía capta el peor rendimiento del sistema en relación con el rendimiento óptimo posible. El precio de la estabilidad, por otro lado, capta el rendimiento relativo del mejor equilibrio del sistema. Estos conceptos son equivalentes a la razó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 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 solo dos agentes. . En cambio, los equilibrios correlacionados pueden calcularse eficientemente mediante programación lineal, así como aprenderse siguiendo estrategias de no arrepentimiento.

Elección social computacional La elección social computacional estudia algunos aspectos de tipo computacional de las elecciones sociales, es decir, la agregación de las preferencias de los agentes individuales. Algunos ejemplos incluyen la complejidad de las reglas de votación y la formación de coaliciones.

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

Criptomonedas Mercados de Prediccion Sistemas reputacionales Economía colaborativa Crowdsourcing Economías de la nube

Véase también

Teoría de la subasta Gamificación Equilibrio de carga (informática) Diseño de mecanismos Sistema multiagente La votación en la teoría de juegos

John von Neumann, Oskar Morgenstern (1944) Teoría de juegos y comportamiento económico . Princeton Univ. Press. Edición de 2007.

Referencias

Categoría:Algoritmos Categoría:Teoría de juegos