Logics for Analyzing Games

1. Overview

The present entry provides a comprehensive survey of logics for analyzing games, arranged under a number of unifying themes and perspectives. Also, occasional connections are made with other strands at the interface of logic and games covered elsewhere in this Encyclopedia. This overview section is a brief tour d’horizon for topics that will return in more detail later on.

1.2 Logic and Game Theory

In many of the above topics, logics meets game theory. One such interface area is epistemic game theory where game play and solution concepts are analyzed and justified in light of various assumptions about players and their epistemic states, such as common knowledge or common belief in rationality. Epistemic game theory may be viewed as a joint offspring of logic and game theory, a form of progeny which constitutes a reliable sign of success of an interdisciplinary contact.

There are also other viable logical perspectives. In particular, one can look at game theory the way mathematical logicians look at any branch of mathematics. Following the style of the famous Erlangen Program, one can discuss the structures studied in that field and look for structural invariance relations and matching logical languages. Game theory is rich in structure, as it has several different natural notions of invariance. The tree format of extensive games offers a detailed view of what happens step by step as players make their moves, whereas the matrix format of strategic form games offers a high-level view that centers on outcomes. Yet other formats, to be discussed below, focus on players’ control over the various outcomes. All these different levels of game structure come with their own logical systems, as will be detailed in Section 2. Moreover, these different logics do not just provide isolated snapshots: they can be related in a systematic manner.

In this way, the usual logical techniques can be brought to bear. For instance, formal languages can express basic properties of games, while model-checking techniques can determine efficiently whether these hold in given concrete games (cf. Clarke, Grumberg, & Peled 1999).

Example Winning strategies.

Consider the following game tree, with move relations for both players, and propositional letters \(\win_{i}\) marking winning positions for player i.

Clearly, player E has a winning strategy against player A, i.e., a recipe that guarantees her to win, no matter what A does. This is expressed by a modal formula capturing exactly the right dynamics:

Here \([\move_A]\) is the universal modality “for all moves by player A”, and \(\langle \move_E\rangle\) is the existential modality “for some move by player E”. This two-step modality- or quantifier-based response pattern is typical for strategic powers of players in arbitrary games, as it captures the essence of sequential interaction. Crucially, logical laws can acquire game-theoretic import. For instance, the law of Excluded Middle applied to the above formula yields:

or in a logically equivalent formulation:

In two-step games like the above, where exactly one player wins (i.e., \(\win_A\leftrightarrow\neg\win_E\)), the latter formula expresses that either player E or player A has a winning strategy. More generally, this disjunctive assertion is a special case of Zermelo’s theorem, stating that every finite full information game is determined.

Having established the connection to logical languages, further model-theoretic themes can be applied fruitfully to games. Language based reasoning allows, for instance, to examine the preservation of properties between different games, based on the exact syntactic shape of their definition. Besides, logical syntax also supports logical proof theory. Hence, the latter’s rich pool of proof calculi may help to analyze basic results in game theory. This entry illustrates major recurring patterns of reasoning about interaction that come to light in this way.

Game theory also has a further natural level of representation, suppressing details of local moves and choices. The most familiar format for this are games in strategic form. In the simplest case of only two players, these correspond to a two-dimensional matrix, with rows standing for some player’s strategies, and columns for the other’s. Individual cells of such matrix hence correspond to the different possible strategy profiles of the game. Typically, all cells are labeled with information about the outcomes resulting from playing the corresponding strategies against one another. This labeling specifies players’ attitudes to outcome in terms of pay-offs, more abstract utilities, or ordinal markers for players’ preferences orders among outcomes.

Strategic form games, too, can model significant social scenarios. Here is an illustration from the philosophical literature on the evolution of social behavior.

Example The following game in matrix form is the Stag Hunt of Skyrms (2003), going back to ideas of David Hume. It serves as a metaphor for the social contract.

