Hispanopedia Wiki
Articulo de referencia

Juego estocástico

En teoría de juegos , un juego estocástico (o juego de Markov ) es un juego repetido con transiciones probabilísticas jugado por uno o más jugadores. El juego se desarrolla en u...

Hispanopedia WikiContenido en espanolLectura gratuita

En teoría de juegos , un juego estocástico (o juego de Markov ) es un juego repetido con transiciones probabilísticas jugado por uno o más jugadores. El juego se desarrolla en una secuencia de etapas. Al comienzo de cada etapa, el juego se encuentra en un estado inicial . Los jugadores seleccionan acciones y cada uno recibe una recompensa que depende del estado actual y de las acciones elegidas. A continuación, el juego pasa a un nuevo estado aleatorio cuya distribución depende del estado anterior y de 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 de un jugador suele ser la suma descontada de las recompensas de las etapas o el límite inferior de las medias de las recompensas de las etapas.

Los juegos estocásticos fueron introducidos por Lloyd Shapley a principios de la década de 1950. [ 1 ] Generalizan los procesos de decisión de Markov a múltiples agentes decisores que interactúan entre sí, 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 grafos dirigidos se utilizan ampliamente para el modelado y análisis de sistemas discretos que operan en un entorno desconocido (adversario) . 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 su "naturaleza". Una ejecución del sistema corresponde entonces a un camino infinito en el grafo. Así, un sistema y su entorno pueden considerarse como dos jugadores con objetivos antagónicos, donde un jugador (el sistema) busca maximizar la probabilidad de obtener buenas ejecuciones, mientras que el otro jugador (el entorno) busca lo contrario.

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

Una versión modificada del juego de piedra, papel o tijera, que se juega con dados, representada de forma general en el primer gráfico y con mayor detalle en el segundo. Cada jugador dispone de un conjunto de 6 dados, donde 4 caras de cada dado muestran piedra, papel o tijera, y 2 caras muestran una de las otras opciones, de modo que el conjunto de 6 dados contiene todas las combinaciones posibles. "RP" significa un dado con 4 piedras y 2 papeles, y aunque no ambos jugadores puedan elegir este dado, cualquier par de combinaciones es equivalente a una combinación de cualquier dado base con otro dado, por lo que se utiliza BR como base. En caso de empate, los jugadores pueden elegir un nuevo dado si lo desean. El gráfico más extenso es necesario porque la probabilidad de que los jugadores ganen está influenciada por el dado que ellos y sus oponentes elijan. Por lo tanto, la probabilidad de cada resultado es una función de los perfiles de acción de los jugadores durante la fase de "elección y lanzamiento".

Presentamos conceptos básicos y cuestiones algorítmicas estudiadas en este campo, y mencionamos algunos problemas abiertos de larga data. A continuación, destacamos algunos resultados recientes.

Teoría

Los ingredientes de un juego estocástico son: un conjunto finito de jugadoresI{\displaystyle I}; un espacio de estadosS{\displaystyle S}(ya sea un conjunto finito o un espacio medible)(S,S){\displaystyle (S,{\mathcal {S}})}); para cada jugadori∈I{\displaystyle i\in I}, un conjunto de accionesAi{\displaystyle A^{i}} (ya sea un conjunto finito o un espacio medible)(Ai,Ai){\displaystyle (A^{i},{\mathcal {A}}^{i})}); una probabilidad de transiciónPAG{\displaystyle P}deS×A{\displaystyle S\times A}, dóndeA=×i∈IAi{\displaystyle A=\times _{i\in I}A^{i}}son los perfiles de acción, paraS{\displaystyle S}, dóndePAG(S∣s,a){\displaystyle P(S\mid s,a)}es la probabilidad de que el siguiente estado esté enS{\displaystyle S}dado el estado actuals{\displaystyle s}y el perfil de acción actuala{\displaystyle a}y una función de pagogramo{\displaystyle g}deS×A{\displaystyle S\times A}aRI{\displaystyle R^{I}}, donde eli{\displaystyle i}-ésima coordenada degramo{\displaystyle g},gramoi{\displaystyle g^{i}}es la recompensa para el jugadori{\displaystyle i}como función del estados{\displaystyle s}y el perfil de accióna{\displaystyle a}.

