Logics for Analyzing Power in Normal Form Games

This entry discusses the use of mathematical languages to express and analyze the formal properties of power in normal form games. The mathematical languages discussed in this entry will be referred to as logics, and classified according to their ability to express game-related concepts.

The material in this entry will be limited to the logical analysis of strategies and preferences of (groups of) individuals in normal form games. It will not cover the use of game theory to study logical languages nor the role of epistemic concepts in strategic decisions. It will also not cover aspects of sequential decisions-making, typical of strategic reasoning in extensive games. An account of those can be found in the related entries logic and games, epistemic foundations of game theory (see also van Benthem, Pacuit, & Roy 2011 and van Benthem 2014).

• 1. The Logic Underneath Normal Form Games
• 2. The Basic Ingredients
  • 2.1 Preferences
  • 2.2 Choices
• 3. Analyzing Power
  • 3.1 Cooperative Games and Their Logic
  • 3.2 Strategic Games and Their Logic
    • 3.2.1 Non-monotonic Action Logics
    • 3.2.2 Logic-Based Games
• 4. Conclusions: On the Right Level of Analysis
• Bibliography
• Academic Tools
• Other Internet Resources
• Related Entries

---

1. The Logic Underneath Normal Form Games

A (normal-form) game is a mathematical description of the relation between a set of individuals (or groups of individuals) and a set of potential outcomes. Individuals choose, independently and concurrently, a subset of the outcomes, with the final outcome being selected from the combination of each choice. Independently means that individuals’ choices do not influence one another. Concurrently means that each individual’s choices are taken not knowing the other players’ choices. Each individual is assumed to have a preference over the set of outcomes, i.e., he or she likes some outcomes more than others, and typically assumed to know the other individuals’ potential choices and preferences, adjusting their decisions accordingly.

Games are used to model all sorts of situations, ranging from animal behavior to international conflict resolution (Osborne & Rubinstein 1994). A useful application for the purpose of this entry is collective decision-making, an instance of which is going to be the working example throughout.

Depending on players’ preferences, knowledge and capabilities some outcomes will be more likely to be chosen. In order to understand which ones, game theory has devised solution concepts, formally functions from the set of games to the set of outcomes in each of these games, which describe players’ rationality in mathematical terms. Solution concepts, as we will see later, can be succinctly expressed in simple and well-behaved logics.

Next we describe games as mathematical structures, emphasizing various key ingredients (e.g., the possibility of forming coalitions, the possibility to take decisions in time etc.) and the best suited languages to express them.

2. The Basic Ingredients

Formally, games consist of a finite set of players \(N=\{1,2, \ldots, n\}\) and a possibly infinite set of outcomes \(W=\{w_1, w_2, \ldots, w_k, \ldots \}\).

On top of players and outcomes, games come with two more relations:

• a preference relation, denoted \(\succeq\), describing players’ preferences over outcomes;
• an action relation, denoted \(E\), describing the outcomes that players or groups of players are able to impose or, conversely, rule out;

An important relation in games is knowledge, which formally describes what players know of the game and their opponents. This relation is sometimes given explicitly, other times left implicit. The present entry will not make the relation explicit, but will rather incorporate it in the formalization of players’ rationality.

Both the preference and the action relations collect families of individual relations, one per player. The preference relation, for instance, is broken down into a family \(\{\succeq_i\}_{i\in N}\), describing the preference over outcomes for each of the individuals, while the action relation collects a family \(\{E_C\}_{C\subseteq N}\) each describing what a specific group of players can achieve.

Overall, a game can be seen as a mathematical structure

\[(\mathcal{N}, W, \succeq, E)\]

where \(\mathcal{N}\) is the set of players, typically finite, \(W\) the set of outcomes, \(\succeq\) the preference relation and \(E\) the action relation.

This mathematical structure is also known as a relational structure (Blackburn, Rijke, & Venema 2001), which is the set-theoretic equivalent of a so-called modal logic (Blackburn et al. 2001), a mathematical language that is well-suited to express the mathematical properties of relations. A relational structure will henceforth be denoted \(F\), which stands for frame.

The last ingredient that we need, in order to link relational structures and modal logics, is the specification of a set of atomic propositions Atoms, which expresses the relevant properties of the outcomes we are interested in. This set is usually taken to be countable^[1] and is associated to outcomes by means of a valuation function, i.e., a function of the form

\[V: W \to 2^\texttt{Atoms}\]

associating to each outcome the set of propositional atoms that are true at that outcome.

A tuple \((F,V)\) will be referred to as model, which will be denoted \(M\).

The relations in a game structure, which are relative to individual players (and groups), will formally be described in connection with the main modal logics used to express their properties, at different levels of description and granularity.

The following paragraph collects the background technical notions needed to interpret the modal languages used in this entry. The reader already acquainted with modal logic can skip it. For a more in depth exploration one can consult the related entry on modal logic (Garson 2014). Well-known classic textbooks are Modal Logic: An Introduction (Chellas 1980), which focuses on non-normal modal logics, and Modal Logic (Blackburn et al. 2001), which focuses instead on a more mathematical treatment of normal modal logics.^[2]

A model for this language is a structure \(M = ((W, R_1, \ldots, R_n, \ldots), V)\), consisting of a set of worlds or states or outcomes \(W\); an accessibility relation \(R_i\) for each modal operator \(\Box_i\), defined via so-called neighborhood functions (Chellas 1980), i.e., functions \(R_i: W \to 2^{2^{W}}\); and a valuation function \(V: \texttt{Atoms} \to 2^{W}\), which assigns to each atomic proposition a subset of \(W\), with the idea that each atomic proposition is assigned to the set of worlds at which this proposition is true.

