On the Complexity of the Core over Coalition Structures

1 Introduction

A coalitional game is a pair G = 〈N, v〉, where N is a set of players, and v is a function associating with each coalition S ⊆ N the worth v(S) ∈ R that players in S obtain by collaborating with each other. A fundamental problem for coalitional games is to characterize the most desirable outcomes in terms of appropriate notions of worth distributions, which are called solution concepts. Traditionally, this problem has been formulated over games that are superadditive, i.e., v(S ∪ T) ≥ v(S) + v(T) is assumed to hold, for each pair of disjoint coalitions S and T . Indeed, on superadditive games, the grand-coalition consisting of all the players in N forms and, accordingly, solution concepts just suggest how the total worth v(N) can be divided among them in a way that is fair and stable [Osborne and Rubinstein, 1994].

While being rather appealing from a conceptual viewpoint, superadditivity might however not hold in several social environments because of a plethora of different reasons, ranging from normative considerations, to information (observability) imperfections, and to technological constraints (cf. [Greenberg, 1994]). Under these circumstances, players might want to organize themselves in a coalition structure, i.e., in a partition π of N consisting of disjoint and exhaustive coalitions. By doing so, the total available worth ∑C∈π v(C) might happen to be greater than the worth v(N) associated with the grand-coalition. Whenever this is the case, classical solution 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

concepts are not appropriate, and stable outcomes have to be characterized from the "coalition structure" perspective, as it was first suggested by Aumann and Dreze [1974]. As an example, the core of a coalitional game, which is probably the best-known solution concept, finds a counterpart in the coalition structure core-formal definitions are in Section 2.

1.1 Complexity of Solution Concepts

In the last few years, coalitional games gained popularity within the artificial intelligence community, where solution concepts have been often (re-)considered from the computational complexity viewpoint. Indeed, moving from the observation that explicitly listing all associations of coalitions with their worths requires exponential space, compact gameencoding mechanisms have been proposed, and the amount of resources needed to compute solution concepts on the basis of such encodings have been characterized (see, for instance, [Deng and Papadimitriou, 1994; Elkind et al., 2009; Ieong and Shoham, 2005; Conitzer and Sandholm, 2006]).

As a matter of fact, even though such complexity studies usually focus on classes of games that are not superadditive, they do not consider solution concepts specifically designed for games with coalition structures. Rather, they tacitly assume that the goal is to distribute the total worth v(N) available to the grand-coalition, even when it is more efficient to form some coalition structures. Thus, while several deep results have been attained, the following foundational questions did not find even partial answers in the literature:

1. How complex are superadditive games? The main source of our current knowledge on the complexity of superadditive games is the work by Conitzer and Sandholm [2006], who showed that deciding whether the core is not empty is an NP-complete problem, even when restricted on superadditive games (based on synergies among coalitions). However, as they explicitly pointed out, even computing the worth associated with some given coalition is NP-hard in the proposed encoding. Hence, while the intractability of the core comes with no surprise in that setting, we still do not know whether core-related problems remain intractable over superadditive games whose worth functions can moreover be computed in polynomial-time.
2. How complex are coalition structures? The complexity of solution concepts in the presence of coalition structures has

been recently investigated by Elkind et al. [2008], where weighted voting games have been considered. Basically, they observed that checking the non-emptiness of the coalition structure core and whether a given outcome belongs to it are NP-hard and co-NP-complete problems, respectively. Since these problems are feasible in polynomial time over games without coalition structures, the results evidence that coalition structures provide an additional source of complexity to solution concepts. Note that an upper bound for the non-emptiness problem was missing in [Elkind et al., 2008]. Moreover, no analysis has been conducted on corerelated concepts in presence of coalition structures of games with arbitrary polynomial-time computable worth functions.

3) Which restrictions make coalition structures easy? Many NP-hard problems arising 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 [Robertson and Seymour, 1984]. In particular, various classical solution concepts on game encodings whose structures have bounded treewidth are tractable (see, e.g., [Greco et al., 2009; Ieong and Shoham, 2005; Brafman et al., 2010]). Good news are also known for solution concepts over coalition structures. With any coalitional game G = 〈N, v〉, we can associate an interaction graph IG(G) over the set N of players prescribing the set of coalitions that are allowed to form: A coalition S can form only if the subgraph of IG(G) induced over S is connected. A beautiful result by Demange [2004] states that the coalition structure core is non-empty over games whose associated interaction graph is a tree. Thus, there is hope that corerelated questions over bounded treewidth games with coalition structures are tractable. Yet, assessing whether this is actually the case was not explored in earlier literature.