El juego comienza en un estado inicial.s1{\displaystyle s_{1}}En el escenariot{\displaystyle t}Los jugadores observan primerost{\displaystyle s_{t}}y luego, simultáneamente, elegir accionesati∈Ai{\displaystyle a_{t}^{i}\in A^{i}}Luego, observe el perfil de acción.at=(ati)i{\displaystyle a_{t}=(a_{t}^{i})_{i}}y luego la naturaleza seleccionast+1{\displaystyle s_{t+1}}según la probabilidadPAG(⋅∣st,at){\displaystyle P(\cdot \mid s_{t},a_{t})}. Un juego del juego estocástico,s1,a1,…,st,at,…{\displaystyle s_{1},a_{1},\ldots ,s_{t},a_{t},\ldots }define una serie de pagosgramo1,gramo2,…{\displaystyle g_{1},g_{2},\ldots }, dóndegramot=gramo(st,at){\displaystyle g_{t}=g(s_{t},a_{t})}.

El juego con descuentoΓλ{\displaystyle \Gamma _{\lambda }}con factor de descuentoλ{\displaystyle \lambda }(0<λ≤1{\displaystyle 0<\lambda \leq 1}) es el juego donde la recompensa para el jugadori{\displaystyle i}esλ∑t=1∞(1−λ)t−1gramoti{\displaystyle \lambda \sum _{t=1}^{\infty }(1-\lambda )^{t-1}g_{t}^{i}}. Elnorte{\displaystyle n}-El juego de etapa es el juego donde la recompensa para el jugadori{\displaystyle i}esgramo¯nortei:=1norte∑t=1nortegramoti{\displaystyle {\bar {g}}_{n}^{i}:={\frac {1}{n}}\sum _{t=1}^{n}g_{t}^{i}}.

El valorvnorte(s1){\displaystyle v_{n}(s_{1})}respectivamentevλ(s1){\displaystyle v_{\lambda }(s_{1})}, de un juego estocástico de suma cero para dos personasΓnorte{\displaystyle \Gamma _{n}}respectivamenteΓλ{\displaystyle \Gamma _{\lambda }}, con un número finito de estados y acciones existe, y Truman Bewley y Elon Kohlberg (1976) demostraron quevnorte(s1){\displaystyle v_{n}(s_{1})}converge a un límite cuandonorte{\displaystyle n}va hasta el infinito y esovλ(s1){\displaystyle v_{\lambda }(s_{1})}converge al mismo límite queλ{\displaystyle \lambda }va a0{\displaystyle 0}.

El juego "sin descuento" Γ∞{\displaystyle \Gamma _{\infty }}es el juego donde la recompensa para el jugadori{\displaystyle i}es el "límite" de los promedios de las ganancias de la etapa. Se necesitan algunas precauciones al definir el valor de un juego de suma cero para dos personas.Γ∞{\displaystyle \Gamma _{\infty }}y al definir las recompensas de equilibrio de una suma no nulaΓ∞{\displaystyle \Gamma _{\infty }}. El valor uniformev∞{\displaystyle v_{\infty }}de un juego estocástico de suma cero para dos personasΓ∞{\displaystyle \Gamma _{\infty }}existe si para cadaε>0{\displaystyle \varepsilon >0}hay un número entero positivonorte{\displaystyle N} y un par de estrategiasσε{\displaystyle \sigma _{\varepsilon }}del jugador 1 yτε{\displaystyle \tau _{\varepsilon }}del jugador 2 tal que para cadaσ{\displaystyle \sigma }yτ{\displaystyle \tau }y cadanorte≥norte{\displaystyle n\geq N} la expectativa degramo¯nortei{\displaystyle {\bar {g}}_{n}^{i}}con respecto a la probabilidad en jugadas definidas porσε{\displaystyle \sigma _{\varepsilon }}yτ{\displaystyle \tau }es al menosv∞−ε{\displaystyle v_{\infty }-\varepsilon }y la expectativa degramo¯nortei{\displaystyle {\bar {g}}_{n}^{i}}con respecto a la probabilidad en jugadas definidas porσ{\displaystyle \sigma }y τε{\displaystyle \tau _{\varepsilon }}es como máximov∞+ε{\displaystyle v_{\infty }+\varepsilon }Jean -François Mertens y Abraham Neyman (1981) demostraron que todo juego estocástico de suma cero para dos personas con un número finito de estados y acciones tiene un valor uniforme. [ 3 ]

