conference paper published yes Krishnendu Chatterjee author 2E5DCA20-F248-11E8-B48F-1D18A9856A870000-0002-4561-241X Laurent Doyen author Hugo Gimbert author Thomas A Henzinger author 40876CD8-F248-11E8-B48F-1D18A9856A870000−0002−2985−7724 KrCh department ToHe department MFCS: Mathematical Foundations of Computer Science COMponent-Based Embedded Systems design Techniques project Design for Embedded Systems project 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 (players interact simultaneously); and (b) turn-based (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. 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. Springer2010Brno, Czech Republic eng 1006.067310.1007/978-3-642-15155-2_23 6281246 - 257 https://research-explorer.ista.ac.at/record/1731 K. Chatterjee, L. Doyen, H. Gimbert, and T. A. Henzinger, “Randomness for free,” presented at the MFCS: Mathematical Foundations of Computer Science, Brno, Czech Republic, 2010, vol. 6281, pp. 246–257. Chatterjee, K., Doyen, L., Gimbert, H., &#38; Henzinger, T. A. (2010). Randomness for free (Vol. 6281, pp. 246–257). Presented at the MFCS: Mathematical Foundations of Computer Science, Brno, Czech Republic: Springer. <a href="https://doi.org/10.1007/978-3-642-15155-2_23">https://doi.org/10.1007/978-3-642-15155-2_23</a> K. Chatterjee, L. Doyen, H. Gimbert, T.A. Henzinger, in:, Springer, 2010, pp. 246–257. Chatterjee, Krishnendu, et al. <i>Randomness for Free</i>. Vol. 6281, Springer, 2010, pp. 246–57, doi:<a href="https://doi.org/10.1007/978-3-642-15155-2_23">10.1007/978-3-642-15155-2_23</a>. Chatterjee K, Doyen L, Gimbert H, Henzinger TA. 2010. Randomness for free. MFCS: Mathematical Foundations of Computer Science, LNCS, vol. 6281, 246–257. Chatterjee, Krishnendu, Laurent Doyen, Hugo Gimbert, and Thomas A Henzinger. “Randomness for Free,” 6281:246–57. Springer, 2010. <a href="https://doi.org/10.1007/978-3-642-15155-2_23">https://doi.org/10.1007/978-3-642-15155-2_23</a>. Chatterjee K, Doyen L, Gimbert H, Henzinger TA. Randomness for free. In: Vol 6281. Springer; 2010:246-257. doi:<a href="https://doi.org/10.1007/978-3-642-15155-2_23">10.1007/978-3-642-15155-2_23</a> 38562018-12-11T12:05:32Z2025-09-23T10:32:00Z