Discounting and averaging in games across time scales

K. Chatterjee, R. Majumdar, International Journal of Foundations of Computer Science 23 (2012) 609–625.

Download
No fulltext has been uploaded. References only!

Journal Article | Published | English
Author
;
Department
Abstract
We introduce two-level discounted and mean-payoff games played by two players on a perfect-information stochastic game graph. The upper level game is a discounted or mean-payoff game and the lower level game is a (undiscounted) reachability game. Two-level games model hierarchical and sequential decision making under uncertainty across different time scales. For both discounted and mean-payoff two-level games, we show the existence of pure memoryless optimal strategies for both players and an ordered field property. We show that if there is only one player (Markov decision processes), then the values can be computed in polynomial time. It follows that whether the value of a player is equal to a given rational constant in two-level discounted or mean-payoff games can be decided in NP ∩ coNP. We also give an alternate strategy improvement algorithm to compute the value. © 2012 World Scientific Publishing Company.
Publishing Year
Date Published
2012-04-01
Journal Title
International Journal of Foundations of Computer Science
Volume
23
Issue
3
Page
609 - 625
IST-REx-ID

Cite this

Chatterjee K, Majumdar R. Discounting and averaging in games across time scales. International Journal of Foundations of Computer Science. 2012;23(3):609-625. doi:10.1142/S0129054112400308
Chatterjee, K., & Majumdar, R. (2012). Discounting and averaging in games across time scales. International Journal of Foundations of Computer Science, 23(3), 609–625. https://doi.org/10.1142/S0129054112400308
Chatterjee, Krishnendu, and Ritankar Majumdar. “Discounting and Averaging in Games across Time Scales.” International Journal of Foundations of Computer Science 23, no. 3 (2012): 609–25. https://doi.org/10.1142/S0129054112400308.
K. Chatterjee and R. Majumdar, “Discounting and averaging in games across time scales,” International Journal of Foundations of Computer Science, vol. 23, no. 3, pp. 609–625, 2012.
Chatterjee K, Majumdar R. 2012. Discounting and averaging in games across time scales. International Journal of Foundations of Computer Science. 23(3), 609–625.
Chatterjee, Krishnendu, and Ritankar Majumdar. “Discounting and Averaging in Games across Time Scales.” International Journal of Foundations of Computer Science, vol. 23, no. 3, World Scientific Publishing, 2012, pp. 609–25, doi:10.1142/S0129054112400308.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar