Concise Characteristic Function Representations in Coalitional Games Based on Agent Types

1 Introduction

Forming effective coalitions is a major research challenge in AI and multi-agent systems (MAS). A coalition of agents can sometimes accomplish things that individual agents cannot or can do things more efficiently. There are two major research topics in coalitional games. The first topic involves partitioning a set of agents into coalitions so that the sum of the rewards of all coalitions is maximized. This problem is called the Coalition Structure Generation problem (CSG) [Sandholm et al., 1999; Rahwan and Jennings, 2008]. The second topic involves how to divide the value of the coalition among agents. The theory of coalitional games provides a number of solution concepts, such as the core, the Shapley value, and the nucleolus.

A range of previous studies have found that many problems in coalitional games, including CSG, tend to be computationally intractable. Traditionally, the input of a coalitional game is a black-box function called a characteristic function, which takes a coalition as an input and returns the value of the coalition (or a coalition structure as a whole). Recently, several concise representation schemes for a characteristic function have been proposed, e.g., synergy coalition group (SCG) [Conitzer and Sandholm, 2006] and marginal contribution nets (MC-nets) [Ieong and Shoham, 2005]. These schemes represent a characteristic function as a set of rules rather than as a single black-box function and can effectively reduce the representation size. However, most problems are still computationally intractable (Table 1).

In this paper, we develop a new concise representation scheme for a characteristic function, which is based on the idea of agent types. Intuitively, a type represents a set of agents, which are recognized as having the same contribution. Most of the hardness results in Table 1 are obtained by assuming that all agents are different types. In practice, however, in many MAS application problems, while the number of agents grows, the number of different types of agents remains small. This type-based representation can be exponentially more concise than existing concise representation schemes. Furthermore, this idea can be used in conjunction with existing schemes, i.e., SCG and MC-nets, for further reducing the representation size. We show that most of the problems in coalitional games, including CSG, can be solved in polynomial time in the number of participating agents, assuming the number of possible types t is fixed (Table 2).

Let us introduce a motivating example that can be formalized as coalitional games with agent types. Consider a problem of forming rescue groups in a disaster area. There exists a set of participating agents and each agent has following different capabilities: providing medical treatment, driving a vehicle, acting as a firefighter, etc. We can regard the capability of an agent as the agent type. In the problem, while the number of agents grows, we can assume that the number of agent types is fixed. Thus, we can use type-based characteristic function representations to compactly represent this problem.

We can also consider our type-based representation provides an approximation method. Even if the capabilities of agents are not exactly the same, as long as they are similar, we can consider that their types are the same and assume each member of that type has the same capability (e.g., the average of members). Then, by using our type-based representation, we can obtain an approximate solution efficiently.

Our idea of using agent types is inspired by the recent innovative work of [Shrot et al., 2010]. They assume that a game is already represented in some concise representation, e.g., SCG. More precisely, they consider the cases where a game is represented as a graphical representation [Deng and Papadimitriou, 1994], a coalition resource game [Wooldridge and Dunne, 2006], or SCG. The goal of their work is first to identify agent types and then to efficiently solve problems in coalitional games by utilizing the knowledge of agent types. For example, they show that when the characteristic function is represented as an SCG and types of agents are determined, computing the Shapley value and determining whether the core is non-empty can be done in polynomial time in the number of agents. However, this approach becomes infeasible when a standard characteristic function representation is used, since there exists no efficient way for identifying agent types.

In contrast to their study, we assume that agent types are explicitly used for describing a characteristic function in the first place. Also, we consider a wider range of problems including CSG. As a result, the overlap between our work and [Shrot et al., 2010] is very small. In Table 2, only two entries, i.e., Core non-empty and the Shapley value for SCG, might be considered as somewhat overlapping, while other topics are not discussed in [Shrot et al., 2010].

1.1 RelatedWorks

Several other works than [Shrot et al., 2010] have also examined the concept of agent types to represent agent capabilities. Bachrach and Rosenschein [2008] introduce coalitional skill games, where the capability of an agent is characterized by its skills. We can consider such skills correspond to agent types. However, they do not assume that the possible types/skills of an agent are fixed (even if the number of skills is fixed, the combinations of skills are exponential). Thus, their algorithms and complexity results are quite different from ours. Chalkiadakis et al. [2009] consider another representation scheme that can represent any characteristic function, as well as ours. However, they examine the complexity of coalition formation problems only in simple games, where the value of a characteristic function is either 0 or 1, while we consider general games, where the value can be arbitrary determined.

Furthermore, the literature of weighted voting games [Bachrach and Elkind, 2008; Elkind and Pasechnik, 2009] assumes that the possible types of an agent are bounded. In this game, each agents has a weight and the value of a coalition is determined by the sum of their weights. The value of a coalition is 1 if the total weights exceeds a certain quota, and 0 otherwise. Their works are very similar to our works if we regard each agent's weight as the agent type. They showed that the core-related coalition formation problems and computing the Shapley value and the nucleolus become more tractable when the number of weights is bounded. However, as well as [Chalkiadakis et al., 2009], they concentrate on only simple games and their type-based representation by using a weight is a subclass of our proposed one where all types are classified by a cardinal utility. Thus, we believe that this paper has significant new contributions since it can handle general characteristic functions.

2 Model

2.1 Coalitional Games and Coalition Structure Generation

Let A = {1, 2, . . . , n} be a set of all agents. The value of a coalition S is given by a characteristic function v. A characteristic function v : 2A → R assigns a value to each set of agents (coalition) S ⊆ A. We assume that each coalition's value is non-negative.

5 These problems can be solved in linear time in the input size.

6 This bound is not tight. Examining a tight bound is an open problem.

Let x = (x1, x2, . . . , xn) be a payoff vector. A solution concept assigns to each coalitional game a set of reasonable payoff vectors. Two of the best-known ones are the core and the Shapley value.

Definition 1. The core is the set of all payoff vectors x, which satisfy the feasibility condition: ∑i∈A xi = v(A), and the non-blocking condition: ∀S ⊆ A, ∑i∈S xi ≥ v(S).

If there exists a blocking coalition S such that ∑i∈S xi < v(S) holds, then the agents in S have an incentive to collectively deviate from the grand coalition and divide v(S) themselves. In general, the core can be empty or contain a large set of payoff vectors.

One intuitive interpretation of the Shapley value is that it averages an agent's marginal contribution over all possible orders in which the agent may join the coalition.

A coalition structure CS is a partition of A, into disjoint, exhaustive coalitions. More precisely, CS = {S1, S2, . . . } satisfies the following conditions: ∀i, j (i ̸= j), Si ∩ Sj = φ, ⋃Si∈CS Si = A. In other words, in CS, each agent belongs to exactly one coalition, and some agents may be alone in their coalitions.

The value of a coalition structure CS, denoted as V (CS), is given by: V (CS) = ∑Si∈CS v(Si). An optimal coalition structure CS ∗ is a coalition structure that satisfies the following condition: ∀CS, V (CS ∗ ) ≥ V (CS). We say a characteristic function is super-additive, if for any disjoint sets Si, Sj, v(Si ∪ Sj) ≥ v(Si) + v(Sj) holds. If the characteristic function is super-additive, solving CSG becomes trivial, i.e., the grand coalition is optimal. In this paper, we assume a characteristic function can be non-super-additive.

Example 1. Let there be four agents a, b, c, and d. The characteristic function is given as follows:

In this case, there exist multiple optimal CSs. For example, {{a, b, c}, {d}} and {{a, b, d}, {c}} are optimal CSs, and the value of these CSs is 10.

2.2 Agent Types

Shrot et al. [2010] introduced the idea of using agent types to reduce the computational complexity of coalition formation problems. If two agents have the same type, their marginal contributions are the same. They introduced two different notions of agent types, i.e., strategic types and representational types. The former defines types based on the strategic power of the agents, and the latter defines them based on the representation of the game.

Strategic types are defined based on the marginal contribution of each agent, i.e., if two agents are strategically equivalent, they belong to the same (strategic) type.

Definition 3 (Definition 2.1 in [Shrot et al., 2010]). Agents i, j ∈ A are strategically equivalent if for any coalition S, such that i, j /∈ S : v(S ∪ {i}) = v(S ∪ {j}).

The notion called representational type is introduced to check the equivalence of agents more conveniently based on a concise representation. Agents are representationally equivalent if they only differ in their identifier. If two agents are representationally equivalent, they are also strategically equivalent, but not vice versa.

Shrot et al. [2010] examined the computational complexity for determining strategic or representational types for several concise representations [Deng and Papadimitriou, 1994; Wooldridge and Dunne, 2006; Conitzer and Sandholm, 2006]. They further showed that if the number of types is fixed in these representations, most intractable problems in coalitional games become polynomial.

3 Type-based Characteristic Function Representation

Shrot et al. assume that a game is already represented in some concise representation. The goal of their work is to identify agent types and to solve problems in coalitional games by efficiently utilizing agent types.

In this paper, we propose an alternate approach. We assume the person who is describing a game has some prior information about the equivalence of agents. Then the person will describe the game by explicitly using the information of the agent types of which he/she is aware. We need another notion of agent types. This is because (i) the information of the person can be partial and he/she is not necessarily aware of all strategic equivalence, and (ii) the equivalence that he/she is aware of is representation-independent. Therefore, we introduce another notion called recognizable types.

Definition 4. Agents i, j ∈ A are recognizably equivalent if the person who is describing the game (either by a characteristic function or by a concise representation) knows that for any coalition S, such that i, j /∈ S : v(S∪{i}) = v(S∪{j}).

From this definition, if two agents are recognizably equivalent, they are also strategically equivalent, but not vice versa. Furthermore, assuming appropriate representation is chosen, if two agents are recognizably equivalent, they are very likely to be representationally equivalent.

Let T = {1, 2, . . . , t} be the set of all recognizable types and niA be the number of agents of type i ∈ T in the set of all agents A. Also, nA = 〈n1A, n2A, . . . , ntA〉 denotes a vector, where each element represents the number of agents of each type in A.

We represent a characteristic function as follows:

Definition 5. For a coalition S, the coalition type of S is a vector nS = 〈n1S , n2S , . . . , ntS 〉, where each niS is the number of type i agents in S. We denote the set of all possible coalition types as At = {〈n1 , n2 , . . . , nt 〉 | 0 ≤ ni ≤ niA}. A type-based characteristic function is defined as vt : At → R.

From the definition of recognizable equivalence, ∀S and its type nS, v(S) = vt(nS) holds.

Theorem 1. A type-based characteristic function requires O(nt ) space.

Proof. It is clear from the fact that |At | = (n1A + 1) × . . . × (ntA + 1) < nt .

Example 2. Let agents a, b be type 1 and agents c, d be type 2 in Example 1. A type-based characteristic function representation for Example 1 is given as follows:

For example, the type of coalition S = {a, b, c} is 〈2, 1〉 because S contains two agents of type 1 and one agent of type 2. Thus, v(S) = 8. Here, the type-based representation defines the value for each of eight possible coalition types, while the standard representation needs to specify the value for each of fifteen possible coalitions. In general, a type-based representation is exponentially more concise than a standard representation.

We say a payoff vector is symmetric if all agents with the same type receive an identical amount. We can restrict our attention to symmetric payoff vectors without loss of generality (Lemma 3.2 in [Shrot et al., 2010]). From these definitions, we obtain the following theorems about the coalition formation problems of the core and the Shapley value.

Theorem 2. If the number of agent types t is fixed, by using a type-based characteristic function, determining whether the core is non-empty can be done in polynomial time in the number of agents n. Also, determining whether a symmetric payoff vector x is in the core can be done in O(nt ) time.

Theorem 3. By using a type-based characteristic function representation, computing the Shapley value of any agent can be done in O(nt ) time.

For space reasons, we omit the proofs. These results come from the fact that the number of possible coalition types |At | is at most O(nt ).

4 Coalition Structure Generation with Agent Types

In this section, we develop an algorithm for the CSG problem based on knapsack problems [Kellerer et al., 2004]. A multidimensional unbounded knapsack problem (MUKP) is the knapsack problem, where the knapsack has multidimensional constraint and multiple copies exist for each item. For each item j, we denote the profit as pj, the weight of the ith constraint as wij , and the number of copies packed in the knapsack as qj . A MUKP with m items and t constraints of knapsack c1, . . . , ct is formalized as follows:

Theorem 4. By using a type-based characteristic function representation, finding an optimal coalition structure can be done in O(n2t ) time.