Existencia de un equilibrio

equilibrio de Nash

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

El juego estocástico de suma no nulaΓ∞{\displaystyle \Gamma _{\infty }}tiene una recompensa de equilibrio uniformev∞{\displaystyle v_{\infty }}si por cadaε>0{\displaystyle \varepsilon >0}hay un número entero positivonorte{\displaystyle N} y un perfil estratégicoσ{\displaystyle \sigma }de tal manera que por cada desviación unilateral de un jugadori{\displaystyle i}, es decir, un perfil estratégico τ{\displaystyle \tau }conσj=τj{\displaystyle \sigma ^{j}=\tau ^{j}}a pesar dej≠i{\displaystyle j\neq i}y cadanorte≥norte{\displaystyle n\geq N} la expectativa degramo¯nortei{\displaystyle {\bar {g}}_{n}^{i}}con respecto a la probabilidad en jugadas definidas porσ{\displaystyle \sigma }es al menosv∞i−ε{\displaystyle v_{\infty }^{i}-\varepsilon }y la expectativa degramo¯nortei{\displaystyle {\bar {g}}_{n}^{i}}con respecto a la probabilidad en jugadas definidas por τ{\displaystyle \tau }es como máximov∞i+ε{\displaystyle v_{\infty }^{i}+\varepsilon }Nicolas Vieille ha demostrado que todos los juegos estocásticos de dos personas con espacios de estado y acción finitos tienen una recompensa de equilibrio uniforme. [ 4 ]

El juego estocástico de suma no nulaΓ∞{\displaystyle \Gamma _{\infty }}tiene una recompensa de equilibrio promedio límitev∞{\displaystyle v_{\infty }}si por cadaε>0{\displaystyle \varepsilon >0}Hay un perfil de estrategiaσ{\displaystyle \sigma }de tal manera que por cada desviación unilateral de un jugadori{\displaystyle i}, la expectativa del límite inferior de los promedios de los pagos de la etapa con respecto a la probabilidad en las jugadas definidas porσ{\displaystyle \sigma }es al menosv∞i−ε{\displaystyle v_{\infty }^{i}-\varepsilon }y la expectativa del límite superior de los promedios de los pagos de la etapa con respecto a la probabilidad en las jugadas definidas por τ{\displaystyle \tau }es como máximov∞i+ε{\displaystyle v_{\infty }^{i}+\varepsilon }Jean -François Mertens y Abraham Neyman (1981) demuestran que todo juego estocástico de suma cero para dos personas con un número finito de estados y acciones tiene un valor límite promedio, [ 3 ] y Nicolas Vieille ha demostrado que todos los juegos estocásticos para dos personas con espacios finitos de estados y acciones tienen una recompensa de equilibrio límite promedio. [ 4 ] En particular, estos resultados implican que estos juegos tienen un valor y una recompensa de equilibrio aproximada, llamada recompensa de equilibrio límite inferior (respectivamente, límite superior), cuando la recompensa total es el límite inferior (o el límite superior) de los promedios de las recompensas de las etapas.

Determinar si todo juego estocástico con un número finito de jugadores, estados y acciones tiene una recompensa de equilibrio uniforme, una recompensa de equilibrio promedio límite o incluso una recompensa de equilibrio promedio límite inferior es una cuestión abierta y compleja.

Perfiles aceptables para minmax

Perfil estratégicos∗{\displaystyle s^{*}}se denomina minmax-aceptable [ 5 ] [ 6 ] si la utilidad de cada jugador ens∗{\displaystyle s^{*}}es al menos el valor minmax del jugador:

