Juego estocástico

En teoría de juegos , un juego estocástico (o juego de Markov ), introducido por Lloyd Shapley a principios de la década de 1950, ^[1] es un juego repetido con transiciones probabilísticas jugado por uno o más jugadores. El juego se juega en una secuencia de etapas. Al comienzo de cada etapa, el juego está en algún estado . Los jugadores seleccionan acciones y cada jugador recibe una recompensa que depende del estado actual y las acciones elegidas. El juego luego pasa a un nuevo estado aleatorio cuya distribución depende del estado anterior y las acciones elegidas por los jugadores. El procedimiento se repite en el nuevo estado y el juego continúa durante un número finito o infinito de etapas. La recompensa total para un jugador a menudo se toma como la suma descontada de las recompensas de la etapa o el límite inferior de los promedios de las recompensas de la etapa.

Los juegos estocásticos generalizan los procesos de decisión de Markov a múltiples tomadores de decisiones que interactúan, así como los juegos de forma estratégica a situaciones dinámicas en las que el entorno cambia en respuesta a las elecciones de los jugadores. ^[2]

Juegos para dos jugadores

Los juegos estocásticos de dos jugadores en gráficos dirigidos se utilizan ampliamente para modelar y analizar sistemas discretos que operan en un entorno desconocido (adversario) ^{[ cita requerida ]} . Las posibles configuraciones de un sistema y su entorno se representan como vértices, y las transiciones corresponden a acciones del sistema, su entorno o la "naturaleza". Una ejecución del sistema corresponde entonces a un camino infinito en el gráfico. Por lo tanto, un sistema y su entorno pueden verse como dos jugadores con objetivos antagónicos, donde un jugador (el sistema) apunta a maximizar la probabilidad de ejecuciones "buenas", mientras que el otro jugador (el entorno) apunta a lo opuesto.

En muchos casos, existe un valor de equilibrio de esta probabilidad, pero puede que no existan estrategias óptimas para ambos jugadores.

Presentamos conceptos básicos y cuestiones algorítmicas estudiadas en esta área y mencionamos algunos problemas abiertos desde hace mucho tiempo. Luego, mencionamos resultados recientes seleccionados.

Teoría

Los ingredientes de un juego estocástico son: un conjunto finito de jugadores ; un espacio de estados (ya sea un conjunto finito o un espacio medible ); para cada jugador , un conjunto de acciones (ya sea un conjunto finito o un espacio medible ); una probabilidad de transición de , donde son los perfiles de acción, a , donde es la probabilidad de que el siguiente estado sea en dado el estado actual y el perfil de acción actual ; y una función de pago de a , donde la -ésima coordenada de , , es el pago al jugador en función del estado y el perfil de acción . ${\displaystyle I}$ ${\displaystyle S}$ ${\displaystyle (S,{\mathcal {S}})}$ ${\displaystyle i\in I}$ ${\displaystyle A^{i}}$ ${\displaystyle (A^{i},{\mathcal {A}}^{i})}$ ${\displaystyle P}$ ${\displaystyle S\times A}$ ${\displaystyle A=\times _{i\in I}A^{i}}$ ${\displaystyle S}$ ${\displaystyle P(S\mid s,a)}$ ${\displaystyle S}$ ${\displaystyle s}$ ${\displaystyle a}$ ${\displaystyle g}$ ${\displaystyle S\times A}$ ${\displaystyle R^{I}}$ ${\displaystyle i}$ ${\displaystyle g}$ ${\displaystyle g^{i}}$ ${\displaystyle i}$ ${\displaystyle s}$ ${\displaystyle a}$

El juego comienza en un estado inicial . En la etapa , los jugadores primero observan , luego eligen simultáneamente acciones , luego observan el perfil de acciones y luego la naturaleza selecciona según la probabilidad . Una jugada del juego estocástico, define una secuencia de pagos , donde . ${\displaystyle s_{1}}$ ${\displaystyle t}$ ${\displaystyle s_{t}}$ ${\displaystyle a_{t}^{i}\in A^{i}}$ ${\displaystyle a_{t}=(a_{t}^{i})_{i}}$ ${\displaystyle s_{t+1}}$ ${\displaystyle P(\cdot \mid s_{t},a_{t})}$ ${\displaystyle s_{1},a_{1},\ldots ,s_{t},a_{t},\ldots }$ ${\displaystyle g_{1},g_{2},\ldots }$ ${\displaystyle g_{t}=g(s_{t},a_{t})}$