Proof. We show that a CSG problem with m = |At | coalition types and t possible agent types can be formalized as a MUKP with m items and t constraints. Let us assume that one possible coalition type nSj ∈ At corresponds to item j, where its value pj is equal to vt(nSj ) and its weight for the i-th constraint is equal to niSj . The capacity constraint of knapsack ci is determined by niA.

Let zj[d1] . . . [dt] be the optimal solution value for the knapsack problem (CSG) with j coalition types {nS1 , . . . , nSj } and a capacity constraint of knapsack ci = di, ∀i ∈ T . If zj-1[d1] . . . [dt] is known for all capacity values 0 ≤ di ≤ niA, ∀i ∈ T , then we can include another coalition type nSj and compute the corresponding solutions zj[d1] . . . [dt] using the following recursive formula:

We can construct a dynamic programming based algorithm from this recursive formula, which takes O(nt × |At |) = O(n2t ) steps (see Section 9.3.2 in [Kellerer et al., 2004]). Thus, for any fixed t, finding an optimal coalition structure can be done in O(n2t ) time.

A similar argument has been done for the winner determination problem in combinatorial auctions with a fixed number of types of items [Tennenholtz, 2000]. In fact, a CSG problem can be mapped into that problem by assuming each coalition type corresponds to a bid and that each type of agent corresponds to a type of item.

5 Combining with Concise Representation Schemes

5.1 Type-based SCG

We first show the original definition of SCG [Conitzer and Sandholm, 2006].

Definition 6. An SCG consists of a set of pairs of the form: (S, v(S)). For any coalition S, the value of the characteristic function is: v(S) = max{∑Si∈pS v(Si)}, where pS is a partition of S, i.e., all Si are disjoint and ∪Si∈pS Si = S, and for all the Si, (Si, v(Si)) ∈ SCG. To avoid senseless cases that have no feasible partitions, we require that ({a}, 0) ∈ SCG whenever {a} does not receive a value elsewhere in SCG.

Using this original definition, we can represent only superadditive characteristic functions. To allow for characteristic functions that are not super-additive, Ohta et al. [2009] slightly modify the definition, i.e., they add the following requirement for partition pS: ∀p′S ⊆ pS, where |p′S | ≥ 2, (∪Si∈p′S Si, v(∪Si∈p′S Si)) is not an element of SCG. We refer to this modified definition as a standard SCG.

Next, we introduce the definition of a type-based SCG.

Definition 7. A type-based SCG consists of a set of pairs of the form: (nS, vt(nS)). For any coalition type nS, the value of the characteristic function is defined in a similar way as a standard SCG.

Theorem 5. A type-based SCG can represent any characteristic function represented in a standard SCG using at most the same amount of space and is exponentially more concise than a standard SCG for certain games.

We omit the proofs due to space limitations. Intuitively, the worst case occurs when the recognizable types of all agents are different. Also, when all agents have an identical type, the value of a characteristic function is determined only by the number of agents in a coalition. Then the required size of a type-based SCG becomes O(n), but the size of a standard SCG can be exponential.

Example 3. A type-based SCG for Example 1 is given as follows:

In this case, vt(〈2, 1〉) = vt(〈1, 0〉)+vt(〈1, 0〉)+vt(〈0, 1〉) = 8. Here, the type-based SCG defines the value of four coalition types, while the type-based characteristic function representation needs to describe eight possible coalition types.

As discussed in [Conitzer and Sandholm, 2006], corerelated coalition formation problems remain hard in a standard SCG, because determining the value of the grand coalition is hard. If the value of the grand coalition is given explicitly, these problems become tractable. By using a type-based SCG, we can obtain the value of the grand coalition using a method similar to the DP-based algorithm described in Theorem 4. As a result, the following theorem holds.

Theorem 6. If the number of agent types t is fixed, by using a type-based SCG representation, determining whether the core is non-empty can be done in polynomial time in the number of agents n. Also, determining whether a symmetric payoff vector x is in the core can be done in O(n2t ) time.

Unfortunately, as far as the authors are aware, there is no efficient way to compute Shapley values using SCG-based representations. However, we can use a naive translation approach, which can be done in polynomial time.

