Juego estocástico

En la teoría de juegos, un juego estocástico, introducido por Lloyd Shapley a principios de 1950, es un juego dinámico 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 del juego se está en algún estado. Los jugadores eligen acciones y cada jugador recibe un pago que depende del estado actual y las acciones elegidas. El juego se mueve a un nuevo estado aleatoriamente cuya distribución depende del estado previo y las acciones elegidas por los jugadores. El procedimiento se repite en el nuevo estado y el juego continúa por un número finito o infinito de etapas. El pago total a un jugador se toma a menudo como la suma descontada de los pagos etapa por etapa o el límite inferior de los promedios de las rentabilidades de cada etapa.

Los juegos estocásticos generalizan tanto los procesos de decisión de Markov y los juegos repetidos.

Teoría

Los ingredientes de un juego estocástico son: un conjunto finito de jugadores ${\displaystyle I}$; Un espacio de estados ${\displaystyle M}$, (Ya sea un conjunto finito o un espacio medible ${\displaystyle (M,{\mathcal {A}})}$, un conjunto de jugadores ${\displaystyle i\in I}$, Un conjunto de acciones ${\displaystyle S^{i}}$ (Ya sea un conjunto finito o un espacio medible ${\displaystyle (S^{i},{\mathcal {S}}^{i})}$); una transición de probabilidad ${\displaystyle M\times S}$, donde ${\displaystyle S=\times _{i\in I}S^{i}}$ son los perfiles de acción a ${\displaystyle M}$, donde ${\displaystyle P(A\mid m,s)}$ es la probabilidad de que el siguiente estado este en ${\displaystyle A}$, dado el estado actual es ${\displaystyle m}$ y el perfil de acción actual es ${\displaystyle s}$.

El juego comienza en un estado inicial ${\displaystyle m_{1}}$. En la etapa ${\displaystyle t}$, Los jugadores primero observan ${\displaystyle m_{t}}$, a continuación, elija simultáneamente acciones ${\displaystyle s_{t}^{i}\in S^{i}}$, posteriormente observe el perfil de acción ${\displaystyle s_{t}=(s_{t}^{i})_{i}}$ , en donde la naturaleza selecciona ${\displaystyle m_{t+1}}$ de acuerdo a la probabilidad ${\displaystyle P(\cdot \mid m_{t},s_{t})}$. Una jugada del partido estocástico, ${\displaystyle m_{1},s_{1},\ldots ,m_{t},s_{t},\ldots }$, Define una corriente de pagos ${\displaystyle g_{1},g_{2},\ldots }$, en donde ${\displaystyle g_{t}=g(m_{t},s_{t})}$.

Lecturas adicionales

• Condon, A. (1992). «The complexity of stochastic games». Information and Computation 96: 203-224. doi:10.1016/0890-5401(92)90048-K. 
• H. Everett (1957). «Recursive games». En Melvin Dresher, Albert William Tucker, Philip Wolfe, ed. Contributions to the Theory of Games, Volume 3. Annals of Mathematics Studies. Princeton University Press. pp. 67-78. ISBN 978-0-691-07936-3. (Reprinted in Harold W. Kuhn, ed. Classics in Game Theory, Princeton University Press, 1997. ISBN 978-0-691-01192-9). 
• Filar, J. & Vrieze, K. (1997). Competitive Markov Decision Processes. Springer-Verlag. ISBN 0-387-94805-8. 
• Mertens, J. F. & Neyman, A. (1981). «Stochastic Games». International Journal of Game Theory 10 (2): 53-66. doi:10.1007/BF01769259. 
• Neyman, A. & Sorin, S. (2003). Stochastic Games and Applications. Dordrecht: Kluwer Academic Press. ISBN 1-4020-1492-9. 
• Shapley, L. S. (1953). «Stochastic games». PNAS 39 (10): 1095-1100. doi:10.1073/pnas.39.10.1095. 
• Vieille, N. (2002). «Stochastic games: Recent results». Handbook of Game Theory. Amsterdam: Elsevier Science. pp. 1833-1850. ISBN 0-444-88098-4. 
• Yoav Shoham; Kevin Leyton-Brown (2009). Multiagent systems: algorithmic, game-theoretic, and logical foundations. Cambridge University Press. pp. 153–156. ISBN 978-0-521-89943-7.  (suitable for undergraduates; main results, no proofs)