As a general convention, a multimodal language with modalities \(\Box_1\), …, \(\Box_n\), … will be denoted by \(\mathcal{L}^{f(\Box_1),\ldots, f(\Box_n),\ldots}\), where the function \(f\) associates to each modality its intuitive shorthand. Let \(\Delta\) be a modal language consisting of modalities \(\Box_1\), …, \(\Box_n\), … and let \(M = ((W, R_1, \ldots, R_n, \ldots), V )\) be a model for this language. The satisfaction relation of a formula \(\varphi \in \Delta\) with respect to a pair \((M,w)\), where \(w \in W\), is defined according to the following truth conditions:

\[\begin{align*} M,w&\models p &\mbox{ if and only if }& w \in V(p)\\ M,w&\models \neg\varphi &\mbox{ if and only if }& M,w\not\models\varphi \\ M,w&\models \varphi\land\psi &\mbox{ if and only if }& M,w\models\varphi \mbox{ and } M,w\models\psi \\ M,wy&\models \Box_i \varphi &\mbox{ if and only if }& \varphi^M\in R_i(w) \\ \end{align*} \]

where \(\varphi^{M}=\{w \in W \mid M,w \models \varphi\}\) is called the truth set or the extension of \(\varphi\).

A formula \(\varphi\) of a modal language \(\Delta\): holds at a state \(w\) of model \(M\) whenever \(M,w \models \varphi\); is valid in a model \(M\), denoted \(\models_{M} \varphi\), if and only if \(M,w \models \varphi\) for every \(w \in W\), where \(W\) is the domain of \(M\); is valid in a class of models \(\mathcal{M}\), denoted \(\models_{\mathcal{M}} \varphi\), if and only if it is valid in every \(M \in \mathcal{M}\); is valid in a frame \({F}\), denoted \(\models_{{F}} \varphi\), if and only if for every valuation \(V\) we have that \(\models_{(F,V)} \varphi\); is valid in a class of frames \(\mathcal{F}\), denoted \(\models_{\mathcal{F}} \varphi\), if and only if it is valid in every \(F \in \mathcal{F}\).

The set of formulas of \(\Delta\) that are valid in a class of models \(\mathcal{M}\) is denoted \(\Delta_{\mathcal{M}}\) (for frames the denotation is \(\Delta_{\mathcal{F}}\)). For a set of formulas \(\Sigma\), we write \(M,w \models \Sigma\) to say that \(M,w \models \sigma\), for all \(\sigma\in \Sigma\). We say that a set of formulas \(\Sigma\) semantically entails a formula \(\varphi\) in a class of models \(\mathcal{M}\), denoted \(\Sigma \models_{\mathcal{M}} \varphi\), if for every \(M \in \mathcal{M}\) we have that \(\models_{M} \Sigma\) implies \(\models_{M} \varphi\).

A modal rule

\[\frac{\varphi_1,\ldots ,\varphi_n }{\psi}\]

is sound in a class of models \(\mathcal{M}\) if \(\varphi_1,\ldots ,\varphi_n \models_{\mathcal{M}} \psi\).

Recall, following Chellas (1980), that a modal logic \(\Delta\) is called classical if it is closed under the rule of equivalence, i.e., for each \(\Box\) in the language \(\Delta\) we have:

\[\frac{\varphi \leftrightarrow \psi}{\Box \varphi \leftrightarrow \Box \psi}\]

It is called monotonic if it is classical and it is moreover closed under the rule of monotonicity, i.e., for each \(\Box\) in the language \(\Delta\) we have:

\[\frac{\varphi \rightarrow \psi}{\Box \varphi \rightarrow \Box \psi}\]

It is called normal if it is monotonic, it is closed under the rule of generalization and contains the \(K\) axiom, i.e., for each \(\Box\) in the formulas of \(\Delta\) we have

\[\frac{\varphi}{\Box \varphi}\]

and \(\Delta\) contains \(\Box(\varphi \to \psi) \to (\Box \varphi \to \Box \psi)\).

A normal modal logic can be interpreted in structures of the form \(M = ((W, R'_1, \ldots, R'_n, \ldots), V)\), where each \(R'_i\) is a principal filter^[3] or, alternatively, it is of the form \(R'_i: W \to 2^{W}\).

2.1 Preferences

Recall the relational structure \((\mathcal{N},W, \succeq, E)\) and consider the relation \(\succeq\). This relation compactly represents a family \(\{\succeq_i\}_{i\in N}\) of individual preference relations each indexed with a player.

Formally, a preference for player \(i\) is a relation

\[\succeq_i \subseteq W \times W\]

The idea is that if two outcomes \(w\) and \(w'\) are such that \((w,w')\in \succeq_i\) then player \(i\) considers outcome \(w\) at least as good as outcome \(w'\). The fact that \((w,w')\in \succeq_i\) will be abbreviated \(w \succeq_i w'\). Its inverse is the relation \(\preceq_i\),which holds for \((w,w')\) whenever \(w' \succeq_i w\). Its strict counterpart is the relation \(\succ_i\), which holds for \((w,w')\) whenever \(w \succeq_i w'\) and it is not the case that \(w' \succeq_i w\). Moreover \(w \sim_i w'\) denotes the fact that \(w \succeq_i w'\) and \(w' \succeq_i w\), meaning that \(i\) is indifferent between \(w\) and \(w'\).

Properties of these relations can be expressed by means of modal logics. To do so we introduce modal operators \(\Diamond^{\preceq}_i\), \(\Diamond^{\prec}_i\) and \(\Diamond^{\sim}_i\) for each of the corresponding relations.

The interpretation, for \(R \in \{\preceq, \prec, \sim\}\), is as follows:

\[ M,w \models \Diamond^{R}_i \varphi\enskip \mbox{ if and only if }\enskip M,w^{\prime} \models \varphi, \mbox{ for some } w^{\prime} \mbox{ with } w R_i w^{\prime}\]

The relations in question often come with extra properties. For instance, \(\preceq_i\) is usually taken to satisfy the following:

The first two properties can be characterized in a normal modal logic with one modal operator per player, by means of the following axioms and validities.

However this is not the case for connectedness, as modal languages such as this one can only talk about local properties of relations (Blackburn et al. 2001).

To do so we need to introduce a special type of operator: the universal (or global) modality (Goranko & Passy 1992). This modality expresses properties of all the states in a domain \(W\) of a model \(M\) and it is interpreted as follows.

\[ M,w \models A\varphi \enskip\mbox{ if and only if }\enskip M,w^{\prime} \models \varphi, \mbox{ for all } w^{\prime} \in W\]

The formula \(\neg A \neg \varphi\) will be abbreviated \(E\varphi\). The symbol \(E\) is the existential dual of \(A\) and it indicates that a certain formula holds at some state in the model. With the global modality we have a genuine addition of expressivity (together with further costs and further gains, as shown in Goranko & Passy 1992), therefore we can express validity in a model by means of expressing truth in a world, witness the fact that \(M,w \models A \varphi\) holds if and only if \( \models_M \varphi\) does.

Recall that a relation \(R\) is trichotomous if and only if for all \(x,y\in W\) it is either the case that \(xRy, yRx\) or \(y=x\). We can use a combination of preference and global modalities to obtain the following frame correspondence.

An alternative and possibly more intuitive formula that can be used instead is, for \(p,q\) being atomic propositions:

\[E p \land E q \to E(p \land q) \lor E(p \land \Diamond^{\preceq}_i q) \lor E(q \land \Diamond^{\preceq}_i p)\]

Trichotomy, transitivity and reflexivity of \(\preceq_i\) are equivalent to the relation being a weak linear order, and thus being connected.

The relation \(\prec_i\), i.e., the relation of strict preference, can be defined in terms of \(\preceq_i\). But \(\prec_i\) satisfies the following property:

Irreflexivity is not definable in basic modal logic (Blackburn et al. 2001). However if the atomic propositions are powerful enough to tell each outcome apart, then irreflexivity becomes definable. For instance let \(w_k\) be a variable identifying world \(w_k\).^[4] We have the following.

Finally, the indifference relation \(\sim\) satisfies the properties of reflexivity, transitivity and symmetry. While reflexivity and transitivity are defined analogously to the previous modalities, symmetry is defined as follows.

While the axioms for the first two are similar to the ones for \(\preceq_i\), symmetry is characterized as follows

The three properties above say, together, that each \(\sim_i\) is mathematically an equivalence relation, i.e., a relation such that

\[\bigcup_{w \in W} \{[w] \mid w' \in [w] \mbox{ whenever } w \sim_i w' \}\]

is a partition of \(W\). Each element of this partition is an indifference class for player \(i\), i.e., a set of outcomes he or she is indifferent to.

The logic of equivalence relations, such as \(\sim_i\), is also known as the \({\bf S5}\) system.

Preferences and utilities Because of their widespread use in game theory, an important class of preference relations are those that correspond to numerical values, or utility functions.

A utility function is a function

\[u_i: W \rightarrow \mathbb{R}\]

mapping outcomes to real numbers, representing how much a player values a certain state.

Utility functions naturally induce preference relations, in the following sense.

Notice how every weak linear order over a finite set of outcomes corresponds to some utility function.

We refer to the related entries on preferences (Hansson & Grune-Yanoff 2011) and decision-theory (Steele & Stefansson 2015) for a more detailed analysis on the role of preferences in philosophy and decision theory.

2.2 Choices

A game is also a description of what players can achieve, on their own or within coalitions. To formalize this we use effectivity functions, an abstract model of power introduced to study voting strategies in committees (Moulin & Peleg 1982).

An effectivity function (Moulin & Peleg 1982) is a function

\[E:2^{N} \to 2^{2^{W}}\]

associating to each group of players a set of sets of outcomes.

The idea is that, whenever it is the case that \(X\in E(C)\), then coalition \(C\) is able to decide that the outcome of the game lies inside the set \(X\), and can therefore rule out the outcomes \(W \setminus X\) from being eventually chosen. In other words \(X\) is within the power of coalition \(C\).

Effectivity functions are closed under supersets, i.e., we have that \(X\in E(C)\) and \(X\subseteq Y \subseteq W\) imply that \(Y \in E(C)\). In other words, if \(X\) is within the power of coalition \(C\) then so is each of \(X\)’s supersets. From this, notice, it follows that if an effectivity function of a certain coalition is not empty then it always contains the set of all outcomes.
For \(\mathcal{X} \subseteq {2^{W}}\) we denote \(\mathcal{X}^{+}\) its superset closure.

Properties of effectivity functions can be expressed in modal logic. To do so it is important to observe that each effectivity function corresponds to a (non-normal) relation in a relational structure. So what effectivity functions do is to induce a special kind of neighborhood structure, which we refer to as Coalition Model.

As the reader will notice, dynamic effectivity functions allow each state to possibly have different power distributions among coalitions. This is strictu sensu irrelevant for the treatment of power in normal form games (Section 3), where the effectivity functions associated to outcomes could as well be taken to be equivalent everywhere in the model, but the model is general enough to treat extensive and repeated interaction, where the sequential structure of the interaction is defined explicitly. We will usually abbreviate \(E(w)(C)\) as \(E_w(C)\) or even \(E(C)\) when clear from the context.

The language used to talk about Coalition Models is Coalition Logic (Pauly 2001), a non-normal modal logic to express choices of groups of players. Coalition Logic is an extension of propositional logic with \(|2^{N}|\) modalities of the form \([C]\), so a modal operator each indexed with a coalition.

The satisfaction relation of the formulas of the form \([C]\varphi\) with respect to a pair \(M,w\) is defined as follows:

\[M,w\models [C]\varphi \enskip\textrm{if and only if}\enskip \varphi^M\in E_w(C) \]

where, \(\varphi^M = \{w\in W \mid M,w\models\varphi\}\).

Intuitively \(\varphi^M\in E_w(C)\) means that coalition \(C\) is able to achieve property \(\varphi\).

As closure under superset, or outcome monotonicity, is taken to be a property of all effectivity functions, the rule of monotonicity is valid in Coalition Logic, which is therefore a monotonic modal logic (Hansen 2003).

The rule of monotonicity takes this form for each \(C\subseteq N\):

\[\frac{\varphi \to \psi}{[C]\varphi \to [C]\psi}\]

Intuitively, if \(C\) is able to achieve \(\varphi\) and we have that \(\varphi\) implies \(\psi\), then \(C\) is also able to achieve \(\psi\).

Mathematical properties of power Apart from outcome monotonicity, many other properties can be deemed necessary to model coalitional power in games. For instance an effectivity function has the property of:

An effectivity function is called playable (Pauly 2001) if it has liveness, safety, N-maximality and superadditivity. It is called truly playable (Goranko, Jamroga, & Turrini 2013) if it is playable and well-founded. Observe that if \(W\) is finite, an effectivity function is playable if and only if it is truly playable (Goranko et al. 2013).

True playability is a fundamental property of effectivity functions, and connects one-shot coalitional games to one-shot strategic games, as will be clear later.

In neighborhood structures, relations between set-theoretical and logical properties are often immediate and standard correspondence results between class of frames and neighborhood functions (Chellas 1980) can be automatically used for Coalition Logic.

Coalition Logic is in fact expressive enough to characterize all the constraints mentioned so far.

For the proofs, consult Pauly 2001.

Correspondence results allow us to distinguish by modal means a number of class of frames. However expressivity of the modal operators strongly limit the capacity of the language to discern classes of structures. To this extent the reader should notice that the logics of both playable and truly playable effectivity frames share the fact that \(\models_F [\emptyset]\top\). However this proposition, whose interpretation is that for each \(w\in W, \{W\} \in E_w(\emptyset)\), is not sufficient to make a formal distinction between \(E_w(\emptyset)\) in the two different classes of effectivity functions.

Along these lines, the following result tells us that Coalition Logic is also good enough to reason about (or, if you prefer, too weak to distinguish) truly playable effectivity functions.

This follows from the fact that Playable Coalition Logic has the finite model property (Pauly 2001) and, in finite models, playable effectivity functions are truly playable.^[5]

As pointed out earlier on, this entry will only mention how knowledge is implicit in game structures but will not delve into the study of epistemic preconditions of rational play. Related entries devoted to epistemic logic (Hendricks & Symons 2006), dynamic epistemic logic (Baltag & Renne 2016), and in particular epistemic game theory (Pacuit & Roy 2015) explore in depth the role of knowledge in decision-making. A treatment of modal logics for games which focuses instead on the role of information is Hoek & Pauly 2006.

3. Analyzing Power

This section looks at games in which individuals or groups take their choices independently and concurrently, and, we stress once more, abstracting away from how the interaction evolves in time. It pays particular attention to the relation between players’ choices and preferences, mentioning the role of knowledge, and most importantly it deals with how to express solution concepts in a logical language.

The section first describes the general setting of cooperative games, then it considers the more restricted and possibly better-known class of strategic games.

3.1 Cooperative Games and Their Logic

The description of the game given in a relational structure of the form \((\mathcal{N}, W, \succeq, E)\) is not enough to understand which exact outcome will be chosen in the end. For that we need a solution concept, i.e., a mapping that associates to a game a set of outcomes of that game (Abdou & Keiding 1991).

A number of solution concepts have been introduced for coalitional games (see for instance Osborne & Rubinstein 1994, and Apt 2009 (Other Internet Resources)). For the present purposes we are only going to discuss what is possibly the best-known: the core. The core is a collection of stable outcomes, i.e., outcomes for which no coalition exists whose members are both able and willing to deviate from it. It can be seen as the set of outcomes to which there is no effective opposition (Abdou & Keiding 1991).

Formally, given a relational structure \(F=(\mathcal{N}, W, \succeq, E)\), an outcome \(w\in W\) is said to be stable if there is no coalition \(C\) and set of outcomes \(X\subseteq W\) such that both of the following conditions are satisfied:

1. \(X \in E(C)\)
2. \(y \in X\) and \(i\in C\) implies that \(y \succ_i w\)

In words, an outcome is stable if there is no group of individuals that can achieve an alternative that they all strictly prefer.

The core is the collection of all stable outcomes.

Modal logic can be used to represent the core. Consider first the formula

\[p \rightarrow \bigvee_{C\subseteq N} [C]\left(\bigwedge_{i\in C}\Diamond^\succ_i p\right)\]

This says that if \(p\) is true then members of some coalition can improve upon some \(p\) world, which does not seem the right formula to express stability in logic. However we can prove the following results, which utilizes the correspondence between the formula and a specific class of frames.

Let \(E\) be an (outcome monotonic) effectivity function and let \(\succeq_i\) a weak linear order. Then:

\[(F,V'), w \models p \rightarrow \bigvee_{C\subseteq N} [C]\left(\bigwedge_{i\in C}\Diamond^\succ_i p\right)\]

holds at \(w\) for each \(V'\) if and only there exists a \(C\subseteq N\) and \(X \in E_w(C)\) such that, for all \(i\in C\), \(x\in X\) we have that \(x \succ_i w\).

So the formula holds at \(w\) for each valuation if and only if \(w\) does not belong to the core. Clearly, if the formula is false at an outcome and some valuation, then this means that the outcome does belong to the core.

Notice that, since effectivity functions are outcome monotonic, if we have that \(X \in E_w(C)\) and

\[X \subseteq \left(\bigwedge_{i\in C} \Diamond^\succ_i p\right)^{(F,V')},\]

then

\[\left(\bigwedge_{i\in C} \Diamond^\succ_i p\right)^{(F,V')} \in E_w(C).\]

Also notice that the result above allows for the case of

\[\emptyset=\left(\bigwedge_{i\in C}\Diamond^\succ_i p\right)^{M} \in E_w(C),\]

which might be counterintuitive. Requiring \(E\) to have liveness takes care of this.

Notice also how we had to impose a universal quantification on the set of valuations. Without this explicit quantification, the formula would only hold for one specific model, which would not be an appropriate solution. If instead we are only interested in knowing whether there exists some outcome that is stable or, conversely, whether the core is empty, it is sufficient to require the formula above to be an axiom. This would amount to say that no outcome is stable, i.e., that the core is empty.

Again, liveness would take care of the trivial case in which

\[\left(\bigwedge_{i\in C}\Diamond^\succ_i p\right)^{(F,V)}=\emptyset.\]

An alternative approach is to identify each outcome with a name (or nominal) in the language, i.e., to use a hybrid logic. Then we have the following.

So depending on the properties we are interested in, different extensions of basic modal logic combined with different forms of validity (at a world vs model vs frame) are best-suited to express them.

3.2 Strategic Games and Their Logic

Normal form games, or strategic games, are a representation of what individuals, rather than coalitions, can achieve, and what their preferences are.

Formally, a strategic game form is a tuple

\[(N, W, \{\Sigma_i\}_{i\in N}, o)\]

where N is a finite set of players, \(W\) a set of outcomes, \(\{\Sigma_i\}_{i\in N}\) a collection of strategies, one for each player \(i\), \(o: \prod_{i\in N} \Sigma_i \to W\) an outcome function, associating a tuple of strategies to an outcome.

A strategic game is a tuple \((S,\{\succeq_i\}_{i\in N})\), where \(S\) is a strategic game form and \(\{\succeq_i\}_{i\in N}\) a collection of preference relations, one for each player \(i\).

Looking at the unified treatment of our example, there seem to be relationship between normal form games and coalitional games. This relationship can be specified formally.

Let us first consider what a group of players can do in a normal form game. To do so we define the \(\alpha\)-effectivity function, a mathematical description of coalitional strategies in a game in terms of the sets outcomes that they can force.

Intuitively the \(\alpha\)-effectivity function of \(S\) collects, for every group of players, the set of outcomes that they can achieve by fixing a strategy of theirs, no matter how their opponents play.

The following result shows the relationship between strategies and effectivity functions.

This is a generalization of the result in Peleg 1998 for finite games, starting from models of strategic games first defined in Pauly 2001. In a nutshell what these results imply is the following.

In the same way we did for cooperative games, we can ask ourselves whether an outcome is stable, or rational, in a strategic situation.

Nash equilibrium and definability The main solution concept to analyze strategic games is Nash equilibrium. Informally a Nash equilibrium is a collection of strategies, one per player, such that no player is interested to change his or her strategy, given the others stick to theirs. Formally, a strategy profile \(\sigma\) is a (pure strategy) Nash equilibrium if for all players \(i\in N\) and for all \(\sigma'_i\in \Sigma_i\) we have that

\[o(\sigma_i,\sigma_{-i}) \succeq_i o(\sigma'_i,\sigma_{-i})\]

How to express Nash equilibria in logic? Recall how the formula

\[p\to \bigvee_{C\subseteq N} [C]\left(\bigwedge_{i\in C}\Diamond^\succ_i p\right)\]

holds at a frame \(F\) if and only if the core is empty, and a hybrid logic extension can tell us whether a specific outcome belongs to the core. If \(F\) is based on a truly playable effectivity function we already have a normal form game version of the core: an outcome such that no coalition is together able and willing to deviate from, not taking into account what the others do. However Nash Equilibrium fixes a profile of strategies, such that no player is able and willing to deviate from there. In other words it requires the notion of best response for a player with respect to a given profile.

Formalisms such as Coalition Logic are too weak to express Nash equilibria. However, they can express the fact that certain effectivity functions allow for the possibility of a Nash equilibrium. This is what in Hansen & Pauly 2002 is called Nash-consistent Coalition Logic. Nash Equilibrium is in fact not definable in basic modal logic (Benthem et al. 2011), but it can be done with a modality that intersects both the preference and the choice relations (Benthem et al. 2011).

Then the best response for \(i\) is defined as \( \langle \approx_i \cap \succ_i \rangle \top\), as there is no alternative that is at the same time achievable and preferable to \(i\). Alternatively a hybrid logic that mentions strategy profiles in the language can provide a solution, similarly to the case of the core.

3.2.1 Non-monotonic Action Logics

Some logics exploit a more compact representation of those relational structures that correspond to strategic games.

Rather than using effectivity functions, each player \(i\) is associated with an equivalence relation \(\approx_i \subseteq W\times W\), whose induced partition represent the choices he or she can perform. These equivalence relations describe the exact set of choices that a group of players can perform and the originating models are referred to as consequentialist in the literature (see for instance Belnap, Perloff, & Ming 2001).

Now define an effectivity function \(E^{*}\) for which it holds that

\[E^{*}(i)= \{[x] \mid x' \in [x] \mbox{ whenever } x \approx_i x' \}^{+}\]

Intuitively \(E^{*}(i)\) collects what exactly the individuals can achieve and all their supersets.

\(E^{*}\) is called consequentialist if holds that:

• \(E^{*}(C)= \{\bigcap_{i\in C} X_i \mid \mbox{for some } X_i \in E^{*}(i)\}\)
• \(\emptyset\not\in E^{*}(C)\) for each \(C\neq N\)
• \(E^{*}(N) = \{\{x\} \mid x \in W\}^{+}\)

Notice that \(E^*\) is a truly playable effectivity function.

The last property is well-foundedness, as in the case of arbitrary effectivity functions. This is not a property that is assumed in all variants, e.g., the choice structures in Kooi & Tamminga 2008 and its temporal variant STIT (Belnap et al. 2001) do not. However, as observed in Turrini 2012 and Tamminga 2013, well-founded consequentialist models correspond to strategic games and the effectivity function \(E\) can be effectively simulated by the equivalence relation \(\approx_i\) for each player. Intuitively \(E^{*}(i)\) is the set of sets of outcomes that \(i\) can choose without being able to refine further.

To reason about consequentialist models, we use so-called consequentialist logics, i.e., propositional logic extended with modalities of the form \([C]\varphi\), interpreted as follows:

\(M,w \models [C]\varphi\) if and only if \(M,w'\models \varphi\) for all \(w'\) such that \(w (\bigcap_{i \in C} \approx_i)w'\)

Consequentialist logics have been developed to reason about action and consequence, and have interesting applications in deontic logic, such as Kooi & Tamminga 2008; Tamminga 2013; Turrini 2012. They are moreover the basis of temporal logics of strategy such as STIT and strategic STIT, discussed later. A special case are the logics of propositional control (Hoek & Wooldridge 2005; Troquard, Hoek, & Wooldridge 2009).

3.2.2 Logic-Based Games

In many situations agents have control over certain propositional variables (Hoek & Wooldridge 2005), for instance they can be responsible for traffic flow or they can veto a certain issue. Variables can also be shared (Gerbrandy 2006), an example being voting, where players share control over a variable whose realization is determined by a certain aggregation function, e.g., majority (Troquard, Hoek, & Wooldridge 2011). These logics of propositional control specify what propositions agents have in their effectivity function. For instance, if agent \(i\) controls \(p\), then both \(p^{M}\) and \(\neg p^{M}\) are in his or her effectivity function. In a way these models are very special types of effectivity function, and what agents control can be seen as a choice, or a strategy, available to them.

Logics for propositional control have modalities of the type \([[i]]\varphi\), meaning that player \(i\) has a “control” strategy to see to it that, no matter how the other agents choose their control strategies, then \(\varphi\) holds in the end. But they also have modalities of the type \([[C]]\varphi\), meaning that players in \(C\) have a joint control strategy ensuring \(\varphi\) in the end. A strategy profile is thus equivalent to a valuation function, which assigns a truth value of every proposition available. In turn, a strategy of a player \(i\) can thus be seen as a partial valuation function, that assigns a truth value only to the propositions controlled by \(i\).

Slightly abusing notation, we say that a valuation \(V\) satisfies a formula \(\varphi\), denoted \(V \models \varphi\), whenever it makes \(\varphi\) true under the current assignment of propositions. In other words, propositional control games are played in one single world, and the individual assignments determine what propositions are true are that world. Denoting \(\mathcal{V}\) the set of all valuations and \(\mathcal{V}_i\) to the partial ones under the control of \(i\) we have the following.

\((F,V) \models [[C]]\varphi\) if and only if for all \(i \in C\), there exists \(V'_i \in \mathcal{V}_i\) such that, for all \(k \in \overline{C}, V'_{k}\in \mathcal{V}_k\), we have that \((F,V')\models \varphi\)

So when \([[C]]\varphi\) holds, coalition \(C\) can play a control strategy in such a way that no matter what the control strategy is that their opponents play, the resulting outcome satisfies \(\varphi\).

Logics for propositional control can be extended to goal-based formalisms, the so called Boolean games (Harrenstein, van der Hoek, Meyer, & Witteveen 2001): propositions are partitioned among the players, with each player controlling the set of propositions he or she is assigned to. On top of that each player is also assigned a formula of propositional logic which is meant to be his or her goal and whose realization might not only depend upon the choices he or she is able to make.

Boolean games have been extensively studied in the field of multi-agent systems, as simple and compact models to represent strategic interaction in a logic-based setting (Dunne & Hoek 2004; Dunne & Wooldridge 2012; Dunne, Hoek, Kraus, & Wooldridge 2008).

In their most general variants they are an extension of logics with propositional control, where each agent is assigned a goal formula. The goal formula is a satisfiable formula of the language and the important feature is that the goal of each agent does not need to be under his or her control.

For instance, agent \(i\) may be assigned the control of proposition \(p\) only, but might have the goal that \(p \leftrightarrow q\). So whether \(i\)’s goal is satisfied depends not only on \(i\) setting proposition \(p\) to be true, but also some other agent, say \(j\), setting proposition \(q\) to be true. Agent \(j\), on the other hand, might or might not be interested in having \(q\) set to true. For instance he or she may want proposition \(r\) to be true, and therefore being indifferent to whether \(q\) or \(\overline{q}\) is realized in the end. Or might even have the goal that \(\overline{q}\).

In Boolean games some objectives can be realized all together, for instance agents might all want \(p \vee \neg q\) to be true, or it might be the case that certain valuations do not realize the objectives of all agents, but no unhappy agent is able to improve his or her own situation by changing the assignment to the propositional variables he or she controls. This situation is a very simple form of Nash equilibrium that can be expressed in Boolean games.

So, for \(\gamma_i\) being the objective of player \(i\) and \(v_i\) a partial valuation that is under control of player \(i\), we say that valuation \(v\) is a Nash equilibrium if we have that for each \(i\) and each \(v'_i\).

\[(v_i,v_{-i}) \not\models\gamma_i \mbox{ implies that } (v'_i,v_{-i}) \not\models\gamma_i\]

So if \(v\) does not satisfy \(i\)’s goal, there is nothing \(i\) can do to satisfy it.

The analysis of Nash equilibria in Boolean game shows a close correspondence between these games and propositional logic: using a reduction to the satisfiability problem of propositional logic formulas, the problem of checking whether an outcome \(v\) is a Nash equilibrium of a Boolean game is co-NP complete (Wooldridge, Endriss, Kraus, & Lang 2013).

4. Conclusions: On the Right Level of Analysis

Recall the very first example, in which the set of outcomes of a voting game could be described only considering the overall outcome of the vote or by explicitly describing what each of the Countries had voted.

Often times, when describing mathematical structures by succinct languages we are confronted with the question of which one is the most suitable language. Some are able to express preferences, knowledge and coalitional ability all together, some others only about two of them, some others about only one. Finally some languages might only be able to express what individuals, and not coalitions, can achieve.

Again, there is no right answer to this question. It all depends on what the fundamental characteristics are that one is trying to model. To express Nash equilibria in a coordination game, there is no need for a temporal logic-based formalism. On the contrary, if one wants to express backwards induction, then a language that does not make the sequential structure of the decision problem explicit is probably not the right one.

Going back to our example, some Countries might have preferences over how other Countries vote, and this might affect their decision-making, changing the overall equilibrium points of the game. If this is the case then the richer language matters. Otherwise, if we can safely rule out this possibility, the more succinct language seems to be the appropriate choice.

Bibliography

• Abdou, Joseph and Hans Keiding, 1991, Effectivity Functions in Social Choice, (Theory and Decision Library 8), Dordrecht: Springer Netherlands, doi:10.1007/978-94-011-3448-4
• Baltag, Alexandru and Bryan Renne, 2016, “Dynamic Epistemic Logic”, in Stanford Encyclopedia of Philosophy, (Winter 2016 Edition), Edward N. Zalta (ed.), URL = <https://plato.stanford.edu/archives/win2016/entries/dynamic-epistemic/>
• Belnap, Nuel, Michael Perloff, and Ming Xu, 2001, Facing the Future: Agents and Choices in Our Indeterminist World, Oxford: Oxford University Press.
• Benthem, Johan van, 2014, Logic in Games, Cambridge, MA: MIT Press.
• Benthem, Johan van, Eric Pacuit, and Olivier Roy, 2011, “Toward a Theory of Play: A Logical Perspective on Games and Interaction”, Games, 2(1): 52–86. doi:10.3390/g2010052
• Blackburn, Patrick, Maarten de Rijke, and Yde Venema, 2001, Modal Logic, Cambridge: Cambridge University Press. doi:10.1017/CBO9781107050884
• Chellas, Brian, 1980, Modal Logic: An Introduction, Cambridge: Cambridge University Press.
• Dalen, Dirk van, 1980, Logic and Structure, Berlin: Springer-Verlag. doi:10.1007/978-3-662-02962-6
• Dunne, Paul E. and Wiebe van der Hoek, 2004, “Representation and Complexity in Boolean Games”, in José Júlio Alferes & João Alexandre Leite (eds.), Logics in Artificial Intelligence, 9th European Conference, JELIA 2004, Lisbon, Portugal, September 27–30, 2004, Proceedings, Berlin, Heidelberg: Springer, 3229: 347–359. doi:10.1007/978-3-540-30227-8_30
• Dunne, Paul E. and Michael Wooldridge, 2012, “Towards Tractable Boolean Games”, in Wiebe van der Hoek, Lin Padgham, Vincent Conitzer, & Michael Winikoff (eds.), Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems, (AAMAS 2012), Valencia, Spain, June 4–8, 2012, Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems, vol. 2, pp. 939–946.
• Dunne, Paul E., Wiebe van der Hoek, Sarit Kraus, and Michael Wooldridge, 2008, “Cooperative Boolean Games”, in Lin Padgham, David C. Parkes, Jörg P. Müller, & Simon Parsons (eds.), Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems, (AAMAS 2008), Estoril, Portugal, May 12–16, 2008, Richland, SC: International Foundation for Autonomous Agents and Multiagent System, vol. 2, pp. 1015–1022.
• Garson, James, 2014, “Modal Logic”, in Stanford Encyclopedia of Philosophy, (Spring 2016 Edition), Edward N. Zalta (ed.), URL = <https://plato.stanford.edu/archives/spr2016/entries/logic-modal/>.
• Gerbrandy, Jelle, 2006, “Logics of Propositional Control”, in Hideyuki Nakashima, Michael P. Wellman, Gerhard Weiss, & Peter Stone (eds.), Proceedings of the 5th International Joint Conference on Autonomous Agents and Multiagent Systems, (AAMAS 2006), Hakodate, Japan, May 8–12, 2006, New York: ACM, pp. 193–200. doi:10.1145/1160633.1160664
• Goranko, Valentin and Salomon Passy, 1992, “Using the Universal Modality: Gains and Questions”, Journal of Logic and Computation, 2(1): 5–30. doi:10.1093/logcom/2.1.5
• Goranko, Valentin, Wojciech Jamroga, and Paolo Turrini, 2013, “Strategic Games and Truly Playable Effectivity Functions”, Autonomous Agents and Multi-Agent Systems, 26(2): 288–314. doi:10.1007/s10458-012-9192-y
• Hansen, Helle Hvid, 2003, Monotonic Modal Logics, Master Thesis, Universiteit van Amsterdam.
• Hansen, Helle Hvid and Marc Pauly, 2002, “Axiomatising Nash-Consistent Coalition Logic”, in Sergio Flesca, Sergio Greco, Nicola Leone, & Giovambattista Ianni (eds.), Logics in Artificial Intelligence, Berlin: Springer, 2424: 394–406. doi:10.1007/3-540-45757-7_33
• Hansen, Helle Hvid, Clemens Kupke, and Eric Pacuit, 2009, “Neighbourhood Structures: Bisimilarity and Basic Model Theory”, Logical Methods in Computer Science, 5(2): lmcs:1167. [Hansen, Kupke, & Pacuit 2009 available online]
• Hansson, Sven Ove and Till Grune-Yanoff, 2011, “Preferences”, in Stanford Encyclopedia of Philosophy, (Fall 2011 Edition), Edward N. Zalta (ed.), URL = >https://plato.stanford.edu/archives/fall2011/entries/preferences/>
• Harrenstein, Paul, Wiebe van der Hoek, John-Jules Meyer, and Cees Witteveen, 2001, “Boolean Games”, in Johan van Benthem (ed.), Proceedings of the 8th Conference on Theoretical Aspects of Rationality and Knowledge, (Tark ’01), San Francisco: Morgan Kaufmann, pp. 287–298.
• Hendricks, Vincent and John Symons, 2006, “Epistemic Logic”, in Stanford Encyclopedia of Philosophy, (Spring 2006 Edition), Edward N. Zalta (ed.), URL = <https://plato.stanford.edu/archives/spr2006/entries/logic-epistemic/>
• Hodges, Wilfrid, 2013, “Logic and Games”, in Stanford Encyclopedia of Philosophy, (Spring 2013 Edition), Edward N. Zalta (ed.), URL = <https://plato.stanford.edu/archives/spr2013/entries/logic-games/>.
• Hoek, Wiebe van der and Marc Pauly, 2006, “Modal Logic for Games and Information”, in Patrick Blackburn, Johan van Benthem, & Frank Wolter (eds.), Handbook of Modal Logic, pp. 1077–1148, Elsevier.
• Hoek, Wiebe van der and Michael Wooldridge, 2005, “On the Logic of Cooperation and Propositional Control”, Artificial Intelligence, 164(1–2): 81–119. doi:10.1016/j.artint.2005.01.003
• Kooi, Barteld and Allard Tamminga, 2008, “Moral Conflicts Between Groups of Agents”, Journal of Philosophical Logic, 37(1): 1–21. doi:10.1007/s10992-007-9049-z
• Kracht, Marcus and Frank Wolter, 1999, “Normal Monomodal Logics Can Simulate All Others”, Journal of Symbolic Logic, 64(1): 99–138. doi:10.2307/2586754
• Moulin, Herve and Bezalel Peleg, 1982, “Cores of Effectivity Functions and Implementation Theory”, Journal of Mathematical Economics, 10(1): 115–145. doi:10.1016/0304-4068(82)90009-X
• Osborne, Martin and Ariel Rubinstein, 1994, A Course in Game Theory, Cambridge, MA: MIT Press.
• Pacuit, Eric and Olivier Roy, 2015, “Epistemic Foundations of Game Theory”, in Stanford Encyclopedia of Philosophy, (Spring 2015 Edition), Edward N. Zalta (ed.), URL = <https://plato.stanford.edu/archives/spr2015/entries/epistemic-game/>
• Pauly, Marc, 2001, Logic for Social Software, Ph.D. thesis, University of Amsterdam. [Pauly 2001 available online]
• Peleg, Bezalel, 1998, “Effectivity Functions, Game Forms, Games and Rights”, Social Choice and Welfare, 15(1): 67–80. doi:10.1007/s003550050092
• Steele, Katie and Orri Stefansson, 2015, “Decision Theory”, in Stanford Encyclopedia of Philosophy, (Winter 2015 Edition), Edward N. Zalta (ed.), URL = <https://plato.stanford.edu/archives/win2015/entries/decision-theory/>
• Tamminga, Allard, 2013, “Deontic Logic for Strategic Games”, Erkenntnis, 78(1): 183–200. doi:10.1007/s10670-011-9349-0
• Troquard, Nicolas, Wiebe van der Hoek, and Michael Wooldridge, 2009, “A Logic of Games and Propositional Control”, in Carles Sierra, Cristiano Castelfranchi, Keith S. Decker, & Jaime Simão Sichman (eds.), Proceedings of the 8th International Joint Conference on Autonomous Agents and Multiagent Systems, (AAMAS 2009), Budapest, Hungary, May 10–15, 2009, Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems, vol. 2, pp. 961–968.
• –––, 2011, “Reasoning About Social Choice Functions”, Journal of Philosophical Logic, 40(4): 473–498. doi:10.1007/s10992-011-9189-z
• Turrini, Paolo, 2012, “Agreements as Norms”, in Thomas Ågotnes, Jan Broersen, & Dag Elgesem (eds.), Deontic Logic in Computer Science: 11th International Conference, (DEON 2012), Bergen, Norway, July 16–18, 2012, Berlin: Springer, 7393: 31–45. doi:10.1007/978-3-642-31570-1_3
• Wooldridge, Michael, Ulle Endriss, Sarit Kraus, and Jérôme Lang, 2013, “Incentive Engineering for Boolean Games”, Artificial Intelligence, 195: 418–439. doi:10.1016/j.artint.2012.11.003

Academic Tools

	How to cite this entry.
	Preview the PDF version of this entry at the Friends of the SEP Society.
	Look up this entry topic at the Internet Philosophy Ontology Project (InPhO).
	Enhanced bibliography for this entry at PhilPapers, with links to its database.

Other Internet Resources

• Apt, Krzysztof, 2009, “Cooperative Games”, Course Notes, Centrum Wiskunde & Informatica, Amsterdam.
• Logic in Action

Related Entries

decision theory | game theory: epistemic foundations of | logic: and games | logic: dynamic epistemic | logic: epistemic | logic: modal | preferences

Acknowledgments

The author wishes to thank the anonymous reviewers and Valentin Goranko for the very constructive comments on earlier versions of the manuscript.