Each agent must decide between pursuing their own little project, hunting a hare, or joining in a larger collective endeavor, hunting stag. The former gives a moderate but guaranteed income, no matter what others do. The collective endeavor, on the other hand, can only succeed if all contribute, in which case everybody receives a high profit. If, however, some do not join, all contributions are lost and no contributor receives anything. In the corresponding strategic form game, all players have to decide on what to do in parallel, without knowing the actions of others.

The Stag Hunt game has two pure strategy Nash equilibria: every contributes, and nobody contributes. Which of these stable outcomes ensues will crucially depend on the players’ reasoning, their expectations about each other, and perhaps even further information stemming, for instance, from pre-game communication.

Clearly, analyzing strategic games involves agentive information, reasoning and expectations. All these aspects have tight connections to logic. Viewing outcomes as possible worlds, three relevant relations emerge between these. Within the matrix above, relating all cells in the same row fixes a unique choice already made by the row player A, while leaving E’s move completely open. In short, each horizontal row lists all possible choices of the column player E which A has to take into account. The corresponding modality may hence be said to describe A’s knowledge about the outcomes of the game given his choice. Still assuming the row player’s perspective, relating cells vertically rather than horizontally corresponds to A’s freedom of choice among his available strategies. Of course, one could also assume player E’s perspective instead, viewing the horizontal direction as E’s freedom of movement, while the vertical directions captures her epistemic uncertainty.

Thus, a bimodal logic arises for matrix games with laws such as

capturing the grid structure of matrix games. For more than two players, this logic gains some additional options and subtleties to be discussed in Section 2.6.

The crucial third relation is that of player’s preferences among outcomes. These, again, have matching modalities, now taken from preference logic (Hansson 2001). With the help of some auxiliary devices, the three modalities can define the central game-theoretic notion of a Nash equilibrium (Harrenstein 2004; van der Hoek & Pauly 2007).

Logics for matrix games differ from those for extensive games, as grids behave quite differently from trees in terms of complexity. Yet, both fall under the same general methodology. Towards a common understanding, one might view the logic of matrix games as capturing the basic laws of parallel, rather than sequential action.

1.3 Computation and Agency

Philosophical logic and mathematical logic are not the only illuminating perspectives on games. A third relevant viewpoint is that of computational logic. In modern computation, the paradigm is no longer single Turing machines but interacting systems of multiple processors. These processors may cooperate, but they might also compete for resources. In general, hence, it is useful to study multiple agents engaging in computation, be it within human, artificial or mixed societies. Though doing so, games become a natural model for computation, too. In fact, games are rich multi-agent systems where agents process information, communicate, and engage in actions, all driven by their respective preferences and goals. In the converse direction, computer science themes such as complexity and algorithmics have entered game theory, resulting in the area of computational game theory (Nisan et al. 2007). For a richer survey of computational logics of agency and games, see van der Hoek and Pauly (2007) and Shoham and Leyton-Brown (2008). The present entry contains occasional links to computation. These are especially prominent for reasoning about temporally extended games and their strategies (Sections 4.2, 4.4) and in the context of gamification (Section 6), where games are explored as a novel semantics for classical logical systems.

1.4 Games in Logic

Finally, recall the start of this section, but with reverse perspective: instead of asking what logic can do for games, ask what games can do for logic. Argumentation and dialogue are basic notions for logic. Both can be studied using techniques and results from game theory (Lorenzen & Lorenz 1978; Hamblin 1970). In this perspective, logical validity of consequence rests on there being a winning strategy for a Proponent claiming the conclusion against an Opponent granting the premises in a game where moves are regulated by the logical constants. Many games have found uses in modern logic since the 1950s, with Ehrenfeucht-Fraïssé games for model comparison being a paradigmatic example. Besides these, also semantic verification or model construction can be cast as natural logic games.

