How do we remember the past in randomised strategies?

J. Cristau, C. David, F. Horn, in:, Proceedings of GandALF 2010, Open Publishing Association, 2010, pp. 30–39.


Conference Paper | Published | English
Author
; ;
Department
Series Title
EPTCS
Abstract
Graph games of infinite length are a natural model for open reactive processes: one player represents the controller, trying to ensure a given specification, and the other represents a hostile environment. The evolution of the system depends on the decisions of both players, supplemented by chance. In this work, we focus on the notion of randomised strategy. More specifically, we show that three natural definitions may lead to very different results: in the most general cases, an almost-surely winning situation may become almost-surely losing if the player is only allowed to use a weaker notion of strategy. In more reasonable settings, translations exist, but they require infinite memory, even in simple cases. Finally, some traditional problems becomes undecidable for the strongest type of strategies.
Publishing Year
Date Published
2010-06-09
Proceedings Title
Proceedings of GandALF 2010
Volume
25
Page
30 - 39
Conference
GandALF: Games, Automata, Logic, and Formal Verification
Conference Location
Minori, Amalfi Coast, Italy
Conference Date
2010-06-17 – 2010-06-18
IST-REx-ID

Cite this

Cristau J, David C, Horn F. How do we remember the past in randomised strategies? . In: Proceedings of GandALF 2010. Vol 25. Open Publishing Association; 2010:30-39. doi:10.4204/EPTCS.25.7
Cristau, J., David, C., & Horn, F. (2010). How do we remember the past in randomised strategies? . In Proceedings of GandALF 2010 (Vol. 25, pp. 30–39). Minori, Amalfi Coast, Italy: Open Publishing Association. https://doi.org/10.4204/EPTCS.25.7
Cristau, Julien, Claire David, and Florian Horn. “How Do We Remember the Past in Randomised Strategies? .” In Proceedings of GandALF 2010, 25:30–39. Open Publishing Association, 2010. https://doi.org/10.4204/EPTCS.25.7.
J. Cristau, C. David, and F. Horn, “How do we remember the past in randomised strategies? ,” in Proceedings of GandALF 2010, Minori, Amalfi Coast, Italy, 2010, vol. 25, pp. 30–39.
Cristau J, David C, Horn F. 2010. How do we remember the past in randomised strategies? . Proceedings of GandALF 2010. GandALF: Games, Automata, Logic, and Formal Verification, EPTCS, vol. 25. 30–39.
Cristau, Julien, et al. “How Do We Remember the Past in Randomised Strategies? .” Proceedings of GandALF 2010, vol. 25, Open Publishing Association, 2010, pp. 30–39, doi:10.4204/EPTCS.25.7.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar