Randomness for free

K. Chatterjee, L. Doyen, H. Gimbert, T.A. Henzinger, Information and Computation 245 (2015) 3–16.


Journal Article | Published | English
Author
Abstract
We consider two-player zero-sum games on graphs. These games can be classified on the basis of the information of the players and on the mode of interaction between them. On the basis of information the classification is as follows: (a) partial-observation (both players have partial view of the game); (b) one-sided complete-observation (one player has complete observation); and (c) complete-observation (both players have complete view of the game). On the basis of mode of interaction we have the following classification: (a) concurrent (both players interact simultaneously); and (b) turn-based (both players interact in turn). The two sources of randomness in these games are randomness in transition function and randomness in strategies. In general, randomized strategies are more powerful than deterministic strategies, and randomness in transitions gives more general classes of games. In this work we present a complete characterization for the classes of games where randomness is not helpful in: (a) the transition function probabilistic transition can be simulated by deterministic transition); and (b) strategies (pure strategies are as powerful as randomized strategies). As consequence of our characterization we obtain new undecidability results for these games.
Publishing Year
Date Published
2015-12-01
Journal Title
Information and Computation
Volume
245
Issue
12
Page
3 - 16
IST-REx-ID

Cite this

Chatterjee K, Doyen L, Gimbert H, Henzinger TA. Randomness for free. Information and Computation. 2015;245(12):3-16. doi:10.1016/j.ic.2015.06.003
Chatterjee, K., Doyen, L., Gimbert, H., & Henzinger, T. A. (2015). Randomness for free. Information and Computation, 245(12), 3–16. https://doi.org/10.1016/j.ic.2015.06.003
Chatterjee, Krishnendu, Laurent Doyen, Hugo Gimbert, and Thomas A Henzinger. “Randomness for Free.” Information and Computation 245, no. 12 (2015): 3–16. https://doi.org/10.1016/j.ic.2015.06.003.
K. Chatterjee, L. Doyen, H. Gimbert, and T. A. Henzinger, “Randomness for free,” Information and Computation, vol. 245, no. 12, pp. 3–16, 2015.
Chatterjee K, Doyen L, Gimbert H, Henzinger TA. 2015. Randomness for free. Information and Computation. 245(12), 3–16.
Chatterjee, Krishnendu, et al. “Randomness for Free.” Information and Computation, vol. 245, no. 12, Elsevier, 2015, pp. 3–16, doi:10.1016/j.ic.2015.06.003.

Link(s) to Main File(s)
Access Level
OA Open Access
Material in IST:
Earlier Version

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar