La teoría de juegos algorítmicos ( AGT ) es un área en la intersección de la teoría de juegos y la ciencia de la computación , con el objetivo de comprender y diseñar algoritmos en entornos estratégicos .
Por lo general, en los problemas de teoría de juegos algorítmicos, la información de entrada de un algoritmo determinado se distribuye entre muchos participantes que tienen un interés personal en el resultado. En esas situaciones, los agentes pueden no informar la información de entrada de manera veraz debido a sus propios intereses personales. Podemos ver la teoría de juegos algorítmicos desde dos perspectivas:
Además de los requisitos habituales en el diseño de algoritmos clásicos (por ejemplo, tiempo de ejecución en tiempo polinomial , buena relación de aproximación), el diseñador también debe preocuparse por las restricciones de incentivos.
En 1999, el artículo seminal de Noam Nisan y Amir Ronen [1] atrajo la atención de la comunidad de la informática teórica hacia 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 sus propios intereses. 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 vean mejor atendidos 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 desea el diseñador del algoritmo. Aplicamos las herramientas estándar del diseño de mecanismos a los problemas algorítmicos y, en particular, al problema del camino más corto.
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]
Los otros dos artículos citados en el Premio Gödel 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 “Worst-case Equilibria”, [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ó recién un par de años después. [4] )
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 para el enfoque clásico de computación "de arriba hacia abajo" que se había mantenido 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 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 de las comunicaciones [ 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.
La reformulación de 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 equilibrios, se debe responder a otra pregunta: ¿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 de la teoría de juegos algorítmicos.
El diseño de mecanismos es el 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.
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 sus participantes. El precio de la anarquía capta el peor rendimiento del sistema en equilibrio en relación con el rendimiento óptimo posible. [5] El precio de la estabilidad , por otro lado, capta el rendimiento relativo del mejor equilibrio del sistema. [6] Estos conceptos son contrapartes de 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 utilizando teoremas de punto fijo no constructivos . No existen algoritmos eficientes conocidos para calcular equilibrios de Nash . El problema es completo para la clase de complejidad PPAD incluso en juegos de 2 jugadores. [7] En cambio, los equilibrios correlacionados se pueden calcular de manera eficiente utilizando programación lineal, [8] así como aprenderse mediante estrategias de no arrepentimiento. [9]
La elección social computacional estudia los aspectos computacionales de la elección social , 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. [10]
Otros temas incluyen:
Y el área cuenta con diversas aplicaciones prácticas: [11] [12]
Los artículos sobre teoría de juegos algorítmicos también suelen publicarse en revistas de teoría de juegos como GEB , [15] revistas de economía como Econometrica y revistas de informática como SICOMP . [16]