8739 articles  [english version]

hal-00760370, version 1

Uniform Strategies

Bastien Maubert (Auteur à contacter de préférence, http://www.irisa.fr/prive/bmaubert/) a1, Sophie Pinchinat (, http://people.irisa.fr/Sophie.Pinchinat/) a1

N° RR-8144 (2012)

Résumé : We consider turn-based game arenas for which we investigate uniformity properties of strategies. These properties involve bundles of plays, that arise from some semantical motive. Typically, we can represent constraints on allowed strategies, such as being observation-based. We propose a formal language to specify uniformity properties and demonstrate its relevance by rephrasing various known problems from the literature. Note that the ability to correlate different plays cannot be achieved by any branching-time logic if not equipped with an additional modality, so-called R in this contribution. We also study an automated procedure to synthesize strategies subject to a uniformity property, which strictly extends existing results based on, say standard temporal logics. We exhibit a generic solution for the synthesis problem provided the bundles of plays rely on any binary relation definable by a finite state transducer. This solution yields a non-elementary procedure.

  • a –  Université de Rennes 1
  • 1 :  S4 (INRIA - IRISA)
  • CNRS : UMR6074 – INRIA – Institut National des Sciences Appliquées (INSA) - Rennes – Université de Rennes 1
  • Domaine : Informatique/Informatique et théorie des jeux
  • Mots-clés : game theory – temporal logic – epistemic logic – uniform strategies
  • Référence interne : RR-8144
  • hal-00760370, version 1
  • oai:hal.inria.fr:hal-00760370
  • Contributeur : 
  • Soumis le : Lundi 3 Décembre 2012, 18:02:06
  • Dernière modification le : Mardi 4 Décembre 2012, 10:01:15