Characterising the Manipulability of Boolean Games

1 Introduction

Game theory is widely used in multi-agent systems and artificial intelligence to model and understand the behaviour of systems in which components are assumed to act in pursuit of individual preferences [Shoham and Leyton-Brown, 2008]. Probably the most important analytical concept in game theory is the notion of Nash equilibrium, representing a state of affairs such that no participant has any rational incentive to deviate. However, a standard problem in game theory is that strategic scenarios may have Nash equilibria with undesirable properties. In the Prisoner's Dilemma, for example,

Michael Wooldridge

University of Oxford United Kingdom mjw@cs.ox.ac.uk

the unique Nash equilibrium outcome is strictly worse for all players than an alternative outcome. This problem - the presence of undesirable equilibria - has motivated research on the development of mechanisms for modifying games, with the goal of either eliminating undesirable equilibria, or inducing desirable ones.

Taxation mechanisms represent one natural class of mechanisms for manipulating games. The idea is that by levying taxes on the actions of agents, it is possible to incentivise an agent to avoid or choose a particular action (cf., e.g., [Cordes, 1999; Tobin, 1978; Meade, 1952; Coase, 1960]). In the multiagent systems literature, this idea has been investigated in the context of Boolean games with costs [Wooldridge et al., 2013]. In such a game, each player exercises unique control over a set of propositional variables, in the sense that the player can choose to assign values (true or false) to these variables as they wish. Preferences in the game are defined by associating with each agent a propositional formula representing a goal that the player desires to see satisfied. Different assignments of values to variables induce different costs for the corresponding agent, and while players are primarily motivated to seek the satisfaction of their goal, they are secondarily motivated to minimise costs. Because taxation schemes can apply additional costs to actions (or subsidise actions), designing such a scheme can influence the rational behaviour of players, making it possible to eliminate some equilibria or introduce new ones. However, as players always prefer to get their goal achieved than otherwise, there is an inherent limit to the manipulation that is possible through taxation: a player can never be incentivised away from achieving her goal.

The basic framework of taxation mechanism for Boolean games with costs was introduced by [Wooldridge et al., 2013], and has since been investigated and extended by other authors [Harrenstein et al., 2014; Turrini, 2013; 2016]. However, fundamental questions remain unanswered about the extent to which Boolean games can be manipulated through taxation. One issue in particular is that, while it may be possible to eliminate some undesirable equilibrium from a game, this process may inadvertently introduce new undesirable equilibria. Consider for example the Boolean game in Figure 1 with three equilibria. The top-right outcome is an equilibrium in which all players have their goals achieved at minimum cost. The other two equilibria are less desirable for all players. Yet, as illustrated in Figure 2, any attempt at eliminating these with the same taxation scheme will result in the bottom-left outcome becoming an equilibrium. This outcome, however, is worse for all players than the original two that were eliminated.

To date, the problem of precisely characterising the sets of equilibria that can be eliminated or introduced through taxation has remained open. It is this problem that we address, and settle, in the present paper: we give for the first time a complete characterisation of the sets of outcomes in Boolean games with costs that may be induced or eliminated through taxation mechanisms.

2 Boolean Games with Costs

We use the framework of Boolean games with costs as presented in [Wooldridge et al., 2013]. 1 Formally, a Boolean game with costs (hereafter just "Boolean game" or "game") is given by a structure, (N, {Φi}i∈N, {γi}i∈N, c). Here, N = {1, 2, . . . , n} is a set of players (or agents). Each player i uniquely controls a set of propositional variables Φi and is associated with a goal γi, a propositional logic formula constructed from the total set of propositional variables Φ = Φ1 ∪ · · · ∪ Φn. The sets Φ1, . . . ,Φn are assumed to partition Φ, ensuring that each variable is controlled by precisely one player. A choice (or strategy or action) for player i is a an assignment of truth or falsity to all variables that i controls, that is, a function of the form vi : Φi → {⊤,⊥}. The set of all such choices for player i is denoted Vi. Players, independently and simultaneously, make individual choices, giving rise to a profile (of choices) of the form (v1, . . . , vn). The set of profiles is denoted V and we let (v-i, v′i ) abbreviate the profile (v1, . . . , vi-1, v′i , vi+1, . . . , vn). Each profile (v1, . . . , vn) naturally defines to a unique valuation v: Φ → {⊤,⊥} for the total set of propositional variables. We write p¯q¯r to denote the profile in which variable p is set to true and variables q and r are set to false, and similarly for other valuations. We will generally not notationally distinguish between profiles and valuations. For a profile v and formula ϕ over Φ, we will thus write v |= ϕ to signify that v satisfies ϕ, where |= is the standard propositional satisfaction relation. We also say that the valuation v = v1 ∪ · · · ∪ vn is the outcome that results if profile (v1, . . . , vn) is played.

