Logic and Games

Course Description

This course will discuss the inter-connection between logic and games, focussing on both ‘games for logic’ and ‘logic for games’ perspectives. On one hand we will study various logical concepts that can be viewed as games, on the other hand, we will study various game-theoretic concepts from the logical viewpoint. A connection involving this dual dependency between logic and games will also be discussed. We will conclude with providing some current research directions in these areas.

  • Lecturer:Sujata Ghosh (Indian Statistical Institute) and Jeremy Seligman (Tsinghua University and University of Auckland)
  • TA: Li Lei (李磊, lilei19@mails.tsinghua.edu.cn) 
  • Time: 13:30-16:05, 26 June – 30 June
  • Venue: 三教3104
  • Zoom ID: 81707963268

Schedule

Day 1: We will first introduce some game-theoretic concepts with examples, to set the stage for our subsequent discussion. Then we will introduce first-order logic and propositional modal logic over graphs and certain games corresponding to distinct semantic concepts in logic.

Day 2: We will delve deeper into the ‘games for logic’ perspective and continue studying games related to the various semantic concepts, and describe the connection between the existence of winning strategies for players in the respective logic games vis-á-vis the corresponding query in the logic frameworks.

Day 3: We will shift our focus from ‘games for logic’ to ‘logic for games’ and introduce Parikh’s game logic [8] and its variants to begin with. Then we will build up a connection between these game logics and the model-checking or the evaluation games we discussed earlier.

Day 4: We will merge the discussion on games, logics and graphs by presenting certain logics describing games on graphs, a topic that has picked up a renewed interest following van Benthem and Liu [10]. We will particularly focus on on cops and robber game and sabotage game.

Day 5: Before finishing, we concentrate on strategic reasoning in games on graphs and relevant logic frameworks. We will end with giving pointers to further challenges, especially involving studies on imperfect and incomplete information.

Background Knowledge​

This course will only assume knowledge of basic propositional logic and will not assume any knowledge about concepts in game theory [5]. We will introduce the syntax of first order logic [1] and propositional modal logic [2]. We will mainly consider graphs as our models while we introduce these frameworks. For the first order logic part as well as the ‘games for logic’ part you can have a look at Models and Games, by Väänänen [4]. A detailed analysis on both games for logic and logic for games can be found in Logic in Games, by van Benthem [3].

In general, it would be helpful if you have some understanding about these logics beforehand. Also, we will mention several technical results involving axiom systems, completeness, decidability, satisfiability, model-checking, homomorphisms and isomorphisms, and bisimulation, among others. We will explain all these concepts in the course, but if you have not seen them before, it would be better to read them up from some logic book. All these concepts are explained in details in the book, Modal Logic, by Blackburn, de Rijke and Venema [2].

References:

A list of relevant books, research papers, tutorial articles is given below (to be updated as the course progresses).

* Some text books on first-order and modal logics

[1] A mathematical introduction to logic: H.B. Enderton, Academic Press, 2nd edition, 2001.

[2] Modal logic: P. Blackburn, M. de Rijke and Y. Venema, Cambridge University Press, 2001.

* Some text books on logic and games

[3] Logic in games: J. van Benthem, The MIT Press, 2014.

[4] Models and games: J. Väänänen, Cambridge University Press, 2011.

* Some text books on game theory

[5] A course in game theory: M.J. Osborne and A. Rubinstein, The MIT Press, 1994.

[6] Game theory: A playful introduction: M. DeVos and D.A. Kent, AMS, 2016.

* A tutorial article on logics, games and strategies

[7] Strategies in games: A logic-automata study: S. Ghosh and R. Ramanujam, LNCS 7388, Springer, pp. 110-159, 2012.

* Articles on game logics

[8] The logic of games and its applications: R. Parikh, Annals of Discrete Mathematics, 24:111-140, 1985.

[9] Logic games are complete for game logics: J. van Benthem, Studia Logica 75:183-203, 2003.

* A recent article on logic and graph games

[10] Graph games and logic design: J. van Benthem and F. Liu, Knowledge, Proof and Dynamics, Logic in Asia: Studia Logica Library, Springer, pp. 125-146, 2020.

* On Cops and Robber games

[11] The game of cops and robbers on graphs, A. Bonato and R.J. Nowakowski, AMS, 2011

[12] A simple logic of the hide and seek game: D. Li, S. Ghosh, F. Liu and Y. Tu, Studia Logica, 2023.

* On Sabotage games

[13] An essay on sabotage and obstruction: J. van Benthem, LNCS 2605, pp. 268 – 276, 2005.

[14] Modal logics of sabotage revisited: G. Aucher, J. van Benthem and D. Grossi, Journal of Logic and Computation 28(2):269-303, 2018.

 

Materials

Please access the slides and accompanying handout through the following link: https://cloud.tsinghua.edu.cn/d/72ad90e4156d4b1389e4/

Recordings