Nash \(\epsilon\)-equilibria for stochastic games with total reward functions: an approach through Markov decision processes. (English) Zbl 1449.91018

González-Padilla, Francisco J.; Montes-de-Oca, Raúl

Kybernetika 55, No. 1, 152-165 (2019).

Summary: The main objective of this paper is to find structural conditions under which a stochastic game between two players with total reward functions has an \(\epsilon\)-equilibrium. To reach this goal, the results of Markov decision processes are used to find \(\epsilon\)-optimal strategies for each player and then the correspondence of a better answer as well as a more general version of Kakutani’s fixed point theorem to obtain the \(\epsilon\)-equilibrium mentioned. Moreover, two examples to illustrate the theory developed are presented.

MSC:

91A15	Stochastic games, stochastic differential games
91A05	2-person games
90C40	Markov and semi-Markov decision processes

Keywords:

stochastic games; Nash equilibrium; Markov decision processes; total rewards

References:

[1]	Aliprantis, C. D.; Border, K. C., Infinite Dimensional Analysis., Springer 2006
[2]	Ash, R. B., Real Analysis and Probability., Academic Press, New York 1972
[3]	Bartle, R., The Elements of Real Analysis., John Wiley and Sons, Inc. 1964
[4]	Cavazos-Cadena, R.; Montes-de-Oca, R., Optimal and nearly optimal policies in Markov decision chains with nonnegative rewards and risk-sensitive expected total-reward criterion., In: Markov Processes and Controlled Markov Chains 2002 (Z. Hou, J. A. Filar and A. Chen, eds.), Kluwer Academic Publishers, pp. 189-221
[5]	Filar, J.; Vrieze, K., Competitive Markov Decision Processes., Springer-Verlag, New York 1997
[6]	Habil, E. D., Double sequences and double series., The Islamic Univ. J., Series of Natural Studies and Engineering 14 (2006), 1-32. (This reference is available at the Islamic University Journal’s site: http://journal.iugaza.edu.ps/index.php/IUGNS/article/view/1594/1525.)
[7]	Hernández-Lerma, O.; Lasserre, J. B., Discrete-Time Markov Control Processes: Basic Optimality Criteria., Springer-Verlag, New York 1996
[8]	Hordijk, A., Dynamic Programming and Markov Potential Theory., Mathematical Centre Tracts 51, Amsterdam 1974
[9]	Jaśkiewicz, A.; Nowak, A. S., Stochastic games with unbounded payoffs: Applications to robust control in Economics., Dyn. Games Appl. 1 (2011), 2, 253-279
[10]	Kakutani, S., A generalization of Brouwer’s fixed point theorem., Duke Math. J. 8 (1942), 457-459
[11]	Kelley, J. L., General Topology., Springer, New York 1955
[12]	Köthe, G., Topological Vector Spaces I., Springer-Verlag, 1969
[13]	Puterman, M., Markov Decision Processes., John Wiley and Sons, Inc. New Jersey 1994
[14]	Shapley, L. S., Stochastic games., Proc. Nat. Acad. Sci. U. S. A. 39 (1953), 1095-1100
[15]	Thuijsman, F., Optimality and Equilibria in Stochastic Games., CW1 Tract-82, Amsterdam 1992
[16]	Zeidler, E., Nonlinear Functional Analysis and its Applications., Springer-Verlag, New York Inc. 1988