This entry discusses the use of mathematical languages to express andanalyze the formal properties of power in games. The mathematicallanguages discussed in this entry will be referred to aslogics, and classified according to their ability toexpress game-related concepts.

The material in this entry will be limited to the logical analysis ofstrategies and preferences of (groups of) individuals in cooperativeand non-cooperative normal form games. It will not cover the use ofgame theory to study logical languages nor the role of epistemicconcepts in strategic decisions. It will also not cover aspects ofsequential decisions-making, typical of strategic reasoning inextensive games. An account of those can be found in the relatedentrieslogic and games,epistemic foundations of game theory (see also van Benthem, Pacuit, & Roy 2011 and vanBenthem 2014).

• 1. The Logic Underneath Games
• 2. The Basic Ingredients
  • 2.1 Preferences
  • 2.2 Choices
• 3. Analyzing Power
  • 3.1 Cooperative Games and Their Logic
  • 3.2 Non-cooperative Games and Their Logic
    • 3.2.1 Injective Games and PDL with Intersection
    • 3.2.2 Non-monotonic Action Logics
    • 3.2.3 Quantified and Higher-Order Coalition Logic
    • 3.2.4 Probabilities and Resource Bounds
    • 3.2.5 Conditional Power and Coordination
    • 3.2.6 Dynamic Coalition Logic
    • 3.2.7 Logic-Based Games
• 4. Conclusions: On the Right Level of Analysis
• Bibliography
• Academic Tools
• Other Internet Resources
• Related Entries

1. The Logic Underneath Games

Agame is a mathematical description of the relationbetween a set ofindividuals (or groups ofindividuals) and a set of potentialoutcomes.Individuals choose,independently and concurrently, asubset of the outcomes, with the final outcome being selected from thecombination of each choice.Independently means thatindividuals’ choices do not influence one another.Concurrently means that each individual’s choices aretaken not knowing the other players’ choices. Each individual isassumed to have a preference over the set of outcomes, i.e., he or shelikes some outcomes more than others, and typically assumed to knowthe other individuals’ potential choices and preferences,adjusting their decisions accordingly.

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

Depending on players’ preferences, knowledge and capabilitiessome outcomes will be more likely to be chosen. In order to understandwhich ones, game theory has devised solution concepts, formallyfunctions from the set of games to the set of outcomes in each ofthese games, which describe players’ rationality in mathematicalterms. Solution concepts, as we will see later, can be succinctlyexpressed in simple and well-behaved logics.

Next we describe games as mathematical structures, emphasizing variouskey ingredients (e.g., the possibility of forming coalitions, thepossibility to take decisions in time etc.) and the best suitedlanguages 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 \}\).

Example 2. In the example above the set of playersN is {France, Germany, Italy, Belgium, The Netherlands,Luxembourg}. If we consider the issueadoptionof border-protection scheme, there are two outcomes: yes andno, i.e., \(W = \{\mbox{yes, no}\}\). If we instead consider the issuemillions spent on border-protectionscheme there is a potentially infinite outcome space, i.e., \(W= \{\textrm{0M}, \textrm{1M}, \textrm{2M}, \ldots \}\). It is possibleto have a set of outcomes that is even refined further, for instancespecifying the way players have voted. In this case the outcome inwhich France votes yes, the others vote no, and the result is no,would be different from the outcome in which Italy votes yes, theothers vote no, and the result is no, although the result of the voteis the same. What is important to emphasize is that each set ofoutcomes comes with alevel of description of what ishappening in the underlying interaction. There is no a priori right orwrong level of description, the choice depends on the properties ofthe game that one is interested in.

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

• apreference relation, denoted \(\succeq\),describing players’ preferences over outcomes;
• anaction relation, denoted \(E\), describing theoutcomes that players or groups of players are able to impose or,conversely, rule out;

An important relation in games is knowledge, which formally describeswhat players know of the game and their opponents. This relation issometimes given explicitly, other times left implicit. The presententry will not make the relation explicit, but will rather incorporateit in the formalization of players’ rationality.

Both the preference and the action relations collect families ofindividual relations, one per player. The preference relation, forinstance, 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

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

This mathematical structure is also known as arelationalstructure (Blackburn, Rijke, & Venema 2001), which (in acertain sense) is a set-theoretic equivalent of a so-calledmodal logic (Blackburnet al. 2001), amathematical language that is well-suited to express the mathematicalproperties of relations. A relational structure will henceforth bedenoted \(F\), which stands forframe.

The last ingredient that we need, in order to link relationalstructures and modal logics, is the specification of a set of atomicpropositionsAtoms, which expresses therelevant properties of the outcomes we are interested in. This set isusually taken to be countable^[1] and is associated to outcomes by means of avaluationfunction, i.e., a function of the form

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

A tuple \((F,V)\) will be referred to asmodel, whichwill be denoted \(M\).

The relations in a game structure, which are relative to individualplayers (and groups), will formally be described in connection withthe main modal logics used to express their properties, at differentlevels of description and granularity.

The following paragraph collects the background technical notionsneeded to interpret the modal languages used in this entry. The readeralready acquainted with modal logic can skip it. For a more in depthexploration one can consult the related entry onmodal logic. Well-known classic textbooks areModal Logic: AnIntroduction (Chellas 1980), which focuses on non-normal modallogics, andModal Logic (Blackburnet 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 ofworlds orstates oroutcomes \(W\); anaccessibility relation \(R_i\) for each modaloperator \(\Box_i\)which we here assume are so-called neighborhoodfunctions (Chellas 1980), i.e., functions \(R_i: W \to 2^{2^{W}}\);and avaluation function \(V: \texttt{Atoms} \to2^{W}\), which assigns to each atomic proposition a subset of \(W\),with the idea that each atomic proposition is assigned to the set ofworlds 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 thefunction \(f\) associates to each modality its intuitive shorthand.Let \(\Delta\) be a modal language with modalities \(\Box_1\),…, \(\Box_n\), … and let \(M = ((W, R_1, \ldots, R_n,\ldots), V )\) be a model for this language. Thesatisfactionrelation of a formula \(\varphi \in \Delta\) with respect toa pair \((M,w)\), where \(w \in W\), is defined according to thefollowing truth conditions:

where \(\varphi^{M}=\{w \in W \mid M,w \models \varphi\}\) is calledthetruth set or theextension of\(\varphi\).

A formula \(\varphi\) of a modal language:holds at astate \(w\) of model \(M\) whenever \(M,w \models \varphi\);isvalid in a model \(M\), denoted \(\models_{M}\varphi\), if and only if \(M,w \models \varphi\) for every \(w \inW\), where \(W\) is the domain of \(M\); isvalid in a classof models \(\mathcal{M}\), denoted \(\models_{\mathcal{M}}\varphi\), if and only if it is valid in every \(M \in \mathcal{M}\);isvalid in a frame \({F}\) (a model without avaluation function), denoted \(\models_{{F}} \varphi\), if and only iffor every valuation \(V\) we have that \(\models_{(F,V)} \varphi\); isvalid 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}\).

We can view amodal logic as the set of formulas\(\Delta_{\mathcal{M}}\)(\(\Delta_{\mathcal{F}}\)) that are valid in agiven class of models \(\mathcal{M}\) (frames \(\mathcal{F}\)). For aset of formulas \(\Sigma\), we write \(M,w \models \Sigma\) to saythat \(M,w \models \sigma\), for all \(\sigma\in \Sigma\). We say thata set of formulas (globally)semantically entails aformula \(\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\). When \(\mathcal{F}\) is a class of frames, \(\Sigma\models_{\mathcal{F}} \phi\) means that \(\Sigma \models_{\mathcal{M}}\phi\) where \(\mathcal{M}\) is the set of models based on frames in\(\mathcal{F}\).

A modal rule

issound 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\) iscalledclassical if it is closed under the rule ofequivalence, i.e., for each \(\Box\) in the language we have:

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

It is callednormal if it is monotonic, it is closedunder the rule of generalization and contains the \(K\) axiom, i.e.,for each \(\Box\) we have

and \(\Delta\) contains all instances of \(\Box(\varphi \to \psi) \to(\Box \varphi \to \Box \psi)\).

When \( R_i\) is a principal filter^[3], we say that we say that the modality \(\Box_i\) isnormal. In that case \(R_i\)can equivalently be representedas a relation of the form \(R_i: W \to 2^{W}\), and then we have that\(M,w \models \Box_i \phi\) if and only if \(M,v \models \phi\) forall \(v \in W\) such that \(wR_iv\). Anormal modal logic canbe interpreted in structures of the form \(M = ((W, R'_1, \ldots,R'_n, \ldots), V)\)where every \(R'_i\) is a principal filter.

2.1 Preferences

Recall the relational structure \((\mathcal{N},W, \succeq, E)\) andconsider the relation \(\succeq\). This relation compactly representsa family \(\{\succeq_i\}_{i\in N}\) of individual preference relationseach indexed with a player.

Formally, apreference for player \(i\) is arelation

The idea is that if two outcomes \(w\) and \(w'\) are such that\((w,w')\in \succeq_i\) then player \(i\) considers outcome \(w\) atleast 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\) isindifferent between \(w\) and \(w'\).

Example 3. Let us go back to our main example.Typically Countries have preferences over the outcome of the decision,e.g., Italy think we should spend between 5 and 10 million euros forthe scheme, Germany think we should spend between 1 and 2, Belgiumbetween 4 and 5, Luxembourg, The Netherlands and France exactly 5.This means, for instance, that Italy’s preference relation issuch that \(w \succ_{\textrm{Italy}} w'\) whenever \(\textrm{5M} \leqw \leq \textrm{10M}\) and either \(w'>\textrm{10M}\) or \(0\leqw'<\textrm{5M}\). What about all other couples of outcomes? In thesimplest case Italy are indifferent between them. So \(w\sim_{\textrm{Italy}} w'\), otherwise. However, we could also assume amore complex preference. For instance, Italy would like to spend asmuch money as possible within their desired budget. In this case thepreference relation is: \(w \succ_{\textrm{Italy}} w'\) whenever\(\textrm{5M} \leq w \leq \textrm{10M}\) and either\(w'>\textrm{10M}\) or \(0\leq w'<\textrm{5M}\), \(w\succ_{\textrm{Italy}} w'\) whenever \(\textrm{5M} \leq w' < w \leq\textrm{10M}\) while \(w \sim_{\textrm{Italy}} w'\), otherwise. Notall outcomes of a vote are going to reach an agreement. We then, fortechnical purposes, define an auxiliary outcome \(w^{*}\), interpretedas a disagreement outcome. The idea is that this is an outcome of thevote that does not reach any consensus. We assume that any agreementis strictly better for any player than disagreement, i.e., \(w\succ_{{i}} w'\) whenever \(w'=w^{*}\) and \(w\neq w^{*}\), for each\(i\in N\).

Properties of these relations can be expressed by means of modallogics. To do so we introduce modal operators\(\Diamond^{\preceq}_i\), \(\Diamond^{\prec}_i\) and\(\Diamond^{\sim}_i\) for each of the corresponding relations, and wecan view a relational structure as a modal logic frame with therelation \(\preceq_i\) interpreting \(\Diamond^{\preceq}_i\) and soon.

The interpretation in a model \(M\) based on such a frame, for \(R \in\{\preceq, \prec, \sim\}\), is then as follows (note that thesemodalities are normal):

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

The first two properties can be characterized by means of thefollowing axioms and validities.

However this is not the case for connectedness, as modal languagessuch as this one can only talk aboutlocal properties ofrelations (Blackburnet al. 2001).

To characterize connectedness we need to introduce a special type ofoperator: the universal (or global) modality (Goranko & Passy1992). This modality expresses properties of all the states in adomain \(W\) of a model \(M\) and it is interpreted as follows.

The formula \(\neg A \neg \varphi\) will be abbreviated \(E\varphi\).The symbol \(E\) is the existential dual of \(A\) and it indicatesthat a certain formula holds at some state in the model. With theglobal modality we have a genuine addition of expressivity (togetherwith further costs and further gains, as shown in Goranko & Passy1992), therefore we can express validity in a model by means ofexpressing 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\). Wecan use a combination of preference and global modalities to obtainthe following frame correspondence.

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

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

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

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

Finally, the indifference relation \(\sim\) satisfies the propertiesof reflexivity, transitivity and symmetry. While reflexivity andtransitivity 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\) ismathematically anequivalence relation, i.e., arelation such that

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

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

Preferences and utilities: Because of theirwidespread use in game theory, an important class of preferencerelations are those thatcorrespond to numerical values, orutility functions.