1.2 Contribution

In this paper, we provide answers to the three questions illustrated above over games with polynomial-time computable worth functions. Complexity results are given for superadditive games, for games with coalition structures, and for games whose sets of feasible coalitions are restricted over tree-like interaction graphs. The analysis is focused on the well-known notion of the core, and on two related weaker stability criteria: the least core [Maschler et al., 1979], which is a classical approximation of the core where an additional penalty is imposed for leaving the grand coalition, and the recently introduced cost of stability [Bachrach et al., 2009], which is the minimum worth that a benevolent external party must supply in order for the game to have a non-empty core. In order to establish computational results, novel characterizations for the core and for the cost of stability over coalitional games with coalition structures have been derived, which are of independent technical and conceptual interest on their own.

2 Formal Framework

Let G = 〈N, v〉 be a coalitional game. The following notation is inspired by [Osborne and Rubinstein, 1994; Elkind et al., 2008; Bachrach et al., 2009; Meir et al., 2009].

Core of Coalitional Games. Let x be a payoff vector in R|N| whose components are one-to-one associated with the players in N, i.e., xi ∈ R is the value received in x by player i ∈ N. For any coalition S ⊆ N, let x(S) denote the value ∑i∈S xi.

We say that x ∈ R|N| is an imputation if it is individually rational, i.e., xi ≥ v({i}), for each i ∈ N, and efficient, i.e., x(N) = v(N). The core of G is the set Core(G) of all imputations x such that x(S) ≥ v(S) holds, for each S ⊆ N.

Let π be a coalition structure. We say that a payoff vector x ∈ R|N| is efficient w.r.t. π if x(C) = v(C), for each coalition C ∈ π. A CS-imputation is a pair 〈π, x〉 where π is a coalition structure, and x ∈ R|N| is a payoff vector that is individually rational and efficient w.r.t. π. The coalition structure core of G is the set CS-Core(G) of all CS-imputations 〈π, x〉 such that x(S) ≥ v(S) for all S ⊆ N.

Note that if x ∈ Core(G), then 〈{N}, x〉 ∈ CS-Core(G).

Cost of Stability. Let GΔ = 〈N, vΔ〉 denote the coalitional game such that vΔ(S) = v(S), for each coalition S ⊂ N; and vΔ(N) = v(N) + Δ. The cost of stability of G is the value COS(G) = min{Δ | Core(GΔ) ̸= ∅ ∧ Δ ≥ 0}.

For any coalition structure π = {C1, . . . , Cm} and for any vector ⃗Δ ∈ Rm, let G⃗Δ = 〈N, v⃗Δ〉 be the coalitional game with v⃗Δ(S) = v(S), for each coalition S ⊆ N such that S /∈ π; and v⃗Δ (Cj) = v(Cj)+ ⃗Δj , for each coalition Cj ∈ π.

The cost of stability of π in G is the value CS-COS(G, π) = min{∑mj=1 ⃗Δj | ∃x, 〈π, x〉 ∈ CS-Core(G⃗Δ ) and ∀j ∈ {1, . . . ,m}, ⃗Δj ≥ 0}. The coalition structure cost of stability of G, denoted by CS-COS(G), is the minimum value of CS-COS(G, π) over all possible coalition structures π of G.

Least Core Value. For any real number ε, let G-ε = 〈N, v-ε〉 be the coalitional game such that v-ε(S) = v(S) - ε, for each S ⊂ N, and v-ε(N) = v(N). The least core (resp., least coalition structure core) of G is the set of all imputations in the set Core(G-ε) (resp., CS-Core(G-ε)) such that Core(G-ε) ̸= ∅ (resp., CS-Core(G-ε) ̸= ∅), and Core (G-¯ ε) = ∅ (resp., CS-Core(G-¯ ε) = ∅) for each ¯ ε < ε.

The number ε determined by the least core (resp., least coalition structure core) is called its value, and it is hereinafter denoted by LCV(G) (resp., CS-LCV(G)).

