# characterising_the_manipulability_of_boolean_games__dc57f421.pdf

Characterising the Manipulability of Boolean Games

Paul Harrenstein University of Oxford United Kingdom paul.harrenstein@cs.ox.ac.uk

Paolo Turrini Imperial College London United Kingdom paolo.turrini@imperial.ac.uk

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

The existence of (Nash) equilibria with undesirable properties is a well-known problem in game theory, which has motivated much research directed at the possibility of mechanisms for modifying games in order to eliminate undesirable equilibria, or introduce desirable ones. Taxation schemes are one mechanism for modifying games in this way. In the multi-agent systems community, taxation mechanisms for incentive engineering have been studied in the context of Boolean games with costs. These are games in which each player assigns truth-values to a set of propositional variables she uniquely controls with the aim of satisfying an individual propositional goal formula; different choices for the player are also associated with different costs. In such a game, each player prefers primarily to see the satisfaction of their goal, and secondarily, to minimise the cost of their choice. However, within this setting in which taxes operate on costs only it may well happen that the elimination or introduction of equilibria can only be achieved at the cost of simultaneously introducing less desirable equilibria or eliminating more attractive ones. Although this framework has been studied extensively, the problem of precisely characterising the equilibria that may be induced or eliminated has remained open. In this paper we close this problem, giving a complete characterisation of those mechanisms that can induce a set of outcomes of the game to be exactly the set of Nash equilibrium outcomes.

1 Introduction Game theory is widely used in multi-agent systems and artiﬁcial 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,

0, 3, 1 0, 0, 0

1, 1, 2 5, 0, 1

0, 3, 1 0, 0, 0

1, 1, 1 5, 0, 1

Figure 1: A three-player Boolean game with costs. The row player controls proposition p, the column player q, and the matrix player r. The numerical entries refer to the costs incurred by, respectively, the row, column, and matrix player at the corresponding outcome. An entry being underlined indicates that the corresponding player has her goal satisﬁed and Nash equilibria are encircled. The shaded cells are equilibria under no taxation scheme.

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 deﬁned by associating with each agent a propositional formula representing a goal that the player desires to see satisﬁed. 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 inﬂuence 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

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

2, 3, 1 0, 0, 0

1, 1, 2 5, 2, 1

2, 3, 1 0, 0, 0

1, 1, 1 5, 2, 1

Figure 2: An attempt to raise taxes to eliminate the undesirable equilibria pqr and p qr of the game in Figure 1. As a result, pqr which is less desirable for every player than either pqr and p qr in the original game becomes a Nash equilibrium. Notice that no such attempt will be successful: the set {pqr, pqr, p qr} is dominating but contains no cycle involving at least two players.

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 ﬁrst 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

1The 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].

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 proﬁle (of choices) of the form (v1, . . . , vn). The set of proﬁles is denoted V and we let (v i, v i) abbreviate the proﬁle (v1, . . . , vi 1, v i, vi+1, . . . , vn). Each proﬁle (v1, . . . , vn) naturally deﬁnes to a unique valuation v: Φ { , } for the total set of propositional variables. We write p q r to denote the proﬁle 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 proﬁles and valuations. For a proﬁle v and formula ϕ over Φ, we will thus write v |= ϕ to signify that v satisﬁes ϕ, where |= is the standard propositional satisfaction relation. We also say that the valuation v = v1 vn is the outcome that results if proﬁle (v1, . . . , vn) is played. At each proﬁle every player incurs a cost. These costs are modelled by an (outcome-based) cost function c, which for each player i speciﬁes a function ci : V Q 0, associating a non-negative rational cost with each proﬁle. (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 speciﬁc 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 Bd 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, c0 i (v) = 0 for all players i and all valuations v. Furthermore, we write B0

for Bc0 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 reﬁne 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

(i) v |= γi and v |= γi, or

(ii) both v |= γi if and only if v |= γi, and ci(v) ci(v ).

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

Deﬁned thus, Boolean games represent strategic games and as such the standard solution concepts from game theory are

2The opposite direction also holds: for every preference (i.e., reﬂexive, transitive, and complete) relation i over the outcomes that reﬁnes 0 i , 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].

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

available for their analysis. The solution concept we work with is pure strategy Nash equilibrium. Formally, a proﬁle 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:

v c i (v1, . . . , vi 1, v i, vi+1, . . . , vn).

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 proﬁle v is an initial equilibrium of a Boolean game B if it is an equilibrium of B0. Having observed that c i reﬁnes 0 i for every cost function c and every player i, it follows that generally NE(Bc) NE(B0). Accordingly, proﬁle v is an initial equilibrium of a Boolean game B if and only if v is an equilibrium of Bc for some cost function c. By contrast, a hard equilibrium of B is a proﬁle v that is a Nash equilibrium in Bc 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 proﬁle to a non-negative rational number, that is,

τi : V Q 0.

A taxation scheme τ modiﬁes the cost function of a Boolean game, meaning that it increases the cost for every player i at every proﬁle v according to τ. Given Boolean game B with cost function c, a taxation scheme τ gives rise to a cost function cτ = c + τ deﬁned such that, for each player i and each proﬁle v, cτ i (v) = ci(v) + τi(v).

Thus, the application of a taxation scheme τ to a Boolean game B with cost function c results in the Boolean game Bcτ

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 afﬁne transformations. We write Bτ for Bcτ 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) equilibrium may inevitably result in another, perhaps worse, equilibrium coming into being. For Boolean game B and set of proﬁles 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 proﬁles 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 ﬁnd 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 proﬁles. 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] identiﬁed necessary and sufﬁcient 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 ﬁrst 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.

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

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 proﬁle 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 ﬁrst generalise the concept of a hard equilibrium to sets of proﬁles 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 proﬁle v outside X. In the game of Figure 2, we thus ﬁnd 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 deﬁne as a sequence v0, v1, . . . , vk of k 3 distinct proﬁles in X such that v0 = vk and v0 i1 v1 i2 . . . ik vk for some players i1, . . . , ik N. We say that a cycle v0, . . . , vk 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

pq rs 1 p q rs 3 p q r s 1 pq r s 3 pq rs.

After a couple of technical lemmas, we will be in a position to prove that a set X of proﬁles 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 ﬁrst. We thus ﬁnd that sets that do not contain any dominating sets are always eliminable. Observe that this excludes the set V of all proﬁles, 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,

X1 = {v X : v i v for some v V \ X and i N},

Xm+1 = {v X : v i v for some v Xm and i N} Xm.

Observe that X1 X2 X3 . Moreover, as X is nonempty and not dominating, X1 = . Also, for every m 1, we have that Xm X and X \ Xm is not dominating. Accordingly, Xm Xm+1 provided that Xm = X. As V is ﬁnite, it follows that S m 1 Xm = X. Deﬁne τ such that, for each v V and each player i,

τi(v) = min{m 1 : v Xm} v X, 0 otherwise.

Now consider an arbitrary v X. Then, there is a minimal m 1 with v Xm. 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 Xm 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 ﬁnite number of proﬁles, 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 proﬁles, we say a taxation scheme is local on X (or X-local) if τi(v) = 0, for all players i and all proﬁles 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 proﬁle 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 proﬁtable 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.

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

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, deﬁne τ X such that for all players i and all v V,

τ X i (v) =

