El equilibrio de programas es un concepto de solución de teoría de juegos para un escenario en el que los jugadores envían programas de computadora para jugar el juego en su nombre y los programas pueden leer el código fuente de los demás. El término fue introducido por Moshe Tennenholtz en 2004. [1] El mismo escenario había sido estudiado previamente por R. Preston McAfee , [2] JV Howard [3] y Ariel Rubinstein . [4]
La literatura sobre el equilibrio de programas considera el siguiente escenario. Consideremos un juego de forma normal como juego base. Para simplificar, consideremos un juego de dos jugadores en el que y son los conjuntos de estrategias disponibles y y son las funciones de utilidad de los jugadores . Luego construimos un nuevo juego de programa (de forma normal) en el que cada jugador elige un programa de computadora . La ganancia (utilidad) para los jugadores se determina entonces de la siguiente manera. El programa de cada jugador se ejecuta con el otro programa como entrada y genera una estrategia para Jugador . Por conveniencia, a menudo también se imagina que los programas pueden acceder a su propio código fuente. [nb 1] Finalmente, las utilidades para los jugadores están dadas por para , es decir, aplicando las funciones de utilidad para el juego base a las estrategias elegidas.
Además, hay que lidiar con la posibilidad de que uno de los programas no se detenga. Una forma de hacerlo es restringir los conjuntos de programas disponibles de ambos jugadores para evitar que los programas no se detengan. [1] [5]
Un equilibrio de programas es un par de programas que constituyen un equilibrio de Nash del juego de programas. En otras palabras, es un equilibrio de programas si ningún jugador puede desviarse a un programa alternativo tal que su utilidad sea mayor en que en .
En lugar de programas, algunos autores hacen que los jugadores envíen otros tipos de objetos, como fórmulas lógicas que especifican qué acción realizar dependiendo de una codificación de la fórmula lógica enviada por el oponente. [6] [7]
Varios autores han propuesto formas de lograr el equilibrio del programa cooperativo en el dilema del prisionero .
Varios autores han propuesto de forma independiente el siguiente programa para el dilema del prisionero: [1] [3] [2]
algoritmo CliqueBot(programa_oponente): si programa_oponente == este_programa entonces devuelve Cooperar de lo contrario devuelve Defecto
Si ambos jugadores envían este programa, la cláusula if se resolverá como verdadera en la ejecución de ambos programas. Como resultado, ambos programas cooperarán. Además, (CliqueBot,CliqueBot) es un equilibrio. Si alguno de los jugadores se desvía hacia algún otro programa que sea diferente de CliqueBot, entonces el oponente desertará. Por lo tanto, desviarse hacia un programa diferente puede, en el mejor de los casos, resultar en la recompensa de la deserción mutua, que es peor que la recompensa de la cooperación mutua.
Este enfoque ha sido criticado por ser frágil. [5] Si los jugadores no logran coordinar el código fuente exacto que envían (por ejemplo, si un jugador agrega un espacio adicional), ambos programas fallarán. El desarrollo de las técnicas que se describen a continuación está motivado en parte por este problema de fragilidad.
Otro enfoque se basa en dejar que el programa de cada jugador intente demostrar algo sobre el programa del oponente o sobre cómo se relacionan los dos programas. [6] [8] [9] [10] Un ejemplo de dicho programa es el siguiente:
algoritmo FairBot(programa_oponente): si hay una prueba de que programa_oponente(este_programa) = Cooperar entonces devuelve Cooperar de lo contrario devuelve Defecto
Utilizando el teorema de Löb se puede demostrar que cuando ambos jugadores envían este programa, cooperan entre sí. [8] [9] [10] Además, si un jugador en su lugar enviara un programa que falla contra el programa anterior, entonces (asumiendo que se utiliza la consistencia del sistema de prueba) la condición if se resolvería como falsa y el programa anterior fallaría. Por lo tanto, (FairBot,FairBot) también es un equilibrio de programas.
Otro programa propuesto es el siguiente: [5] [11]
algoritmo GroundedFairBot(programa_oponente): Con probabilidad : devuelve Cooperar devuelve oponente_programa(este_programa)
Aquí hay un pequeño número positivo.
Si ambos jugadores presentan este programa, entonces es casi seguro que terminarán y cooperarán. El número esperado de pasos hasta la terminación está dado por la serie geométrica . Además, si ambos jugadores presentan este programa, ninguno puede desviarse de manera rentable, suponiendo que sea suficientemente pequeño, porque desertar con probabilidad haría que el oponente desertara con probabilidad .
Aquí presentamos un teorema que caracteriza qué pagos se pueden lograr en el equilibrio del programa.
El teorema utiliza la siguiente terminología: Un par de pagos se denomina factible si existe un par de estrategias (potencialmente mixtas) tales que para ambos jugadores . Es decir, un par de pagos se denomina factible si se logra en algún perfil de estrategia . Un pago se denomina individualmente racional si es mejor que el pago minimax de ese jugador; es decir, si , donde el mínimo es sobre todas las estrategias mixtas para el Jugador . [nb 2]
Teorema (teorema popular para el equilibrio de programas): [4] [1] Sea G un juego base. Sea un par de pagos de valor real. Entonces, las dos afirmaciones siguientes son equivalentes:
El resultado se denomina teorema popular en referencia a los llamados teoremas populares (teoría de juegos) para juegos repetidos , que utilizan las mismas condiciones en los pagos de equilibrio .