Computational Setting. We assume that the input for any reasoning problem consists (at least) of a game G = 〈N, v〉 whose worth function v is an oracle computable in polynomial time in the size ||G|| of the game representation. 1 This setting encompasses all those where games are (implicitly) described over some "compact encodings", and where simple calculations on such encodings are to be performed to compute the worth of any coalition. Therefore, our membership results will immediately carry over to the classes of games defined by such encodings, whereas hardness results are specific to the oracle setting, and do not hold in general for any (sub)setting. Analysis will be focused on the problems:

• CORE-CHECK: Given a payoff vector x, is x in Core(G)?
• CORE-NONEMPTINESS: Is Core(G) ̸= ∅?

1 As usual, it is implicitly assumed that the game representation includes the list of players, i.e., for every coalition S, ||S|| ≤ ||G||.

• COS: Given a real number Δ, is COS(G) ≤Δ?
• LCV: Given a real number ε, is LCV(G) ≤ ε?

Moreover, for each problem P, we analyze the problem CS-P over the corresponding notion for coalition structures.

3 A Fresh Look at Coalition Structures

For any coalition structure π, let CS-v(π) denote the total worth ∑C∈π v(C). Let sw(G) be the social welfare of G, i.e., the maximumworth CS-v(π) over all the possible coalition structures π. The set of all coalition structures π such that CS-v(π) = sw(G) is denoted by CS-opt (G).

Recall that G is cohesive if v(N) ≥ CS-v(π), for each coalition structure π [Osborne and Rubinstein, 1994], and that, though not necessarily superadditive, the grand-coalition anyway always forms in cohesive games. Define ˜ G = 〈N, ˜ v〉 as the cohesive game, called the cohesive cover of G, where ˜ v(S) = v(S) for each coalition S ⊂ N, and ˜ v(N) = sw(G).

3.1 Characterization of CS-Cores

In [Aumann and Dreze, 1974], it has been observed that the CS-core can be characterized in terms of the superadditive cover of G, which is the superadditive game ˆ G = 〈N, ˆ v〉 such that, for each S ⊆ N, ˆ v(S) is the maximumworth CS-v(πS) over all the possible coalition structures πS of S. Formally, it holds that Core( ˆ G) = ∅ if, and only if, CS-Core(G) = ∅.

Our first result is to show that, in order to characterize CScores, we can just "cover" the grand-coalition (by the cohesive cover ˜ G) rather than all the possible coalitions (as in ˆ G).

Proof. Consider a CS-imputation 〈π, x〉 ∈ CS-Core(G). By definition, x(S) ≥ v(S), for each coalition S ⊆ N. And, it is well-known that x(N) = sw(G). Hence, x ∈ Core( ˜ G).

Lemma 3.2. If x ∈ Core( ˜ G), then 〈π, x〉 ∈ CS-Core(G), for each π ∈ CS-opt (G).

Proof. Consider any imputation x ∈ Core( ˜ G). Let π be any coalition structure belonging to CS-opt(G), and observe that ∑C∈π x(C) = x(N) = ˜ v(N) = sw(G) = CS-v(π) = ∑C∈π v(C). Moreover, as π ∈ CS-opt(G), we have ∑C∈π v(C) = ∑C∈π ˜ v(C) and, hence, ∑C∈π x(C) = ∑C∈π ˜ v(C). Recall now that x ∈ Core( ˜ G) also implies that x(S) ≥ ˜ v(S) holds, for each coalition S ⊆ N (and, thus, for each C ∈ π). Combined with the above equality, this leads to conclude that x(C) = ˜ v(C), for each C ∈ π. That is, x is efficient w.r.t. π. Eventually, to conclude the proof, note that x(S) ≥ ˜ v(S) = v(S) for each S ⊂ N, and that x(N) = sw(G) ≥ v(N). Hence, 〈π, x〉 ∈ CS-Core(G).

The above two lemmas immediately entail the characterization of CS-cores in terms of the cores of cohesive covers.

We conclude by specializing Theorem 3.3 to cohesive (and, hence, to superadditive) games. To this end, just observe that if G is cohesive, then sw(G) = CS-v({N}) = v(N).