1 The framework of Boolean games was initiated by [Harrenstein et al., 2001]. Important follow-up work includes [Bonzon et al., 2006; 2009], [Dunne et al., 2008], [Grant et al., 2011], [Mavronicolas et al., 2015], and [Clercq et al., 2015].

At each profile every player incurs a cost. These costs are modelled by an (outcome-based) cost function c, which for each player i specifies a function ci : V → Q≥0, associating a non-negative rational cost with each profile. (Here we deviate from the more restrictive additive notion of cost in [Wooldridge et al., 2013], where costs are associated with setting a propositional variables to a specific Boolean value: the present model is more expressive.) If B is a Boolean game with cost function c and d is another cost function, then B d denotes the Boolean game that results from B by replacing c by d. We denote by c0 the zero-cost function, which assigns cost 0 to every player i and every valuation, that is, c0i (v) = 0 for all players i and all valuations v. Furthermore, we write B0 for B c0 to avoid cluttered notation.

As discussed in the introduction, players prioritise goal realisation over cost minimisation, that is, each will prefer outcomes that satisfy her goal to outcomes that do not, no matter the respective costs, and prefer cheaper outcomes to more expensive ones, otherwise. Accordingly, costs refine the dichotomous preferences each player has over the outcomes on basis of her goal alone. Formally, we model the preferences of player i as a complete and transitive relation over outcomes. Thus, given a Boolean game with cost function c and a player i with goal γi, we say that i weakly prefers outcome v to outcome v′ , in symbols v ⪰c v′ , if

We use ≻c i and ∼c i for, respectively, the strict and indifferent parts of ⪰c i in the usual way, and write ⪰0i , ≻0i , and ∼0i if c is c0 . Observe that v ≿0i v′ if and only if v′ |= γi implies v |= γi. As a consequence ⪰c i refines ⪰0i , in the sense that ⪰c i is a subset of ⪰0i and thus v ⪰c i v′ implies v ⪰0i v′ . 2

Defined thus, Boolean games represent strategic games and as such the standard solution concepts from game theory are available for their analysis. The solution concept we work with is pure strategy Nash equilibrium. Formally, a profile v = (v1, . . . , vn) of a Boolean game B with cost function c is a (pure strategy) Nash equilibrium if for all players i and all choices v′i ∈ Vi, we have:

2 The opposite direction also holds: for every preference (i.e., reflexive, transitive, and complete) relation ⪰i over the outcomes that refines ⪰0i , there is an outcome-based cost function c such that ⪰i equals ⪰c i . This, however, does not generally hold for the additive cost functions of [Wooldridge et al., 2013].

We denote the set of pure Nash equilibria of a Boolean game B by NE(B). Pure Nash equilibria are not guaranteed to exist, and, when they exist, they need not be unique.

The Nash equilibria of a Boolean game depend both on the players' goals and on the cost function. Thus, [Harrenstein et al., 2014] distinguished hard, soft, and initial equilibria. A profile v is an initial equilibrium of a Boolean game B if it is an equilibrium of B0 . Having observed that ⪰c i refines ⪰0i for every cost function c and every player i, it follows that generally NE(B c ) ⊆ NE(B0 ). Accordingly, profile v is an initial equilibrium of a Boolean game B if and only if v is an equilibrium of B c for some cost function c. By contrast, a hard equilibrium of B is a profile v that is a Nash equilibrium in B c for every cost function c. Finally, v is a soft equilibrium of B if it is an initial equilibrium of B that is not hard. We denote the initial, hard, and soft equilibria of game B by INIT(B), HARD(B), and SOFT(B), respectively. It is easy to see that the stability of hard equilibria only depends on the players' goals, whereas it is the cost function that determines whether a soft equilibrium is also actually a Nash equilibrium of a given game. For example, the initial equilibria of the game in Figure 1 are pqr, ¯pqr, ¯p¯qr, and p¯q¯r; while the former three are soft, the latter is hard.

