Site de Vincent Gripon

Blog sur mes recherches et mon enseignement

Qualitative Concurrent Stochastic Games with Imperfect Information

V. Gripon et O. Serre, "Qualitative Concurrent Stochastic Games with Imperfect Information," dans Proceedings of 36th International Colloquium of Automata, Languages and Programming, Springer, Lecture Notes in Computer Science, Rhodes, Grèce, pp. 200--211, juillet 2009.

Nous étudions un modèle de jeux qui combine les aspects concurent, information imparfaite et stochastique. Ce sont des jeux à espace fini d’états dans lesquels, à chaque tour, les deux joueurs choisissent simultanément et indépendamment une action. Ensuite, un état successeur est choisi à l’aide d’une distribution probabiliste dépendant de l’état précédent et de la paire d’actions choisies par les joueurs. L’information imparfaite est modélisée comme suit : Chacun des deux joueurs possède une relation d’équivalence sur les états et ne peut observer que la classe d’équivalence de l’état courant. Ainsi un joueur devra se comporter de la même façon dans deux parties qui lui paraissent indistinguables. Nous considérons l’accessibilité (la partie passe-t-elle par un état final ?) et l’objectif de Buchi (la partie passe-t-elle infiniment souvent par un état final ?). Notre contribution principale est de montrer que le problème de décider si le premier joueur a une stratégie qui lui assure de gagner presque sûrement contre toute stratégie du second joueur est complet en 2-ExpTime. Nous caractérisons également ces stratégies qui lui permettent de gagner presque sûrement.

Télécharger le manuscrit.

Bibtex
@inproceedings{GriSer20097,
  author = {Vincent Gripon and Olivier Serre},
  title = {Qualitative Concurrent Stochastic Games
with Imperfect Information},
  booktitle = {Proceedings of 36th International
Colloquium of Automata, Languages and Programming},
  year = {2009},
  editor = {Springer},
  pages = {200--211},
  series = {Lecture Notes in Computer Science},
  address = {Rhodes, Greece},
  month = {July},
}




Vous êtes le 795876ème visiteur

Site de Vincent Gripon