En teoría de juegos , un juego estocástico , 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 se encuentra en algún estado . Los jugadores seleccionan acciones y cada jugador recibe una recompensa.eso depende del estado actual y las acciones elegidas. Luego, 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 para un jugador a menudo se considera 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 de 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). 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 "naturaleza". Entonces, una ejecución del sistema corresponde a una ruta infinita en el gráfico. Así, 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 carreras "buenas", mientras que el otro jugador (el entorno) apunta a lo contrario.
En muchos casos, existe un valor de equilibrio de esta probabilidad, pero es posible que no existan estrategias óptimas para ambos jugadores.
Introducimos conceptos básicos y preguntas algorítmicas estudiadas en esta área, y mencionamos algunos problemas abiertos de larga data. Luego, mencionamos resultados recientes seleccionados.
Teoría
Los ingredientes de un juego estocástico son: un conjunto finito de jugadores ; un espacio estatal(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 , dónde son los perfiles de acción, para , dónde es la probabilidad de que el siguiente estado esté en dado el estado actual y el perfil de acción actual ; y una función de pago de a , donde el -th coordenada de , , es la recompensa para el jugador en función del estado y el perfil de acción .
El juego comienza en algún estado inicial. . En el escenario, los jugadores primero observan , luego elige simultáneamente acciones , luego observe el perfil de acción , y luego la naturaleza selecciona según la probabilidad . Una jugada del juego estocástico,, define un flujo de recompensas , dónde .
El juego con descuento con factor de descuento () es el juego donde la recompensa para el jugador es . La-El juego de escenario es el juego donde la recompensa para el jugador es .
El valor , respectivamente , de un juego estocástico de suma cero para dos personas , respectivamente , con un número finito de estados y acciones existe, y Truman Bewley y Elon Kohlberg (1976) demostraron que converge a un límite como va al infinito y que converge al mismo límite que va a .
El juego "sin descuento" es el juego donde la recompensa para el jugador es el "límite" de los promedios de los pagos de la etapa. Se necesitan algunas precauciones para definir el valor de una suma cero para dos personas. y en la definición de pagos de equilibrio de una suma distinta de cero . El valor uniforme de un juego estocástico de suma cero para dos personas existe si para cada hay un entero positivo y un par de estrategias del jugador 1 y del jugador 2 de modo que para cada y y cada la expectativa de con respecto a la probabilidad de jugadas definida por y Por lo menos , y la expectativa de con respecto a la probabilidad de jugadas definida 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]
Si hay un número finito de jugadores y los conjuntos de acción y el conjunto de 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 la recompensa total es la suma descontada.
El juego estocástico de suma no cero tiene una recompensa de equilibrio uniforme si por cada hay un entero positivo y un perfil de estrategia tal que por 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 definida por Por lo menos , y la expectativa de con respecto a la probabilidad de jugadas definida por es como máximo . Nicolas Vieille ha demostrado que todos los juegos estocásticos de dos personas con estados finitos y espacios de acción tienen una recompensa de equilibrio uniforme. [4]
El juego estocástico de suma no cero tiene una recompensa de equilibrio promedio límite si por cada hay un perfil de estrategia tal que por 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 definida por Por lo menos , y la expectativa del límite superior de los promedios de los pagos de la etapa con respecto a la probabilidad de jugadas definida 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 Los espacios finitos de estado y acción tienen una recompensa de equilibrio promedio límite. [4] En particular, estos resultados implican que estos juegos tienen un valor y una recompensa de equilibrio aproximada, denominada recompensa de equilibrio liminf-average (respectivamente, limsup-average), cuando la recompensa total es el límite inferior (o el límite superior) ) de los promedios de los pagos de la etapa.
Si cada 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 liminf, es una cuestión abierta 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 los juegos bayesianos para modelar la incertidumbre sobre las estrategias de los jugadores. [5] El modelo de "juego estocástico bayesiano" resultante se resuelve mediante una combinación recursiva de la ecuación de equilibrio bayesiano de Nash y la ecuación de optimalidad de Bellman .
Aplicaciones
Los juegos estocásticos tienen aplicaciones en economía , biología evolutiva y redes informáticas. [6] [7] Son generalizaciones de juegos repetidos que corresponden al caso especial donde solo hay un estado.
Ver también
Notas
- ^ 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 .
- ^ Solan, Eilon; Vieille, Nicolas (2015). "Juegos estocásticos" . PNAS . 112 (45): 13743-13746. doi : 10.1073 / pnas.1513508112 . PMC 4653174 . PMID 26556883 .
- ^ a b 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 .
- ^ a b Vieille, N. (2002). "Juegos estocásticos: resultados recientes". Manual de teoría de juegos . Ámsterdam: Elsevier Science. págs. 1833–1850. ISBN 0-444-88098-4.
- ^ 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 .
- ^ Juegos estocásticos restringidos en redes inalámbricas por E.Altman, K.Avratchenkov, N.Bonneau, M.Debbah, R.El-Azouzi, DSMenasche
- ^ Djehiche, Boualem; Tcheukam, Alain; Tembine, Hamidou (27 de septiembre de 2017). "Juegos de tipo campo medio en ingeniería". OBJETIVOS Electrónica e Ingeniería Eléctrica . 1 : 18–73. arXiv : 1605.03281 . doi : 10.3934 / ElectrEng.2017.1.18 . S2CID 16055840 .
Otras lecturas
- 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 y aplicaciones estocásticos . Dordrecht: Kluwer Academic Press. ISBN 1-4020-1492-9.
- Yoav Shoham; Kevin Leyton-Brown (2009). Sistemas multiagente: bases algorítmicas, teóricas de juegos y lógicas . Prensa de la Universidad de Cambridge. 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 a cargo de Antonin Kucera