Exact algorithms for solving stochastic games

0369977 - MÚ 2012 RIV US eng C - Conference Paper (international conference)
Hansen, A. K. - Koucký, Michal - Lauritzen, N. - Miltersen, P.B. - Tsigaridas, E.P.
Exact algorithms for solving stochastic games.
Proceedings of the 43rd annual ACM Symposium on Theory of Computing (STOC 2011). New York: ACM, 2011 - (Fortnow, L.; Vadhan, S.), s. 205-214. ISBN 978-1-4503-0691-1.
[43rd annual ACM symposium on Theory of computing (STOC 2011). San José (US), 06.06.2011-08.06.2011]
R&D Projects: GA ČR GAP202/10/0854; GA AV ČR IAA100190902
Institutional research plan: CEZ:AV0Z10190503
Keywords : stochastic games * recursive games * algorithms
Subject RIV: BA - General Mathematics
http://dl.acm.org/citation.cfm?doid=1993636.1993665

Shapley's discounted stochastic games, Everett's recursive games and Gillette's undiscounted stochastic games are classical models of game theory describing two-player zero-sum games of potentially infinite duration. We describe algorithms for exactly solving these games. When the number of positions of the game is constant, our algorithms run in polynomial time.
Permanent Link: http://hdl.handle.net/11104/0203909