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 ; Un espacio de estados , (Ya sea un conjunto finito o un espacio medible , un conjunto de jugadores , Un conjunto de acciones (Ya sea un conjunto finito o un espacio medible ); una transición de probabilidad , donde son los perfiles de acción a , donde es la probabilidad de que el siguiente estado este en , dado el estado actual es y el perfil de acción actual es .
El juego comienza en un estado inicial . En la etapa , Los jugadores primero observan , a continuación, elija simultáneamente acciones , posteriormente observe el perfil de acción , en donde la naturaleza selecciona de acuerdo a la probabilidad . Una jugada del partido estocástico, , Define una corriente de pagos , en donde .
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)