On the Complexity of Compact Coalitional Games

1 Introduction

A coalitional game is played by a set N of players that can form coalitions in order to guarantee themselves some advantage. Each coalition S ⊆ N is assigned a certain worth v(S) that players in S can obtain if collaborating with each other, and the outcome of the game is a vector of payoffs (xi)i∈N ∈ R|N| that is meant to specify the distribution of the worth granted to each player in N.

A fundamental problem for coalitional games is to characterize the most desirable outcomes in terms of appropriate notions of fair worth distributions, which are usually called solution concepts. Traditionally, this issue has been studied in economics and game theory in the light of providing arguments and counterarguments about why such proposals are reasonable mathematical renderings of the intuitive concepts of fairness and stability. For instance, well-known and widely-accepted solution concepts are the Shapely value, the core, the kernel, the bargaining set, and the nucleolus.

More recently, however, Deng and Papadimitriou [1994] re-considered the definition of such concepts from a computer science perspective, by arguing that decisions taken by realistic agents should not involve unbounded resources to support reasoning, and by suggesting to formally capture such a bounded rationality principle by assessing the amount of resources needed to compute solution concepts in terms of their computational complexity. In particular, they considered the setting of graph games, where worths for coalitions over a set N of players are constructed over a weighted undirected Enrico Malizia and Luigi Palopoli and Francesco Scarcello D.E.I.S. Universit`a della Calabria I-87036 Rende, Italy

{emalizia,palopoli,scarcello}@deis.unical.it

graph G = 〈(N,E),w〉, whose nodes in N correspond to the players and where the list w encodes the edge weighting function, so that w(e) ∈ R is the weight associated with the edge e ∈ E. Then, the worth of an arbitrary coalition S ⊆ N is defined as the sum of the weights associated with the edges contained in S, i.e., as the value v(S) = ∑e∈E|e⊆S w(e).

Within the setting of graph games, Deng and Papadimitriou characterized the intrinsic complexity of various tasks related to solution concepts. For instance, they showed that checking whether the core is non-empty is co-NP-complete. Moreover, they provided a polynomial-time computable closedform characterization for the Shapely value, and showed that this value coincides with the nucleolus, whenever each of its components is non-negative. However, the picture of the complexity issues arising with graph games depicted by Deng and Papadimitriou [1994] is not complete. In particular, the complexity of the problems of checking whether an outcome belongs to the bargaining set and to the kernel was not derived and, in fact, these questions were explicitly stated as open problems there. In addition, the complexity of checking whether an outcome belongs to the nucleolus for general graph games was not derived.

1.1 Contributions

As a matter of fact, the modeling perspective introduced by Deng and Papadimitriou [1994] was very influential in the subsequent literature, and it inspired complexity analysis of several other kinds of compactly specified games (see, e.g., [Ieong and Shoham, 2005; Conitzer and Sandholm, 2006; Elkind et al., 2007; Bilbao, 2000]), that is, of games where associations of coalitions with their worths are implicitly represented as to avoid the exponential blow-up that would result if all of them were explicitly listed. Yet, despite the prominence gained in the last few years of studying the computational properties of solution concepts in graph games, and more generally for compact games, the questions raised by Deng and Papadimitriou are still open problems.

The first contribution of this paper is precisely to solve these open problems, by showing that, for graph games,

1. Checking whether an outcome is in the kernel is ΔP2 - complete;
2. Checking whether an outcome is the nucleolus is ΔP2 - complete; and,

1. Checking whether an outcome is in the bargaining set is ΠP2 -complete.

These main achievements come, however, not alone in the research reportedbelow. Indeed, we go beyond and study various computational issues arising in relevant generalizations and specializations of the setting of graph games.

Generalizations. With respect to generalizing graph games, we consider the fairly more general classes of games in polynomial characteristic function form within the setting discussed in [Bilbao, 2000], where the worth function is provided by means of an oracle, whose call requires polynomial time in size of the game representation. We say that these games are compact (or in compact form). E.g., graph games are an instance of this setting where, for each coalition S ⊆ N, v(S) can be computed in polynomial time as a summation of the weights of all those edges e ⊆ S. Other notable examples of classes of compact games includes the marginal contribution nets [Ieong and Shoham, 2005] and the weighted threshold games [Elkind et al., 2007]. Within this setting,

1. We show that nothing has to be paid for the succinctness of the specifications, since all the membership results that hold for graph games also hold for any class of compact games. Indeed, we show that, on compact games, checking the membership in the kernel, bargaining set and nucleolus are still in ΔP2 , ΠP2 , and ΔP2 , respectively.

Note that, while (1), (2), and (3) are mainly combinatorial contributions (for they rely on the definition of rather elaborate reductions), the contribution in (4) appears algorithmic in its nature. Indeed, it is achieved by showing that the various solution concepts on compact games can ultimately be defined in terms of suitable linear programs over exponentially many inequalities (succinctly specified, in their turn). In particular, those results are established by providing complexity bounds on several problems related to succinctly specified linear programs, which are of interest on their own, and where the complexity for programs with polynomially many constraints is well-known instead.

Specializations. Finally, in the last part of the paper, we investigate suitable specializations of graph games, by looking for tractable classes based on exploiting some of their graph invariants. In particular, we focused on the acyclicity property, motivated by the fact that many NP-hard problems in different application areas are known to be efficiently solvable when restricted to instances whose underlying structures can be modeled via acyclic graphs or nearly-acyclic ones, such as those graphs having bounded treewidth. In fact, Ieong and Shoham [2005] have already observed that deciding the membership of an outcome into the core and deciding the non-emptiness of the core are feasible in polynomial time on bounded treewidth marginal contribution nets. Here, we continue along this line of research, and

1. We show that, on graphs having bounded treewidth, the problems of checking whether an outcome is in the kernel is feasible in polynomial time.

Interestingly, the above result is established by showing how this solution concept can be expressed in terms of an optimization problem over Monadic Second Order Logic (MSO)

formulae. This was not observed in earlier literature, neither for the kernel, nor for other solution concepts. Thus, on graphs having bounded treewidth, tractability emerges as a consequence of Courcelle's Theorem [Courcelle, 1990] and of its generalization to optimization problems due to Arnborg, Lagergren, and Seese [Arnborg et al., 1991].

2 Cooperative Game Theory

A coalitional game G is a pair 〈N, v〉, where N is the set of all the players and where v : 2N ↦→R is the worth function.

A vector (xi)i∈N (with xi ∈ R) is an imputation of G if ∑i∈N xi = v(N ) and xi ≥ v({i}), for each i ∈ N. The set of all the imputations of G is denoted by X (G).

Several (solution) concepts have been proposed in the literature to characterize the most desirable imputations of coalitional games. Below, we recall the notions of kernel, bargaining set, and nucleolus (see, e.g., [Osborne and Rubinstein, 1994]), which will be the subject of our research here.

For any pair of players i and j of G, we denote by Ii,j the set of all coalitions containing player i but not player j. The excess of the generic coalition S at the imputation x ∈ X (G), denoted by e(S, x), is defined as v(S) -x(S), where x(S) is a shorthand for the value ∑i∈S xi. The surplus si,j(x) of i against j at x is si,j(x) = maxS∈Ii,j e(S, x).

Definition 2.1. The kernel K(G) of a game G = 〈N, v〉 is the set: K(G) = {x ∈ X (G) | si,j(x) > sj,i(x) ⇒ xj = v({j}), ∀i, j ∈ N, i ̸= j}. □

Let x be an imputation. We say that (y, S) is an objection of player i against player j to x if S ∈ Ii,j, y(S) = v(S), and yk > xk for all k ∈ S. If (y, S) is an objection of player i against player j to x, then we say i can object against j to x through S. A counterobjection to the objection (y, S) of i against j is a pair (z, T ) where T ∈ Ij,i, z(T ) = v(T ), and zk ≥ xk for all k ∈ T \ S and zk ≥ yk for all k ∈ T ∩ S. If (z, T ) is a counterobjection to the objection (y, S) of i against j, we say that j can counterobject to (y, S) through T . If there does not exist any counterobjection to (y, S), we say that (y, S) is a justified objection.

Definition 2.2. The bargaining set B(G) of G is the set of all imputations to which there is no justified objection. □

For any imputation x of G, we define the vector: θ(x) = (e(S1, x), e(S2, x), . . . , e(S2n-1, x)), where the various excesses of all coalitions (but the empty one) are arranged in non-increasing order. Let θ(x)[i] denote the i-th element of θ(x). For a pair of imputations x and y, we say that θ(x) is lexicographically smaller than θ(y), denoted by θ(x) ≺ θ(y), if there exists a positive integer q such that θ(x)[i] = θ(y)[i] for all i < q and θ(x)[q] < θ(y)[q].

Definition 2.3. The nucleolus N(G) of a game G is the set N(G) = {x ∈ X (G) | ∄y ∈ X (G) s.t. θ(y) ≺ θ(x)}. □

It is well-known that, for any game G, N(G) is a singleton (see, e.g., [Osborne and Rubinstein, 1994]).

3 On the Hardness of Solution Concepts

In this section, we shall characterize the complexity of the kernel, of the nucleolus, and of the bargaining set of graph games. With a small abuse of notation, if G is a weighted graph, we denote by G its associated graph game, too.

We next show a reduction from the ΔP2 -hard problem of deciding whether the lexicographically least significant variable is true in the lexicographically maximum satisfying assignment for a formula [Krentel, 1986] to the problem of deciding whether an imputation belongs to the kernel of a graph game.

Theorem 3.1. Let G be a graph game, and x an imputation of G. Then, deciding whether x belongs to K(G) is ΔP2 -hard.

Proof Idea. Let φ = c1 ∧ . . . ∧ cm be a 3CNF Boolean formula, that is, a Boolean formula in conjunctive normal form over the set of lexicographically ordered variables {α1, . . . , αn} where each clause contains three literals (positive or negated variables) at most. Based on φ, we build in polynomial time the weighted graph K(φ) = 〈(NK ,EK ),w〉, as discussed next (see Figure 1 for an illustration).

The set NK of nodes (i.e, players) includes: a variable player αi, for each variable αi in φ; a clause player cj, for each clause cj in φ; a literal player ℓi,j (either ℓi,j = αi,j or ℓi,j = ¬αi,j), for each literal ℓi (ℓi = αi or ℓi = ¬αi, respectively) as occurring in cj; and, two special players "chall" and "sat". The set EK consists of the three types of edges:

Positive edges: an edge {cj, ℓi,j} with w({cj, ℓi,j}) = 2n+3 , for each literal ℓi occurring in cj; an edge {chall, αi} with w({chall, αi}) = 2i , for each 1 ≤ i ≤ n; an edge {sat, αi} with w({sat, αi}) = 2i , for each 2 ≤ i ≤ n; the edge {sat, α1} with w({sat, α1}) = 21 + 20 .

"Penalty" edges: an edge {ℓi,j , ℓi′ ,j} with w({ℓi,j , ℓi′ ,j}) = -2m+n+7, for each pair of literals ℓi and ℓi′ occurring in cj; an edge {αi,j, ¬αi,j′} with w({αi,j, ¬αi,j′}) = -2m+n+7, for each variable αi occurring positively in cj and negated in cj′ ; an edge {αi, ¬αi,j} with w({αi, ¬αi,j}) = -2m+n+7, for each variable αi occurring negated in cj .

"Normalizer" edge: {chall, sat} with w({chall, sat}) = 1 - ∑e∈EK |e̸={chall,sat} w(e).

Consider the imputation x that assigns 0 to all players of K(φ), but to sat, which receives 1. By Definition 2.1, since sat is the only player that receives in x a payoff strictly greater than her worth as a singleton coalition, and since one may note that w({chall, sat}) ≥ D + 1, where D denotes the maximum worth over all the coalitions not covering the edge {chall, sat}, we have that x ∈ K(K(φ)) if and only if maxS∈Ichall,sat e(S, x) ≤ maxS∈Isat,chall e(S, x).

Now, observe that it is never convenient for a coalition to cover a penalty edge. Thus, since the formula is satisfiable, maxS∈Ichall,sat e(S, x) is precisely achieved over a coalition encoding a satisfying assignment for φ, thereby equating the value CS = m × 2n+3 + maxσ|=φ ∑αi |σ(αi )=true 2i .

The same reasoning applies to maxS∈Isat,chall e(S, x), with the difference that for each S, sat ∈ S implies that x(S) = 1 holds, and that the weight associated with the edge {sat, αi} is 2i , for each 2 ≤ i ≤ n, while 21 + 20 for the case where i = 1. Thus, this maximum coincides with the value SC = m× 2n+3 + maxσ|=φ (|{α1 | σ(α1) = true}| + ∑αi|σ(αi)=true 2i ) - 1.

Finally, CS ≤ SC holds if and only if α1 is true in the lexicographically maximum satisfying assignment for φ.

Theorem 3.2. Let G be a graph game, and x an imputation of G. Then, deciding whether x belongs to N(G) is ΔP2 -hard.

Proof Idea. The reduction is again from the problem of deciding whether α1 is true in the lexicographically maximum satisfying assignment for such a given formula φ. Let φ be a 3CNF Boolean formula and let (NK , EK ) be the graph built in the proof of Theorem 3.1. Let Nk = NK \ {sat}, let N k be the set of players {p | p ∈ Nk ∧ p ̸= α1} containing a copy of each player in Nk but α1, and let Nr = {a, a, b, b}. Moreover, let Ek = {{p, q} | {p, q} ∈ EK ∧ {p, q} ⊆ Nk}.

Based on φ, we define the weighted graph N (φ) = 〈(NN ,EN ),w〉, as discussed next (see Figure 2 for an illustration of the construction).

The set NN of nodes coincides with Nk ∪ N k ∪ Nr. The set EN of edges coincides with Ek ∪ {{p, q} | {p, q} ∈ Ek ∧ {p, q} ⊆ N k} ∪ {{α1, q} | {α1, q} ∈ Ek ∧ q ∈ N k} ∪ {{p, q} | p ∈ Nk \{α1}∧q ∈ N k}∪{{a, b}, {a, b}, {b, b}}. Moreover, weights partition edges into three groups:

Positive edges: w({cj, ℓi,j}) = w({cj, ℓi,j}) = 2n+3 , for each literal ℓi occurring in cj; w({chall, αi}) = w({chall, αi}) = 2i , for each 2 ≤ i ≤ n; and, w({chall, α1}) = w({chall, α1}) = 21 .

"Penalty" edges: w({ℓi,j, ℓi′ ,j}) = w({ℓi,j, ℓi′ ,j}) = -2m+n+7, for each pair of literals ℓi and ℓi′ occurring in cj ; w({αi,j , ¬αi,j′ }) = w({αi,j , ¬αi,j′ }) = -2m+n+7, for each variable αi occurring positively in cj and negated in cj′ ; w({αi, ¬αi,j}) = w({αi, ¬αi,j}) = -2m+n+7, for each variable αi with i ̸= 1 occurring negated in cj; w({α1, ¬α1,j}) = w({α1, ¬α1,j}) = -2m+n+7, for each clause cj where α1 negatively occurs; and w({p, q}) = -2m+n+7, for each pair of players p ̸= α1 and q, with p ∈ Nk and q ∈ N k.

Consider the graph game N (φ), which can in fact be built in polynomial time, and the imputation x that assigns 0 to all players of N (φ), but to α1, which receives 1. Note that x is an imputation, because of the weights of the edges in Nr.

Let S∗ = argmaxS⊆Nk v(S). Along an analogous line of reasoning as in the proof of Theorem 3.1, one can show that v(S∗) = m× 2n+3 +maxσ|=φ ∑αi|σ(αi)=true 2i and, in fact, that α1 ∈ S∗ if and only if α1 evaluates to true in the lexicographically maximum satisfying assignment for φ.

Moreover, one can show the two following properties: (i) the excess of S∗ is the maximum one, no matter what specific imputation is considered. Therefore, x is in the nucleolus if and only if it minimizes the excess of S∗. And (ii), each coalition S ⊆ Nk has a dual coalition S ⊆ N k ∪ {α1} (and viceversa) such that S = {p | p ∈ S ∧ p ̸= α1} ∪ {α1 | α1 ∈ S} and v(S) = v(S).

By combining the two observations above, it emerges that if α1 evaluates to true in the lexicographically maximum satisfying assignment for φ, then all the coalitions achieving the maximum excess precisely share α1 only-in particular, this is the case because there is no single normalizer edge, which instead would have occurred in each coalition achieving the maximum excess. Hence, assigning 1 to α1 at x is the best we can do as to minimize such maximum excesses.

On the other hand, if α1 evaluates to false in the lexicographically maximum satisfying assignment for φ, then it is not convenient that α1 retains all the worth.

Theorem 3.3. Let G be a graph game, and x be an imputation of G. Then, deciding whether x belongs to B(G) is ΠP2 -hard.

Proof Idea. Let Φ = (∀α)(∃β)φ(α, β) be a quantified Boolean formula over the variables α = {α1, . . . , αn} and β = {β1, . . . , βr}, where φ(α, β) = c1 ∧. . .∧cm is a 3CNF

formula, and where each universally quantified variable αk ∈ α occurs only in the two clauses ci(k) = (αk ∨ ¬βk) and c¯i(k) = (¬αk ∨ βk). Deciding whether such a quantified formula is valid is known to be a ΠP2 -complete problem.

Based on Φ, we define the weighted graph BS(Φ) = 〈(NBS , EBS ), w〉, as discussed next (see Figure 3).

The set NBS of the nodes (i.e., players) includes: a clause player cj, for each clause cj; a literal player ℓi,j, for each literal ℓi occurring in cj; and, two special players "chall" and "sat". The set EBS of edges includes three kinds of edges.

Positive edges: an edge {cj, ℓi,j} with w({cj, ℓi,j}) = 1, for each literal ℓi occurring in the clause cj; and an edge {chall, ℓi,j} with w({chall, ℓi,j}) = 1, for each literal ℓi of the form αi or ¬αi (i.e., built over a universally quantified variable) occurring in cj .

"Penalty" edges: an edge {γi,j, ¬γi,j′} with w({γi,j, ¬γi,j′}) = -m - 1, for each variable xi (either γi = αi or γi = βi) occurring in cj and cj′ ; an edge {ℓi,j, ℓi′ ,j} with w(ℓi,j, ℓi′ ,j) = -m - 1, for each pair of literals ℓi and ℓi′ occurring in cj; an edge {chall, ℓi,j} with w({chall, ℓi,j}) = -m - 1, for each literal ℓi of the form βi or ¬βi (i.e., built over an existentially quantified variable) in cj; and, an edge {chall, cj} with w({chall, cj}) = -m - 1, for each cj.

Note that the graph game BS(Φ) can be built in polynomial time fromΦ. Then, consider the imputation x that assigns m to sat, n - 1 to chall, and 0 to all other players. Note that x is indeed an imputation, since v(N ) = m+ n - 1 because w({chall, sat}) = m + n - 1 - ∑e∈EBS |e̸={chall,sat} w(e).

Firstly, we can prove that no player has a justified objection against a clause or a literal player, that no player has a justified objection against chall, and that no player different from chall has a justified objection against sat. Therefore, we can focus on the objections of chall against sat.

Then, it can be observed that the objections of chall against sat are in a one-to-one correspondence with truth assignments for universally quantified variables. Moreover, counterobjections encode ways to satisfy the formula, while being consistent with the assignment encoded in the objection at hand. Therefore, x is in the bargaining set if and only if Φ is valid.

4 Membership Results

In this section, we show that the various hardness results derived in Section 3 are tight, since the corresponding membership results can be established. In fact, memberships are proven to hold over much wider classes of games than graph games, that we call compact games. Formally, let C be a class of games. We say C is a class of compact games if, for every game G ∈ C, the game encoding (whose size is denoted by ||G||) includes the set N of the players (so that, |N| ≤ ||G||), and the worth function v is implicitly given by an oracle such that, for each coalition S, v(S) can be computed in polynomial time w.r.t. ||G||. Hereafter, let Ccg be a class of compact games. We start by analyzing the kernel.

Theorem 4.1. For any G ∈ Ccg, deciding whether an imputation x belongs to K(G) is feasible in ΔP2 .

Proof. Given the imputation x, we firstly observe that, for each pair of players i and j, the value si,j (x) can be computed in polynomial time by means of a binary search over the range of the possible values for the worth functions, by using an NP oracle. Indeed, for any value h in this range, we can decide in NP whether there is a coalition S such that v(S) > h, by guessing the coalition S, and by checking in polynomial time that v(S) > h. Eventually, we can compute in polynomial time the value v({i}) for each player i ∈ {1, . . . , n}. Thus, after polynomially-many oracle calls, we may check in polynomial time that for each pair of players i and j such that xj ̸= v({j}), it is the case that si,j(x) ≤ sj,i(x).

The cases of the bargaining set and of the nucleolus are more intricate and will be discussed in details below.

4.1 Bargaining Set

It was argued that checking whether an imputation belongs to the bargaining set is in ΠP2 for graph games, with the argument that one may guess in NP objections and counterobjections (hence, by focusing only on those that can be represented via polynomially many bits) [Deng and Papadimitriou, 1994]. Our main achievement is to show that membership in ΠP2 can indeed be established independently of the precision adopted to represent the real values of interest in the game. To this end, we first provide a useful characterization of a player i having a justified objection against some player j.

Lemma 4.2. Player i has a justified objection against player j to x through coalition S ∈ Ii,j if and only if there exists a vector y ∈ R|S| such that: (1) y(S) = v(S); (2) yk > xk, for each k ∈ S; and, (3) v(T ) < y(T ∩S)+x(T \S), ∀T ∈ Ij,i.

Theorem 4.3. For any G ∈ Ccg, deciding whether an imputation x belongs to B(G) is feasible in ΠP2 .

Proof Idea. We prove that the complementary problem of deciding whether x ̸∈ B(G) is in ΣP2 , because an NTM may guess two players i and j, and a coalition S ∈ Ii,j , and then it may perform a co-NP check that the system of inequalities in Lemma 4.2, determined by i, j, and S, has a solution. We have to show that deciding whether this system, say LP, has no solutions is feasible in NP. Observe that LP has |S| variables (y1, . . . , y|S|). From Helly's Theorem, given a collection C = {c1, . . . , ch} of convex subsets of Rn, ⋂ci∈C ci = ∅ implies the existence of a collection C ′ ⊆ C such that |C ′ | ≤ n + 1 and ⋂ci∈C′ ci = ∅. Hence, if LP has no solutions, there is a subsystem LP′ of LP consisting of (at most) |S| +1 inequalities that has no solutions, too. Thus, an NTMmay guess LP′ , and check in polynomial time that LP′ is infeasible, by standard linear programming techniques.

4.2 Nucleolus

Let G = 〈N, v〉 be a game, and consider the following linear programming problem LPk, for k > 0:

where Λ0 = {∅,N}, ϵ0 = 0, F0 = ∅, and where ϵr is the optimum of LPr, Λr = {S ⊆ N | x(S) = v(S) - ϵr, for every x ∈ Vr} with Vr = {x | x ∈ X (G) ∧ (x, ϵr) is an optimal solution to LPr}, and Fr = {S ⊆ N | x(S) = y(S), ∀x, y ∈ Vr}.

FollowingMaschler et al. [1979], it can be shown that there is an index k∗ ≤ |N| such that LPk∗ has exactly one optimal solution (x∗, ϵk∗ ), where x∗ is the nucleolus of G.

Theorem 4.4. For any G ∈ Ccg, computing the nucleolus of G is feasible in FΔP2 , and thus deciding whether an imputation is the nucleolus of G is in ΔP2 .

Proof Idea. We build in FΔP2 a linear program ¯ LP that is equivalent to LPk∗ and consists of n equalities at most, where n is the number of players N in G. Then, the nucleolus is clearly computable in polynomial time from ¯ LP. To compute this program, we represent in a succinct form the above programs LPk, for 1 ≤ k ≤ n. Roughly, equations of the form x(S) = v(S) - ϵr are replaced by some basis Bk-1 of the affine hull of the polytope defined by LPk-1. We can show that such a basis can be computed in FΔP2 . Moreover, given any coalition S, there is a polynomial-time oracle giving its associated inequality in LPk, which amounts to decide whether the vector of Rn encoded by S may be obtained as a linear combination of basis vectors. If this test fails, then the inequality x(S) ≥ v(S) - ϵ belongs to LPk. Then, we compute the optimal value for this program, and continue with the next program. We can show that solving such a succinct linear program is feasible in FΔP2 , as well as computing the dimension of its associated polytope. After at most n steps, we get a linear program whose associated polytope has dimension 0, and we stop the procedure. It can be seen that the program consisting of all the bases computed so far is equivalent to LPk∗ , and of course has a unique solution (as the polytope dimension is 0), which is the nucleolus of G.

5 Tractable Classes of Graph Games

Monadic Second Order (MSO) Logic formulae on graphs are built from logical connectives ∨, ∧, and ¬, the membership relation ∈, the quantifiers ∃ and ∀, and vertices variables and vertex sets variables-in addition, it is often convenient to use symbols like ⊆, ⊂, ∩, ∪, and → with their usual meaning, as abbreviations. Courcelle [1990] considered an extension of MSO, called MSO2, where variables for edge sets are also allowed. The fact that an MSO2 sentence φ holds over a graph G is denoted by G |= φ.

An important generalization of MSO2 formulae to optimization problems is presented by Arnborg et al. [1991]. Next, we state a simplified version of these kinds of problems. Optimization problems are defined over MSO2 formulae containing free variables, and over graphs that are weighted on both nodes and edges.

Let G = 〈(N, E), fN , fE〉 be a weighted graph where fN and fE are the lists of weights associated with nodes and edges, respectively. Then, fN(v) (resp., fE(e)) denotes the weight associated with v ∈ N (resp., e ∈ E).

Let φ(X, Y ) be an MSO2 formula over the graph (N,E), where X and Y are the free variables occurring in φ, with X (resp., Y ) being a vertex (resp., edge) set variable. For a pair of interpretations 〈zN, zE〉 mapping X to subsets of N and Y to subsets of E, we denote by φ[〈zN, zE〉] the MSO2 formula (without free variables) where X and Y are replaced by the sets zN(X ) and zE(Y ), respectively. A solution to φ over G is a pair of interpretations 〈zN, zE〉 such that (N, E) |= φ[〈zN, zE〉] holds. The cost of 〈zN, zE〉 is the value ∑x∈zN(X) fN(x) + ∑y∈zE(Y ) fE(y). A solution of minimum cost is said optimal.

For a positive constant k, let hereafter Ck be a class of graphs having treewidth bounded by k.

Theorem 5.1 (simplified from [Arnborg et al., 1991]). Let φ be a fixed MSO2 sentence and let G = 〈(N, E), fN, fE〉 be a weighted graph such that (N, E) ∈ Ck. Then, computing an optimal solution to φ over G is feasible in P (w.r.t. ||G||).

5.1 MSO2 and the Kernel

We are now in the position of stating a tractability result about the kernel over bounded treewidth graph games.

Theorem 5.2. Let G = 〈(N,E),w〉 be a graph game such that (N,E) ∈ Ck, and let x be an imputation of G. Then, deciding whether x ∈ K(G) is feasible in P.

Proof Idea. Firstly, consider the problem of computing the coalition over which the maximum excess at x is achieved. For each X ⊆ N and Y ⊆ E, consider the following MSO2 formula, stating that Y is the set of all those edges e ∈ E such that e ⊆ X: proj(X, Y ) ≡ ∀v, v′ ({v, v′} ∈ Y → {v, v′} ⊆ X ) ∧ ∀v, v′ ({v, v′} ⊆ X ∧ {v, v′} ∈ E → {v, v′} ∈ Y ).

Let wE and wN be such that wE({v, v′ }) = -w({v, v′}) and wN(v) = xv, and observe that maxS⊆N e(S, x) = minS⊆N (x(S) - v(S)) coincides with the cost of an optimal solution to proj(X, Y ) over 〈(N, E), wN , wE〉.

Recall, now, that x ∈ K(G) if and only if, for each pair of players i ̸= j, si,j(x) > sj,i(x) ⇒ xj = v({j}), where si,j(x) = maxS∈Ii,j e(S, x). In fact, one may modify the weights of i and j in G so that, in any optimal solution of the above formula, i ∈ X and j /∈ X, so that maxS⊆N e(S, x) coincides with si,j. Hence, by Theorem 5.1 and the above MSO2 formula, si,j (and sj,i, too) is computable in polynomial time. By checking this condition for each pair i, j, membership of x in K(G) can be decided in polynomial time.

6 Conclusions

In this paper, we have provided a picture of the complexity issues arising from graph games (by closing several longstanding open problems) and, more generally, with succinctly specified coalitional games. Our membership results apply to most of the classes of compact games proposed in the literature, while hardness results represent lower bounds (and, in fact, exact bounds) for the complexity of reasoning over them.

The paper also introduced a logic-based approach to isolate classes of tractable games for the kernel. An avenue of further research is to apply this approach to trace the tractability frontier for the nucleolus and the bargaining set.