Autility function is a function

mapping outcomes to real numbers, representinghow much aplayer values a certain state.

Utility functions naturally induce preference relations, in thefollowing sense.

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

We refer to the related entries onpreferences anddecision-theory for a more detailed analysis on the role of preferences in philosophyand decision theory.

2.2 Choices

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

Aneffectivity function (Moulin & Peleg 1982) isa function

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)\), thencoalition \(C\) is able to decide that the outcome of the game liesinside the set \(X\), and can therefore rule out the outcomes \(W\setminus X\) from being eventually chosen. In other words \(X\) iswithin the power of coalition \(C\).

Effectivity functions of games areclosed undersupersets, i.e., we have that \(X\in E(C)\) and \(X\subseteqY \subseteq W\) imply that \(Y \in E(C)\). In other words, if \(X\) iswithin the power of coalition \(C\) then so is each of \(X\)’ssupersets. From this, notice, it follows that if an effectivityfunction of a certain coalition is not empty then it always containsthe 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 adynamiceffectivity function, essentially an effectivity function in eachstate of the model, corresponds to a (non-normal) relation in arelational structure. So what effectivity functions do is to induce aspecial kind of neighborhood structure, which we refer to asCoalition Model.

Acoalition frame is a model without the valuation function.Coalition models are, of course, relational game structures indisguise. As the reader will notice, dynamic effectivity functionsallow each state to possibly have different power distributions amongcoalitions. This isstrictu sensu irrelevant for thetreatment of power in games (Section 3), where the effectivity functions associated to outcomes could as wellbe taken to be equivalent everywhere in the model, but the model isgeneral enough to treat extensive and repeated interaction, where thesequential structure of the interaction is defined explicitly. We willusually abbreviate \(E(w)(C)\) as \(E_w(C)\) or even \(E(C)\) whenclear from the context.

The language used to talk about Coalition Models isCoalitionLogic (Pauly 2001), a non-normal modal logic to expresschoices of groups of players. Coalition Logic is an extension ofpropositional 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:

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

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

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

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

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 outcomemonotonicity, many other properties can be deemed necessary to modelcoalitional power in games. For instance an effectivity functiontypically has the following properties:

An effectivity function is calledplayable (Pauly2001) if it has liveness, safety,N-maximality andsuperadditivity. It is calledtruly playable(Goranko, Jamroga, & Turrini 2013) if it is playable andwell-founded. Observe that if \(W\) is finite, an effectivity functionis playable if and only if it is truly playable (Gorankoetal. 2013).

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

Example 5. The effectivity functions of our workingexample are all truly playable.

In neighborhood structures, relations between set-theoretical andlogical properties are often immediate and standard correspondenceresults between class of frames and neighborhood functions (Chellas1980) can be automatically used for Coalition Logic.

Coalition Logic is in fact expressive enough to characterize all theconstraints mentioned so far, except the last one.

In fact, the axioms and deduction rule above are, in addition topropositional logic, sound and complete with respect to the class ofall models with playable effectivity functions. For proofs, consultPauly 2001.

Correspondence results allow us to distinguish by modal means a numberof classes of frames. However expressivity of the modal operatorsstrongly limit the capacity of the language to discern classes ofstructures. To this extent the reader should notice that the logics ofboth playable and truly playable effectivity frames share the factthat \(\models_F [\emptyset]\top\). However this proposition, whoseinterpretation 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 effectivityfunctions.

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

Theorem 8. (Gorankoet al. 2013) Let\(\mathcal{P}\) be the class of playable frames and\(\mathcal{P}^{*}\) the class of truly playable ones. Then, for everyformula of Coalition Logic \(\varphi\)

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

As pointed out earlier on, this entry will only mention how knowledgeis implicit in game structures but will not delve into the study ofepistemic preconditions of rational play. Related entries devoted toepistemic logic,dynamic epistemic logic, and in particularepistemic game theory explore in depth the role of knowledge in decision-making. Atreatment of modal logics for games which focuses instead on the roleof information is Hoek & Pauly 2006.

3. Analyzing Power

This section looks at games in which individuals or groups take theirchoices independently and concurrently, and, we stress once more,abstracting away from how the interaction evolves in time. It paysparticular attention to the relation between players’ choicesand preferences, mentioning the role of knowledge, and mostimportantly it deals with how to express solution concepts in alogical language.

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

3.1 Cooperative Games and Their Logic

The description of the game given in a relational structure of theform \((\mathcal{N}, W, \succeq, E)\) is not enough to understandwhich exact outcomewill be chosen in the end. For that weneed a solution concept, i.e., a mapping that associates to a game aset of outcomes of that game (Abdou & Keiding 1991). We hereconsider the general setting ofcooperative orcoalitional games, where \(E: W \rightarrow (2^N \rightarrow2^{2^W})\)is a (not necessarily playable) dynamic effectivity function(again, strictly speaking a dynamic effectivity function assigns acoalitional game to each state/outcome).

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

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

