Affiliations: Institute of Information and Computing Sciences,
Utrecht University, Utrecht, the Netherlands | Computer Science Department, The University of
Liverpool, Liverpool, United Kingdom | Faculty of Electrical Engineering, Mathematics and
Computer Science, Delft University of Technology, Delft, the Netherlands
Abstract: Multi-agent systems comprise entities whose individual
decision making behavior may depend on one another's. Game-theory
provides apposite concepts to reason in a mathematically precise fashion about
such interactive and interdependent situations. This paper concerns a logical
analysis of the game-theoretical notions of Nash equilibrium and its
subgame perfect variety as they apply to a particular class of extensive games
of perfect information. Extensive games are defined as a special type of
labelled graph and we argue that modal languages can be employed in their
description. We propose a logic for a multi-modal language and prove its
completeness with respect to a class of frames that correspond with a
particular class of extensive games. In this multi-modal language
(subgame perfect) Nash equilibria can be characterized. Finally, we show how
this approach can formally be refined by using Propositional Dynamic Logic
(PDL), though we leave completeness as an open question.
Keywords: modal logic, dynamic logic, game theory, nash equilibrium
