×

Randomness for free. (English) Zbl 1333.91008

Summary: We consider two-player zero-sum games on finite-state 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 the transition function and randomness in the strategies. In general, randomized strategies are more powerful than deterministic strategies, and probabilistic transitions give 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 transitions can be simulated by deterministic transitions); and (b) strategies (pure strategies are as powerful as randomized strategies). As a consequence of our characterization we obtain new undecidability results for these games.

MSC:

91A43 Games involving graphs
68Q60 Specification and verification (program logics, model checking, etc.)
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
91A05 2-person games
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alur, R.; Henzinger, T. A.; Kupferman, O., Alternating-time temporal logic, J. ACM, 49, 672-713 (2002) · Zbl 1326.68181
[2] Baier, C.; Bertrand, N.; Größer, M., On decision problems for probabilistic Büchi automata, (FoSSaCS. FoSSaCS, Lect. Notes Comput. Sci., vol. 4962 (2008), Springer), 287-301 · Zbl 1139.68030
[3] Bertrand, N.; Genest, B.; Gimbert, H., Qualitative determinacy and decidability of stochastic games with signals, (Proc. of LICS (2009), IEEE Computer Society), 319-328
[4] Billingsley, P., Probability and Measure (1995), Wiley-Interscience · Zbl 0822.60002
[5] Büchi, J. R.; Landweber, L. H., Solving sequential conditions by finite-state strategies, Trans. Am. Math. Soc., 138, 295-311 (1969) · Zbl 0182.02302
[6] Cerný, P.; Chatterjee, K.; Henzinger, T. A.; Radhakrishna, A.; Singh, R., Quantitative synthesis for concurrent programs, (CAV (2011)), 243-259
[7] Chatterjee, K.; Chmelik, M., POMDPs under probabilistic semantics (2014), (Conference version: UAI, 2013) · Zbl 1329.90158
[8] Chatterjee, K.; Chmelik, M.; Tracol, M., What is decidable about partially observable Markov decision processes with omega-regular objectives, (CSL (2013)), 165-180 · Zbl 1356.68142
[9] Chatterjee, K.; Doyen, L., Partial-observation stochastic games: how to win when belief fails, ACM Trans. Comput. Log., 15, 2, 16 (2014) · Zbl 1291.91021
[10] Chatterjee, K.; Doyen, L.; Henzinger, T. A.; Raskin, J.-F., Algorithms for omega-regular games of incomplete information, Log. Methods Comput. Sci., 3, 4 (2007) · Zbl 1125.91028
[11] Chatterjee, K.; Henzinger, T. A., Semiperfect-information games, (FSTTCS’05. FSTTCS’05, Lect. Notes Comput. Sci., vol. 3821 (2005), Springer) · Zbl 1172.68540
[12] Chatterjee, K.; Jurdziński, M.; Henzinger, T. A., Quantitative stochastic parity games, (SODA’04 (2004), SIAM), 121-130 · Zbl 1318.91027
[13] Chatterjee, K.; Majumdar, R.; Jurdziński, M., On Nash equilibria in stochastic games, (CSL’04. CSL’04, Lect. Notes Comput. Sci., vol. 3210 (2004), Springer), 26-40 · Zbl 1095.91001
[14] de Alfaro, L.; Henzinger, T. A., Interface theories for component-based design, (EMSOFT’01. EMSOFT’01, Lect. Notes Comput. Sci., vol. 2211 (2001), Springer), 148-165 · Zbl 1050.68518
[15] Everett, H., Recursive games, (Contributions to the Theory of Games III. Contributions to the Theory of Games III, Ann. Math. Stud., vol. 39 (1957)), 47-78 · Zbl 0078.32802
[16] Gimbert, H.; Oualhadj, Y., Deciding the value 1 problem for ♯-acyclic partially observable Markov decision processes, (SOFSEM (2014)), 281-292 · Zbl 1435.91022
[17] Goubault-Larrecq, J.; Segala, R., Random measurable selections, (Horizons of the Mind (2014)), 343-362 · Zbl 1407.68255
[18] Henzinger, T. A.; Kupferman, O.; Rajamani, S., Fair simulation, Inf. Comput., 173, 64-81 (2002) · Zbl 1009.68071
[19] Kechris, A., Classical Descriptive Set Theory (1995), Springer · Zbl 0819.04002
[20] Martin, D. A., The determinacy of Blackwell games, J. Symb. Log., 63, 4, 1565-1581 (1998) · Zbl 0926.03071
[21] McNaughton, R., Infinite games played on finite graphs, Ann. Pure Appl. Log., 65, 149-184 (1993) · Zbl 0798.90151
[22] Mertens, J.-F.; Sorin, S.; Zamir, S., Repeated games, Core Discuss. Pap., 9422 (1994)
[23] Pnueli, A.; Rosner, R., On the synthesis of a reactive module, (POPL’89 (1989), ACM Press), 179-190
[24] Ramadge, P. J.; Wonham, W. M., Supervisory control of a class of discrete-event processes, SIAM J. Control Optim., 25, 1, 206-230 (1987) · Zbl 0618.93033
[25] Reif, J. H., The complexity of two-player games of incomplete information, J. Comput. Syst. Sci., 29, 2, 274-301 (1984) · Zbl 0551.90100
[26] Thomas, W., Languages, automata, and logic, (Handbook of Formal Languages, vol. 3, Beyond Words (1997), Springer), 389-455, chapter 7
[27] Vardi, M. Y., Automatic verification of probabilistic concurrent finite-state systems, (FOCS (1985), IEEE Computer Society Press), 327-338
[28] Zwick, U.; Paterson, M., The complexity of mean payoff games on graphs, Theor. Comput. Sci., 158, 343-359 (1996) · Zbl 0871.68138
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.