Corollary 3.4. Let G be a coalitional game that is cohesive. Then, (1) CS-Core(G) = CS-opt(G) × Core(G); (2) CS-Core(G) = ∅ if, and only if, Core(G) = ∅; and, (3) x ∈ Core(G) if, and only if, 〈{N}, x〉 ∈ CS-Core(G).

3.2 Characterization of the CS-COS

Our second result in this section is to show that cohesive covers can also be exploited to characterize (in terms of the standard cost of stability) the coalition structure cost of stability.

Proof. We shall show that, for any Δ, CS-COS(G) ≤ Δ if, and only if, COS( ˜ G) ≤ Δ, from which the claim follows.

˜

First, we show that COS( G) ≤ Δ entails CS-COS(G) ≤ Δ. Let x be a payoff vector in Core( ˜ GΔ), hence a witness that COS( ˜ G) ≤ Δ. Then, x(N) = sw(G) + Δ and, for each S ⊆ N, x(S) ≥ v(S) hold. Consider a coalition structure π = {C1, . . . , Cm} with CS-v(π) = sw(G), and let ⃗Δ ∈ Rm be the vector such that ⃗Δj = x(Cj) - v(Cj) ≥ 0, for each j ∈ {1, . . . ,m}. We claim that 〈π, x〉 ∈ CS-Core(G⃗Δ ). Indeed, x(S) ≥ v(S) = v⃗Δ(S), for each S ̸∈ π, and x(Cj) = v(Cj) + ⃗Δj = v⃗Δ(Cj), for each Cj ∈ π. Thus, CS-COS(G) ≤ ∑mj=1 ⃗Δj. To conclude, notice that x(N) = ∑mj=1 x(Cj ) = CS-v(π) + ∑mj=1 ⃗Δj = sw(G) + ∑mj=1 ⃗Δj . In fact, we have already observed that x(N) = sw(G) +Δ holds. It follows that ∑mj=1 ⃗Δj = Δ.

Now, we show that CS-COS(G) ≤ Δ implies in its turn COS( ˜ G) ≤ Δ. To this end, note that if CS-COS(G) ≤ Δ, then there is a coalition structure π = {C1, . . . , Cm}, a vector ⃗Δ ∈ Rm with ∑mj=1 ⃗Δj = Δ and ⃗Δj ≥ 0, ∀j ∈ {1, . . . ,m}, and a payoff vector x such that 〈π, x〉 ∈ CS-Core(G⃗Δ). Thus, x(S) ≥ v(S), for each S ⊆ N, and x(Cj) = v(Cj) + ⃗Δj , for each Cj ∈ π. Observe now that x(N) = ∑mj=1 x(Cj) = CS-v(π)+Δ ≤ sw(G)+Δ. Let x′ be the payoff vector such that x′i = xi + (sw(G) +Δ- x(N))/|N|. Then, x′ (S) ≥ x(S) ≥ v(S), for each S ⊆ N, and x′ (N) = sw(G) +Δ, i.e., x′ ∈ Core( ˜ GΔ). Hence, COS( ˜ G) ≤ Δ.

As a cohesive game G coincides with its cohesive cover ˜ G, the following is immediate.

Corollary 3.6. If G is cohesive (or superadditive), then CS-COS(G) = COS(G).

4 Concepts without Coalition Structures

In this section, we provide the answer to question (1) posed in the Introduction, by characterizing the complexity of corerelated problems on superadditive games.

Hardness results will be established via reductions that refer to Boolean formulae. Assume that a formula Φ is given, and let vars(Φ) be the set of all its variables. For any set S, let σ(S) be the truth assignment where X ∈ vars(Φ) is true if X occurs in S. The fact that σ(S) satisfies Φ is denoted by σ(S) |= Φ. Let vars(Φ) be the set {¬X | X ∈ vars(Φ)}. Literals in vars(Φ) ∪ vars(Φ) shall be viewed as players. In particular, a coalition S ⊆ vars(Φ) ∪ vars(Φ) is consistent (w.r.t. Φ) if, ∀X ∈ vars(Φ), |{X, ¬X} ∩ S| = 1 holds.

We start with CORE-NONEMPTINESS and CORE-CHECK. Theorem 4.1. CORE-NONEMPTINESS and CORE-CHECK are co-NP-complete. Hardness holds on superadditive games.