El juego descontado con factor de descuento ( ) es el juego en el que el pago al jugador es . El juego de -etapa es el juego en el que el pago al jugador es . ${\displaystyle \Gamma _{\lambda }}$ ${\displaystyle \lambda }$ ${\displaystyle 0<\lambda \leq 1}$ ${\displaystyle i}$ ${\displaystyle \lambda \sum _{t=1}^{\infty }(1-\lambda )^{t-1}g_{t}^{i}}$ ${\displaystyle n}$ ${\displaystyle i}$ ${\displaystyle {\bar {g}}_{n}^{i}:={\frac {1}{n}}\sum _{t=1}^{n}g_{t}^{i}}$

Existe el valor , respectivamente , de un juego estocástico de suma cero de dos personas , respectivamente , con un número finito de estados y acciones, y Truman Bewley y Elon Kohlberg (1976) demostraron que converge a un límite cuando tiende al infinito y que converge al mismo límite cuando tiende a . ${\displaystyle v_{n}(s_{1})}$ ${\displaystyle v_{\lambda }(s_{1})}$ ${\displaystyle \Gamma _{n}}$ ${\displaystyle \Gamma _{\lambda }}$ ${\displaystyle v_{n}(s_{1})}$ ${\displaystyle n}$ ${\displaystyle v_{\lambda }(s_{1})}$ ${\displaystyle \lambda }$ ${\displaystyle 0}$

El juego "sin descuento" es el juego en el que el pago al jugador es el "límite" de los promedios de los pagos de la etapa. Se necesitan algunas precauciones para definir el valor de un juego estocástico de suma cero de dos personas y para definir los pagos de equilibrio de un juego estocástico de suma cero distinto de cero . El valor uniforme de un juego estocástico de suma cero de dos personas existe si para cada hay un entero positivo y un par de estrategias del jugador 1 y del jugador 2 tales que para cada y y cada la expectativa de con respecto a la probabilidad de jugadas definidas por y es al menos , y la expectativa de con respecto a la probabilidad de jugadas definidas por y es como máximo . Jean-François Mertens y Abraham Neyman (1981) demostraron que todo juego estocástico de suma cero de dos personas con un número finito de estados y acciones tiene un valor uniforme. ^[3] ${\displaystyle \Gamma _{\infty }}$ ${\displaystyle i}$ ${\displaystyle \Gamma _{\infty }}$ ${\displaystyle \Gamma _{\infty }}$ ${\displaystyle v_{\infty }}$ ${\displaystyle \Gamma _{\infty }}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle N}$ ${\displaystyle \sigma _{\varepsilon }}$ ${\displaystyle \tau _{\varepsilon }}$ ${\displaystyle \sigma }$ ${\displaystyle \tau }$ ${\displaystyle n\geq N}$ ${\displaystyle {\bar {g}}_{n}^{i}}$ ${\displaystyle \sigma _{\varepsilon }}$ ${\displaystyle \tau }$ ${\displaystyle v_{\infty }-\varepsilon }$ ${\displaystyle {\bar {g}}_{n}^{i}}$ ${\displaystyle \sigma }$ ${\displaystyle \tau _{\varepsilon }}$ ${\displaystyle v_{\infty }+\varepsilon }$

Si hay un número finito de jugadores y los conjuntos de acciones y estados son finitos, entonces un juego estocástico con un número finito de etapas siempre tiene un equilibrio de Nash . Lo mismo es cierto para un juego con infinitas etapas si el resultado total es la suma descontada.

El juego estocástico de suma no nula tiene un pago de equilibrio uniforme si para cada hay un entero positivo y un perfil de estrategia tal que para cada desviación unilateral de un jugador , es decir, un perfil de estrategia con para todos , y cada la expectativa de con respecto a la probabilidad de jugadas definidas por es al menos , y la expectativa de con respecto a la probabilidad de jugadas definidas por es como máximo . Nicolas Vieille ha demostrado que todos los juegos estocásticos de dos personas con espacios de estados y acciones finitos tienen un pago de equilibrio uniforme. ^[4] ${\displaystyle \Gamma _{\infty }}$ ${\displaystyle v_{\infty }}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle N}$ ${\displaystyle \sigma }$ ${\displaystyle i}$ ${\displaystyle \tau }$ ${\displaystyle \sigma ^{j}=\tau ^{j}}$ ${\displaystyle j\neq i}$ ${\displaystyle n\geq N}$ ${\displaystyle {\bar {g}}_{n}^{i}}$ ${\displaystyle \sigma }$ ${\displaystyle v_{\infty }^{i}-\varepsilon }$ ${\displaystyle {\bar {g}}_{n}^{i}}$ ${\displaystyle \tau }$ ${\displaystyle v_{\infty }^{i}+\varepsilon }$

