4 results
Search Results
Now showing 1 - 4 of 4
- ItemA potential reduction algorithm for two-person zero-sum mean payoff stochastic games(Oberwolfach : Mathematisches Forschungsinstitut Oberwolfach, 2015) Borosz, Endre; Elbassionix, Khaled; Gurvich, Vladimir; Makino, KazuhisaWe suggest a new algorithm for two-person zero-sum undiscounted stochastic games focusing on stationary strategies. Given a positive real , let us call a stochastic game -ergodic, if its values from any two initial positions dier by at most . The proposed new algorithm outputs for every > 0 in nite time either a pair of stationary strategies for the two players guaranteeing that the values from any initial positions are within an -range, or identies two initial positions u and v and corresponding stationary strategies for the players proving that the game values starting from u and v are at least =24 apart. In particular, the above result shows that if a stochastic game is -ergodic, then there are stationary strategies for the players proving 24-ergodicity. This result strengthens and provides a constructive version of an existential result by Vrieze (1980) claiming that if a stochastic game is 0-ergodic, then there are -optimal stationary strategies for every > 0. The suggested algorithm is based on a potential transformation technique that changes the range of local values at all positions without changing the normal form of the game.
- ItemOn canonical forms for two-person zero-sum limit average payoff stochastic games(Oberwolfach : Mathematisches Forschungsinstitut Oberwolfach, 2011) Boros, Endre; Elbassioni, Khaled; Gurvich, Vladimir; Makino, KazuhisaWe consider two-person zero-sum mean payoff undiscounted stochastic games. We give a sufficient condition for the existence of a saddle point in uniformly optimal stationary strategies. Namely, we obtain sufficient conditions that enable us to to bring the game, by applying potential transformations to a canonical form in which locally optimal strategies are globally optimal, and hence the value for every initial position and the optimal strategies of both players can be obtained by playing the local game at each state. We show that this condition is satisfied by the class of additive transition games, that is, the special case when the transitions at each state can be decomposed into two parts, each controlled completely by one of the two players. An important special case of additive games is the so-called BWR-games which are played by two players on a directed graph with positions of three types: Black, White and Random. We given an independent proof for the existence of canonical form in such games, and use this to derive the existence of canonical form (and hence of a saddle point in uniformly optimal stationary strategies) in a wide class of games, which includes stochastic games with perfect information, switching controller games and additive rewards, additive transition games.
- ItemA nested family of k-total effective rewards for positional games(Oberwolfach : Mathematisches Forschungsinstitut Oberwolfach, 2015) Borosz, Endre; Elbassionix, Khaled; Gurvich, Vladimir; Makino, KazuhisaWe consider Gillette's two-person zero-sum stochastic games with perfect information. For each k 2 Z+ we introduce an effective reward function, called k-total. For k = 0 and 1 this function is known as mean payoff and total reward, respectively. We restrict our attention to the deterministic case. For all k, we prove the existence of a saddle point which can be realized by uniformly optimal pure stationary strategies. We also demonstrate that k-total reward games can be embedded into (k+1)-total reward games.
- ItemA pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions(Oberwolfach : Mathematisches Forschungsinstitut Oberwolfach, 2015) Borosz, Endre; Elbassionix, Khaled; Gurvich, Vladimir; Makino, KazuhisaWe consider two-person zero-sum stochastic mean payoff games with perfect information, or BWR-games, given by a digraph G = (V;E), with local rewards r : E Z, and three types of positions: black VB, white VW, and random VR forming a partition of V . It is a long- standing open question whether a polynomial time algorithm for BWR-games exists, or not, even when |VR| = 0. In fact, a pseudo-polynomial algorithm for BWR-games would already imply their polynomial solvability. In this paper, we show that BWR-games with a constant number of random positions can be solved in pseudo-polynomial time. More precisely, in any BWR-game with |VR| = O(1), a saddle point in uniformly optimal pure stationary strategies can be found in time polynomial in |VW| + |VB|, the maximum absolute local reward, and the common denominator of the transition probabilities.