Proof. Membership in co-NP was shown in [Malizia et al., 2007]. Hardness results are next established via reductions from the co-NP-complete problem of deciding whether a Boolean formula Φ is unsatisfiable.

Given a formula Φ, we build in polynomial time the game G(Φ) = 〈N, v〉, where N = vars(Φ) ∪ vars(Φ) and where, for each set of players S, v is such that:

Consider CORE-CHECK: Let ¯x be such that ¯xi = 2/|N|, for each i ∈ N, and note that ¯x is individually rational and efficient. We claim that Φ is unsatisfiable ⇔ ¯x ∈ Core(G(Φ)).

• (⇒) Assume that Φ is unsatisfiable. Then, there is no coalition S with σ(S) |= Φ. Thus, for any coalition S such that |S| = |N|/2, we have v(S) = 0, and hence ¯x(S) ≥ v(S). Moreover, for any coalition S such that |S| > |N|/2 (resp., |S| < |N|/2), ¯x(S) ≥ v(S) = 2|S|/|N| (resp., ¯ x(S) ≥ v(S) = 0). Thus, ¯x ∈ Core(G(Φ)).

¯

• (⇐) Assume that Φ is satisfiable. Then, there is a coalition S such that σ( ¯ S) |= Φ. It follows that v( ¯ S) = 1+1/|N| > 1 = ¯ x( ¯ S). Therefore, ¯ x /∈ Core(G(Φ)).

Consider CORE-NONEMPTINESS: Consider any element x ∈ Core(G(Φ)). Then, for each player i ∈ N, x(N \{i}) ≥ v(N \{i}) = 2(|N|-1)/|N| = 2-2/|N|. Moreover, as x is efficient, we have x(N) = 2 and, thus, xi = 2/|N| = ¯ xi, for each i ∈ N. It follows that Core(G(Φ)) ̸= ∅ if, and only if, ¯x ∈ Core(G(Φ)) and thus if, and only if, Φ is unsatisfiable.

To conclude the proof, we now show that G(Φ) is superadditive. To this end, assume, w.l.o.g., that a variable evaluates true in every satisfying assignment, i.e., that Φ is of the form ¯Φ ∧ W, where W is a variable not in ¯Φ. Moreover, observe that |S| = |N|/2 holds, for any consistent coalition S. Then, let S and T be two non-overlapping coalitions, i.e., S ∩ T = ∅, and let us check that v(S ∪ T ) ≥ v(S) + v(T ).

If max{|S|, |T |} < |N|/2, then v(S∪T ) ≥ v(S)+v(T ) = 0. If max{|S|, |T |} > |N|/2 (w.l.o.g., |S| > |N|/2 and |T | < |N|/2, as S ∩ T = ∅), then v(S ∪ T) = 2(|S| + |T |)/|N| ≥ v(S) + v(T) = 2|S|/|N|. If max{|S|, |T |} = |N|/2, then v(S∪T ) = 2(|S|+|T |)/|N| ≥ 1+2/|N|, while v(S) + v(T ) ≤ 1 + 1/|N| as only one coalition can contain W and, thus, possibly encode a satisfying assignment.

Complexity results for COS and LCV follow easily.

Corollary 4.2. COS and LCV are co-NP-complete. Hardness hold on superadditive games.

Proof. Hardness follows by observing that deciding whether COS(G) ≤ 0 (resp., LCV(G) ≤ 0) coincides with the CORENONEMPTINESS problem. For the membership, note that in order to decide whether COS(G) ≤ Δ (resp., LCV(G) ≤ ε), we can check whether Core(GΔ) ̸= ∅ (resp., Core(G-ε) ̸= ∅), which is feasible in co-NP [Malizia et al., 2007].

5 Concepts with Coalition Structures

We next discuss the complexity of core-related questions for solution concepts designed to deal with coalition structures. A summary of our results is depicted in Figure 1, which provides the answer to question (2) of the Introduction.

Note first that, after Corollary 3.4 and Corollary 3.6, results for superadditive games in Figure 1 immediately derive from the results we discussed in Section 4. We omit the straightforward details, but we still want to stress a subtle technical issue arising here, which is sometimes ignored in the literature: Restricting the analysis of a problem P over some specific class C means that the analysis is carried under the promise that all instances being provided as input belong to C. Of course, it is desirable that confirming/disproving the promise of membership in C is not more complex than solving P over C. In fact, we next show that checking whether a game is superadditive does not represent a computational overhead w.r.t. the complexity results emerging from Figure 1.

