Stochastic Limit-Average Games are in EXPTIME

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

The value of a finite-state two-player zero-sum stochastic game with limit-average payoff can be approximated to within $ε$ in time exponential in a polynomial in the size of the game times polynomial in logarithmic in $\frac{1}ε$, for all $ε>0$.
15 Pages

Keywords

Computer Science and Game Theory

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/212606

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0805.2622
 http://arxiv.org/abs/0805.2622

Collections

arXiv