Complexity of Determining Nonemptiness of the Core

1 Introduction

Coalition formation is a key problem in automated negotia­ tion among self-interested agents. A coalition of agents can sometimes accomplish things that the individual agents can­ not, or can do things more efficiently. However, motivat­ ing the agents to abide to a solution requires careful analy­ sis: only some of the solutions are stable in the sense that no group of agents is motivated to break off and form a new coalition. This constraint has been studied extensively in co­ operative game theory. However, the computational questions around this constraint have received less attention. When it comes to coalition formation among software agents (that represent real-world parties), these questions become increas­ ingly explicit.

*The material in this paper is based upon work supported by the National Science Foundation under CAREER Award IRI-9703122,

Grant IIS-9800994, ITR IIS-0081246, and ITR IIS-0121678.

In general, computational complexity could stem from each potential coalition having some hard optimization prob­ lem. For example, when the agents are carrier companies with their own trucks and delivery tasks, they can save costs by forming a coalition (pooling their trucks and tasks), but each potential coalition faces a hard optimization problem: a vehicle routing problem defined by the coalition's trucks and tasks. The effect of such hard optimization problems on coalition formation has been studied by Sandholm and Lesser [Sandholm and Lesser, 1997]. As in the bulk of re­ search on coalition formation, in this paper we do not address that issue. Rather, we assume that such optimization prob­ lems have already been solved (at least the pertinent ones), and given this, we characterize the stable feasible outcomes. This has been the focus of most of the work in coalition for­ mation. The contribution of this paper belongs to the rela­ tively new, small set of papers that study the complexity of characterizing such solutions.

The determination of stable solutions has electronic com­ merce applications beyond automated negotiation as well. For example, consider a large number of companies, some subsets of which could form profitable virtual organizations that can respond to larger or more diverse orders than the in­ dividual companies can. Determining stable value divisions allows one to see which potential virtual organizations would be viable in the sense that the companies in the virtual orga­ nization would naturally stay together. As another example, consider a future online service that determines how much each employee of a company should be paid so that the com­ pany does not collapse as a result of employees being bought away by other companies. The input to this service would be how much subsets of the company's employees would be paid if they left collectively (for instance, a whole department could be bought away). This input could come from salary databases or a manager's estimate. The computational prob­ lem of determining a stable renumeration would be crucial for such a service. Both of these example problems fit ex­ actly under the model that we study in this paper.

The rest of the paper is organized as follows. In Section 2, we review the required concepts from cooperative game the­ ory. In Section 3, we define a concise general representation for games in characteristic form that relies on superadditiv­ ity, and show that it allows for efficient checking of whether a given outcome is in the core. In Section 4, we show that determining whether the core is nonempty is NP-complete both with and without transferable utility. In Section 5, we demonstrate that what makes the problem hard in both cases is determining the collaborative possibilities (the set of out­ comes possible for the grand coalition), by showing that if these are given, the problem becomes tractable in both cases. In Section 6, we show that for a hybrid version of the prob­ lem, where utility transfer is possible only within the grand coalition, the problem remains NP-complete even when the collaborative possibilities are given.

2 Definitions from cooperative game theory

In this section we review standard definitions from coopera­ tive game theory, which we will use throughout the paper. In the definitions, we follow the most prevalent advanced text­ book in microeconomics [Mas-Colell et al., 1995].

In general, how well agents in a coalition do may depend on what nonmembers of the coalition do (e.g. [Bernheim et al., 1987; Chatterjee et al., 1993; Evans, 1997; Milgrom and Roberts, 1996; Moreno and Wooders, 1996; Okada, 1996; Ray, 1996]). However, in cooperative game theory, coali­ tion formation is usually studied in the context of charac­ teristic function games where the utilities of the coalition members do not depend on the nonmembers' actions [Ka­ han and Rapoport, 1984; van der Linden and Verbeek, 1985; Zlotkin and Rosenschein, 1994; Charnes and Kortanek, 1966; Shapley, 1967; Wu, 1977]. (One way to interpret this is to consider the coalition members' utilities to be the utilities they can guarantee themselves no matter what the nonmem­ bers do [Aumann, 1959; Tohme and Sandholm, 1999].)