Theorem 5.1. Deciding whether a coalitional game is superadditive is co-NP-complete.

Proof Sketch. The problem is in co-NP, as in order to prove that a given game G = 〈N, v〉 is not superadditive, it suffices to guess two disjoint coalitions S and T and then check in deterministic polynomial-time that v(S ∪ T ) < v(S) + v(T ). In particular, recall that computing v(S ∪ T ), v(S), and v(T ) are feasible in polynomial time in our setting.

As for the hardness, given a Boolean formula Φ, consider the game G(Φ) = 〈N, v〉 where N = vars{Φ} ∪ vars{Φ}, and where v(S) = 1 if S is consistent and σ(S) |= Φ, and v(S) = 0 otherwise. It is immediate to check that Φ is unsatisfiable if, and only if, G(Φ) is superadditive.

We turn now to analyze the complexity of arbitrary games. The case of CS-CORE-CHECK is rather simple.

Theorem 5.2. CS-CORE-CHECK is co-NP-complete.

Proof. A pair 〈π, x〉 belongs to CS-Core(G) if (i) 〈π, x〉 is a CS-imputation; and (ii) there is no coalition S such that v(S) > x(S). Membership in co-NP holds since condition (i) can be checked in polynomial time, while the complement of (ii) can be checked in NP, by guessing such a coalition S. Hardness follows from Theorem 4.1 and Corollary 3.4.

The analysis of the other problems requires some elaborations. The first ingredient is a hardness result, where the characterization of the coalition structure core in terms of cohesive covers is very useful (cf. Section 3). Recall that ΔP2 (resp., FΔP2 ) is the class of all decision (computation) problems solvable in polynomial time, by using an NP oracle.

Theorem 5.3. CS-CORE-NONEMPTINESS is ΔP2 -hard.

Proof. Let Φ be a satisfiable Boolean formula over the variables X1, . . . , Xn. Assume a variable ordering over the variables such that Xi is less significant than Xj if and only if i < j, which induces a lexicographical ordering over truth assignments for Φ. Recall that the problem of deciding whether X1 is true in the lexicographical maximum satisfying assignment σ∗ of Φ is ΔP2 -complete.

Based on Φ, we build in polynomial time the game G(Φ) = 〈N, v〉, where N = vars(Φ)∪{a, b, c, l} and where, for each set of players T , v is such that:

where S ⊆ {X1, . . . , Xn} and w(S) = ∑Xi∈S 2i . Moreover, let S ∗ ⊆ {X1, . . . ,Xn} be such that σ(S ∗ ) = σ∗ .

˜

Let G be the cohesive cover of G(Φ). From Theorem 3.3, CS-Core(G(Φ)) ̸= ∅ ⇔ Core( ˜ G) ̸= ∅. Thus, the result can be established by showing that Core( ˜ G) ̸= ∅⇔X1 is in S ∗ :

• (⇐) If X1 ∈ S ∗ , then ˜ v(N) = w(S ∗ )+1 and the imputation ¯x such that ¯xl = w(S ∗ ), ¯xa = ¯xb = ¯xc = 1/3, and ¯xi = 0, for any other player, belongs to the core of ˜ G.
• (⇒) If X1 ̸∈ S ∗ , then ˜ v(N) = w(S ∗ ) + 2/3. In this case, for an imputation x to be in ˜ G, we must have x(N) = w(S ∗ ) + 2/3, x(S ∗ ∪ {l}) ≥ w(S ∗ ), and x(T ) ≥ 2/3 for each T ⊆ {a, b, c} and |T | ≥ 2. However, no such an imputation exists, and thus Core( ˜ G) = ∅.

The second ingredient is an oracle-based algorithm to compute the social welfare in FΔP2 .

Lemma 5.4. Computing the social welfare is in FΔP2 .

