A tutorial by Laurent Perrussel (University Toulouse Capitole, IRIT) and Munyque Mittelmann (University of Naples Federico II).
Contact emails: laurent.perrussel@irit.fr, munyque.mittelmann@unina.it
Slides: Parts 1 and 2, Parts 3,4, and 5.
Model checkers for ATL/SL: MCMAS, Vitamin, STV (online version)
This tutorial will give an overview on the representation of a game strategy, a key issue in strategic reasoning. Strategic reasoning consists of representing and reasoning on players’ strategies: how an agent should move while considering other players’ possible moves. Several proposals have been made for representing strategies in a logical language, either as plain objects or only at the semantic level. The tutorial will overview several representation models for representing strategies and will explore different variants and extensions (handling uncertainty, incomplete knowledge…). The tutorial will also dedicate time on the reasoning dimension and the relation with planning.
Strategic Reasoning
Overall goal
Game as State-Transition Models
Strategy as Functions
Reasoning about Strategy abilities
Alternating-time-Temporal Logics
Strategy Logic
Representing a strategy: Natural Strategy
Strategies as a sequence of conditional plans
Key characteristics of Natural Strategies
Expressive power
Model Checking
Epistemic extension: strategy considering knowledge about other agents
Representing a strategy as a plain object in logical formulas
Reasoning about Games
Game Description Logics
Strategies as a sequence of choice
Model Checking
Strategies as Plans or Programs
Interplay between planning and strategic reasoning
Synthesis of strategy as generating a plan
Knowledge base programs and multi-agent planning
Strategies as a learned object
Strategy as a neural network
Strategy as a tuned Monte-Carlo program
The tutorial will assume some basic knowledge of Symbolic Logic or Logic Programming.
This tutorial is relevant for different communities, including:
The community inspired by economic paradigms will be interested in the compact representation perspective on strategies
The knowledge representation community will be interested in the overview of different types of strategy representation.
The (multi-agent) planning community will be interested in learning the standard hypothesis assumed in the representation of strategies and the key differences with plans.
R. Alur, T. A. Henzinger, O. Kupferman. Alternating-Time Temporal Logic. J. of the ACM, 49(5):672-713, 2000
K. Chatterjee, T. A. Henzinger, and N. Piterman. Strategy Logic. Inf. Comput. 208(6):677-693, 2010.
M. Genesereth, M. Thielscher. General Game Playing. Morgan & Claypool publishers. 2014
W. Jamroga, V. Malvone, A. Murano. Natural Strategic Ability. Artif. Intell. 277, 2019.
D. Zhang, M. Thielscher. Representing and Reasoning about Game Strategies. J Philosophical Logic 44(2). 2015
D. Zhang, M. Thielscher. A logic for reasoning about game strategies. Proc. of AAAI-15. 2015
K. Batz, T. J. Biskup, J-P Katoen, and T. Winkler. 2024. Programmatic Strategy Synthesis: Resolving Nondeterminism in Probabilistic Programs. Proc. ACM Program. Lang. 8, POPL,
B. Zanuttini, J. Lang, A. Saffidine, F. Schwarzentruber: Knowledge-based programs as succinct policies for partially observable domains. Artif. Intell. 288: 103365 (2020)
G. De Giacomo, G. Parretti, S. Zhu: LTLf Best-Effort Synthesis in Nondeterministic Planning Domains. ECAI 2023: 533-540
A. Goldwaser, M. Thielscher: Deep Reinforcement Learning for General Game Playing. AAAI 2020: 1701-1708
T. Cazenave: Monte Carlo Game Solver. CoRR abs/2001.05087 (2020)
G. Jiang, L. Perrussel, D. Zhang, H. Zhang, Y. Zhang: Game equivalence and expressive power of game description languages: a bisimulation approach. J. Log. Comput. 33(1): 163-187 (2023)
F. Belardinelli, W. Jamroga, V. Malvone, M. Mittelmann, A. Murano, L. Perrussel: Reasoning about Human-Friendly Strategies in Repeated Keyword Auctions. AAMAS 2022: 62-71