首页    期刊浏览 2024年09月14日 星期六
登录注册

文章基本信息

  • 标题:Solving Simple Stochastic Games with Few Random Vertices
  • 本地全文:下载
  • 作者:Hugo Gimbert ; Florian Horn
  • 期刊名称:Logical Methods in Computer Science
  • 印刷版ISSN:1860-5974
  • 电子版ISSN:1860-5974
  • 出版年度:2009
  • 卷号:5
  • 期号:02
  • DOI:10.2168/LMCS-5(2:9)2009
  • 出版社:Technical University of Braunschweig
  • 摘要:

    Simple stochastic games are two-player zero-sum stochastic games with turn-based moves, perfect information, and reachability winning conditions. We present two new algorithms computing the values of simple stochastic games. Both of them rely on the existence of optimal permutation strategies, a class of positional strategies derived from permutations of the random vertices. The "permutation-enumeration" algorithm performs an exhaustive search among these strategies, while the "permutation-improvement" algorithm is based on successive improvements, à la Hoffman-Karp. Our algorithms improve previously known algorithms in several aspects. First they run in polynomial time when the number of random vertices is fixed, so the problem of solving simple stochastic games is fixed-parameter tractable when the parameter is the number of random vertices. Furthermore, our algorithms do not require the input game to be transformed into a stopping game. Finally, the permutation-enumeration algorithm does not use linear programming, while the permutation-improvement algorithm may run in polynomial time.

  • 关键词:Stochastic Games;Perfect Information;Linear Programming;Polynomial Time;Permutations
国家哲学社会科学文献中心版权所有