Proof Sketch. Computing sw(G) can be accomplished by means of a binary search on the range [v(N),M], where M is the maximum value representable in polynomial space in the size of the game representation. In the binary search, we ask to an oracle whether there is a coalition structure π such that CS-v(π) ≥ k. The oracle just guesses (in NP) such a coalition structure π and then checks in polynomial time that CS-v(π) ≥ k. Note that the search space is exponential in the size of the representation of the game, and hence the number of calls made to the oracle is polynomial in the size of the game representation. Thus, computing sw(G) is in FΔP2 .

Putting it all together, we get the following result that in particular, for the case of weighted voting games, provides the complexity bound on CS-CORE-NONEMPTINESS which is missing in [Elkind et al., 2008].

Theorem 5.5. CS-CORE-NONEMPTINESS, CS-COS, and CS-LCV are ΔP2 -complete.

Proof. Checking CS-COS(G) ≤ 0 and CS-LCV(G) ≤ 0 are both equivalent to check that CS-Core(G) ̸= ∅. Thus, ΔP2 - hardness for CS-COS and CS-LCV follows by Theorem 5.3.

We now show that CS-COS is feasible in ΔP2 , which entails that CS-CORE-NONEMPTINESS is feasible in ΔP2 . Indeed, recall from Theorem 3.5 that CS-COS(G) = COS( ˜ G). Thus, given a value Δ, in order to check that CS-COS(G) ≤ Δ, we can find (the worth of the grand-coalition of) ˜ G in P NP (as in Lemma 5.4). Subsequently, we can check that COS( ˜ G) ≤ Δ in co-NP (by Corollary 4.2).

Finally, as for CS-LCV, recall that CS-LCV(G) ≤ ε if, and only if, CS-Core(G-ε) ̸= ∅. By the above line of reasoning, such a non-emptiness condition can be checked in ΔP2 .

6 Structural Restrictions

Let G = 〈N, v〉 be a coalitional game, and IG(G) be its interaction graph. The interaction-constrained coalition structure core is the set CSIG-Core(G) of all CS-imputations 〈π, x〉 such that x(S) ≥ v(S), for each S such that the subgraph of IG(G) induced over S is connected (e.g., [Demange, 2004]).

Whenever IG(G) is a tree, it is known that CSIG-Core(G) is non-empty [Demange, 2004]. Graphs that are closest to trees are those having treewidth 2. In this section, we explore the complexity of interaction-constrained core-related questions on such graphs, and address question (3) of the Introduction. Problems are hereinafter assumed to be defined over CSIG-Core(G) rather than on CS-Core(G).

Recall that a tree decomposition of a graph G = (V, E) is a pair 〈T, χ〉, where T = (N, F) is a tree, and χ is a labeling function assigning to each vertex p ∈ N a set of vertices χ(p) ⊆ V , such that the following conditions are satisfied: (1) for each node b of G, there exists p ∈ N such that b ∈ χ(p); (2) for each edge (b, d) ∈ E, there exists p ∈ N such that {b, d} ⊆ χ(p); and, (3) for each node b of G, the set {p ∈ N | b ∈ χ(p)} induces a connected subtree. The width of 〈T, χ〉 is the number maxp∈N(|χ(p)| - 1). The treewidth of G, denoted by tw(G), is the minimum width over all its tree decompositions. G is acyclic if, and only if, tw(G) = 1.

The first step is to show that, unlike trees, on games G such that tw(IG(G)) = 2, the set CSIG-Core(G) can be empty. In fact, all ΔP2 -hardness results in Figure 1 hold over them.

Theorem 6.1. CS-CORE-NONEMPTINESS, CS-COS, and CS-LCV are ΔP2 -hard even on games G with tw(IG(G))=2.

Proof. Consider again the game G(Φ) = 〈N, v〉 built in the proof of Theorem 5.3, and let its interaction graph IG(G(Φ)) be the one shown in Figure 2. Note that tw(IG(G(Φ))) = 2, and that, for each coalition S ⊆ N such that the subgraph induced over S is not connected, we have v(S) = 0.

Since for any coalition S ⊆ N, v(S) ≥ 0 holds, then the restriction over IG(G(Φ)) is immaterial, and we have CSIG-Core(G(Φ)) = CS-Core(G(Φ)). Thus, there are formulae Φ such that CSIG-Core(G(Φ)) = ∅, and all hardness results follow from Theorem 5.5.

