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 determinado 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 información con sinceridad debido a sus propios intereses personales. Podemos ver la Teoría Algorítmica de Juegos desde dos perspectivas:
Además de los requisitos habituales en el diseño de algoritmos clásicos (por ejemplo, tiempo de ejecución polinomial , buena relación de aproximación), el diseñador también debe preocuparse por las restricciones de incentivos.
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 problemas algorítmicos en un entorno distribuido donde no se puede suponer que los participantes sigan el algoritmo sino 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 está adornada 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 de diseño de mecanismos a problemas algorítmicos y en particular al problema del camino 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 del crecimiento de la teoría algorítmica de juegos". [2]
Los otros dos artículos citados en el Premio Gödel 2012 por 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 "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 "El precio de la anarquía" sólo apareció un par de años después. [4] )
Internet creó una nueva economía, como base para el intercambio y el comercio y 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 había mantenido hasta entonces. Por 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 generalmente se define 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 necesaria ] . La teoría de juegos proporciona herramientas para analizar 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 equilibrios, se debe responder a una pregunta adicional: ¿se puede encontrar un equilibrio en un tiempo razonable? Esto lleva 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.
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 los 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 captura el peor desempeño del sistema 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.
La existencia de un equilibrio en un juego normalmente se establece mediante teoremas de punto fijo no constructivos . No se conocen algoritmos eficientes para calcular los equilibrios de Nash . El problema está 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 mediante programación lineal, [8] y también se pueden aprender mediante estrategias sin 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. Los ejemplos incluyen algoritmos y complejidad computacional de las reglas de votación y 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 algorítmica de juegos también se publican a menudo 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]