( τ Y i (v) if v Y, τ X\Y i (v) + max{τ Y i (u) : y Y} otherwise.

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

We can now establish necessary and sufﬁcient conditions for the eliminability of minimal dominating sets. To appreciate our results, call a cycle v0, v1, . . . , vk a deviation cycle if vk c ik vk 1 c ik 1 c i1 v0. Obviously, no proﬁle contained in a deviation cycle can be an equilibrium, irrespective of the costs on the other proﬁles. The intuition underlying Lemma 9 is that, for every cycle in a minimal dominating set involving at least two players, we can ﬁnd 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 ﬁnd, moreover, that this sufﬁcient 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 ﬁnite, it follows that there are v0, v1, . . . , vm with v0 τ i1 v1 τ i2 τ im vm and v0 = vm. Then, by Lemma 2, also v0 i1 v1 i2 . . . im vm, that is, v0, v1, . . . , vm is a cycle in X. By assuming that v0, v1, . . . , vm involves only one player i, we would obtain v0 τ i vm whereas v0 = vm, a contradiction. We may therefore conclude that v0, v1, v2, . . . , vm is a cycle in X involving at least two players. For the opposite direction, assume that X contains a cycle v0, v1, . . . , vm that involves at least two players i and j. Then, v0 i1 v1 i2 . . . im vm. Now deﬁne a taxation scheme τj for each player j as follows. As v0, v1, . . . , vm involves at least two players, there is a least 1 k m such that j = ik. Let

w1, . . . , wm = vk, . . . , vm, v1, . . . , vk 1

and then deﬁne τj(wm ) = m m for every 1 m m. Accordingly, w1 τ j τ j wm. Intuitively, the cycle is linearised by breaking it at the kth edge and decreasing taxes on j are raised along vk, . . . , vm, v1, . . . , vk 1. This induces deviations for j. Thus, j incurs low taxes at vk 1 and relatively high ones at vk and j does not want to deviate from vk 1 to vk. 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 deﬁned τ in this way, it follows that v0 τ i1 v1 τ i1 τ im vm. Accordingly, τ eliminates

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

The results obtained so far put us in a position to prove our ﬁrst 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 Y1, . . . , Ym be all the minimal dominating sets contained in X and assume for each 1 k m that Yk contains a cycle involving at least two players. By Lemmas 7 and 9, each Yk is endogenously eliminable by some Yk-local taxation scheme τ k. Deﬁne τ Y such that, for every proﬁle v and player i,

τ Y i (v) = τ Y1(v) + + τ Yk i (v).

Observe that τ Y is local on Y = Y1 Yk. By virtue of Lemma 4, moreover, the sets Y1, . . . , Ym are pairwise disjoint and, therefore, τ Y i (v) = τ Yk(v) if and only if v Yk. Some reﬂection 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 ﬁnd 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.

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

3, 1, 1 3, 0, 1

2, 1, 1 2, 0, 1

1, 1, 1 1, 0, 1

0, 1, 1 0, 0, 1

3, 1, 0 3, 0, 0

2, 1, 0 2, 0, 0

1, 1, 0 1, 0, 0

0, 1, 0 0, 0, 0

Figure 3: A Boolean game with additive costs in which the set V \ {pq r s, p q r s, pqrs, p qrs} can be eliminated by an outcome-based taxation scheme, but not by an additive one.

4.2 On Additive Costs and Taxes Our deﬁnitions 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, deﬁne outcomebased cost-functions ˆc and outcome-based taxation schemes ˆτ such that, for every player i and outcome v,

p Φi : v(p)= c(p, ) + X

p Φi : v(p)= c(p, ) ˆτi(v) = X

p Φi : v(p)= τ(p, ) + X

p Φi : v(p)= τ(p, ).

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 ﬁnd 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.

3This 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]).

3, 1, 1 3, 0, 1

2, 1, 1 2, 0, 1

1, 1, 1 1, 0, 1

0, 1, 1 0, 0, 1

3, 1, 0 3, 0, 0

2, 1, 0 2, 0, 0

1, 1, 0 1, 0, 0

0, 1, 0 0, 0, 0

Figure 4: The game of Figure 3 with players goal satisfaction in rows pq and p q interchanged.

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 (Do C-AI1048).

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

