|
Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica, 2017, Number 1, Pages 77–94
(Mi basm435)
|
|
|
|
Stochastic games on Markov processes with final sequence of states
Alexandru Lazari Moldova State University, 60 Mateevici str., Chişinău, Republic of Moldova, MD–2009
Abstract:
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.
Keywords and phrases:
Markov process, final sequence of states, game duration, win probability, homogeneous linear recurrence, generating function.
Received: 24.10.2016
Citation:
Alexandru Lazari, “Stochastic games on Markov processes with final sequence of states”, Bul. Acad. Ştiinţe Repub. Mold. Mat., 2017, no. 1, 77–94
Linking options:
https://www.mathnet.ru/eng/basm435 https://www.mathnet.ru/eng/basm/y2017/i1/p77
|
Statistics & downloads: |
Abstract page: | 173 | Full-text PDF : | 33 | References: | 27 |
|