Game theory and modal logic

Alexandru Baltag

CWI P.O. Box 94079, 1090 GB Amsterdam, The Netherlands

Abstract:(, abstract.pdf) In this series of lectures I try to give an overall picture of the relations between logic, games and (co)algebra, stressing especially the modal logic aspects of important gametheoretic concepts. There are two main possible ways of relating logic and games: logic games and game logics. The first approach is the more "classical" one from the logician's point of view, and uses games for the purposes of logic. In this category fall the model-comparison games (Ehreunfeucht-Fraisse, simulation games etc) and the game-theoretic semantics. I will not insist further on this approach, as it is thoroughly investigated in two other LUATCS'99 courses. The second approach uses logic for the purposes of game theory. In order to deal with this approach, I introduce (in my second lecture and maybe part of the third) some basic gametheoretic notions and results: strategic and extensive games, (im)perfect information games, perfect recall, open games pure, mixed and behavioural strategies, Nash equilibrium, winning, belief, knowledge, action and rationality. In the third lecture I start presenting various game logics, namely dynamic logics for games (e.g. Parikh's logic), temporal-logic, epistemic logic and strategic logic; I also mention briefly the way modal logic has been used to analyze the still problem of game equivalence In the fourth lecture, I investigate the relations between games, coalgebras and process algebra. I define a class of game processes, as coalgebras of a specific functor, and introduce a process algebra calculus; strategies are themselves processes, and a play is determined by parallel composition of the strategies. A "game-process" logic is introduced, as a mixture of dynamic and epistemic logic, used to capture various game-theoretic relations. In the fifth lecture I concentrate on the epistemic and informational aspects of game-actions ("moves"), and more specifically on modelling information updates in a multi-agent system. I use a logic of "epistemic actions", developed by L. Moss, S. Slawek and myself, to express and prove results about half-hidden or non-transparent actions, such as cheating moves in a game, private learning, secret communication, wiretapping, suspicion of cheating etc.

Lecture Plan:


Prerequisites: Some familiarity with the basic notions in standard modal logic is required. Some vague recollection of basic process-algebra and/or coalgebra notions might help, but is not obligatory.

A Few References:

1. The 1999 course notes of the "Logic and Games" course given at Stanford University by Johan van Benthem, available at

2. Notes on "Dynamic Epistemic Logic of Games", notes on "Information Update and Epistemic Logic" and Johan van Benthem's paper "When Are Two Games the Same?", all available at

3. Proceedings of the ILLC Workshop on Logic and Games, Amsterdam 1999. Available at

4. A. Baltag, L.S. Moss and S. Solecki, The Logic of Public Announcements, Common Knowledge and Private Suspicion, 1998. Submited for publication to APAL, November 1999. A preliminary version was presented at TARK'98, is published in the Proceedings, and is also available at

5. A. Baltag, A Logic of Epistemic Actions. 1999. In the Proceedings of the Workshop on "Foundations and Applications of Collective Agent-Based Systems", ESSLLI'99. To appear as CWI 1999 Report.

6. A. Baltag, Truth-as-Simulation: a Coalgebraic Perspective on Logic and Games. Presented at the 1999 Summer School in Logic and Computation, Heriot-Watt University, April 1999.

7. A. Baltag, Games as Processes. In preparation. 8. G. Bonanno, The Logic of Rational Play in Games of Perfect Information, in bf Economics and Philosophy 7, 37-65, 1991.

9. J. Gerbrandy, Dynamic Epistemic Logic, in L. S. Moss et al, bf Logic, Language and Information, vol. 2, CSLI Publications, Stanford University 1999.

10. R. Fagin, J. Y. halpern, Y. Moses, M. Y. Vardi, Reasoning About Knowledge, MIT Press, 1995.

11. M. Kaneko, T. J. Nagashima, it Game Logic anmd its Applications, Studia Logica 57, 325-354.

12. M. J. Osborne and A. Rubinstein, A Course in Game Theory, MIT Press 1994.

13. R. Parikh, it The Logic of Games and its Applications, in Topics in the Theory of Computation, Karpinski and van Leeuwen, eds. Annals of Discrete Mathematics 24 (1985), pp. 111-140.

14. M. Pauly, Formal Game Semantics for Dynamic Logic. In preparation.