---
title: "Constrained Coalition Formation on Valuation Structures: Formal Framework, Applications, and Islands of Tractability (Extended Abstract)"
authors:
  - "Gianluigi Greco"
  - "Antonella Guzzo"
doi: "10.24963/ijcai.2018/795"
url: "https://ijcai.org/proceedings/2018/795"
pdf: "https://ijcai.org/proceedings/2018/0795.pdf"
venue: "Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence"
year: 2018
pages: "5612-5616"
track: "Journal track"
keywords:
  - "Agent-based and Multi-agent Systems: Cooperative Games"
  - "Agent-based and Multi-agent Systems: Coordination and Cooperation"
  - "Knowledge Representation and Reasoning: Computational Complexity of Reasoning"
---

# Constrained Coalition Formation on Valuation Structures: Formal Framework, Applications, and Islands of Tractability (Extended Abstract)

Gianluigi Greco, Antonella Guzzo

*Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence*, pages 5612-5616. DOI: [10.24963/ijcai.2018/795](https://doi.org/10.24963/ijcai.2018/795)

## Abstract

Coalition structure generation is considered in a setting where feasible coalition structures must satisfy constraints of two different kinds modeled in terms of a valuation structure, which consists of a set of pivotal agents that are pairwise incompatible, plus an interaction graph prescribing that a coalition C can form only if the subgraph induced over the nodes/agents in C is connected. It is shown that valuation structures can be used to model a number of relevant problems in real-world applications. Moreover, complexity issues arising with them are studied, by focusing in particular on identifying islands of tractability based on topological properties of the underlying interaction graph. Stability issues on valuation structures are studied too.

## Full text

## 1 Introduction

Coalition structure generation is a fundamental problem in the study of coalition formation processes in multi-agent systems. The problem is defined over a coalitional game 〈N, v〉, where N = {a1, . . . , an} is a set of agents and where v is a valuation function that, for each coalition C, i.e., non-empty set C ⊆ N of agents, returns a real number v(C) meant to express the worth that the members of C can jointly achieve by cooperating. The goal is to find an optimal coalition structure, that is, a partition {C1, . . . ,Ck} of the agents into disjoint coalitions with C1 ∪· · ·∪Ck = N and whose total value v(C1) + · · · + v(Ck) is maximized [Rahwan et al., 2015].

While coalition structure generation has been classically studied in the literature by assuming that all coalitions are allowed to form, a number of works [Rahwan et al., 2011; Demange, 2009; Shehory and Kraus, 1998; Rahwan and Jennings, 2007] evidenced that in real-world domains some coalition structures might be forbidden, because they might violate some constraints induced by the specific semantics of the application at hand. In the paper, we continue along this line of research by proposing and studying a framework

∗This paper is an extended abstract of an article in the Artificial Intelligence Journal [Greco and Guzzo, 2017]. The work was partially supported by the POR project "Explora Process" and the PON project "IDService: Digital Identity and Service Accountability".

## Antonella Guzzo

University of Calabria, Italy antonella.guzzo@unical.it

where constraints of two kinds can be simultaneously expressed in terms a valuation structure.

In a nutshell, a valuation structure equips each coalitional game 〈N, v〉 with an interaction graph G = (N, E), defined over the set of the agents, so that a coalition C is considered as a feasible one, only if the subgraph of G induced over the nodes in C is connected [Myerson, 1977]. Moreover, the structure allows us to define a set S of pairwise "incompatible" (pivotal) agents, so that every coalition C must also satisfy the condition |S ∩ C| ≤ 1 in order to be a feasible one.

Our analysis moves from the observation that coalitional games with valuation structures are rather powerful from the knowledge representation viewpoint. This motivates a systematic study of the algorithmic and complexity issues arising with them. Our main result refers to the setting where valuation functions are independent of disconnected members (short: IDM), i.e., such that two agents have no effect on each other's marginal contribution to their separator w.r.t. the interaction graph [Voice et al., 2012]. Formally, for each pair i, j of agents that are not directly connected in the graph, and for each C ⊆ N with i, j ̸∈ C, it holds that

<!-- formula-not-decoded -->

Note that, in absence of pivotal agents, coalition structure generation is known [Voice et al., 2012] to be tractable for IDM functions over acyclic interaction graphs, or more generally over graphs having bounded treewidth [Robertson and Seymour, 1984]. The question is then whether this nice result can be extended to our more general setting. The main contribution of the paper is to provide a positive answer to this question. Moreover, we go beyond and we show that tractability can be established not only for IDM functions, but also for functions derived from IDM ones via "affine transformations". For an example of an affine transformation, consider a setting where in order to leave the grand-coalition N, a "splitting cost" c has to be paid. In this case, we would obtain an "adjusted" (no longer IDM) valuation function v′ such that v′ (C) = v(C)-c, for each C ⊂ N, and v′ (N) = v(N).

Finally, we address the question of determining how the worth that is obtained by forming an optimal coalition structure can be distributed over the agents in a way that is stable [Osborne and Rubinstein, 1994]. In particular, we show that core-related problems can be solved in polynomial time for classes of IDM valuation functions over graphs having bounded treewidth, even in presence of valuation structures.

## 2 Valuation Structures for Coalitional Games

In this section, we formalize the concept of valuation structure and we discuss its possible applications to deal with a number of problems occurring real-world domains.

## 2.1 Formal Framework

Let Γ = 〈N, v〉 be a coalitional game. A valuation structure for Γ is a tuple σ = 〈G, S, α, β, x, y〉 where G = (N, E) is an interaction graph, S ⊆ N is a possibly-empty set of agents, called pivotal agents, α, β : S ↦→ Q are two functions, and x, y ∈ Q are rational numbers.

The role of the interaction graph G and of the set S of pivotal agents has been already discussed in the Introduction. Whenever the constraints induced by them are satisfied by a coalition C, then we say that C is σ-feasible. The set of all σ-feasible coalitions in the game Γ is denoted by Fσ(Γ).

The functions α and β and the rational numbers x and y are used, instead, to define an affine transformation valσ of the valuation function v. Formally, if C ∈ Fσ(Γ) is a σ-feasible coalition, then we define its σ-value as follows:

<!-- formula-not-decoded -->

A σ-feasible coalition structure for Γ is a set Π = {C1, . . . ,Ck} of σ-feasible coalitions such that C1 ∪ · · · ∪ Ck = N and Ci ∩ Cj = ∅, for each pair i, j ∈ {1, . . . , k} with i ̸= j. The set of all possible coalition structures is denoted by CSσ(Γ). Note that CSσ(Γ) ̸= ∅, because each singleton coalition is σ-feasible, that is, {ai} ∈ Fσ(Γ) holds, for each ai ∈ N. For any Π ∈ CSσ(Γ), by slightly abusing of notation, we define valσ(v,Π) (or, shortly, valσ(Π) if the valuation function v is clearly understood) as the value ∑C∈Π valσ(v,C), which is called the σ-value of Π. Moreover, we denote by optσ(Γ) the maximum σ-value that can be attained over all possible σ-feasible coalition structures.

A coalition structure Π∗ ∈ CSσ(Γ) such that valσ(Π∗ ) = optσ(Γ) is said to be σ-optimal on Γ, and the set of all σoptimal coalition structures is denoted by CS-optσ(Γ).

It is worthwhile observing that, given any coalitional game Γ = 〈N, v〉, by defining ⊥ = 〈KN, ∅, α, β, x, y〉 as the valuation structure where KN is the complete interaction graph over the set N of agents and where there are no pivotal agents (so that the functions α and β and the numbers x and y play no role), we can immediately check that any coalition S ⊆ N is ⊥-feasible and that val⊥(v, S) = v(S) holds. Therefore, results in the literature where no valuation structures have been considered can be inherited in our setting as results that hold over ⊥-optimal coalition structures.

## 2.2 Applications of Valuation Structures

Arbitrary valuation structures find useful applications in a number of problems occurring in real-world domains. In the following, we overview an application in the framework for correlation clustering proposed by [Bansal et al., 2004]. Details and further applications-including multicut problems, multiway cut problems [Dahlhaus et al., 1994], and chromatic partitioning [Bonchi et al., 2012; Cowans and Szummer, 2005]-can be found in [Greco and Guzzo, 2017].

Figure 1: Illustration of Example 2.1.

![Image](https://ijcai.org/proceedings/2018/fulltext/795/image_000000_252a57d2196315486234302eb70af3aee45b90305c83ee70d529d9784a0bf901.png)

In correlation clustering, we have an undirected graph G = (N,E) where each edge e ∈ E has a label in ℓe ∈ {+,-}. A cluster C is a non-empty subset of N such that the subgraph of G induced over C is connected. 1 A clustering is just a partition of N into disjoint and exhaustive clusters. For any cluster C ⊆ N, we denote by E+(C) = {e ∈ E | e ⊆ C, ℓe = +} the set of its positive intra-cluster edges, and by E-(C) = {e ∈ E | |e ∩ C| = 1, ℓe = -} the set of negative inter-cluster edges with one end in C. Then, the correlation value of C is given by vcc(C) = |E+(C)| + |E-(C)|, while the correlation value of a clustering Π is the sum of the correlation values of its clusters, i.e., the value ∑C∈Π vcc(C). The goal is to find an optimal clustering, that is, a clustering having maximum correlation value.

Example 2.1. Consider the graph illustrated in Figure 1.(c), where each edge is associated with a label in {+,-}. It can be checked that an optimal correlation clustering is given by the set {C1, C2, C3}. In particular, note that vcc(C1) = 1+2, vcc(C2) = 4 + 3, and vcc(C3) = 4 + 1, so that the overall value of the clustering is 3 + 7 + 5 = 15. ⊳

Note that, in the basic correlation clustering framework, the number of clusters is not a-priori fixed. More recently, an extension of this framework has been studied, where the number of clusters is stipulated to be a small constant k [Giotis and Guruswami, 2006]. For instance, in the case of Figure 1, by fixing k = 2, we would look for a bipartition of the graph in two connected components maximizing the correlation value-interestingly, the problem is NP-hard even in this case [Giotis and Guruswami, 2006]. Accordingly, we would single out the two components C1 and C2 ∪C3, where vcc(C2∪C3) = 11. In particular, the clustering {C1,C2,C3} is no longer admissible because it consists of 3 clusters.

In order to accommodate this k-clustering problem in our setting, we need not only to define suitable pivotal agents, but also to use an affine transformation of the valuation function. Formally, for any set R ⊆ N of nodes, we consider the valuation structure σR = 〈G, R, 1, 0, 0, -∞〉, where 1 and 0 are the constant functions returning 1 and 0, respectively, and∞ is "sufficiently large" rational number.

Intuitively, according to σR, it is always suboptimal to form a coalition that does not include an agent in R, so that any σR-feasible coalition structure Π such that valσR (vcc,Π) ≥ 0 consists of exactly |R| distinct coalitions (as R is the set of pivotal agents, there cannot be less than |R| coalitions). Moreover, note that the set of possible coalitions is restricted to those that are feasible according to the graph G, as to avoid clusters formed by unconnected components. Therefore, Π is a clustering and val σR (vcc , Π) is precisely its value. On the other hand, it is immediate to check that if Π is a clustering, then Π is also a σR-feasible coalition structure, for any set R including precisely one element for each cluster in Π. Hence, an optimal k-clustering can be computed as a coalition structure having the maximum σR-value over all σR-optimal coalition structures for any subset R ⊆ N with |R| = k. In particular, since k is a given fixed constant [Giotis and Guruswami, 2006], then polynomially many subsets R have to be considered.

1 The connectivity condition is not necessary, but simplifies the presentation of the extension we shall next address.

## 3 Coalition Structure Generation

An instance for the coalition structure generation problem on valuation structures, denoted in the following as CSGVAL, is a pair (Γ, σ), where Γ = (N, v) is a coalitional game, and σ = 〈G, S, α, β, x, y〉 is a valuation structure on Γ. The goal is to compute a σ-optimal coalition structure Π∗ ∈ CS-optσ(Γ).

In this section, we study the computational complexity of the problem CSGVAL. To this end, we preliminary need to adopt a representation for the input. On the one hand, concerning σ, we can simply adopt a standard explicit encoding for its elements. On the other hand, we have to observe that a trivial representation for Γ would just list all possible coalitions, with attached their associated valuations, hence requiring exponential space (w.r.t. |N|). However, more compact encodings can be obtained in some cases [Megiddo, 1978; Kalai and Zemel, 1980; Deng and Papadimitriou, 1994; Elkind et al., 2009; Ieong and Shoham, 2005; Conitzer and Sandholm, 2006; Chalkiadakis et al., 2011]. Just think, as an extreme case, that a valuation function v such that v(C) = 0, for each C ⊆ N, needs only constant space to be represented.

In the paper, we do not commit ourselves to a specific representation strategy. Rather, by following [Greco et al., 2011], we assume that a representation R for coalitional games defines two functions ξR and vR, which are used to encode a class of games denoted by C(R). In particular, for each coalitional game Γ ∈ C(R), ξR(Γ) is the encoding of Γ, while vR(ξR(Γ), C) is the value associated to the coalition C according to v. We require that this value can be computed in polynomial time w.r.t. ||Γ||. Moreover, we assume as usual that all agents in N are listed in ξR(Γ), i.e., ||ξR(Γ)|| ≥ |N|.

## 3.1 Complexity in the General Case

The complexity of the coalition structure generation problem without valuation structures has been already studied in the literature, and it has been shown to be NP-hard even when very specific kinds of encodings are considered, in particular, when coalitional games are given as graph games [Voice et al., 2012]. Here, we recall that according to the graph-game representation gg, the encoding ξ gg (Γ) of a coalitional game Γ = 〈N, v〉 ∈ C(gg) is given in terms of a graph (N,E) where each edge e ∈ E is also equipped with a weight we ∈ Q. In particular, for each coalition C ⊆ N, the value v(C) = vgg (ξ gg (Γ),C) is just given by the sum of the weights of the edges covered by the agents in C.

Surprisingly, however, the precise complexity of the coalition structure generation problem (without valuation structures) has been not pointed out in earlier literature. In fact, our first technical contribution is to show that the problem is slightly more complex than just being NP-hard. Indeed, it emerges to be complete for the class F∆P2 consisting of all those computation problems that can be solved in polynomial time by possibly invoking, each time with a unitary cost, an oracle that solves a decision problem in the class NP.

Figure 2: Illustration of Example 3.2: An interaction graph and a tree decomposition having width 2.

![Image](https://ijcai.org/proceedings/2018/fulltext/795/image_000001_ef387385a86f410a3ff978ae5aca8a7d3bf3f2333101a2bced97b43f2d771600.png)

Theorem 3.1. CSGVAL is F∆P2 -complete. Hardness holds even on the structures ⊥ and for games in the class C(gg).

## 3.2 Structural Restrictions: Further Bad News

In the light of the above intractability result, it is sensible to single out classes of instances over which CSGVAL can be efficiently solved. A natural approach to identify such classes is to focus on interaction graphs enjoying suitable structural properties. In fact, a basic structural property of a graph is acyclicity, and we next consider the more general concept of bounded treewidth [Robertson and Seymour, 1984].

For the sake of completeness, we recall that a tree decomposition of a graph G = (N,E) is a pair 〈T, χ〉, where T = (V, F) is a tree, and χ is a labeling function assigning to each vertex p ∈ V a set of vertices χ(p) ⊆ N, such that the following conditions are satisfied: (1) for each node b of G, there exists p ∈ V such that b ∈ χ(p); (2) for each edge {b, d} ∈ E, there exists p ∈ V such that {b, d} ⊆ χ(p); and, (3) for each node b of G, the set {p ∈ V | b ∈ χ(p)} induces a connected subtree of T . The width of 〈T, χ〉 is the number maxp∈V (|χ(p)|-1). The treewidth of G, denoted by tw(G), is the minimum width over all its tree decompositions. A graph G is acyclic if and only if tw(G) = 1. Deciding if a given graph has treewidth bounded by a fixed natural number k is known to be feasible in linear time [Bodlaender, 1996].

Example 3.2. Consider the graph G = (N,E) shown in Figure 2.(a), and note that it contains a cycle over the nodes/agents in {a1, a2, a3}. In Figure 2.(b), a tree decomposition of G is reported whose width is 2. ⊳

By focusing on interactions graphs of bounded treewidth, we significantly constraint the coalitions that are allowed to form. However, this is not yet sufficient to end up with an island of tractability, as the following can be shown.

Theorem 3.3. CSGVAL is F∆P2 -hard, even on structures 〈G, ∅, α, β, x, y〉 such that G is acyclic.

## 3.3 Islands of Tractability for CSGVAL

In the light of the above bad news, it emerges that islands of tractability for the coalition structure generation problem has to be identified not only based on topological restrictions, but also by focusing on special classes of valuation functions.

Our choice here is to consider IDM valuation functions, for which tractability in absence of valuation structures has been established in [Voice et al., 2012]. Our main technical achievement in the paper is then to generalize that result to arbitrary valuation structures (but still with bounded treewidth interaction graphs). This is formalized below.

Theorem 3.4. Let h ≥ 0 be a fixed natural number. Let R be any representation for coalitional games, let Γ = 〈N, v〉 ∈ C(R) be a game such that v is a valuation function independent of disconnected members w.r.t. a graph G with tw(G) ≥ h. Let σ = 〈G, S, α, β, x, y〉 be a valuation structure. Then, CSGVAL can be solved on (Γ, σ) in polynomial time (w.r.t. ||ξR(Γ)|| and ||σ||).

The proof of the result is rather involved and for details we refer the reader to [Greco and Guzzo, 2017]. At a highlevel, we observe here that the proof is based on two technical ingredients that are interesting in their own right:

- (1) First, we show that, over bounded treewidth graphs, any IDM valuation function admits a very simple kind of succinct representation, in terms of the well-known encoding based on marginal contribution networks [Ieong and Shoham, 2005]. Moreover, no matter of the representation scheme originally adopted for the valuation function, an equivalent marginal contribution network can be computed in polynomial time.
- (2) Second, we exhibit a polynomial-time algorithm solving CSGVAL over marginal contribution networks whose underlying interaction graphs have bounded treewidth. The algorithm is defined by means of a non-trivial encoding in terms of a constraint satisfaction problem, and by exploiting known structural tractability results in this latter setting. The approach uses novel ideas and methods that might be re-used in other application domains.

## 4 Stability Issues under Valuation Structures

Computing an optimal coalition structure Π∗ is generally not enough in applications where agents collaborate within the same environment. Indeed, another fundamental problem for coalitional games is to determine how the worth that is obtained by forming the structure Π∗ can be subsequently distributed over the agents in a way that is stable. This problem has been largely studied in the literature, and several approaches have been proposed founding on well-known solution concepts, such as the core, the kernel, the bargaining set, the nucleolus, and the Shapley value (see, e.g., [Osborne and Rubinstein, 1994]). In the following, we focus on the core, which is the most influential and considered stability concept.

## 4.1 Solution Concepts

Let Γ = 〈N, v〉 be a coalitional game, where N = {a1, . . . , an}. A worth distribution in Γ can be simply viewed as a n-dimensional payoff vector x ∈ Rn whose i-th component, denoted by xi, is the worth received by agent ai, for each i ∈ {1, . . . , n}. For any coalition S ⊆ N, x(S) is here-

inafter used as a shorthand for ∑ai∈S xi. Let σ be a valuation structure for Γ, and assume that the agents organize themselves in the σ-feasible coalition structure Π ∈ Fσ(Γ). According to Π, the worth to be divided over the agents in a coalition C ∈ Π is given by valσ(v, C). Therefore, the "output" of the game can be viewed as a pair (Π, x), where x ∈ Rn is a payoff vector that is efficient w.r.t. Π, that is, x(C) = valσ(v,C) holds, for each C ∈ Π. In the following, we denote by Eσ(v, Π) (or, shorty, by Eσ(Π) if v is understood) the set of all such efficient payoff vectors.

Note that Eσ(v, Π) can contain infinitely many payoff vectors, and so the fundamental problem arises of singling out the most desirable ones among them. To face this problem, we consider a natural generalization of the concept of core to the setting where valuation structures are taken into account. Formally, we consider the coalition structure core of Γ w.r.t. σ, 2 defined as the set CS-coreσ(Γ) = {(Π, x) | Π ∈ CSσ(Γ), x ∈ Eσ(Π), and x(C) ≥ valσ(C), ∀C ∈ Fσ(Γ)}.

Note that elements (Π, x) in this set CS-coreσ(Γ) can be considered to be "stable" because there is no σ-feasible coalition whose members will receive a higher payoff than in x by leaving the current coalition structure Π.

## 4.2 Complexity Analysis

With the above concepts in place, we now study the complexity of the CS-CORE-FIND problem that, given as input a pair (Γ, σ), asks to compute an element in CS-coreσ(Γ), or decide that CS-coreσ(Γ) = ∅. In fact, the problem is easily seen to be intractable, formally NP-hard, as it inherits the results that are known to hold for coalitional games without coalitional structures [Chalkiadakis et al., 2016].

Motivated by the above bad news, we next consider IDM functions evaluated w.r.t. interaction graphs having bounded treewidth. In particular, because of the argument (1) in the proof of Theorem 3.4, we study, w.l.o.g., CS-CORE-FIND on the class CTW-h(mcn) of all marginal contribution networks whose agent graphs have treewidth h at most, where h is a fixed constant. Our findings are summarized as follows.

Theorem 4.1. Let h ≥ 0 be a fixed natural number. Let Γ = 〈N, v〉 ∈ CTW-h(mcn) and let σ = 〈G, S, α, β, x, y〉 be a valuation structure. Then, CS-CORE-FIND can be solved on (Γ, σ) in polynomial time (w.r.t. ||ξmcn (Γ)|| and ||σ||).

The result is established by observing that, armed with the knowledge of an optimal coalition structure (which can be computed in polynomial time by Theorem 3.4), the set CS-coreσ(Γ) can be defined as the solution of a system of linear (in)equalities defined over |N| variables and possibly exponentially-many (in)equalities. Now, the system can be solved in polynomially-many steps, provided the existence of a separation oracle that is able to decide whether a given vector is a solution and, if not, to report an (in)equality that is violated. In fact, a separation oracle can be exhibited based on an algorithm that decides whether the minimum possible excess over all coalitions 3 is non-negative. So, the main technical ingredient to establish Theorem 4.1 is the proof that this oracle takes polynomial time on CTW-h(mcn) and in presence of valuation structures-in absence of valuation structures, tractability was already known [Ieong and Shoham, 2005].

2 Whenever σ = 〈G, ∅, α, β, x, y〉 holds, the concept reduces to the notion of the core discussed, for instance, by [Breton et al., 1992; Demange, 2004; Chalkiadakis et al., 2016].

3 The excess of C at x is the value x(C) - val σ(v, C).

## References

1. [Bansal et al., 2004] Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation clustering. Machine Learning, 56(1- 3):89-113, 2004.
2. [Bodlaender, 1996] Hans L. Bodlaender. A linear-time algo- rithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25(6):1305-1317, 1996.
3. [Bonchi et al., 2012] Francesco Bonchi, Aristides Gionis, Francesco Gullo, and Antti Ukkonen. Chromatic corre- lation clustering. In Proc. of KDD'12, pages 1321-1329.
4. [Breton et al., 1992] M. Breton, G. Owen, and S. Weber. Strongly balanced cooperative games. International Jour- nal of Game Theory, 20(4):419-427, 1992.
5. [Chalkiadakis et al., 2011] Georgios Chalkiadakis, Edith Elkind, and Michael Wooldridge. Computational aspects of cooperative game theory. Synthesis Lectures on Artifi- cial Intelligence and Machine Learning, 5(6):1-168, 2011.
6. [Chalkiadakis et al., 2016] Georgios Chalkiadakis, Gian- luigi Greco, and Evangelos Markakis. Characteristic function games with restricted agent interactions: Core- stability and coalition structures. Artificial Intelligence, 232:76-113, 2016.
7. [Conitzer and Sandholm, 2006] Vincent Conitzer and Tuo- mas Sandholm. Complexity of constructing solutions in the core based on synergies among coalitions. Artificial Intelligence, 170(6-7):607-619, May 2006.
8. [Cowans and Szummer, 2005] Philip J Cowans and Martin Szummer. A graphical model for simultaneous partition- ing and labeling. In Proc. of AISTATS'05, pages 73-80.
9. [Dahlhaus et al., 1994] E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, and M. Yannakakis. The complexity of multiterminal cuts. SIAM Journal of Com- puting, 23(4):864-894, 1994.
10. [Demange, 2004] Gabrielle Demange. On group stability in hierarchies and networks. Journal of Political Economy, 112(4):754-778, August 2004.
11. [Demange, 2009] Gabrielle Demange. The strategy structure of some coalition formation games. Games and Economic Behavior, 65(1):83-104, 2009.
12. [Deng and Papadimitriou, 1994] Xiaotie Deng and Chris- tos H. Papadimitriou. On the complexity of cooperative solution concepts. Mathematics of Operations Research, 19(2):257-266, 1994.
13. [Elkind et al., 2009] Edith Elkind, Leslie Ann Goldberg, Paul W. Goldberg, and Michael Wooldridge. On the com- putational complexity of weighted voting games. Annals of Mathematics and Artificial Intelligence, 56(2):109-131, 2009.
14. [Giotis and Guruswami, 2006] Ioannis Giotis and Venkate- san Guruswami. Correlation clustering with a fixed num- ber of clusters. In Proc. of SODA'06, pages 1167-1176.
15. [Greco and Guzzo, 2017] Gianluigi Greco and Antonella Guzzo. Constrained coalition formation on valuation structures: Formal framework, applications, and islands of tractability. Artificial Intelligence, 249:19-46, 2017.
16. [Greco et al., 2011] Gianluigi Greco, Enrico Malizia, Luigi Palopoli, and Francesco Scarcello. On the complexity of core, kernel, and bargaining set. Artificial Intelligence, 175(12-13):1877-1910, 2011.
17. [Ieong and Shoham, 2005] Samuel Ieong and Yoav Shoham. Marginal contribution nets: a compact representation scheme for coalitional games. In Proc. of EC'05, pages 193-202, 2005.
18. [Kalai and Zemel, 1980] Ehud Kalai and Eitan Zemel. On totally balanced games and games of flow. Discussion Paper 413, Northwestern University, Center for Mathe- matical Studies in Economics and Management Science, Evanston, IL, USA, 1980.
19. [Megiddo, 1978] Nimrod Megiddo. Computational com- plexity of the game theory approach to cost allocation for a tree. Mathematics of Operations Research, 3(3):189-196, 1978.
20. [Myerson, 1977] Roger B. Myerson. Graphs and cooper- ation in games. Mathematics of Operations Research, 2(3):225-229, 1977.
21. [Osborne and Rubinstein, 1994] Martin J. Osborne and Ariel Rubinstein. A Course in Game Theory. The MIT Press, Cambridge, MA, USA, July 1994.
22. [Rahwan and Jennings, 2007] Talal Rahwan and Nicholas R. Jennings. An algorithm for distributing coalitional value calculations among cooperating agents. Artificial Intelli- gence, 171(8-9):535-567, 2007.
23. [Rahwan et al., 2011] Talal Rahwan, Tomasz P Michalak, Edith Elkind, Piotr Faliszewski, Jacek Sroka, Michael Wooldridge, and Nicholas R Jennings. Constrained coali- tion formation. In Proc. of AAAI'11, pages 719-725, 2011.
24. [Rahwan et al., 2015] Talal Rahwan, Tomasz P. Michalak, Michael Wooldridge, and Nicholas R. Jennings. Coali- tion structure generation: A survey. Artificial Intelligence, 229:139-174, 2015.
25. [Robertson and Seymour, 1984] N. Robertson and P.D. Sey- mour. Graph minors iii: Planar tree-width. Journal of Combinatorial Theory, Series B, 36(1):49-64, February 1984.
26. [Shehory and Kraus, 1998] Onn Shehory and Sarit Kraus. Methods for task allocation via agent coalition formation. Artificial Intelligence, 101(1-2):165-200, 1998.
27. [Voice et al., 2012] Thomas Voice, Maria Polukarov, and Nicholas R. Jennings. Coalition structure generation over graphs. Journal of Artificial Intelligence Research, 45(1):165-196, 2012.