túi(s∗)≥mins−imáximositúi(s−i,si){\displaystyle u_{i}(s^{*})\geq \min _{s_{-i}}\max _{s_{i}}u_{i}(s_{-i},s_{i})}.

Todo equilibrio de Nash es aceptable en el sentido minmax, ya que en un equilibrio de Nash se cumple la siguiente propiedad más fuerte:

túi(s∗)=máximositúi(s−i∗,si){\displaystyle u_{i}(s^{*})=\max _{s_{i}}u_{i}(s_{-i}^{*},s_{i})}.

Pero lo contrario no es necesariamente cierto. Solan [ 5 ] y Flesch y Solan [ 6 ] demostraron la existencia general de perfiles aceptables para el criterio Minmax en juegos estocásticos. Esto contrasta con los equilibrios de Nash, cuya existencia general se desconoce.

Otros conceptos de equilibrio

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

Juegos bayesianos estocásticos

Los juegos estocásticos se han combinado con juegos bayesianos para modelar la incertidumbre sobre las estrategias de los jugadores. [ 7 ] 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 .

Detener los juegos

EB Dynkin [ 8 ] presentó el siguiente problema en teoría de juegos relacionado con la detención de procesos estocásticos. Supongamos queFnorte,norte=0,1,…{\displaystyle {\mathcal {F}}_{n},n=0,1,\ldots }, sea una secuencia creciente de σ-álgebras en algún espacio de probabilidad(Ω,F,PAG){\displaystyle (\Omega ,{\mathcal {F}},{\mathbf {P} })}, dóndeF{\displaystyle {\mathcal {F}}}contiene todo elFnorte{\displaystyle {\mathcal {F}}_{n}}Dos jugadores observan secuencias estocásticas.{incógnitanorte}norte=1∞{\displaystyle \{X_{n}\}_{n=1}^{\infty }},{Φnorte}norte=1∞{\displaystyle \{\varPhi _{n}\}_{n=1}^{\infty }}, es decir, funciones medibles con respecto a{Fnorte}norte=0∞{\displaystyle \{{\mathcal {F}}_{n}\}_{n=0}^{\infty }}. Un juego puede ser detenido en el tiempo n por el primer jugador siΦnorte≥0{\displaystyle \varPhi _{n}\geq 0}y por el segundo jugador siΦnorte<0{\displaystyle \varPhi _{n}<0}. Si el juego se detiene en el tiempo n, entonces el primer jugador recibe del segundo jugadorincógnitanorte{\displaystyle x_{n}}El jugador 1 busca maximizar la ganancia esperada, y el jugador 2 busca minimizarla.