3 Manipulating Boolean Games

Over the past few years, a number of contributions have focussed on understanding how a system designer can incentivise players in a Boolean game by manipulating the cost function by levying taxes. This line of research started with [Wooldridge et al., 2013] and was pursued further by, e.g., [Harrenstein et al., 2014; 2016]. For the purposes of this paper, we have an (outcome-based) taxation scheme τ associate with every player i a function τi that maps each profile to a non-negative rational number, that is,

A taxation scheme τ modifies the cost function of a Boolean game, meaning that it increases the cost for every player i at every profile v according to τ. Given Boolean game B with cost function c, a taxation scheme τ gives rise to a cost function cτ = c + τ defined such that, for each player i and each profile v,

Thus, the application of a taxation scheme τ to a Boolean game B with cost function c results in the Boolean game B cτ with cost function cτ . Every taxation scheme induces a cost transformation and, moreover, every cost transformation can be achieved by a taxation scheme modulo positive affine transformations. We write Bτ for B cτ and v ⪰τi v′ for v ⪰cτ i v′ , whenever c is known from the context. For τ and τ ′

taxation schemes, we write τ + τ ′ for the taxation scheme τ ′′ such that τ ′′ i (v) = τi(v) + τ ′ i (v).

Previous work on incentive engineering for Boolean games, in particular [Wooldridge et al., 2013], has focussed on taxation schemes that eliminate individual soft equilibria or induce such to become Nash equilibria. However, if v can be eliminated under some taxation scheme and v′ under another, it does not generally follow that v and v′ can both be eliminated by the same taxation scheme. As we saw in Figures 1 and 2, the elimination of some (undesirable) equilibriummay inevitably result in another, perhaps worse, equilibrium coming into being.

For Boolean game B and set of profiles X, we say that a taxation scheme τ induces X if NE(Bτ ) = X and eliminates X if no v ∈ X is a Nash equilibrium in Bτ , that is, if NE(Bτ ) ∩ X = ∅. Our main research question can then be phrased as which sets of profiles can be eliminated by some (outcome-based) taxation scheme and which sets can be induced. In Section 4, we answer this question by providing characterisations of inducible and eliminating sets in Boolean games that do not involve cost functions or taxation schemes and only pertains to the players' goals. For reasons of space, we will omit some of the easier proofs.

We find that attention can be restricted to games with the zero cost function c0 . Let B be a game with cost function c and τ a taxation scheme. Recall that then NE(Bτ ) ⊆ NE(B0 ). Moreover, for every taxation scheme τ, there is another taxation scheme τ ′ such that c + τ = c0 + τ ′ . Similarly, for every τ ′ there is a τ and constant k and such that c0 + τ ′ + k = c + τ. As raising costs by a constant everywhere does not affect the preference structure, we have the following lemma.

Lemma 1. Let B be a Boolean game with cost function c and X ⊆ V a subset of profiles. Then,

• (i) X is inducible in B if and only if X is inducible in B0 ,
• (ii) X is eliminable in B if and only if X is eliminable in B0 .

4 Characterising Inducible and Eliminable Sets

[Harrenstein et al., 2016] identified necessary and sufficient conditions for hard, soft, and initial equilibria that only depend on the players' goals and not on the cost functions. In order to achieve the same for inducible and eliminable sets of equilibria, we first distinguish initial, soft, and hard deviations. Let v, v′ be two distinct outcomes and i a player and v′ = (v-i, v′′ i ) for some v′′ i ∈ Vi. We then say that:

• v′ is an initial deviation for i from v, (denoted v →i v′ ), if v |= γi implies v′ |= γi,
• v′ is a soft deviation for i from v, (denoted by v ⇆i v′ ), if both v →i v′ and v′ →i v.
• v′ is a hard deviation for i from v, (denoted by v ⇒i v′ ), if v →i v′ but not v′ →i v.