The second step is based on a technical lemma, whose role is to show that bounded treewidth interaction graphs are as "powerful" as arbitrary ones, even on superadditive games.

Lemma 6.2. Given any superadditive game G = 〈N, v〉, we can build in polynomial time a superadditive game G′ =

〈N ′ , v′ 〉, an interaction graph IG(G′ ) with tw(IG(G′ )) = 2, and a function h : R|N| ↦→ R|N ′ | such that: 〈{N ′}, x′ 〉 ∈ CSIG-Core(G′ ) ⇔ 〈{N}, x〉 ∈ CS-Core(G) and x′ = h(x).

Proof. Let G′ = 〈N ′ , v′ 〉 be the game over the players N ′ = N ∪ {p, q}, where {p, q} ∩ N = ∅. Let v′ (p) = v′ (q) = 0, and v′ (S ′ ) = v(S ′ \{p, q}), for each S ′ ⊆ N ′ with S ′ ∩N ̸= ∅. The interaction graph IG(G′ ) = (N ′ , {p}×N∪N×{q}) is the one depicted in Figure 2. Note that tw(IG(G′ )) = 2.

First, we claim that G′ is superadditive. Consider any two disjoint coalitions S ′ and T ′ . In the case where S ′ ∩N ̸= ∅ and T ′ ∩N ̸= ∅, we have v′ (S ′ ∪T ′ ) = v(S ′ ∪T ′ \{p, q}) ≥ v(S ′ \{p, q})+v(T ′ \{p, q}) = v′ (S ′ )+v′ (T ′). To complete the analysis, consider, then, the case where T ′ ⊆ {p, q}. In this case, we have v′ (S ′ ∪T ′ ) = v(S ′ ∪T ′ \ {p, q}) = v(S ′ \ {p, q}) = v′ (S ′ ), while v′ (T ′ ) = 0.

Let 〈{N}, x〉 ∈ CS-Core(G), and consider the vector x′ = h(x) such that x′i = xi, for each i ∈ N, and x′p = x′q = 0. We claim that 〈{N ′}, x′ 〉 ∈ CSIG-Core(G′ ). Indeed, note first that x′ (N ′ ) = x(N) = v(N) = v′ (N ′ ). Moreover, for each S ′ ⊆ N ′ with S′ ∩ N ̸= ∅, x′ (S ′ ) = x(S ′ \ {p, q}) ≥ v(S ′ \ {p, q}) = v′ (S ′ ). In order to complete the proof, consider any CS-imputation 〈{N ′}, x′ 〉 ∈ CSIG-Core(G′ ). We have x′ (N ′ ) = v′ (N ′ ) = v(N), x′ (N ∪ {p}) ≥ v′ (N ∪ {p}) = v(N) and x′ (N ∪ {q}) ≥ v′ (N ∪ {q}) = v(N). Therefore, x′p = x′q = 0. Consider then the vector x such that x′ = h(x), and note that 〈{N}, x〉 ∈ CS-Core(G). Indeed, x(N) = x′ (N ′ ) = v′ (N ′ ) = v(N). Moreover, for each S ⊆N, x(S) = x′ (S ∪ {p, q}) ≥ v′ (S ∪ {p, q}) = v(S). In particular, note that, in the above relationships, S ∪ {p, q} is guaranteed to induce a connected subgraph over IG(G ′ ).

We are now in the position of completing the picture of the complexity analysis carried out in the paper: While various solution concepts are tractable on specific game encodings when their structures have bounded treewidth, on general polynomial-time computable worth functions (even on superadditive ones), bounded treewidth is not a key for tractability.

Theorem 6.3. All hardness results in Figure 1 hold even on classes of games G with tw(IG(G)) = 2.

Proof Sketch. After Theorem6.1, we have just to focus on the complexity of games that are superadditive-in fact, co-NPhardness of CS-CORE-CHECK on superadditive games immediately applies to arbitrary games. Consider the proofs of Theorem 4.1 and Corollary 4.2, and notice that they are based on the superadditive game G(Φ). Thus, from from Corollary 3.4 and Corollary 3.6, hardness for CS-CORE-CHECK, CS-CORE-NONEMPTINESS, CS-COS, and CS-LCV hold on the corresponding superadditive game as in Lemma 6.2.