Randomness for FreeReport as inadecuate

Randomness for Free - Download this document for free, or read online. Document in PDF available to download.

1 IST Austria - Institute of Science and Technology Austria 2 LSV - Laboratoire Spécification et Vérification Cachan 3 LaBRI - Laboratoire Bordelais de Recherche en Informatique

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.

Author: Krishnendu Chatterjee - Laurent Doyen - Hugo Gimbert - Thomas Henzinger -

Source: https://hal.archives-ouvertes.fr/


Related documents