Thus, ⇒i and ⇆i partition the initial deviation relation →i into a strict and a non-strict part, respectively. Also observe that →i, ⇆i, and⇒i are independent of the cost function and only depend on i's goal formula. In particular, we have that v ⇒i v′ if and only if v ̸|= γi and v′ |= γi. The following lemma, moreover, is an immediate consequence of the lexicographic nature of preferences in Boolean games with costs.

Lemma 2. Let B be a Boolean game. Then, for all distinct outcomes v, v′ ∈ V, each of the following hold.

• (i) v →i v′ if and only if v′ ≻c i v for some cost function c,
• (ii) v ⇆i v′ if and only if v′ ≻c i v for some cost function c and v ≻c′ i v′ for another cost function c′ ,
• (iii) v ⇒i v′ if and only if v′ ≻c i v for all cost functions c.

Accordingly, a profile v is an initial equilibrium if and only if there is no hard deviation from v, and that v is a hard equilibrium if and only if there is no initial deviation from v. A soft equilibrium, moreover, is an initial equilibrium from which there is at least one soft deviation. As our main result we show that in a similar way we can characterise inducible and eliminable sets in terms of the initial deviation relations →i.

We first generalise the concept of a hard equilibrium to sets of profiles and say that a nonempty set X is dominating if for all v ∈ X, all players i, and all v′′ i ∈ Vi such that (v-i, v′′ i ) /∈ X, it holds that (v-i, v′′ i ) ⇒i v. Equivalently, a nonempty set X is dominating if and only if there is no player i for whom there is an initial deviation from some v in X to some profile v′ outside X. In the game of Figure 2, we thus find that {pqr, ¯pqr, ¯p¯qr} is a dominating set, because p¯qr ⇒1 ¯p¯qr, p¯qr ⇒2 pqr, as well as pq¯r ⇒3 pqr, ¯pq¯r ⇒3 ¯pqr, and ¯p¯q¯r ⇒3 ¯p¯qr. It can easily be seen that V is (trivially) a dominating set and that dominating sets are closed under union. By a (set-inclusion) minimal dominating set we understand a subset of outcomes that is dominating and contains no dominating sets as strict subsets.

A cycle in X, moreover, we define as a sequence v0 , v1 , . . . , v k of k ≥ 3 distinct profiles in X such that v0 = v k and v0 →i1 v1 →i2 . . . →ik v k for some players i1, . . . , ik ∈ N. We say that a cycle v0 , . . . , v k in X involves player i if i = im for some 1 ≤ m ≤ k. Thus, in Figure 2, the set {pqr, ¯pqr, ¯p¯qr} can be seen to contain no cycle. In the game depicted in Figure 3, however, ¯pq¯rs, ¯p¯q¯rs, ¯p¯q¯r¯s, ¯pq¯r¯s, ¯pq¯rs is a cycle in V, because

After a couple of technical lemmas, we will be in a position to prove that a set X of profiles is eliminable if and only if all dominating sets in X contain a cycle involving at least two players (Theorem 10) and that X is inducible if and only if X is a subset of initial equilibria and the complement V \ X is eliminable (Theorem 11).

4.1 Characterisation

The characterisation of inducible sets relies on the characterisation of eliminable sets and we concentrate on the latter first. We thus find that sets that do not contain any dominating sets are always eliminable. Observe that this excludes the set V of all profiles, which is dominating itself.

Lemma 3. Let B be a Boolean game and assume X ⊆ V contains no dominating sets. Then, X is eliminable.

Proof. By Lemma 1, we may assume that B = B0 . If X is empty we are done immediately. Now assume that X is nonempty. As V is dominating, X ̸= V. Hence, V \ X

is non-empty. We now construct inductively a sequence X1 , X2 , X3 . . . of subsets of V such that, for every m ≥ 1,

Observe that X1 ⊆ X2 ⊆ X3 ⊆ · · · . Moreover, as X is nonempty and not dominating, X1 ̸= ∅. Also, for every m ≥ 1, we have that X m ⊆ X and X \ X m is not dominating. Accordingly, X m ⊊ X m+1 provided that X m ̸= X. As V is finite, it follows that ⋃m≥1 X m = X. Define τ such that, for each v ∈ V and each player i,

