Equilibrio del programa

Teoría de juegos

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]

Configuración y definición

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. ${\displaystyle S_{1}}$ ${\displaystyle S_{2}}$ ${\displaystyle u_{1}}$ ${\displaystyle u_{2}}$ ${\displaystyle i}$ ${\displaystyle p_{i}}$ ${\displaystyle p_{i}}$ ${\displaystyle p_{-i}}$ ${\displaystyle s_{i}}$ ${\displaystyle i}$ ${\displaystyle u_{i}(s_{1},s_{2})}$ ${\displaystyle i=1,2}$

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]} ${\displaystyle p_{i}}$

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 . ${\displaystyle (p_{1},p_{2})}$ ${\displaystyle (p_{1},p_{2})}$ ${\displaystyle i}$ ${\displaystyle p_{i}'}$ ${\displaystyle (p_{i}',p_{-i})}$ ${\displaystyle (p_{1},p_{2})}$

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]}

Diferentes mecanismos para lograr el equilibrio del programa cooperativo en el dilema del prisionero

Varios autores han propuesto formas de lograr el equilibrio del programa cooperativo en el dilema del prisionero .

Cooperación basada en comparación sintáctica

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. ${\displaystyle p_{i}}$ ${\displaystyle p_{i}}$

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.

Cooperación basada en pruebas

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.

Cooperación con simulación basada en ε

Otro programa propuesto es el siguiente: ^{[5] [11]}

algoritmo GroundedFairBot(programa_oponente): ${\displaystyle \epsilon }$ Con probabilidad : devuelve Cooperar devuelve oponente_programa(este_programa) ${\displaystyle \epsilon }$

Aquí hay un pequeño número positivo. ${\displaystyle \epsilon }$

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 . ${\displaystyle \epsilon }$ ${\displaystyle \Delta }$ ${\displaystyle (1-\epsilon )\Delta }$

Teorema popular

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]} ${\displaystyle (v_{1},v_{2})}$ ${\displaystyle (s_{1},s_{2})}$ ${\displaystyle u_{i}(s_{1},s_{2})=v_{i}}$ ${\displaystyle i}$ ${\displaystyle v_{i}}$ ${\displaystyle v_{i}\geq \min _{\sigma _{-i}}\max _{s_{i}}u_{i}(\sigma _{-i},s_{i})}$ ${\displaystyle -i}$

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: ${\displaystyle (v_{1},v_{2})}$

• Los beneficios son factibles y racionales a nivel individual. ${\displaystyle (v_{1},v_{2})}$
• Existe un equilibrio de programa que logra pagos . ${\displaystyle (p_{1},p_{2})}$ ${\displaystyle (v_{1},v_{2})}$

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 . ${\displaystyle (v_{1},v_{2})}$

Véase también

• Superracionalidad

Notas

1. No es necesario que los programas del juego de programas tengan acceso a su propio código fuente. Mediante el lema de diagonalización , se puede utilizar la función de quining para permitir que los programas hagan referencia a su código fuente. ^{[2] [3] [4]}
2. De manera equivalente, (según el teorema minimax de von Neumann ), , donde el máximo es sobre todas las estrategias mixtas para el jugador . ${\displaystyle v_{i}\geq \max _{\sigma _{i}}\min _{s_{-i}}u_{i}(\sigma _{i},s_{-i})}$ ${\displaystyle \sigma _{i}}$ ${\displaystyle i}$

Referencias

1. Tennenholtz, M. (noviembre de 2004). "Program equilibrium". Juegos y comportamiento económico . 49 (2). Elsevier : 363–373. doi :10.1016/j.geb.2004.02.002. ISSN  0899-8256.
2. McAfee, RP (mayo de 1984). Computabilidad efectiva en decisiones económicas (PDF) (informe técnico). Universidad de Western Ontario.
3. Howard, JV (mayo de 1988). "Cooperación en el dilema del prisionero". Teoría y decisión . 24 (3). Kluwer Academic Publishers : 203–213. doi :10.1007/BF00148954. S2CID  121119727.
4. Rubinstein, A. (1998). "Cap. 10.4". Modelado de la racionalidad limitada . MIT Press . ISBN 978-0262681001.
5. Oesterheld, C. (febrero de 2019). "Equilibrio de programa robusto". Teoría y decisión . 86 . Springer : 143–159. doi : 10.1007/s11238-018-9679-3 . S2CID  255103752.
6. van der Hoek, W.; Witteveen, C.; Wooldridge, M. (2013). "Equilibrio de programas: un enfoque de razonamiento de programas". Revista internacional de teoría de juegos . 42 (3). Springer : 639–671. CiteSeerX 10.1.1.228.6517 . doi :10.1007/s00182-011-0314-6. S2CID  253720520. 
7. Peters, Michael; Szentes, Balázs (enero de 2012). "Contratos definibles y contraíbles" (PDF) . Econometrica . 80 (1). The Econometric Society : 363–411. doi :10.3982/ECTA8375.
8. Barasz, M.; Christiano, P.; Fallenstein, B.; Herreshoff, M.; LaVictoire, P.; Yudkowsky, E. (2014). "Cooperación robusta en el dilema del prisionero: equilibrio del programa mediante lógica de demostrabilidad". arXiv : 1401.5577 [cs.GT].
9. Critch, A. (2019). "Una generalización paramétrica y limitada por recursos del teorema de Löb y un criterio de cooperación robusto para la teoría de juegos de código abierto". Journal of Symbolic Logic . 84 (4). Cambridge University Press : 1368–1381. doi :10.1017/jsl.2017.42. S2CID  133348715.
10. Critch, A.; Dennis, M.; Russell, S. (2022). "Diseños de instituciones cooperativas y no cooperativas: sorpresas y problemas en la teoría de juegos de código abierto". arXiv : 2208.07006 [cs.GT].
11. DiGiovanni, A.; Clifton, J. (2023). "Juegos de compromiso con divulgación de información condicional". Actas de la Conferencia AAAI sobre Inteligencia Artificial . arXiv : 2204.03484 .