Authors: Alexandru Lazari
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 stra\-tegy 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.
Moldova State University,
60 Mateevici str., Chi¸ sin˘ au,
Republic of Moldova, MD−2009.
E-mail:
Fulltext

–
0.23 Mb