[Barber a et al., 2004] Salvador Barber a, Walter Bossert, and Prasanta K. Pattanaik. Ranking sets of objects. In S. Barber a, P. J. Hammond, and C. Seidl, editors, Handbook of Utility Theory, volume II, chapter 17, pages 893 977. Kluwer Academic Publishers, 2004. [Bonzon et al., 2006] Elise Bonzon, Marie-Christine Lagasquie, J erˆome Lang, and Bruno Zanuttini. Boolean games revisited. In Proceedings of the Seventeenth European Conference on Artiﬁcial Intelligence (ECAI-2006), pages 265 269, 2006. [Bonzon et al., 2009] Elise Bonzon, Marie-Christine Lagasquie, J erˆome Lang, and Bruno Zanuttini. Compact preference representation and Boolean games. Autonomous Agents and Multi-Agent Systems, 18(1):1 35, 2009. [Clercq et al., 2015] Sophie De Clercq, Steven Schockaert, Ann Now e, and Martine De Cock. Multilateral negotiation in boolean games with incomplete information using generalized possibilistic logic. In Proceedings of the Twenty-Fourth International Joint Conference on Artiﬁcial Intelligence (IJCAI-2015), pages 2890 2896, 2015. [Coase, 1960] Ronald H. Coase. The problem of social cost. Journal of Law and Economics, pages 1 44, 1960. [Cordes, 1999] James Jamieson Cordes. Horizontal equity. In R. D. Ebel, J. J. Cordes, and J. G. Gravelle, editors, Encyclopedia of Taxation and Tax Policy. Urban Institute Press, 1999. [Dunne et al., 2008] Paul E. Dunne, Sarit Kraus, Wiebe van der Hoek, and Michael Wooldridge. Cooperative Boolean games. In Proceedings of the Seventh International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS-2008), pages 1015 1022, 2008. [Grant et al., 2011] John Grant, Sarit Kraus, Michael Wooldridge, and Inon Zuckerman. Manipulating Boolean games through communication. In Proceedings of the 20th International Conference on Artiﬁcial Intelligence (IJCAI-2011), pages 210 215, 2011. [Harrenstein et al., 2001] Paul Harrenstein, Wiebe van der Hoek, John-Jules Ch. Meyer, and Cees Witteveen. Boolean games. In J. van Benthem, editor, Proceeding of the Eighth Conference on Theoretical Aspects of Rationality and Knowledge (TARK VIII), pages 287 298, 2001. [Harrenstein et al., 2014] Paul Harrenstein, Paolo Turrini, and Michael Wooldridge. Hard and soft equilibria in Boolean games. In A. Lomuscio, P. Scerri, A. Bazzan, and M. Huhns, editors, Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2014), pages 845 852, 2014. [Harrenstein et al., 2016] Paul Harrenstein, Paolo Turrini, and Michael Wooldridge. Hard and soft preparation sets in Boolean games. Studia Logica, 104(4):813 847, 2016. [Krantz et al., 1971] David H. Krantz, R. Duncan Luce, Patrick Suppes, and Amos Tversky. Foundations of Mea-

surement. Volume I: Additive and Polynomial Representations. Academic Press, 1971. [Mavronicolas et al., 2015] Marios Mavronicolas, Burkhard Monien, and Klaus W. Wagner. Weighted Boolean formula games. In Algorithms, Probability, Networks, and Games Scientiﬁc Papers and Essays Dedicated to Paul G. Spirakis on the Occasion of His 60th Birthday, pages 49 86, 2015. [Meade, 1952] James Meade. External economies and diseconomies in a competitive situation. Economic Journal, 62(245):54 67, 1952. [Roberts, 1979] Fred S. Roberts. Measurement Theory, volume 7 of Encyclopedia of Mathematics and its Applications. Addison-Wesley, 1979. [Shoham and Leyton-Brown, 2008] Yohav Shoham and Kevin Leyton-Brown. Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. Cambridge University Press, 2008. [Slinko, 2009] Arkadii Slinko. Additive representability of ﬁnite measurement structures. In S. J. Brams, W. V. Gehrlein, and F. S. Roberts, editors, The Mathematics of Preference, Choice and Order Essays in Honor of Peter C. Fishburn, Studies in Choice and Welfare, pages 113 133. Springer, 2009. [Suppes and Zinnes, 1963] Patrick Suppes and Joseph L. Zinnes. Basic measurement theory. In R. D. Luce, R. R. Bush, and E. Galanterl, editors, Handbook of Mathematical Psychology, volume I, chapter 1. Wiley and Sons, 1963. [Tobin, 1978] James Tobin. A proposal for international monetary reform. Eastern Economic Journal, 4(3 4):153 159, 1978. [Turrini, 2013] Paolo Turrini. Endogenous Boolean games. In Proceedings of the Twenty-Third international joint conference on Artiﬁcial Intelligence (IJCAI-2013), pages 390 396, 2013. [Turrini, 2016] Paolo Turrini. Endogenous games with goals: side-payments among goal-directed agents. Autonomous Agents and Multi-Agent Systems, 30(5):765 792, 2016. [Wooldridge et al., 2013] Michael Wooldridge, Ulle Endriss, Sarit Kraus, and J erˆome Lang. Incentive engineering for Boolean games. Artiﬁcial Intelligence, 195:418 439, 2013.

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)