Geodesic
Stochastic games on Markov processes with final sequence of states
Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica, no. 1 (2017), pp. 77-94 
Alexandru Lazari. Stochastic games on Markov processes with final sequence of states. Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica, no. 1 (2017), pp. 77-94. http://geodesic.mathdoc.fr/item/BASM_2017_1_a7/
@article{BASM_2017_1_a7,
     author = {Alexandru Lazari},
     title = {Stochastic games on {Markov} processes with final sequence of states},
     journal = {Buletinul Academiei de \c{S}tiin\c{t}e a Republicii Moldova. Matematica},
     pages = {77--94},
     year = {2017},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/BASM_2017_1_a7/}
}
TY  - JOUR
AU  - Alexandru Lazari
TI  - Stochastic games on Markov processes with final sequence of states
JO  - Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica
PY  - 2017
SP  - 77
EP  - 94
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/BASM_2017_1_a7/
LA  - en
ID  - BASM_2017_1_a7
ER  - 
%0 Journal Article
%A Alexandru Lazari
%T Stochastic games on Markov processes with final sequence of states
%J Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica
%D 2017
%P 77-94
%N 1
%U http://geodesic.mathdoc.fr/item/BASM_2017_1_a7/
%G en
%F BASM_2017_1_a7

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper a class of stochastic games, defined on Markov processes with final sequence of states, is investigated. In these games each player, knowing the initial distribution of the states, defines his stationary strategy, represented by one proper transition matrix. The game is started by first player and, at every discrete moment of time, the stochastic system passes to the next state according to the strategy of the current player. After the last player, the first player acts on the system evolution and the game continues in this way until, for the first time, the given final sequence of states is achieved. The player who acts the last on the system evolution is considered the winner of the game. In this paper we prove that the distribution of the game duration is a homogeneous linear recurrence and we determine the initial state and the generating vector of this recurrence. Based on these results, we develop polynomial algorithms for determining the main probabilistic characteristics of the game duration and the win probabilities of players. Also, using the signomial and geometric programming approaches, the optimal cooperative strategies that minimize the expectation of the game duration are determined.

[1] Lazari A., “Evolution Time of Composed Stochastic Systems with Final Sequence of States and Independent Transitions”, An. Ştiinţ. Univ. Al. I. Cuza Iaşi. Mat. (N.S.), 62:1 (2016), 257–274 | Zbl

[2] Lazari A., Lozovanu D., Capcelea M., Dynamical deterministic and stochastic systems: Evolution, optimization and discrete optimal control, CEP USM, Chişinău, 2015, 310 pp. (in Romanian)

[3] Lazari A., “Determining the Distribution of the Duration of Stationary Games for Zero-Order Markov Processes with Final Sequence of States”, Bul. Acad. Ştiinţe Repub. Mold. Mat., 2015, no. 3(79), 72–78 | MR | Zbl

[4] Lazari A., “Determining the Optimal Evolution Time for Markov Processes with Final Sequence of States”, Bul. Acad. Ştiinţe Repub. Mold. Mat., 2015, no. 1(77), 115–126 | MR | Zbl

[5] Lazari A., “Optimization of Zero-Order Markov Processes with Final Sequence of States”, Universal Journal of Applied Mathematics, 1:3 (2013), 198–206

[6] Lazari A., “Compositions of stochastic systems with final sequence states and interdependent transitions”, Ann. Univ. Buchar. Math. Ser., 4(LXII):1 (2013), 289–303 | MR | Zbl

[7] Lazari A., “Algorithms for Determining the Transient and Differential Matrices in Finite Markov Processes”, Bul. Acad. Ştiinţe Repub. Mold. Mat., 2010, no. 2(63), 84–99 | MR | Zbl

[8] Boyd S., Kim S., Vandenberghe L., Hassibi A., “A tutorial on geometric programming”, Optim. Eng., 8 (2007), 67–127 | DOI | MR | Zbl

[9] Zbaganu G., “Waiting for an ape to type a poem”, Bul. Acad. Ştiinţe Repub. Mold. Mat., 1992, no. 2(8), 66–74 | MR | Zbl

[10] Guibas Leo J., Odlyzko Andrew M., “Periods in Strings”, J. Combin. Theory Ser. A, 30 (1981), 19–42 | DOI | MR | Zbl