Dejarτ{\displaystyle \tau }sea ​​el tiempo de Markov con respecto a la filtración{Fnorte}norte=0∞{\displaystyle \{{\mathcal {F}}_{n}\}_{n=0}^{\infty }}yχA{\displaystyle \chi _{A}}ser la función característica del eventoA{\displaystyle A}. DenotarT{\displaystyle {\mathcal {T}}}el conjunto de todos los tiempos de parada con respecto a la filtración{Fnorte}norte=0∞{\displaystyle \{{\mathcal {F}}_{n}\}_{n=0}^{\infty }},Λ={λ=τχΦτ⩾0,τ∈T}{\textstyle \Lambda =\{\lambda =\tau \chi _{\varPhi _{\tau }\geqslant 0},\tau \in {\mathcal {T}}\}}, yMETRO={μ=τχΦτ<0,τ∈T}{\textstyle \mathrm {M} =\{\mu =\tau \chi _{\varPhi _{\tau }<0},\tau \in {\mathcal {T}}\}}. Dejarλ{\displaystyle \lambda }sea ​​el tiempo de parada seleccionado por el primero (μ{\displaystyle \mu }respectivamente, por el segundo jugador. La recompensa, el pago del segundo jugador al primero, se define entoncesR(λ,μ)=miincógnitaλ∧μ{\displaystyle R(\lambda ,\mu )={\mathbf {E} }X_{\lambda \land \mu }}.

Bajo la condición de quemi(sorbernorte|incógnitanorte|)<∞{\displaystyle {\mathbf {E} }(\sup _{n}|X_{n}|)<\infty }, Dynkin [ 8 ] demostró que el valor del juegov=sorberλ∈Λinfμ∈METROR(λ,μ){\displaystyle v=\sup _{\lambda \in \Lambda }\inf _{\mu \in \mathrm {M} }R(\lambda ,\mu )}existe. Construyó estrategias ε-óptimas e introdujo varias condiciones para la existencia de estrategias óptimas (para una extensión, véase Neveu [ 9 ] y Yasuda [ 10 ] ).

Aplicaciones

Los juegos estocásticos tienen aplicaciones en economía , biología evolutiva y redes informáticas. [ 11 ] [ 12 ] Son generalizaciones de juegos repetidos que corresponden al caso especial donde hay un solo estado.

Véase también

Notas

  1. ↑ Shapley, LS (1953). " Juegos estocásticos" . PNAS . 39 (10): 1095– 1100. Bibcode : 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. 1 2 Mertens, JF y Neyman, A. (1981). "Juegos estocásticos". International Journal of Game Theory . 10 (2): 53– 66. doi : 10.1007/BF01769259 . S2CID 189830419 . 
  4. 1 2 Vieille, N. (2002). «Juegos estocásticos: resultados recientes». Manual de teoría de juegos . Ámsterdam: Elsevier Science. pp. 1833–1850 . ISBN  0-444-88098-4.
  5. 1 2 Solan, Eilon (marzo de 2018). "Perfiles de estrategia aceptables en juegos estocásticos" . Games and Economic Behavior . 108 : 523–540 . arXiv : 1608.05272 . doi : 10.1016/j.geb.2017.01.011 . ISSN 0899-8256 . Archivado del original el 30 de junio de 2020. 
  6. 1 2 Flesch, János; Solan, Eilon (agosto de 2024). "Juegos estocásticos con funciones de pago generales" . Matemáticas de la investigación operativa . 49 (3): 1349– 1371. doi : 10.1287/moor.2023.1385 . ISSN 0364-765X . 
  7. ↑ Albrecht, Stefano; Crandall, Jacob; Ramamoorthy, Subramanian (2016). "Creencia y verdad en comportamientos hipotéticos". Inteligencia artificial . 235 : 63–94 . arXiv : 1507.07688 . doi : 10.1016/j.artint.2016.02.004 . S2CID 2599762 . 
  8. 1 2 Dynkin, EB (1969). "Una versión de teoría de juegos de un problema de parada óptima" (PDF) . Dokl. Akad. Nauk SSSR . 185 (1): 16– 19 – vía ru.
  9. ↑ Neveu, J. (1975). Martingalas de parámetros discretos (en francés e inglés) (Biblioteca Matemática North-Holland, vol. 10 ed.). Ámsterdam: Oxford: North-Holland Publishing Company; Nueva York: American Elsevier Publishing Company, Inc. pp. viii+236, Capítulo 3.  
  10. ↑ Yasuda, M. (1985-12-01). "Sobre una estrategia aleatoria en el problema de parada de Neveu" . Procesos estocásticos y sus aplicaciones . 21 (1): 159– 166. doi : 10.1016/0304-4149(85)90384-9 . ISSN 0304-4149 . 
  11. ↑ Juegos estocásticos restringidos en redes inalámbricas por E. Altman, K. Avratchenkov, N. Bonneau, M. Debbah, R. El-Azouzi, DSMenasche
  12. ↑ Djehiche, Boualem; Tcheukam, Alain; Tembine, Hamidou (27-09-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 . 

Lecturas adicionales

  • 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, de teoría de juegos y lógicos . Cambridge University Press. pp. 153–156 . ISBN  978-0-521-89943-7.(Adecuado para estudiantes de pregrado; resultados principales, sin demostraciones)
  • Conferencia sobre juegos estocásticos para dos jugadores impartida por Antonin Kucera.