Theorem7. If the number of agent types t is fixed, by using a type-based SCG representation, computing the Shapley value can be done in O(n2t ) time.

We can use the DP-based algorithm described in Theorem 4 for finding an optimal coalition structure. The only difference is that we need to consider coalition types that are explicitly represented in a type-based SCG.

Theorem 8. By using a type-based SCG representation, finding an optimal coalition structure can be done in O(n2t ) time.

5.2 Type-basedMC-nets

We first show the original definition of MC-nets [Ieong and Shoham, 2005].

Definition 8. An MC-net consists of a set of rules R. Each rule r ∈ R is of the form: (Pr,Nr) → vr, where Pr ⊆ A,Nr ⊆ A, Pr ∩Nr = ∅, vr ∈ R. vr can be either positive or negative. We say that rule r is applicable to coalition S if Pr ⊆ S and Nr ∩ S = ∅, i.e., S contains all agents in Pr (positive literals) but no agent in Nr (negative literals). For a coalition S, v(S) is given as ∑r∈RS vr, where RS is the set of rules applicable to S.

Next, we introduce the definition of type-based MC-nets.

Definition 9. A type-based MC-net consists of a set of rules R. Each rule r ∈ R is of the form: (Lr, Ur) → vr, where Lr = 〈l1 r , l2 r , . . . , ltr 〉 and Ur = 〈u1r , u2r , . . . , utr 〉. Each lir (and uir) represents the lower (upper) bound of the number of i-th type agents in a coalition so that this rule becomes effective. We say that rule r is applicable to coalition S if ∀i ∈ T, lir ≤ niS ≤ uir. For a coalition S, v(S) is given as ∑r∈RS vr, where RS is the set of rules applicable to S.

Theorem 9. A type-based MC-net can represent any characteristic function represented in a standard MC-net using at most the same amount of space and is exponentially more concise than a standard MC-net for certain games.

For space reasons, we omit the proofs. We can prove these theorems using a similar argument described in Theorem 5.

Example 4. A type-based MC-net for Example 1 is given as follows:

In this case, r2 and r3 are applicable to coalition type 〈2, 1〉, but r1 and r4 are not. Thus, vt(〈2, 1〉) is equal to 6 + 2 = 8. Here, the type-based MC-net consists of four rules, while the type-based characteristic function representation needs to specify the value of eight possible coalition types.

Unfortunately, there is no efficient way to solve corerelated coalition formation problems using MC-net-based representations. However, we can use a naive translation approach, which can be done in polynomial time.

Theorem 10. If the number of agent types t is fixed, by using a type-based MC-net representation, determining whether the core is non-empty can be done in polynomial time in the number of agents n. Also, determining whether a symmetric payoff vector x is in the core can be done in O(n2t ) time.

In contrast to core-related coalition formation problems, the standard MC-net representation is suitable for computing Shapley values. This is also true for our type-based MC-net representation, i.e., the following theoremholds.

Theorem11. If the number of agent types t is fixed, by using a type-based MC-net representation, computing the Shapley value of any agent can be done in O(|R| · n2t ) time.

Proof. To compute the Shapley value of an agent, we can compute its Shapley value for each rule and use the summation of these values (see Proposition 5 in [Ieong and Shoham, 2005]). Furthermore, we can decompose a rule into multiple rules, where each decomposed rule has a form: (〈y1 , . . . , yt 〉, 〈y1 , . . . , yt 〉) → v, i.e., the rule is applicable to exactly one coalition type. The Shapley value of type i agent for rule r number of agents standard SCG grows exponentially compared to that in the type-based SCG. When the number of elements in the typebased SCG representation exceeds 40, we cannot translate the problem instances due to insufficient memory. This result illustrates that the type-based representation is exponentially more concise than the standard representation.

Figure 1: Computation time

We investigate the computation time of our DP-based algorithm. For comparison, we show the results of the MIP formulation in Ohta et al. [2009], which uses a standard SCG representation. To obtain this result, we used CPLEX version 12.1, a general-purpose mixed integer programming package.