Definition 1 Given a set of players A, a utility possibil­ ity vector u 8 for B = {b1, ... , bn 8 } <,:;; A is a vector ( ub,, .. . , ub,. 8 ) representing utilities that the players in B can guarantee themselves by cooperating with each other. A utility possibility set is a set of utility possibility vectors for a given set B.

Definition 2 A game in characteristic form consists of a set of players A and a utility possibility set V (B) for each B <,:;; A.

Sometimes games in characteristic form have transferable utility, which means agents in a coalition can transfer utility among themselves.

Definition 3 A game in characteristic form is said to have transferable utility if for every B <,:;; A there is a number v(B) (the value of B) such that V(B) = {u 8 = (u~, ... ,u~ ) : I:; uf::; v(B)}. B bEB

It is commonly assumed that the joining of two coalitions does not prevent them from acting as well as they could have acted separately. In other words, the composite coalition can coordinate by choosing not to coordinate. This assumption is known as superadditivity. 1 We will assume superadditiv­ ity throughout the paper. This actually makes our hardness results stronger because even a restricted version of the prob­ lem is hard.

Definition 4 A game in characteristic form is said to be su­ peradditive if, for any B, C <,:;; A with B and C disjoint, and for any u 8 E V(B) and u 0 E V(C), we have (u 8 , u 0 ) E V ( B U C). (In the case of transferable utility, this is equiva­ lent to saying that for any B , C <,:;; A with B and C disjoint, v(B u C) ~ v(B) + v(C).)

We now need a solution concept. In this paper, we study only the best known solution concept, which is called the core [Mas-Colell et al., 1995; Kahan and Rapoport, 1984; van der Linden and Verbeek, 1985]. It was first introduced by Gillies [Gillies, 1953].

Definition 5 An outcome uA = ( uf, ... , u~) E V (A) is blocked by coalition B <,:;; A if there exists u 8 = (uf, ... ,uf ) E V(B) such thatforall bE B, 1 "B uf > u~. (In the case of transferable utility, this is equiv­ alent to saying that the outcome is blocked by B if v( B) > I:; u{) An outcome is in the core if it is blocked by no coali­ bEB tion.

In general, the core can be empty. If the core is empty, the game is inherently unstable because no matter what outcome is chosen, some subset of agents is motivated to pull out and form their own coalition. In other words, requiring that no subset of agents is motivated to break off into a coalition of its own overconstrains the system.

An example of a game with an empty core is the one with players { x, y, z }, where we have the utility possibility vectors u{x,y} = (2, 1), u{y,z} = (2, 1), and u{x,z} = (1, 2) (and the ones that can be derived from this through superadditivity). The same example with transferable utility also has an empty core.

In the rest of this paper, we will study the question of how complex it is to determine whether the core is nonempty, that is, whether there is a solution or the problem is overcon­ strained.

3 Representing characteristic form games concisely

In our representation of games in characteristic form, we dis­ tinguish between games without transferable utility, where we specify some utility possibility vectors for some coali­ tions, and games with transferable utility, where we specify the values of some coalitions.

1 When superadditivity holds, it is always best for the grand coalition of all agents to form. On the other hand, without su­ peradditivity, even finding the optimal coalition structure (parti­ tion of agents into coalitions) can be hard [Sandholm et al., 1999; Larson and Sandholm, 2000; Shehory and Kraus, 1998; 1996; Ketchpel, 1994].

If the representation of the game specifies V(B) or v(B) explicitly for each coalition B s;:; A, then the length of the representation is exponential in the number of agents. In that case, any algorithm for evaluating nonemptiness of the core (as long as it reads all the input) requires time exponential in the number of agents. However, that run time is polynomial in the size of the input (this can be accomplished, for example, using the algorithms that we introduce in Section 5).

