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:
Además de los requisitos habituales en el diseño de algoritmos clásicos (por ejemplo, tiempo de ejecución de 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 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 en el que no se puede suponer que los participantes sigan el algoritmo, sino más bien su propio interés. Como tales 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 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 en la teoría de juegos algorítmicos". [2]