Games, Boards and Play: A Logical Perspective
Lei Li

Abstract:
Games are a powerful paradigm for social interaction, but at the same time also good models for analyzing crucial notions in logical reasoning and computation. They provide a versatile platform for simulating diverse scenarios. Exploring game modeling, analyzing game-related reasoning from both player and modeler perspectives, investigating the impact of varying information access on agents' epistemic activities, and addressing computational problems related to games all hold both practical and academic significance. This dissertation specifically delves into game graphs, game board change, and the logical analysis of game elements across various scenarios.

First, we analyze two sorts of games in terms of especially designed corresponding logical systems. The first kind of games we consider are graph games: in particular, sabotage games. These games where the graph that serves as the game board can change in the course of play model scenarios where agents are pushed toward some desirable goal by removing false paths. Sabotage modal logics have provided effective analysis for such games, but the problem of axiomatization remains unresolved, we provide a complete axiomatization for the validities in the language of sabotage modal logic slightly extended with just enough expressive devices from hybrid logic. 

Our next kind of game, i.e., the distributed game, concerns quite different aspects of interactive scenarios: the difference between players’ local internal view and the modeler`s global external view of the game as it proceeds. In Chapter 4 of this thesis we study these ‘distributed games’ with special logical languages allowing us to describe local and global perspectives precisely, and show in detail how they interact.

The remaining topics of the thesis explore two further directions.

First, in Chapter 5 we note that the special game logics developed so far, i.e., sabotage model logics in our first part, can be seen as instances of a much broader class of logics with modalities that describe the effects of various operations of model change. Such logics have been used for modeling both action and information flow, and there is a broad literature on both specific systems and general model-theoretic and proof-theoretic themes running through all of these. We explore what is the precise complexity of testing for the appropriate notions of bisimulation between given finite models.

Our final topic in this thesis concerns another extension of the concerns in our first part on logics for game scenarios. We undertake a practical case study where local and global multi-agent perspectives play in practice: namely, in the functioning of global recommender systems interacting with local individual users. In Chapter 6 we show how the filtration dynamics can be specified and analyzed completely in dynamic-epistemic logics of communication involving filtering actions. 

Finally, we highlight some unresolved issues for further exploration based on existing research. These involve games with imperfect information, attention dynamics in situations with abundant information, strategic reasoning in games, and so forth.

Keywords: graph game; distributed game; model-changing logic; bisimulation; filtering mechanism