Now consider an arbitrary v ∈ X. Then, there is a minimal m ≥ 1 with v ∈ X m . If m = 1, there is a player i and a v′ ∈ V \ X such that v →i v′ and hence v ≺τi v′ . If m > 1, there is a player i and a v′ ∈ X m-1 such that v →i v′ and hence v ≺τi v′ . We may conclude that X contains no Nash equilibria of Bτ , signifying that X is eliminable.

We now consider the case in which the set X to be eliminated does contain dominating sets. Having assumed a finite number of profiles, every dominating set contains at least one minimal dominating set. Although dominating sets may overlap, distinct minimal dominating sets will be disjoint.

Lemma 4. Let B be a Boolean game and X, Y ⊆ V be overlapping dominating sets. Then, X ∩ Y is also a dominating set. Therefore, distinct minimal dominating sets are disjoint.

We now introduce the following auxiliary concept. For X a set of profiles, we say a taxation scheme is local on X (or X-local) if τi(v) = 0, for all players i and all profiles v /∈ X. Thus, a taxation scheme is local if it only raises taxes on valuations in X and no taxes on valuations outside X. The following two lemmas show that taxes that are local on X cannot eliminate equilibria that lie outside X, and that a set X can be eliminated if and only if it can be eliminated by an X-local taxation scheme.

Lemma 5. Let B be a Boolean game, τ be an taxation scheme that is X-local for some X ⊆ V, and v a profile with v /∈ X. Then, v ∈ NE(B) implies v ∈ NE(Bτ ).

Lemma 6. Let B be a Boolean game and X ⊆ V. Then, X is eliminable if and only if X is eliminable by an X-local taxation scheme.

Introducing a second auxiliary concept, we say that a set X is endogenously eliminable if there is a taxation scheme τ such that for every outcome v ∈ X there is a player i and v′i ∈ X such that (v-i, v′i ) ∈ X and v ≻τi (v-i, v′i ), that is, if τ induces profitable deviations from every outcome in X to another outcome in X. Observe that, as a consequence of Lemmas 2 and 6, dominating sets are eliminable only if they are endogenously eliminable by an X-local taxation scheme.

Lemma 7. Let B be a Boolean game and X a dominating set. Then, X is eliminable if and only if X is endogenously eliminable by an X-local taxation scheme.

We moreover have the following simple but useful lemma.

Lemma 8. Let B be a Boolean game with cost function c and Y ⊆ X ⊆ V such that Y is endogenously eliminable. Then, X is eliminable if and only if X \ Y is eliminable.

Proof. The "only if"-direction is immediate. For the opposite direction, let τ X\Y be a taxation scheme that eliminates X \ Y and τ Y one that eliminates Y endogenously. Observe that by virtue of Lemma 6 we may assume that τ X\Y is local on X\Y. Then, define τ X such that for all players i and all v ∈ V,

Now, τ X eliminates X \Y and Y, the latter endogenously.

We can now establish necessary and sufficient conditions for the eliminability of minimal dominating sets. To appreciate our results, call a cycle v0 , v1 , . . . , v k a deviation cycle if v k ≻c ik v k-1 ≻c ik-1 · · · ≻c i1 v0 . Obviously, no profile contained in a deviation cycle can be an equilibrium, irrespective of the costs on the other profiles. The intuition underlying Lemma 9 is that, for every cycle in a minimal dominating set involving at least two players, we can find a taxation scheme that turns it into a deviation cycle and, consequently, eliminates it endogenously. Lemma 8 then guarantees that the minimal dominating set itself can be eliminated. We find, moreover, that this sufficient condition for eliminability is also necessary.

Lemma 9. Let B be a Boolean game and X a minimal dominating set. Then, X is eliminable if and only if X contains a cycle involving at least two distinct players.

Proof. By Lemma 1, we may assume that B = B0 . First assume that taxation scheme τ eliminates X. Having assumed that X is dominating, τ eliminates X endogenously. Hence, for every v ∈ X, there is a v′ ∈ X and player i, such that v ≺τi v′ . As X is finite, it follows that there are v0 , v1 , . . . , v m with v0 ≺τi1 v1 ≺τi2 · · · ≺τim v m and v0 = v m . Then, by Lemma 2, also v0 →i1 v1 →i2 . . . →im v m , that is, v0 , v1 , . . . , v m is a cycle in X. By assuming that v0 , v1 , . . . , v m involves only one player i, we would obtain v0 ≺τi v m whereas v0 = v m , a contradiction. We may therefore conclude that v0 , v1 , v2 , . . . , v m is a cycle in X involving at least two players.

