Files:
Abstract:
Shapley's stochastic games and Everett's recursive games are classical models of game theory describing two-player zero-sum games of potentially infinite duration. In this paper we describe algorithms for exactly solving these games. As the values of both kinds of games may be irrational numbers, our algorithms output the value of the game given as input in isolating interval representation. When the number of positions of the game is constant, our algorithms run in polynomial time and are the first algorithms with this property. As a byproduct, we give new improved upper and lower bounds on the algebraic degree of the values of stochastic and recursive games as a function of the combinatorial parameters of the game. As another byproduct, we give a new upper bound on the complexity of the strategy iteration algorithm for concurrent reachability games, a well-studied special case of recursive games. This upper bound is exponential even when the number of positions is constant, but prior to this paper only a doubly exponential upper bound on the complexity of strategy iteration was known, even for this case.
BibTeX:
@InProceedings{hklmt-stoc-2011,
author = {Kristoffer Arnsfelt Hansen and Michal Koucky and
Niels Lauritzen and Peter Bro Miltersen and Elias~P.
Tsigaridas},
title = {Exact algorithms for solving stochastic games},
booktitle = STOC_2011,
year = 2011,
abstract = "Shapley's stochastic games and Everett's recursive
games are classical models of game theory describing
two-player zero-sum games of potentially infinite
duration. In this paper we describe algorithms for
exactly solving these games. As the values of both
kinds of games may be irrational numbers, our
algorithms output the value of the game given as
input in isolating interval representation. When the
number of positions of the game is constant, our
algorithms run in polynomial time and are the first
algorithms with this property. As a byproduct, we
give new improved upper and lower bounds on the
algebraic degree of the values of stochastic and
recursive games as a function of the combinatorial
parameters of the game. As another byproduct, we
give a new upper bound on the complexity of the
strategy iteration algorithm for concurrent
reachability games, a well-studied special case of
recursive games. This upper bound is exponential
even when the number of positions is constant, but
prior to this paper only a doubly exponential upper
bound on the complexity of strategy iteration was
known, even for this case.",
}
Generated by bib2html.pl (written by Patrick Riley , modified by Elias ) on Wed Oct 23, 2019 21:41:02