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

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

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:

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

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.

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).