For the opposite direction, assume that X contains a cycle v0 , v1 , . . . , v m that involves at least two players i and j. Then, v0 →i1 v1 →i2 . . . →im v m . Now define a taxation scheme τj for each player j as follows. As v0 , v1 , . . . , v m involves at least two players, there is a least 1 ≤ k ≤ m such that j ̸= ik. Let

and then define τj(w m′ ) = m - m′ for every 1 ≤ m′ ≤ m. Accordingly, w1 ≺τj · · · ≺τj w m . Intuitively, the cycle is linearised by breaking it at the kth edge and decreasing taxes on j are raised along v k , . . . , v m, v1 , . . . , v k-1 . This induces deviations for j. Thus, j incurs low taxes at v k-1 and relatively high ones at v k and j does not want to deviate from v k-1 to v k . That does not matter, however, as exactly that deviation is to be performed by player ik, which was assumed to be distinct from j. Having defined τ in this way, it follows that v0 ≺τi1 v1 ≺τi1 · · · ≺τim v m . Accordingly, τ eliminates

{v0 , v1 , . . . , v m} endogenously. To finish the proof, recall that we had assumed X to be minimally dominating. Hence, the set X \ {v0 , v1 , . . . , v m} contains no dominating set and is, by virtue of Lemma 3, eliminable. As, moreover, τ endogenously eliminates {v0 , v1 , . . . , v m}, it follows by Lemma 8 that X is eliminable itself.

The results obtained so far put us in a position to prove our first main result and provide a complete characterisation of eliminable sets of equilibria. Here, the crucial part is to observe that, if two minimal dominating sets are eliminable separately, there is also a taxation scheme that eliminates them both.

Theorem 10. Let B be a Boolean game and X ⊆ V. Then, X is eliminable if and only if every minimal dominating subset Y ⊆ X contains a cycle involving at least two players.

Proof. For the "only if"-direction, let Y be a minimal dominating subset of X and assume for contraposition that Y contains no cycle involving at least two players. By Lemma 9, it follows that Y is not eliminable and, hence, neither is X.

For the opposite direction, let Y 1 , . . . , Y m be all the minimal dominating sets contained in X and assume for each 1 ≤ k ≤ m that Y k contains a cycle involving at least two players. By Lemmas 7 and 9, each Y k is endogenously eliminable by some Yk-local taxation scheme τ k . Define τ Y such that, for every profile v and player i,

Observe that τ Y is local on Y = Y1 ∪ · · · ∪ Yk. By virtue of Lemma 4, moreover, the sets Y 1 , . . . , Y m are pairwise disjoint and, therefore, τ Y i (v) = τ Yk (v) if and only if v ∈ Yk. Some reflection then reveals that τ Y eliminates Y endogenously. Finally observe that X \Y contains no dominating sets and thus, by Lemma 3, is eliminable. By Lemma 8, we may conclude that X is eliminable as well, as desired.

Our second main result, which provides a characterisation of inducible sets, now follows as a corollary of Theorem 10.

Theorem 11. Let B be a Boolean game and X ⊆ V. Then, X is inducible if and only if X ⊆ INIT(B) and every minimal dominating subset Y ⊆ V \ X contains a cycle involving at least two players.

Proof. For the "only if"-direction, assume that there is a taxation scheme τ such that NE(Bτ ) = X. Then, immediately, X ⊆ INIT(B). Moreover, τ eliminates V \ X and hence, by Theorem 10, every minimal dominating set in V \ X contains a cycle involving at least two players.

For the opposite direction, assume that X ⊆ INIT(B) and every minimal dominating subset Y ⊆ V \ X contains a cycle involving at least two players. We show that X can be induced in B0 . Lemma 1 then gives the result.

By Theorem 10, we find that V \ X is eliminable in B0 . By Lemma 6, moreover, V \ X is eliminable in B0 by a V \ Xlocal taxation scheme τ. Now observe that X ⊆ NE(B0 ). Accordingly, Lemma 5 yields X ⊆ NE(B0+τ ). Hence, NE(B0+τ ) = X, that is, X is inducible in B0 , as desired.

4.2 On Additive Costs and Taxes

