A General Notion of Uniform Strategies

Bastien Maubert 1 Sophie Pinchinat 1
1 S4 - System synthesis and supervision, scenarios
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : We consider two-player turn-based game arenas for which we investigate uniformity properties of strategies. These properties involve sets of plays in order to express useful constraints on strategies that are not μ-calculus definable. Typically, we can represent constraints on allowed strategies, such as being observation-based. We propose a formal language to specify uniformity properties, involving an original modality called R, meaning "for all related plays". Its semantics is given by some binary relation between plays. We demonstrate the relevance of our approach by rephrasing various known problems from the literature. 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 binary relation that defines the sets of related plays is recognizable by a finite state transducer. This solution yields a nonelementary procedure. Read More: http://www.worldscientific.com/doi/abs/10.1142/S0219198914400040
Type de document :
Article dans une revue
International Game Theory Review, World Scientific Publishing, 2013, 16 (1), pp.33. 〈10.1142/S0219198914400040〉
Liste complète des métadonnées

Contributeur : Sophie Pinchinat <>
Soumis le : lundi 29 décembre 2014 - 09:28:36
Dernière modification le : vendredi 16 novembre 2018 - 01:21:47

Lien texte intégral



Bastien Maubert, Sophie Pinchinat. A General Notion of Uniform Strategies. International Game Theory Review, World Scientific Publishing, 2013, 16 (1), pp.33. 〈10.1142/S0219198914400040〉. 〈hal-01098738〉



Consultations de la notice