Of course, most characteristic form games that represent real-world settings have some special structure. This usually allows for a game representation that is significantly more concise. The complexity of characterizing the core has al­ ready been studied in certain very specific concisely express­ ible families of games before. For example, Faigle eta!. study the complexity of testing membership in the core in mini­ mum cost spanning tree games [Faigle et al., 1994]. Deng and Papadimitriou study games where the players are nodes of a graph with weights on the edges, and the value of a coali­ tion is determined by the total weight of the edges contained in it [Deng and Papadimitriou, 1994]. Deng eta!. study an in­ teger programming formulation which captures many games on graphs [Deng et al., 1997]. All of those results depend heavily on concise game representations which are specific to the game families under study. Typically, such a family of games is played on a combinatorial structure. Cooperative games on combinatorial structures have been systematically studied [Bilbao, 2000].

As a point of deviation, we study a natural representation that can capture any characteristic form game. 2 Conciseness in our representation stems only from the fact that in many settings, the synergies among coalitions are sparse. When a coalition introduces no new synergy, its utility possibility vectors can be derived using superadditivity. Therefore, the input needs to include only the utility possibility vectors of coalitions that introduce synergy. The following definitions make this precise.

Definition 6 We represent a game in characteristic form without transferable utility by a set of players A, and a set of utility possibility vectors W = { (B, u 8·k)}. (Here there may be multiple vectors for the same B, distinguished by different k indices.) The utility possibility set for a given B s;:; A is then given by V(B) = { u 8 : u 8 = (u 81 ' ... 'u 8 r), ul<i<r Bi = B, all the Bi are disjoint, and for all the Bi, (Bi, ;B0 E W}. To avoid senseless cases that have no outcomes, we also require that ( {a}, (0)) E W for all a E A. 3

Definition 7 We represent a game in characteristic form with transferable utility by a set of players A, and a set of values W = {(B, v(B))}. The value for a given B s;:; A is then given by v(B) = max{ L v(Bi) : ul<i<r Bi = B, all l~i~r - -

the Bi are disjoint, and for all the Bi, (Bi, v(Bi)) E W}. To avoid senseless cases that have no outcomes, we also require that ( {a}, 0) E W whenever {a} does not receive a value elsewhere in W.

2 0ur hardness results are not implied by the earlier hardness re­ sults for specific game families because it is not possible to concisely represent those games in our input language.

3 Setting the utility to 0 in this case is without loss of generality, as we can simply normalize the utility function to obtain this.

So, we only need to specify a basis of utility possibilities, from which we can then derive the others. This representa­ tion integrates rather nicely with real-world problems where determining any coalition's value is complex. For example, in the multiagent vehicle routing problem, we solve the routing problem for every coalition that might introduce new syner­ gies. When it is clear that there is no synergy between two coalitions (for example, if they operate in different cities and each one only has deliveries within its city), there is no need to solve the routing problem of the coalition that would result if the two coalitions were to merge.

The following lemmas indicate that we can also use this representation effectively for checking whether an outcome is in the core, that is, whether it satisfies the strategic con­ straints.

Lemma 1 Without transferable utility, an outcome uA = ( uf, ... , u~) E V (A) is blocked by some coalition if and only if it is blocked by some coalition B through some utility vector u 8 , where (B, u 8 ) E W.

Proof: The "if' part is trivial. For "only if', suppose uA is blocked by coalition C through some uc, so that for every c E C, uf > u~. We know uc = (uc 1 , ··· ,uCr ) where (Ci, UC;) E w. But then, cl blocks uA through Uc 1 · ·

The proof for the same lemma in the case of transferable utility is only slightly more intricate.

Lemma 2 With transferable utility, an outcome uA (uf, ... ,u~) E V(A) is blocked by some coalition if and only if it is blocked by some coalition B through its value v(B), where (B,v(B)) E W.

Proof: The "if' part is trivial. For "only if', suppose uA is blockedbycoalitionCthroughv(C),sothatv(C) > 2.:: u~.

cEC

We know that v(C) = 2.:: v(Ci) where(Ci, v(Ci)) E W.

1t follows that .L: v ( ci) > .L: .L: u~, and hence for at l~i~r l~i~r cEC;

least one Ci, we have v( Ci) > 2.:: u~. But then Ci blocks cEC;

uA through v(Ci)· ·

4 Checking whether the core is nonempty is hard

We now show that with this representation, it is hard to check whether the core is nonempty. This holds both for the non­ transferable utility setting and for the transferable utility set­ ting.

Definition 8 (CORE-NONEMPTY) We are given a super­ additive game in characteristic form (with or without trans­ ferable utility) in our representation language. We are asked whether the core is nonempty.

We will demonstrate NP-hardness of this problem by re­ ducing from the NP-complete EXACT-COVER-BY-3-SETS problem [Garey and Johnson, 1979].

Definition 9 (EXACT-COVER-BY-3-SETS) We are given a setS of size 3m and a collection of subsets { Si} 1 <i<r of S, each of size 3. We are asked if there is a cover of S consisting of m of the subsets.

We are now ready to state our results.

Theorem 1 CORE-NONEMPTY without transferable utility is NP -complete.

Proof: To show that the problem is in NP, nondeterministi­ cally choose a subset of W, and check if the corresponding coalitions constitute a partition of A. If so, check if the out­ come corresponding to this partition is blocked by any ele­ mentofW.

To show NP-hardness, we reduce an arbitrary EXACT­ COVER-BY-3-SETS instance to the following

CORE-NONEMPTY instance. Let the set of players be A = S U { w, x, y, zJ- For each Si, let (Si, u 5 ') be an el­ ement of W, with u ' = (2, 2, 2). Also, for each s E S, let ({s,w},u{s,w}) be an element of W, with u{s,w} = (1,4). Also, let ({w,x,y,z},u{w,x,y,z}) be an element of W, with u{w,x,y,z} = (3, 3, 3, 3) . Finally, let ( {x, y}, u{x,y}) with u{x,y} = (2, 1), ({y,z},u{y,z}) with u{y,z} = (2, 1), ({x,z},u{x, z}) withu{x,z} = (1,2) beelementsofW. The only other elements of W are the required ones giving util­ ity 0 to singleton coalitions. We claim the two instances are equivalent.

First suppose there is an exact cover by 3-sets consisting of Sc 1 , ··· , Scm. Then the following outcome is possible: (uScl' ... 'uScm' u{w,x,y,z}) = (2, 2, ... '2, 3, 3, 3, 3). It is easy to verify that this outcome is not blocked by any coali­ tion. So the core is nonempty.

Now suppose there is no exact cover by 3-sets. Suppose the core is nonempty, that is, it contains some outcome uA = (u 01 , ... ,u 0 r) with each (Ci,u 0 ' ) an element of W, and the Ci disjoint. Then one of the Ci must be { s, w} for some s E S: for if this were not the case, there must be some s E S with u~ = 0, because the ci that are equal to si cannot cover S; but then { s, w} would block the outcome. Thus, none of the Ci can be equal to { w, x, y, z }. Then one of the Ci must be one of {x, y}, {y, z}, {x, z}, or else two of {x, y, z} would block the outcome. By symmetry, we can without loss of generality assume it is {x, y }. But then {y, z} will block the outcome. (Contradiction.) So the core is empty. ·

We might hope that the convexity introduced by transfer­ able utility makes the problem tractable through, for example, linear programming. This turns out not to be the case.

Theorem 2 CORE-NONEMPTY with transferable utility is NP-complete.

Proof: To show that the problem is in NP, nondeterministi­ cally choose a subset of W, and check if the corresponding coalitions constitute a partition of A. If so, nondeterministi­ cally divide the sum of the coalitions' values over the players, and check if this outcome is blocked by any element of W.

To show NP-hardness, we reduce an arbitrary EXACT­ COVER-BY-3-SETS instance to the following

CORE-NONEMPTY instance. Let the set of players be A = S u {x, y}. For each Si, let (Si, 3) be an element of W. Additionally, let (S U {x},6m), (S U {y} ,6m), and ( { x, y }, 6m) be elements of W. The only other elements of Ware the required ones giving value 0 to singleton coalitions. We claim the two instances are equivalent.

First suppose there is an exact cover by 3-sets consist­ ing of Sc 1 , .·· , Scm. Then the value of coalition S is at least :Z::::: v(ScJ = 3m. Combining this with the coalil~i~m

tion { x, y}, which has value 6m, we conclude that the grand coalition A has value at least 9m. Hence, the outcome (1, 1, ... , 1, 3m, 3m) is possible. It is easy to verify that this outcome is not blocked by any coalition. So the core is nonempty.

Now suppose there is no exact cover by 3~sets. Then the coalition S has value less than 3m (since there are no m dis­ joint Si). and as a result the value of the grand coalition is less than 9m. It follows that in any outcome, the total utility of at least one of S U { x }, S U {y }, and { x, y} is less than 6m. So this coalition will block. So the core is empty. ·

Our results imply that it is computationally hard to make any strategic assessment of a game in characteristic form when it is concisely represented.

5 Specifying redundant information about the grand coalition makes the problem tractable

Our proofs that CORE-NONEMPTY is hard relied on con­ structing instances where it is difficult to determine what the grand coalition can accomplish. So, in effect, the hardness derived from the fact that even collaborative optimization is hard in these instances. While this is indeed a real difficulty that occurs in the analysis of characteristic form games, we may nevertheless wonder to what extent computational com­ plexity issues are introduced by the purely strategic aspect of the games. To analyze this, we investigate the computational complexity of CORE-NONEMPTY when V(A) (or v(A)) is explicitly provided as (possibly redundant) input, so that determining what the grand coalition can accomplish can no longer be the source of any complexity. 4 It indeed turns out that the problem becomes easy both with and without trans­ ferable utility.

Theorem 3 When V(A) is explicitly provided, CORE­ NONEMPTY without transferable utility is in P.

Proof: The following simple algorithm accomplishes this ef­ ficiently. For each element of V(A), check whether it is blocked by any element of W. ·

For the transferable utility case, we make use of linear pro­ gramming.

Theorem 4 When v(A) is explicitly provided, CORE­ NONEMPTY with transferable utility is in P.

4 Bilbao et al. have studied the complexity of the core in charac­ teristic form games with transferable utility when there is an oracle that can provide the value v(B) of any coalition B [Bilbao et al., l. Our amended input corresponds to asking one such query in addition to obtaining the unamended input.

Proof: We decide how to allocate the v(A) among the agents by solving a linear program. The core is nonempty if and only if the following linear program has a solution:

• L ui ~ v(A); l ~i~n
• For any (B, v(B)) in W, L ub 2:: v(B). · bEB

The algorithms in the proofs also construct a solution that is in the core, if the core is nonempty.

6 Hybrid games remain hard

Not all complexity issues disappear through having the col­ laborative optimization problem solution available. It turns out that if we allow for hybrid games, where only some coali­ tions can transfer utility among themselves, the hardness re­ turns. In particular, we show hardness in the case where only the grand coalition can transfer utility. This is a natural model for example in settings where there is a market institution that enforces payments, but if a subset of the agents breaks off, the institution collapses so payments cannot be enforced.

We demonstrate NP-hardness of this problem by reducing from the NP-complete NODE-COVER problem [Garey and Johnson, 1979].

Definition 10 (NODE-COVER) We are given a graph G = (V, E), and a number k. We are asked whether there is a subset of V of size k such that each edge has at least one of its endpoints in the subset.

We are now ready to state our result.

Theorem 5 When only the grand coalition can transfer util­ ity,

CORE-NONEMPTY is NP-complete, even when v(A) is ex­ plicitly provided as input.

Proof: To show that the problem is in NP, nondeterministi­ cally divide v(A) over the players, and check if this outcome is blocked by any element of W .

To show NP-hardness, we reduce an arbitrary NODE­ COVER instance to the following CORE-NONEMPTY in­ stance. Let A= V U {x,y, z }, and let v(A) = 6!V[ + k. Furthermore, for each edge (vi, Vj ), let ( {vi , Vj } , u{ v ;,v j }) be an element of W, with u{v; ,v3 } = (1 , 1). Finally, for any a, b E {x, y,z} (a I= b), let ({a,b},u{ a,b}) be an element of W, with u{a,b} = (3[V[, 2[V[). The only other elements of W are the required ones giving utility 0 to singleton coali­ tions. This game does not violate the superadditivity assump­ tion, since without the explicit specification of v(A), super­ additivity can at most imply that v(A) = 6!V[ ~ 6[V[ + k. We claim the two instances are equivalent.

First suppose there is a node cover of size k. Consider the following outcome: all the vertices in the node cover receive utility 1, all the other vertices receive utility 0, and each of x , y, and z receives utility 2[V[ . Using the fact that all the edges are covered, it is easy to verify that this outcome is not blocked by any coalition. So the core is nonempty.

Now suppose there is some outcome uA in the core. In such an outcome, either each of { x, y, z} receives at least 2!V[, or two of them receive at least 3!V[ each. (For if not, there is some a E {x, y, z} with u: < 2[V[ and some bE {x,y , z} (b I= a) with u~ < 3[V[ , and the coalition {b, a} will block through u{b,a} = (3[V[ , 2!V[) .) It follows that the combined utility of all the elements of Vis at most k. Now, for each edge (vi , Vj ), at least one of its vertices must receive utility at least I, or this edge would block. So the ver­ tices that receive at least 1 cover the edges. But because the combined utility of all the elements of V is at most k, there can be at most k such vertices. So there is a node cover. ·

Hybrid games, where only some coalitions can transfer utility, are quite likely to appear in real-world multiagent settings, for example because only some of the agents use a currency. Our result shows that for such hybrid games, even when the collaborative optimization problem has al­ ready been solved, it can be computationally hard to strate­ gically assess the game.

7 Conclusions and future research

Coalition formation is a key problem in automated negotia­ tion among self-interested agents, and other multiagent ap­ plications. A coalition of agents can sometimes accomplish things that the individual agents cannot, or can do things more efficiently. However, motivating the agents to abide to a so­ lution requires careful analysis: only some of the solutions are stable in the sense that no group of agents is motivated to break off and form a new coalition. This constraint has been studied extensively in cooperative game theory. How­ ever, the computational questions around this constraint have received less attention. When it comes to coalition forma­ tion among software agents (that represent real-world par­ ties), these questions become increasingly explicit.

In this paper we defined a concise general representation for games in characteristic form that relies on superadditivity, and showed that it allows for efficient checking of whether a given outcome is in the core. We then showed that deter­ mining whether the core is nonempty is NP-complete both with and without transferable utility. We demonstrated that what makes the problem hard in both cases is determining the collaborative possibilities (the set of outcomes possible for the grand coalition), by showing that if these are given, the problem becomes tractable in both cases. However, we then demonstrated that for a hybrid version of the problem, where utility transfer is possible only within the grand coalition, the problem remains NP-complete even when the collaborative possibilities are given.

Future research can take a number of different directions. One such direction is to investigate the complexity of re­ stricted families of games in characteristic form. 5 Another direction is to evaluate other solution concepts in cooperative game theory from the perspective of computational complex­ ity under our input representation. A long-term goal is to extend our framework for finding a strategically stable solu­ tion to take into account issues of computational complexity in determining the synergies among coalitions (for example, when routing problems need to be solved, potentially only approximately, in order to determine the synergies).

5 0ne interesting restricted family is that of convex games. In a convex game (with transferable utility), for any B , C ~ A, v(B) + v(C) ~ v(B U C) + v(B n C), and in such games the core is known to always be nonempty. How complex it is here to construct a solution in the core with our representation is an open question.