Our definitions of outcome-based cost functions and taxation schemes diverge slightly from the additive variants used by [Wooldridge et al., 2013]. Both additive cost-functions c and additive taxation schemes τ map pairs in Φ × {⊥,⊤} to a non-negative rational and, respectively, define outcomebased cost-functions ˆc and outcome-based taxation schemes ˆ τ such that, for every player i and outcome v,

The structure an additive cost function imposes on the valuations is more regular than that of outcome-based cost functions but nevertheless highly non-trivial. 3 The problem of characterising eliminable and inducible sets of equilibria is correspondingly more complicated in this setting.

Consider the Boolean game in Figure 3, where the additive cost function c is such that c(p, ⊤) = 2, c(q, ⊤) = c(r, ⊤) = c(s,⊤) = 1, and c(x,⊥) = 0 for all variables x. The set X = V \ {pq¯r¯s, p¯q¯r¯s, ¯pqrs, ¯p¯qrs} can be eliminated by the outcome-based taxation scheme τ ′ that levies taxes of 2 on the row player at ¯p¯q¯r¯s and nil taxes otherwise. By contrast, X is not eliminable by any additive taxation scheme. To see this, observe that for any such scheme τ should eliminate the equilibrium ¯p¯q¯r¯s. Hence, ˆ τrow(¯p¯q¯r¯s) - ˆ τrow(¯pq¯r¯s) > 1. This, however, would imply that τ(q,⊥) - τ(q,⊤) > 1. Hence, pqrs ≻ˆ τrow p¯qrs, causing pqrs to be an equilibrium under ˆ τ .

Interestingly, if we consider the game in Figure 4, which results from the one in Figure 3 when the outcomes the rows ¯pq and ¯p¯q are interchanged with respect to the players' goal satisfaction, we find that the set X is eliminable by the additive taxation scheme that levies zero taxes all around. Yet, the graphs on the valuations induced by the initial deviation relations →i in both games are identical up to permuting the valuations. Consequently, eliminability, and therewith inducibility, of sets of outcomes by additive taxation schemes does not only depend on the (graph theoretic) structure of the initial deviation relations →i, but also on the very propositions that are set to true or false in the valuations. This reveals a fundamental mathematical distinction between the outcome-based and additive settings.

3 This issue is closely related to additive conjoint measurement as studied in measurement theory (see, e.g., [Suppes and Zinnes, 1963; Krantz et al., 1971; Roberts, 1979; Slinko, 2009]).

5 Conclusion

We have studied equilibrium elimination and introduction via incentive engineering in the context of Boolean games. The problem of fully characterising the conditions under which this is possible was an open problem we inherited from the related literature, notably [Wooldridge et al., 2013], which had only focussed on induction and elimination strategies for single Nash equilibria. We have settled the problem for the general case outcome-based taxation mechanisms (that is, unconstrained transformations of the players' cost function). Our characterisations reduce to the presence of cycles of possible (that is, initial) deviations in some fully separated subsets of outcomes. Still, a number of research questions remain.

First, there is need to characterise eliminability and inducibility under the more restrictive additional taxation mechanisms. We observed how the characterisation under outcome-based taxation mechanisms does not carry over to the additive setting. This does of course not show that no such characterisation can be obtained, but we have to leave the issue as an open problem. A similar point concerns the sidepayment schemes as studied by [Harrenstein et al., 2014].

A second point that deserves attention is how to compare the desirability of the sets of outcomes that are induced under different taxation or side-payment schemes. If viewed from the perspective of the players' welfare, this requires to raise preferences over outcomes to preferences over sets of outcomes. In the social choice literature there have been several proposals for such metrics (cf. e.g., [Barber`a et al., 2004]).

One of the main advantages of Boolean games lies in their computational aspects and connections with logic. A third issue is therefore to establish the computational complexity of deciding whether a given set of outcomes is inducible or eliminable by a taxation scheme. We trust our results provide deeper insight into the structure of these problems.

Acknowledgments

Michael Wooldridge and Paul Harrenstein are supported by the ERC under Advanced Grant 291528 ("RACE"). Paolo Turrini acknowledges the support of the Imperial College Research Fellowship "Designing Negotiation Spaces for Collective Decision-Making" (DoC-AI1048).