This raises an intricate issue within in the philosophy of logic, concerning the nature of logic and in particular that of logical constants. A ‘weak thesis’ would hold that games constitute a natural technique for analyzing logical notions, as well as a didactic tool for teaching logic that appeals directly to vivid intuitions. Parts of the literature, however, also defend a ‘strong thesis’, suggesting that the primary semantics of certain logical systems may be procedural and game-theoretic, rather than denotational in a standard sense. This perspective, sometimes called ‘logic as games’, occurs in some attractive semantics for first-order languages (Hintikka & Sandu 1997), as well as in game semantics for programming languages.

The theme of logic as games will appear only briefly in the present entry, which is mainly directed toward logics of games. Section 6 will discuss which questions arise from joining both perspectives on the interface of logic and games.

As it happens, the logic-as-games perspective is of broader relevance. Logic games were originally designed for particular tasks inside logic. Yet, taken to reality, they can help analyze or streamline actual lines of argumentation. As such they may be compared to designed parlor games that challenge reasoning skills. A game like Clue involves an intriguing mix of logical deduction, new information from drawing cards or public observation of moves, but also private communication acts by players (van Ditmarsch 2000). Other parlor games, such as Nine Men Morris (Gasser 1996) are graph games (Grädel, Thomas, & Wilke 2002) with added chance moves that serve to diminish the risk of finding a repeatable simple strategy on the fixed board. The logical study of playable designed games for bounded agents, and the design of new such games, is a natural sequel to this entry (cf. van Benthem & Liu 2019).

1.5 Probability

Game theory may be understood as generalized interactive decision theory. A major vehicle for the latter, just as for standard decision theory, is probability theory. Within games, probability can assume many roles. It may, for instance, express players’ degrees of belief quantitatively, but it can also enrich the space of actions with mixed strategies, thereby laying the ground for general equilibrium results. Probability can even play a role in the very definition of certain important games, especially in evolutionary game theory (Osborne & Rubinstein 1994). In this entry, probability is only mentioned in passing. Section 5, however, maps some combinations of logic and probability that are suggested by the study of games.

1.6 Zooming In

Games have a natural interface with logic in all its varieties, including mathematical, philosophical, and computational logic. In one direction of contact, logic can provide new abstract notions underneath game theory. Conversely, game-theoretic notions can also serve to enrich logical analysis. The present entry mainly concentrates on the first of these directions, the use of logic for analyzing games. It does so mostly from a semantic perspective, the dominant paradigm so far in the area. Though proof-theoretic approaches will be mentioned occasionally. The sections to follow elaborate on this theme along several dimensions. Specific perspectives include logics for game structures (Section 2), logical analysis of the nature of players (Section 3) and of the process of game play (Section 4). Additional spotlights are put on the relationship between logic and probability in the context of games (Section 5) and the endeavor of Gamification (Section 6). Each section forms a free-standing exposition, which results in some unavoidable, and perhaps useful, overlap. Throughout the exposition, some familiarity is assumed with the basic concepts of logic and game theory. In particular, notions of game theory left unexplained here can be found in the corresponding entry and in Leyton-Brown and Shoham (2008).

7. Discussion and Further Directions

This entry presents an overview of current work at the interface of logic and games. The topics surveyed fall in a number of strands including current logical analysis of games in the broadest sense, contacts between logic and classical game theory, connections with probability and with computation, and, lastly, the game-theoretic content of logic itself.

All this produced a perhaps bewildering variety of logical systems at the interface with games. Yet, this entry also shows a certain unity in approach, since the same sort of (modal) logics turn out suitable to deal with quite different aspects of game structure and game play. Moreover, when we step back a little, broader perspectives across the specific systems surveyed here arise.

One noteworthy phenomenon is the existence of two different styles of logical analysis. Some logical systems ‘zoom in’ on particular aspects of an activity or reasoning practice, providing more detail than what is usually found in standard mathematical or philosophical analysis. Other logical systems do the opposite, and ‘zoom out’ to general patterns that may not have been visible at the more detailed level of the original practice.

