Filters

20153

More filters

20193
Reset filters

Settings

Author: Elbassionix, Khaled × Author: Gurvich, Vladimir × Start date: 1990 × Publisher: Oberwolfach : Mathematisches Forschungsinstitut Oberwolfach ×

Search Results

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item
    A 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, Kazuhisa
    We 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.
  • Thumbnail Image
    Item
    A potential reduction algorithm for two-person zero-sum mean payoff stochastic games
    (Oberwolfach : Mathematisches Forschungsinstitut Oberwolfach, 2015) Borosz, Endre; Elbassionix, Khaled; Gurvich, Vladimir; Makino, Kazuhisa
    We 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.
  • Thumbnail Image
    Item
    A nested family of k-total effective rewards for positional games
    (Oberwolfach : Mathematisches Forschungsinstitut Oberwolfach, 2015) Borosz, Endre; Elbassionix, Khaled; Gurvich, Vladimir; Makino, Kazuhisa
    We 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.