Figure 1 illustrates the average computation times for solving the generated problem instances by our DP-based algorithm using the type-based SCG (DP) and by CPLEX in the MIP formulation using the standard SCG (CPLEX). The xaxis indicates the number of agents, and the y-axis shows the average computation times. When n ≤ 20, CPLEX is faster than DP, while DP eventually outperforms CPLEX for n > 20. CPLEX can reduce the search space efficiently when the input size is relatively small. However, the input size for CPLEX grows exponentially. Thus, its computation time increases very rapidly. When n > 40, even generating problem instances becomes infeasible. On the other hand, the computation time for DP grows more slowly than the exponential rate. This result corresponds to the theoretical complexity presented in Theorem 8, i.e., finding an optimal coalition structure can be done in O(n2t ) time. As shown in this result, the type-based SCG enables us to solve a CSG problem instance with up to 100 agents in a reasonable amount of time.

7 Conclusion

In this paper, we developed a new concise representation scheme for a characteristic function, which is based on the idea of agent types. The type-based representation can be exponentially more concise than existing concise representation schemes. Furthermore, this idea can be used in conjunction with existing schemes, i.e., MC-nets and SCG, for further reducing the representation size. We showed that most problems in coalitional games, including CSG, can be solved in

Here, f + i (y1, . . . , yt) represents the number of orderings where the marginal contribution of one type i agent is v, and f - i (y1, . . . , yt) represents the number of orderingswhere the marginal contribution of one type i agent is -v. Thus, v n! (f + i (y1, . . . , yt) - f - i (y1, . . . , yt)) represents the Shapley value of type i agent for this rule. Using this procedure, the required time for computing the Shapley value of an agent becomes O(|R| · n2t ).

Although Ohta et al. [2009] proposed an efficient method for solving CSG problems based on the standard MC-net, we cannot apply this method straightforwardly. Nevertheless, we can still rely on a naive approach that translates a type-based MC-net representation into the corresponding type-based characteristic function representation.

Theorem 12. If the number of agent types t is fixed, by using a type-based MC-net representation, finding an optimal coalition structure can be done in O(n2t ) time.

6 Experimental Evaluations

In this section, we experimentally evaluate the performance of our proposed methods. We concentrate on methods for type-based SCG, since we can control the input size of a problem instance. In addition, the DP-based algorithm is also used in other representations. All tests were run on a Core 2 Quad Q9650 3GHz processor with 16GB RAM. The test machine runs Windows 7 Enterprise x64 Edition.

Let us consider a type-based SCG problem instance, where n agents have one of five different types (t = 5). We vary n from 10 to 100 and set the number of elements in a typebased SCG to n, (i.e., equal to the number of agents). We generate each element using a decay distribution as follows. Initially, the required number of agents in each type is set to zero. First, we randomly choose one type and increment the required number of agents in the type by one. Then, we repeatedly choose a type randomly and increment its required number of agents with probability α, until a type is not chosen or the required number of agents exceeds the limit. We choose the value of that coalition between 1 and 10 × n uniformly at random and use α = 0.55. In this way, we generated 50 problem instances for each n.

We translate each generated problem instance represented by type-based SCG into an equivalent problem instance represented by standard SCG. The number of elements in the polynomial time in the number of agents, assuming the number of types t is fixed. We also experimentally showed that a type-based SCG enables us to solve a CSG problem instance with up to 100 agents in a reasonable amount of time. Our idea of using agent types is inspired by the recent work of [Shrot et al., 2010]. However, in contrast to their study, our work introduced the idea of describing a characteristic function explicitly using agent types in the first place, and considered a wider range of problems in coalitional games including CSG.

In future works, we first would like to examine the complexity of other solution concepts in coalitional games with or without coalition structures, such as the nucleolus, kernel, and core with coalition structures. Second, we would like to investigate our representation in conjunction with a graph-based concise representation scheme, e.g. [Deng and Papadimitriou, 1994; Kalai and Zemel, 1982; Bachrach et al., 2008; Aziz et al., 2009; Ueda et al., 2010]. For example, Shrot et al. showed that utilizing agent types makes various problems in coalitional games tractable when a characteristic function is represented graphically by the formalization used in [Deng and Papadimitriou, 1994]. Thus, we guess that our scheme also would work well, by assuming that a graphical structure describes a relationship between agent types, rather than a relationship between agents themselves.

Acknowledgements

This research was partially supported by Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (A), 20240015, 2008. The authors would like to thank anonymous reviewers for helpful discussions.