Opacity Issues in Games with Imperfect Information

Bastien Maubert 1 Sophie Pinchinat 1 Laura Bozzelli 2
1 S4 - System synthesis and supervision, scenarios
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Résumé : Nous étudions en détail la classe des jeux à condition d'opacité, qui sont des jeux à deux joueurs à information imparfaite dans lesquels seul l'un des joueurs n'a pas information parfaite, et où la condition de gain dépend de l'information que celui-ci a au cours du jeu. Ces jeux sont liés à des aspects de sécurité des systèmes informatiques : une partie est opaque si le joueur à information imparfaite ne "sait" jamais avec certitude que la position courante est l'une des positions spéciales dites "secrètes". Nous étudions les problèmes de décision d'existence de stratégie gagnante pour chaque joueur, et nous les appellons opacity-violate problem et opacity-guarantee problem. Le fait de s'intéresser au joueur à information parfaite est nouveau en théorie des jeux à information imparfaite car lorsqu'on considère des conditions de gain classiques cela revient à considérer le jeu à information parfaite sous-jacent. Nous établissons que les deux problèmes sus-mentionnés sont EXPTIME-complets, montrant ainsi que notre condition de gain apporte un saut de complexité pour le joueur à information parfaite, et nous exhibons le problème opacity-verify qui, de manière intéressante, généralise des approches considérées dans la littérature pour l'analyse d'opacité des systèmes à événements discrets. Dans le cas des jeux en aveugle, ce problème se relie aux deux problèmes initiaux, de telle sorte que les jeux en aveugle à condition d'opacité sont déterminés et que les trois problèmes sont PSPACE-complets.
Type de document :
Rapport
[Research Report] 2011, pp.27
Liste complète des métadonnées

https://hal.inria.fr/inria-00630077
Contributeur : Bastien Maubert <>
Soumis le : vendredi 7 octobre 2011 - 11:07:29
Dernière modification le : mercredi 16 mai 2018 - 11:23:04
Document(s) archivé(s) le : dimanche 8 janvier 2012 - 02:25:38

Fichiers

RR-1978.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00630077, version 1

Citation

Bastien Maubert, Sophie Pinchinat, Laura Bozzelli. Opacity Issues in Games with Imperfect Information. [Research Report] 2011, pp.27. 〈inria-00630077〉

Partager

Métriques

Consultations de la notice

425

Téléchargements de fichiers

191