1. \(X \in E_v(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 individualsthat can achieve an alternative that they all strictly prefer.

Thecore is the collection of all stableoutcomes.

Example 6. Consider the outcome 1M, which is the onlyoutcome that Germany reckons acceptable. Germany, as already observed,have an effectivity function of \(E(\{\textrm{Germany}\})=\{W\}\) so,on their own, are not able to turn their preference into an outcome.However, together with other Countries, they are able to do so.Suppose their allies are Belgium, France and The Netherlands. Is 1Mthen agood outcome? If we look at the preferences of theother players in the coalition, i.e., Belgium, France, TheNetherlands, we observe the following. Belgium had rather an outcomebetween 4M and 5M, France and The Netherlands exactly 5M. TheseCountries could get together and select 5M, which is an outcome thatis acceptable to them. However the effectivity function of\(\{\)Belgium, France, The Netherlands\(\}\) is \(E(\{\)Belgium,France, The Netherlands\(\})=\{W\}\), which means that the threeCountries are not enough to pass the 5M bill. But the coalition madeby Belgium, France, Italy and The Netherlands would be. Noticemoreover that 5M is one of Italy’s preferred outcomes. 5M is infact the only stable outcome of the game: there is no coalition thatis together willing and capable of deviating from it.

Modal logic can be used to represent the core, with\(E_w(C)\)interpreting \([C]\)as before. Consider first theformula

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

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

holds at \(w\) forevery \(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 every valuation if and only if \(w\)does not belong to the core. Clearly, if the formula is false at anoutcome and some valuation, then this means that the outcome doesbelong to the core.

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

then

Also notice that the result above allows for the case of

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

Notice also how we had to impose a universal quantification on the setof valuations. Without this explicit quantification, the formula wouldonly hold for one specific model, which would not be an appropriatesolution. If instead we are only interested in knowing whetherthere exists some outcome that is stable or, conversely,whether the core is empty, it is sufficient to require the formulaabove to be valid. This would amount to say thatno outcomeis stable, i.e., that the core is empty.

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

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

Yet another alternative is to have atoms for coalitional power(Ågotnes, van der Hoek and Wooldridge 2009): \((F,V), w \modelsp_C\) iff \(w \in E_w(C)\). Then:

Emptyness of the core of \(E_w\)can then furthermore be expressedusing the universal modality \(A\) from Section 2.1: \((F,V), w\models A(\bigvee_{C \subseteq N} \diamond^\succ p_C)\).

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

3.2 Non-cooperative Games and Their Logic

Non-cooperative games are a representation of what individuals, ratherthan coalitions, can achieve, and what their preferences are.

Formally, astrategic game form is a tuple

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

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

Looking at the unified treatment of our example, there seem to berelationship between non-cooperative games and cooperative games. Thisrelationship can be specified formally.

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

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

The following result shows the relationship between strategies andeffectivity functions.

Theorem 13 (Gorankoet al. 2013). Aneffectivity function is truly playable if and only if it is the\(\alpha\)-effectivity function of some non-cooperative game.

This is a generalization of the result in Peleg 1998 for finite games,starting from models of non-cooperative games first defined in Pauly2001. In a nutshell what these results imply is the following.

In the same way we did for cooperative games, we can ask ourselveswhether an outcome is stable, or rational, in a strategicsituation.

Nash equilibrium and definability The main solutionconcept to analyze non-cooperative games is Nash equilibrium.Informally a Nash equilibrium is a collection of strategies, one perplayer, such that no player is interested to change his or herstrategy, given the others stick to theirs. Formally, a strategyprofile \(\sigma\) is a (pure strategy)Nashequilibrium if for all players \(i\in N\) and for all\(\sigma'_i\in \Sigma_i\) we have that

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

holds at a frame \(F\) if and only if the core is empty, and a hybridlogic extension can tell us whether a specific outcome belongs to thecore. If \(F\) is based on a truly playable effectivity function wealready have a non-cooperative form game version of the core: anoutcome such that no coalition is together able and willing to deviatefrom,not taking into account what the others do. HoweverNash Equilibrium fixes a profile of strategies, such that no player isable and willing to deviate from there. In other words it requires thenotion of best response for a player with respect to a givenprofile.

Formalisms such as Coalition Logic are too weak to express Nashequilibria. However, they can express the fact that certaineffectivity functions allow for the possibility of a Nash equilibrium.This is what in Hansen & Pauly 2002 is called Nash-consistentCoalition Logic. Nash Equilibrium is in fact not definable in basicmodal logic (van Benthemet al. 2011), but it can be donewith a modality thatintersects both the preference and thechoice relations (van Benthemet al. 2011) (for choicerelations see Section 3.2.2 below).

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 thesame time achievable and preferable to \(i\). Alternatively a hybridlogic that mentions strategy profiles in the language can provide asolution, similarly to the case of the core.

3.2.1 Injective Games and PDL with Intersection

The general definition of non-cooperative games given above allowsgames where two different strategy profiles lead to the same outcome,i.e., where \(o(\sigma) = o(\sigma')\) for \(\sigma \neq \sigma'\)-where the outcome function is notinjective. However in gametheory injectivity is very often implicitly or explicitly assumed.Indeed, outcomes are often identified with strategy profiles.

It is thus a natural question what happens to Coalition Logic when werestrict non-cooperative games to be injective. The answer is that,first, not much: the language of Coalition Logic cannot discernbetween injective and non-injective games (Gorankoet al.2006). But, second, the class of effectivity functions changes: notall truly playable effectivity functions are \(\alpha\)-effectivityfunctions of injective games.

Recall thewell-foundedness property of effectivityfunctions: if \(X \in E(N)\)then \(\{x\} \in E(N)\) for some \(x \inX\). This is in fact equivalent (Gorankoet al. 2013) to theproperty that \(E(\emptyset)\) has acomplete non-monotoniccore. The non-monotonic core \(E^{nc}(C)\)of \(E(C)\) its minimalelements: \(E^{nc}(C) = \{X \in E(C) : \neg \exists Y (Y \in E(C)\text{ and } Y \subset X\}\). The non-monotonic core iscomplete if and only if for every \(X \in E(C)\) there is a\(Y \in E^{nc}(C)\) such that \(Y \subseteq X\). While trueplayability implies that the non-monotonic core for the emptycoalition is complete, that is not the case for arbitrarycoalitions.

It is, however, for injective games: in addition to the trueplayability properties, the \(\alpha\)-effectivity functions ofinjective games have a complete non-monotonic core forallcoalitions. In addition, the non-monotonic core has somestructural properties. In more detail, we say that an effectivityfunction \(E\) isinjectively playable (Ågotnes andAlechina 2015) iff it is truly playable and has the followingadditional properties, for all \(C, i, j, X, Y\):

• \(E(C)\) has a complete non-monotonic core;
• \(E^{nc}(C) = \{\bigcap_{i \in C} X_i : X_i \in E^{nc}(\{i\})\}\)when \(C \neq \emptyset\);
• if \(X, Y \in E^{nc}(\{i\})\) and \(X \neq Y\) then \(X \cap Y =\emptyset\);
• if \(X \in E^{nc}(j)\) and \(x \in X\) then \(\exists Y \inE^{nc}(i), x \in Y\).

It follows that \(E(C)\) is completely determined by its non-monotoniccore.

Theorem 15. (Ågotnes and Alechina 2015) Aneffectivity function is injectively playable if and only if it is the\(\alpha\)-effectivity function of some injective non-cooperativegame.

Intersection plays a key role in the effectivity ofcoalitions in games: intuitively, the power of a coalition is theintersection of the power of the individuals in the coalition. Anatural idea then, due to van Benthem 2012, is that coalitional powercould perhaps be expressed by usingintersectionmodalities. This is indeed the case, in the following precisesense (Ågotnes and Alechina 2015): there is a satsifiabilitypreserving translation from Coalition Logic to Propositional DynamicLogic with Intersection (Gargovet al. 1988). Thistranslation relies on the fact that for every non-injective game thereis a (Coalition Logic) equivalent injective game.

3.2.2 Non-monotonic Action Logics

Some logics exploit a more compact representation of those relationalstructures that correspond to non-cooperative games.

Rather than using effectivity functions, each player \(i\) isassociated with an equivalence relation \(\approx_i \subseteq W\timesW\), whose induced partition represent the choices he or she canperform. These equivalence relations describe the exact set of choicesthat a group of players can perform and the originating models arereferred to asconsequentialist in the literature (see forinstance Belnap, Perloff, & Ming 2001).

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

Intuitively \(E^{*}(i)\) collects whatexactly theindividuals can achieve and all their supersets.

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

The last property is well-foundedness, as in the case of arbitraryeffectivity functions. This is not a property that is assumed in allvariants, e.g., the choice structures in Kooi & Tamminga 2008 andits temporal variant STIT (Belnapet al. 2001) do not.However, as observed in Turrini 2012 and Tamminga 2013, well-foundedconsequentialist models correspond to non-cooperative games and theeffectivity function \(E\) can be effectively simulated by theequivalence relation \(\approx_i\) for each player. Intuitively\(E^{*}(i)\) is the set of sets of outcomes that \(i\) can choosewithout being able to refine further.

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

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

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

3.2.3 Quantified and Higher-order Coalition Logic

Many interesting properties of power in games involve quantifying overcoalitions, for example the notion of agent \(i\) being aweakveto player (Wooldridge and Dunne 2004) with respect to \(\phi\),in the sense that any coalition that can enforce \(\phi\) must include\(i\), or, in some first or higher-order extension of Coalition Logic:\(\forall C ([C]\phi \rightarrow i \in C)\).Quantified CoalitionLogic (QCL) (Ågotneset al. 2008) extendsCoalition Logic with a limited form of quantification over coalitions,without making the resulting logic undecidable or indeed increasingthe computational complexity of the satisfiability problem. In QCLcoalitions inside modalities are replaced with coalition predicates.Intuitively, \([P]\phi\) (\(\langle P \rangle \phi\)) means that any(some) coalition satisfying the predicate \(P\) has the ability toenforce \(\phi\). As an example, \(i\) is a weak veto player for\(\phi\):

– it is not the case that any coalition that is not a supersetof \(\{i\}\) has the power to enforce \(\phi\). Or that \(i\) is adictator for \(\phi\): \(\neg \langle \negsupseteq(\{i\})\rangle \phi \wedge [supseteq(\{i\})]\phi\).Such properties, and indeed all properties that can be expressed inQCL, can already be expressed in Coalition Logic, by using disjunctionand conjunction to quantify over coalitions, but those expressionswould typically be exponentially long in the number of agents. QCL canexpress such properties concisely, and indeed is exponentially moresuccinct than Coalition Logic. QCL can also be further extended withBelief-Intention-Desire (BDI) logic (Chenet al. 2014)without increasing complexity.

Higher-order Coalition Logic (HCL) (Boellaet al.2010) extends QCL with to a monadic second-order language, unifyingthe languages for describing coalitions and for describing their powerand significantly extending the expressive power. Expressive tractablefragments of HCL exist (Dohertyet al. 2011).

3.2.4 Probabilities and Resource Bounds

As we have seen, the (truly playable) effectivity functions ofCoalition Logic correspond to games where a joint strategy profile forthe set of all agents uniquely determines the outcome. Colition Logiccan be modified in several ways (Naumovet al. 2021) to dealwithstochastic games, i.e., where such a profile onlydetermines a probability distribution over the set of possibleoutcomes. Having modalities \([C]_p \phi\) interpreted as "\(C\) canenforce \(\phi\) with probability \(p\)" leads to interesting andnon-trivial (in)valid properties, such as the following variant ofsuperadditivity \((C \cap C' = \emptyset)\)

not being valid, while

(where \(N\) is the set of all agents) is valid.

As an alternative to stochastic transitions, games with stochasticfailures can be considerered, which from a logical viewpointare somewhat easier to deal with (Naumovet al. 2021).Interpreting \([C]_p \phi\) as "\(C\) can has a joint strategy toensure that \(\phi\) is true in each outcome and which is guaranteednot to fail with probability at least \(p\) no matter what the otheragents do", we get, e.g., that the variant of the superadditivityaxiom mentioned above holds.

Resource bounds have also been added to coalitionalmodalities, interpreted in coalition models corresponding to gameswith costs on performing joint actions (Alechinaet al.2009). Here, \([C^b]\phi\) means that \(C\) can force \(\phi\) to betrue under resource bound \(b\), i.e., that they can chose a jointaction costing at most \(b\) that will ensure that \(\phi\) is true.These modalities satisfy the following variant of superadditivity \((C\cap D = \emptyset, C \neq \emptyset, D \neq \emptyset)\):

3.2.5 Conditional Power and Coordination

From the viewpoints of truly playable effectivity functions andCoalition Logic, two games are equivalent if coalitions have the samepower as defined by \(\alpha\)-effectivity. Van Benthemetal. 2019 point out, however, that there are meaningfuldifferences between games with same \(\alpha\)-effectivity, due tomonotonicity: \(\{w,v\} \in E(C)\) might be the case for twodifferent reasons. First, it might be that there is a joint action by\(C\) such that there is a joint action by the other agents such thatthe outcome will be \(w\)and there is another joint actionby the other agents such that the outcome will be \(v\), or, second,it might be that that is true for only \(w\)or \(v\) (inwhich case \(\{w\} \in E(C)\) or \(\{v\} \in E(C)\)). The first kindof power is calledbasic power by van Benthemet al.2019, who characterise the properties of effectivity functions ofbasic power in the two-agent case and gives a sound and completeaxiomatisation using a variant of Instantial Neighbourhood Logic (INL)(van Benthemet al. 2010) which again is an extension ofstandard modal logic with neighborhood semantics. One significance ofbasic power is that it captures all the outcome sets in which theother players are free to chose any state, given the choice of one ofthose outcome states for some coalition.

Several extensions of the Coalition Logic language have also beendeveloped to reason about conditional and inter-related power betweenagents and coalitions, typically combining existential and universalquantification over choices. Goranko and Enqvist 2018 introduceextended coalition operators of the form

with the intuitive meaning that \(C\) has the power to make \(\phi\)true while at the same time making it possible that the other agentsat the same time can achieve any of the objectives \(\psi_1,\ldots,\psi_k\). The resulting logic can also be seen as a multi-agentextension of INL. Goranko and Enqvist 2018 also introduce operators ofthe form

with the intuitive meaning that the coalition \(C = C_1 \cup \cdotsC_n\) has a joint strategy such that, for each \(i\), the restrictionof that joint strategy to coalition \(C_i\) enforces objective\(\phi_i\).

Goranko and Ju 2022 notice that the latter type of operator can beused to express a certain kind ofconditional power, namely\([A \triangleright \phi, A \cup B \triangleright \psi]\), intuitivelysaying that \(A\) have a joint action that enforces \(\phi\) while atthe same time enables \(B\) to apply a joint action that will enforce\(\psi\). They also introduce two additional conditional powermodalities:

where the former says that \(B \setminus A\) have a joint strategysuch that if \(A\) applies any action that ensures \(\phi\), then thatjoint strategy (by \(B\setminus A\)) at the same time ensures\(\psi\), and the latter that for any joint action by \(A\) thatenforces \(\phi\) there is a consistent joint action by \(B\) that atthe same time enforces \(\psi\). These notions of power correspond to\(\alpha\)- and \(\beta\)- effectivity, respectively.

Coordination is an issue not only between different coalitions, butalso between the agents in the coalition \(C\) in the interpretationof \([C]\phi\). In Coalition Logic it is implicitly assumed, like itoften is (Schelling 1960), that the agents in \(C\) somehow cancoordinate their actions to achieve the outcome \(\phi\). Hawke 2017introduces a new variant of the coalition modalities that captures astronger notion of coalitional ability, relaxes the assumption aboutcoordination (in the case of two agents). Contrary to \([C],\) thesenew modalities \(((C))\) are not monotonic.

3.2.6 Dynamic Coalition Logic

Inspired by the model update semantics ofdynamic epistemic logic, Coalition Logic has been extended in several ways with dynamicmodalities modeling changes in the ability of coalitions in differentways. Broersen, Meyer and Turrini 2009 add expressions of the form\([C \downarrow \psi]\phi\) with the intuitive meaning that after\(C\) chooses \(\psi\), \(\phi\) holds. Ågotnes and Galimullin2021 add modalities for adding and removing actions and ability,inspired by arrow update logic: \([(\phi,a,\psi)^+]\gamma\)intuitively means that after the coalition model is updated by, ineach \(\phi\)-state, adding a new action for agent \(a\) such that nomatter what the other agents do that action will guarantee \(\psi\),then \(\gamma\) holds. There are similar modalities for removingability. Ågotnes and Galimullin 2023 extend Coalition Logic withmore general and expressive modalities forcoalitional actionmodels, inspired by epistemic action models.

3.2.7 Logic-Based Games

In many situations agents have control over certain propositionalvariables (Hoek & Wooldridge 2005), for instance they can beresponsible for traffic flow or they can veto a certain issue.Variables can also be shared (Gerbrandy 2006), an example beingvoting, where players share control over a variable whose realizationis determined by a certain aggregation function, e.g., majority(Troquard, Hoek, & Wooldridge 2011). These logics ofpropositional control specify what propositions agents havein their effectivity function. For instance, if agent \(i\) controls\(p\), then both \(p^{M}\) and \(\neg p^{M}\) are in his or hereffectivity function. In a way these models are very special types ofeffectivity 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 theother agents choose their control strategies, then \(\varphi\) holdsin the end. But they also have modalities of the type\([[C]]\varphi\), meaning that players in \(C\) have a joint controlstrategy ensuring \(\varphi\) in the end. A strategy profile is thusequivalent to a valuation function, which assigns a truth value ofevery proposition available. In turn, a strategy of a player \(i\) canthus be seen as a partial valuation function, that assigns a truthvalue only to the propositions controlled by \(i\).

Slightly abusing notation, we say that a valuation \(V\) satisfies aformula \(\varphi\), denoted \(V \models \varphi\), whenever it makes\(\varphi\) true under the current assignment of propositions. Inother words, propositional control games are played in one singleworld, and the individual assignments determine what propositions aretrue are that world. Denoting \(\mathcal{V}\) the set of allvaluations and \(\mathcal{V}_i\) to the partial ones under the controlof \(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 controlstrategy in such a way that no matter what the control strategy isthat their opponents play, the resulting outcome satisfies\(\varphi\).

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

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

In their most general variants they are an extension of logics withpropositional control, where each agent is assigned a goal formula.The goal formula is a satisfiable formula of the language and theimportant feature is that the goal of each agent does not need to beunder 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\). Sowhether \(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 otherhand, might or might not be interested in having \(q\) set to true.For instance he or she may want proposition \(r\) to be true, andtherefore being indifferent to whether \(q\) or \(\overline{q}\) isrealized in the end. Or might even have the goal that\(\overline{q}\).

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

So, for \(\gamma_i\) being the objective of player \(i\) and \(v_i\) apartial valuation that is under control of player \(i\), we say thatvaluation \(v\) is a Nash equilibrium if we have that for each \(i\)and each \(v'_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 closecorrespondence between these games and propositional logic: using areduction to the satisfiability problem of propositional logicformulas, the problem of checking whether an outcome \(v\) is a Nashequilibrium of a Boolean game is co-NP complete (Wooldridge, Endriss,Kraus, & Lang 2013).

Another common approach to concisely representing certain classes ofgames, in addition to representing payoffs qualitatively, is to imposerestrictions on the payoff functions. An approach combining the two isfound in Daset al. 2023, in which Monadic Least Fixed Pointlogic is used to express the existence of pure strategy Nashequilibria for games with pairwise separable payoff functions.

4. Conclusions: On the Right Level of Analysis

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

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

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

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

Bibliography

• Abdou, Joseph and Hans Keiding, 1991,Effectivity Functions inSocial Choice, (Theory and Decision Library 8), Dordrecht:Springer Netherlands, doi:10.1007/978-94-011-3448-4
• Ågotnes, Thomas, Alechina, Natasha, 2015, “EmbeddingCoalition Logic in the Minimal Normal Multimodal Logic withIntersection”, in S. Ju, H. Liu, and H. Ono (eds.),Modality, Semantics and Interpretations (Logic in Asia:Studia Logica Library), Berlin, Heidelberg: Springer.
• Ågotnes, Thomas, van der Hoek, W., & Wooldridge, M.,2008, “Quantified Coalition Logic”,Synthese,165(2): 269–294. [Ågotneset al. 2008 available online]
• –––, 2009, “Reasoning about coalitionalgames”, 2009,Artificial Intelligence, 173:45–79.
• Alechina, Natasha, Brian Logan, Hoang Nga Nguyen, Abdur Rakib,2011, “Logic for coalitions with bounded resources”,Journal of Logic and Computation, 21(6): 907–937.doi:10.1093/logcom/exq032
• Baltag, Alexandru and Bryan Renne, 2016, “Dynamic EpistemicLogic”, inStanford Encyclopedia of Philosophy, (Winter2016 Edition), Edward N. Zalta (ed.), URL = <https://plato.stanford.edu/archives/win2016/entries/dynamic-epistemic/>
• Belnap, Nuel, Michael Perloff, and Ming Xu, 2001,Facing theFuture: Agents and Choices in Our Indeterminist World, Oxford:Oxford University Press.
• Benthem, Johan van, 2012, “In praise of strategies”,in J. van Eijck, R. Verbrugge (eds.),Games, Actions and SocialSoftware (Lecture Notes in Computer Science: Volume 7010),Berlin, Heidelberg: Springer, pp. 96–116.
• –––, 2014,Logic in Games, Cambridge,MA: MIT Press.
• Benthem, J. van, Bezhanishvili, N., Enqvist, S., and Yu, J., 2017,“Instantial Neighbourhood Logic”,The Review ofSymbolic Logic, 10(1): 116–144.doi:10.1017/S1755020316000447
• Benthem, Johan van, Eric Pacuit, and Olivier Roy, 2011,“Toward a Theory of Play: A Logical Perspective on Games andInteraction”,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
• Boella, Guido, Dov M. Gabbay, Valerio Genovese, and Leendert vander Torre, 2010, “Higher-Order Coalition Logic”, inProceedings of the 2010 conference on ECAI 2010: 19th EuropeanConference on Artificial Intelligence, IOS Press, NLD,555–560.
• Broersen, J., Mastop, R., Ch.Meyer, J. J. and Turrini, P., 2009,“Strategic Ability Update: A Modal Logic Account”, in2009 IEEE/WIC/ACM International Joint Conference on WebIntelligence and Intelligent Agent Technology, Milan, Italy,2009, pp. 470–473. doi: 10.1109/WI-IAT.2009.328
• Chellas, Brian, 1980,Modal Logic: An Introduction,Cambridge: Cambridge University Press.
• Chen, Q., Li, Q., Su, K., Luo, X., 2014, “QuantifiedCoalition Logic for BDI-Agents: Completeness and Complexity”, inDN. Pham and SB. Park (eds.),PRICAI 2014: Trends in ArtificialIntelligence (Lecture Notes in Computer Science: Volume 8862),Cham: Springer. doi:10.1007/978-3-319-13560-1_72
• Chen, Q., Shi, C., and Wang, Y., 2023, “Reasoning aboutDependence, Preference and Coalitional Power”,Journal ofPhilosophical Logic, first online 28 November2023. doi:10.1007/s10992-023-09727-2
• Dalen, Dirk van, 1980,Logic and Structure, Berlin:Springer-Verlag. doi:10.1007/978-3-662-02962-6
• Das, R., Ramanujam, R., Simon, S., 2023, “A LogicalDescription of Priority Separable Games”, in N. Alechina, A.Herzig, and F. Liang (eds.),Logic, Rationality, andInteraction: LORI 2023 (Lecture Notes in Computer Science: Volume14329), Cham: Springer. doi:10.1007/978-3-031-45558-2_3
• Doherty, Patrick, Barbara Dunin-Keplicz, and Andrzej Szałas,2011, “Tractable model checking for fragments of higher-ordercoalition logic”, inThe 10th International Conference onAutonomous Agents and Multiagent Systems – Volume 2 (AAMAS’11), International Foundation for Autonomous Agents andMultiagent Systems, Richland, SC, 743–750.
• Dunne, Paul E. and Wiebe van der Hoek, 2004, “Representationand Complexity in Boolean Games”, in José JúlioAlferes & João Alexandre Leite (eds.),Logics inArtificial 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, “TowardsTractable Boolean Games”, in Wiebe van der Hoek, Lin Padgham,Vincent Conitzer, & Michael Winikoff (eds.),Proceedings ofthe 11th International Conference on Autonomous Agents and MultiagentSystems, (AAMAS 2012), Valencia, Spain, June 4–8, 2012,Richland, SC: International Foundation for Autonomous Agents andMultiagent Systems, vol. 2, pp. 939–946.
• Dunne, Paul E., Wiebe van der Hoek, Sarit Kraus, and MichaelWooldridge, 2008, “Cooperative Boolean Games”, in LinPadgham, David C. Parkes, Jörg P. Müller, & SimonParsons (eds.),Proceedings of the 7th International JointConference on Autonomous Agents and Multiagent Systems, (AAMAS2008), Estoril, Portugal, May 12–16, 2008, Richland, SC:International Foundation for Autonomous Agents and Multiagent System,vol. 2, pp. 1015–1022.
• Enqvist, Sebastian, Nick Bezhanishvili & Johan van Benthem,2019, “A New Game Equivalence, its Logic and Algebra”,Journal of Philosophical Logic, 48(4): 649–684
• Galimullin, R. and Ågotnes, T., 2021, “DynamicCoalition Logic: Granting and Revoking Dictatorial Powers”, inLogic, Rationality, and Interaction: LORI 2021 (Proceedingsof the 8th International Workshop), Xi’an, China, October 16-18,Berlin, Heidelberg: Springer-Verlag, pp. 88–101.doi:10.1007/978-3-030-88708-7_7
• Galimullin, R., Ågotnes, T., 2023, “Action Models forCoalition Logic”, in C. Areces and D. Costa (eds.),DynamicLogic. New Trends and Applications: DaLí 2022 (LectureNotes in Computer Science: Volume 13780), Cham: Springer.doi:10.1007/978-3-031-26622-5_5
• Gargov, G., Passy, S., 1988, “A note on boolean modallogic”, inMathematical Logic (Proceedings of TheSummer School and Conference on Mathematical Logic, Heyting’88),New York: Plenum Press, pp. 311–321.
• Garson, James, 2014, “Modal Logic”, inStanfordEncyclopedia of Philosophy, (Spring 2016 Edition), Edward N.Zalta (ed.), URL = <https://plato.stanford.edu/archives/spr2016/entries/logic-modal/>.
• Gerbrandy, Jelle, 2006, “Logics of PropositionalControl”, in Hideyuki Nakashima, Michael P. Wellman, GerhardWeiss, & Peter Stone (eds.),Proceedings of the 5thInternational Joint Conference on Autonomous Agents and MultiagentSystems, (AAMAS 2006), Hakodate, Japan, May 8–12, 2006, NewYork: ACM, pp. 193–200. doi:10.1145/1160633.1160664
• Goranko, Valentin and Salomon Passy, 1992, “Using theUniversal Modality: Gains and Questions”,Journal of Logicand Computation, 2(1): 5–30. doi:10.1093/logcom/2.1.5
• Goranko, V., van Drimmelen, G., 2006, “Completeaxiomatization and decidability of alternating-time temporallogic”,Theoretical Computer Science, 353(1–3):93–117 (2006)
• Goranko, Valentin, Wojciech Jamroga, and Paolo Turrini, 2013,“Strategic Games and Truly Playable EffectivityFunctions”,Autonomous Agents and Multi-Agent Systems,26(2): 288–314. doi:10.1007/s10458-012-9192-y
• Goranko, Valentin and Enqvist, Sebastian, 2018, “SociallyFriendly and Group Protecting Coalition Logics”, inProceedings.of the 17th International Conference on AutonomousAgents and Multiagent Systems (AAMAS 2018), M. Dastani, G.Sukthankar, E. André, S. Koenig (eds.), July 10–15, 2018,Stockholm, Sweden. International Foundation for Autonomous Agents andMultiagent Systems.
• Goranko, Vanetin and Ju, Fengkui, 2022, “A Logic forConditional Local Strategic Reasoning”,Journal of Logic,Language and Information, 31: 167–188.
• Hansen, Helle Hvid, 2003,Monotonic Modal Logics, MastersThesis, University of Amsterdam.
• Hansen, Helle Hvid and Marc Pauly, 2002, “AxiomatisingNash-Consistent Coalition Logic”, in Sergio Flesca, SergioGreco, Nicola Leone, & Giovambattista Ianni (eds.),Logics inArtificial 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 ModelTheory”,Logical Methods in Computer Science, 5(2):lmcs:1167. [Hansen, Kupke, & Pacuit 2009 available online]
• Hansson, Sven Ove and Till Grune-Yanoff, 2011,“Preferences”, inStanford Encyclopedia ofPhilosophy, (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 CeesWitteveen, 2001, “Boolean Games”, in Johan van Benthem(ed.),Proceedings of the 8th Conference on Theoretical Aspects ofRationality and Knowledge, (Tark ’01), San Francisco:Morgan Kaufmann, pp. 287–298.
• Hawke, Peter, 2017, “The Logic of Joint Ability inTwo-Player Tacit Games”Review of Symbolic Logic,10(3): 481–508.
• Hendricks, Vincent and John Symons, 2006, “EpistemicLogic”, inStanford Encyclopedia of Philosophy, (Spring2006 Edition), Edward N. Zalta (ed.), URL = <https://plato.stanford.edu/archives/spr2006/entries/logic-epistemic/>
• Hodges, Wilfrid, 2013, “Logic and Games”, inStanford 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 forGames 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 theLogic of Cooperation and Propositional Control”,ArtificialIntelligence, 164(1–2): 81–119.doi:10.1016/j.artint.2005.01.003
• Kooi, Barteld and Allard Tamminga, 2008, “Moral ConflictsBetween Groups of Agents”,Journal of PhilosophicalLogic, 37(1): 1–21. doi:10.1007/s10992-007-9049-z
• Kracht, Marcus and Frank Wolter, 1999, “Normal MonomodalLogics Can Simulate All Others”,Journal of SymbolicLogic, 64(1): 99–138. doi:10.2307/2586754
• Moulin, Herve and Bezalel Peleg, 1982, “Cores of EffectivityFunctions and Implementation Theory”,Journal ofMathematical Economics, 10(1): 115–145.doi:10.1016/0304-4068(82)90009-X
• Naumov, Pavel and Kevin Ros, 2021, “Strategic coalitions instochastic games”,Journal of Logic and Computation,31(7): 1845–1867. doi:10.1093/logcom/exab032
• Osborne, Martin and Ariel Rubinstein, 1994,A Course in GameTheory, Cambridge, MA: MIT Press.
• Pacuit, Eric and Olivier Roy, 2015, “Epistemic Foundationsof Game Theory”, inStanford Encyclopedia ofPhilosophy, (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
• Schelling, T., 1960,The Strategy of Conflict, Cambridge,MA: Harvard University Press.
• Steele, Katie and Orri Stefansson, 2015, “DecisionTheory”, inStanford 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 StrategicGames”,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”, inCarles Sierra, Cristiano Castelfranchi, Keith S. Decker, & JaimeSimão Sichman (eds.),Proceedings of the 8th InternationalJoint Conference on Autonomous Agents and Multiagent Systems,(AAMAS 2009), Budapest, Hungary, May 10–15, 2009, Volume 2,Richland, SC: International Foundation for Autonomous Agents andMultiagent Systems, pp. 961–968.
• –––, 2011, “Reasoning About Social ChoiceFunctions”,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.),DeonticLogic in Computer Science: 11th International Conference (DEON2012), Bergen, Norway, July 16–18, 2012, Berlin: Springer,31–45. doi:10.1007/978-3-642-31570-1_3
• Wooldridge, Michael, & Dunne, P. E., 2004, “On thecomputational complexity of qualitative coalitional games”,Artificial Intelligence, 158(1): 27–73.
• Wooldridge, Michael, Ulle Endriss, Sarit Kraus, andJérôme Lang, 2013, “Incentive Engineering forBoolean 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 theFriends of the SEP Society.
	Look up topics and thinkers related to this entry at the Internet Philosophy Ontology Project (InPhO).
	Enhanced bibliography for this entryatPhilPapers, 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 ValentinGoranko for the very constructive comments on earlier versions of themanuscript.