El juego estocástico de suma no cero tiene un pago de equilibrio promedio límite si para cada hay un perfil de estrategia tal que para cada desviación unilateral de un jugador , la expectativa del límite inferior de los promedios de los pagos de etapa con respecto a la probabilidad de jugadas definidas por es al menos , y la expectativa del límite superior de los promedios de los pagos de etapa con respecto a la probabilidad de jugadas definidas por es como máximo . Jean-François Mertens y Abraham Neyman (1981) demuestran que todo juego estocástico de suma cero de dos personas con un número finito de estados y acciones tiene un valor promedio límite, ^[3] y Nicolas Vieille ha demostrado que todos los juegos estocásticos de dos personas con espacios de estados y acciones finitos tienen un pago de equilibrio promedio límite. ^[4] En particular, estos resultados implican que estos juegos tienen un valor y un pago de equilibrio aproximado, llamado pago de equilibrio liminf-average (respectivamente, limsup-average), cuando el pago total es el límite inferior (o el límite superior) de los promedios de los pagos de la etapa. ${\displaystyle \Gamma _{\infty }}$ ${\displaystyle v_{\infty }}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle \sigma }$ ${\displaystyle i}$ ${\displaystyle \sigma }$ ${\displaystyle v_{\infty }^{i}-\varepsilon }$ ${\displaystyle \tau }$ ${\displaystyle v_{\infty }^{i}+\varepsilon }$

Si cada juego estocástico con un número finito de jugadores, estados y acciones tiene un pago de equilibrio uniforme, o un pago de equilibrio promedio límite, o incluso un pago de equilibrio promedio límite, es una pregunta abierta y desafiante.

Un equilibrio perfecto de Markov es un refinamiento del concepto de equilibrio de Nash perfecto en subjuegos para juegos estocásticos.

Los juegos estocásticos se han combinado con juegos bayesianos para modelar la incertidumbre sobre las estrategias de los jugadores. ^[5] El modelo de juego bayesiano estocástico resultante se resuelve mediante una combinación recursiva de la ecuación de equilibrio de Nash bayesiano y la ecuación de optimalidad de Bellman .

Aplicaciones

Los juegos estocásticos tienen aplicaciones en economía , biología evolutiva y redes de computadoras. ^{[6] [7]} Son generalizaciones de juegos repetidos que corresponden al caso especial donde solo hay un estado.

Véase también

• Proceso estocástico

Notas

1. Shapley, LS (1953). "Juegos estocásticos". PNAS . 39 (10): 1095–1100. Código Bibliográfico :1953PNAS...39.1095S. doi : 10.1073/pnas.39.10.1095 . PMC  1063912 . PMID  16589380.
2. Solan, Eilon; Vieille, Nicolas (2015). "Juegos estocásticos". PNAS . 112 (45): 13743–13746. doi : 10.1073/pnas.1513508112 . PMC 4653174 . PMID  26556883. 
3. Mertens, JF y Neyman, A. (1981). "Juegos estocásticos". Revista internacional de teoría de juegos . 10 (2): 53–66. doi :10.1007/BF01769259. S2CID  189830419.
4. Vieille, N. (2002). "Juegos estocásticos: resultados recientes". Handbook of Game Theory . Ámsterdam: Elsevier Science. págs. 1833–1850. ISBN 0-444-88098-4.
5. Albrecht, Stefano; Crandall, Jacob; Ramamoorthy, Subramanian (2016). "Creencia y verdad en conductas hipotéticas". Inteligencia artificial . 235 : 63–94. arXiv : 1507.07688 . doi :10.1016/j.artint.2016.02.004. S2CID  2599762.
6. Juegos estocásticos restringidos en redes inalámbricas por E. Altman, K. Avratchenkov, N. Bonneau, M. Debbah, R. El-Azouzi, DSMenasche
7. Djehiche, Boualem; Tcheukam, Alain; Tembine, Hamidou (27 de septiembre de 2017). "Juegos de tipo campo medio en ingeniería". AIMS Electronics and Electrical Engineering . 1 : 18–73. arXiv : 1605.03281 . doi :10.3934/ElectrEng.2017.1.18. S2CID  16055840.

Lectura adicional

• Filar, J. y Vrieze, K. (1997). Procesos competitivos de decisión de Markov . Springer-Verlag. ISBN 0-387-94805-8.
• Neyman, A. y Sorin, S. (2003). Juegos estocásticos y aplicaciones . Dordrecht: Kluwer Academic Press. ISBN 1-4020-1492-9.
• Yoav Shoham; Kevin Leyton-Brown (2009). Sistemas multiagente: fundamentos algorítmicos, teóricos de juegos y lógicos . Cambridge University Press. pp. 153–156. ISBN 978-0-521-89943-7.(apto para estudiantes universitarios; resultados principales, sin pruebas)

Enlaces externos

• Conferencia sobre juegos estocásticos para dos jugadores por Antonin Kucera