
Intitulé:
PartialObservation Stochastic Games: How to Win when Belief Fails du groupe Graphes et Logique

Date  20111206 11:0012:00 
Titre  PartialObservation Stochastic Games: How to Win when Belief Fails 
Résumé  We consider twoplayer stochastic games played on finite graphs with reachability (and Buechi) objectives where the first player tries to ensure a target state to be visited (or visited infinitely often) almostsurely, i.e., with probability 1, or positively, i.e., with positive probability, no matter the strategy of the second player.
We classify such games according to the information and to the power of randomization available to the players. On the basis of information, the game can be onesided with either (a) player 1, or (b) player 2 having partial observation, or twosided with (c) both players having partial observation.
On the basis of randomization, (a) the players may not be allowed to use randomization (pure strategies), or (b) they may choose a probability distribution over actions but the actual random choice is external and not visible to the player (actions invisible), or (c) they may use full randomization.
Our main results for pure strategies are as follows: (1) For onesided games with player 2 perfect observation we show that (in contrast to full randomized strategies) beliefbased strategies are not sufficient, and we present an exponential upper bound on memory both for almostsure and positive winning strategies; we show that the problem of deciding the existence of almostsure and positive winning strategies for player 1 is EXPTIMEcomplete. (2) For onesided games with player 1 perfect observation we show that nonelementary memory is both necessary and sufficient for both almostsure and positive winning strategies. (3) We show that for the general (twosided) case finitememory strategies are sufficient for both positive and almostsure winning, and at least nonelementary memory is required.
We establish the equivalence of the almostsure winning problems for pure strategies and for randomized strategies with actions invisible. Our equivalence result exhibits serious flaws in previous results in the literature: we show a nonelementary memory lower bound for almostsure winning whereas an exponential upper bound was previously claimed. 
Lieu  salle 76 
Orateur  Laurent Doyen 
Email  doyen@lsv.enscachan.fr 
Url  CNRS, LSV 
Aucun document lié à cet événement.
Retour Retour à l'index
 