Game theoretic models have proved to be quite versatile in the analysis of multi-agent systems. Solution concepts like equilibria provide a description of the possible outcomes. From the perspective of computer science, one of the fundamental questions is the complexity of computing equilibria in such game models, which in turn require the representation of the model to be compact. While explicit descriptions of classical game theoretic models don't fit this criterion, there are various approaches based on constraining the quantitative payoff functions to achieve compact representation. These result in various well-studied classes of games like polymatix games and additively separable hedonic games. Another approach is to use a logical language to represent agents' objectives.

In this talk, we propose a qualitative model for incomplete information games that has a compact representation. We identify structural properties which guarantee the existence of equilibria. We identify the fragment which precisely corresponds to ``Boolean games'' (a well-studied model of strategic games with Boolean objectives). We also provide complexity results for the natural questions of verification and checking of the emptiness of equilibrium outcomes in this class of games.

This is joint work with Hans van Ditmarsch (CNRS, IRIT France).

Short Bio:
Sunil Simon received his PhD from the Institute of Mathematical Science, Chennai and is currently a faculty member at the Department of Computer Science and Engineering, IIT Kanpur. His research interests include formal verification, logical foundations of multiple-agent systems and computational analysis of games.