Most of the logical systems in this entry are of the fine-grained ‘zooming-in’ variety. Even so, coarse-grained logics of the ‘zooming-out’ variety are interesting, too, as they may highlight laws or general patterns in social behavior that lie beyond the details attended to by games and game theory. One example is the current interest in logics for the abstract notion of dependence (Väänänen 2007; Baltag 2016). Many forms of dependence and independence permeate social life. Baltag and van Benthem (2021) present a simple modal base logic of functional dependence and independence which fits this perspective, suggesting an analysis of strategies in extensive games as dynamic devices that create dependencies among players. Chen, Shi & Wang (2022, Other Internet Resources) then combine this framework, applied to strategic games, with the modal preference logic discussed above to find a common logical structure underlying both competitive and cooperative games. Another example of the logical search for generality in games is the proof-theoretic analysis of Hu and Kaneko (2012) of the general postulates for social interaction in Johansen (1982).

The interface area of logic and games still is in statu nascendi. Correspondingly, there are obvious gaps and desiderata on the logic side, which are reflected in the material in this entry.

In particular, one fundamental theme are syntactic perspectives on game-theoretic reasoning. Samples of a proof-theoretic style of analysis for play can be found in de Bruin (2005). More concretely, Zvesper (2010) analyzes classical results in epistemic game theory, (cf. Tan & Werlang 1988; Aumann 1999), in terms of abstract modalities for belief and optimality, showing how a few simple proof rules from modal μ-calculus can capture the essence of famous results in epistemic game theory. Proof-theoretic aspects of logic have so far been overshadowed by semantic analyses, although this situation is changing slowly (Artemov 2014; Kaneko 2002; Kaneko & Suzuki 2003). Model-based reasoning provides abstract semantic perspectives on games that can aid conceptual clarification, and the discovery of general laws. But it might turn out to be proof theory that governs the concrete reasoning used in the semantics, and that may be able to guide the context of justification in establishing general facts about games.

A further contact with logic that has been ignored in this entry is the rich interface between games and descriptive set theory (Woodin 2010; Kanamori 2003).

It should be stressed once more that logic is not the only formal discipline that throws light on games. Quantitative probability enters the study of games in many ways, both in classical and in evolutionary game theory. The interface of logic and games may well profit from the many old and new contacts between logic and probability (Leitgeb 2017; Lin & Kelly 2012; Harrison-Trainor, Holliday, & Icard 2016).

Another link that remained underrepresented in this entry are computational aspects. The study of games, play and players has natural connections with computation and agency in computer science and AI (Grädel, Thomas, & Wilke 2002; Abramsky 2008; Halpern 2013; Perea 2012; Brandenburger 2014). The proper perspective on what has been presented here may well turn out to be a triangle of interfaces between logic, games, and computation.

As for still broader connections, we have not done justice to all links between logic, games and philosophy, of which more are found in Stalnaker (1996, 1999). The same is true for links to linguistics and psychology (Clark 2012). In this language-oriented connection, one should also mention the work of Bjorndahl, Halpern, and Pass (2017) on the natural language used in specifying games and reasoning about them, thus making game analysis more description-dependent.

Finally, the main thrust of this entry is theoretical and foundational. However, there also is a more practical aspect to logic and games. Logic plays a role in cognitive psychology and experimental game theory, if only to identify testable hypotheses related to Theory of Mind or strategic reasoning (Ghosh, Meijering, & Verbrugge 2014; Ghosh & Verbrugge 2018; Bicchieri 1993; Fagin, Halpern et al. 1995). Lastly, some work at the interface of logic and games suggests outreach to the world of actual parlor games (van Ditmarsch & Kooi 2015; van Benthem & Liu 2019).

All in all, the claim of this entry is a modest one. Logic and games form a natural combination, that may reveal interesting things when pursued explicitly. Even so, too much logic may import too much of a formal apparatus, which may end up strangling the games perspective: logical systems are infinite machineries that can easily overwhelm a concrete game of interest. In short, the contact has to be managed with care.