Filters

2010 - 20155

More filters

20195
Reset filters

Settings

Author: Gurvich, Vladimir × End date: 2019 × Start date: 2010 × Publisher: Oberwolfach : Mathematisches Forschungsinstitut Oberwolfach ×

Search Results

Now showing 1 - 5 of 5
  • 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.
  • Thumbnail Image
    Item
    Stochastic mean payoff games: Smoothed analysis and approximation schemes
    (Oberwolfach : Mathematisches Forschungsinstitut Oberwolfach, 2010) Boros, Endre; Elbassioni, Khaled; Fouz, Mahmoud; Gurvich, Vladimir; Makino, Kazuhisa; Manthey, Bodo
    We consider two-person zero-sum stochastic mean payoff games with perfect information modeled by a digraph with black, white, and random vertices. These BWR-games games are polynomially equivalent with the classical Gillette games, which include many well-known subclasses, such as cyclic games, simple stochastic games, stochastic parity games, and Markov decision processes. They can also be used to model parlor games such as Chess or Backgammon. It is a long-standing open question whether a polynomial algorithm exists that solves BWR-games. In fact, a pseudo-polynomial algorithm for these games with an arbitrary number of random nodes would already imply their polynomial solvability. Currently, only two classes are known to have such a pseudo-polynomial algorithm: BW-games (the case with no random nodes) and ergodic BWR-games (i.e., in which the game's value does not depend on the initial position) with constant number of random nodes. In this paper, we show that the existence of a pseudo-polynomial algorithm for BWR-games with constant number of random vertices implies smoothed polynomial time complexity and the existence of absolute and relative polynomial-time approximation schemes. In particular, we obtain smoothed polynomial time complexity and derive absolute and relative approximation schemes for the above two classes.
  • 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
    On canonical forms for two-person zero-sum limit average payoff stochastic games
    (Oberwolfach : Mathematisches Forschungsinstitut Oberwolfach, 2011) Boros, Endre; Elbassioni, Khaled; Gurvich, Vladimir; Makino, Kazuhisa
    We 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.
  • 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.