PSY 2009: Imperfect-Information Games for System Design. Models, Applications, and Tools / Laurent Doyen (EPFL) One challenge in the analysis of concurrent systems arises with the uncertainty due to the inability of components to observe all occurring events. We discuss games with imperfect information as a modeling framework for such systems. In the first part of our talk, we survey fundamental models of games with imperfect information, and illustrate motivating scenarios for the analysis of interactive systems, in particular controller synthesis, compositional system design, and verification of cryptographic protocols. We present a classical algorithm for solving a basic, but paradigmatic, model of imperfect-information games.This algorithm performs a reduction to perfect-information games via a power-set construction that involves a state-space explosion. In the second part of the talk, we present a generic symbolic approach for dealing with the state-explosion problem. We show that the structure of the classical reduction can be ********* to design a compact data structure. On this data structure, we can compute some important symbolic operations efficiently, while other operations are shown to be NP-hard. We present symbolic algorithms to compute the winning positions of a game of imperfect information, and we extend them to construct winning strategies. Finally, we present experimental results obtained with the tool Alpaga.
