Coalitional Games via Network Flows

1 Introduction

Cooperation is a central concept in artificial intelligence and at the heart of multi-agent systems design. Coalitional game theory is the standard framework to model cooperation; it provides theoretical constructs that allow agents to take joint actions as primitives [Ieong and Shoham, 2006]. One of the most important research questions in this domain is the coalition structure generation problem (CSG), i.e., how can the set of agents be partitioned into groups (coalitions) such that social welfare is maximized? This problem has attracted considerable attention in the recent AI literature [Bachrach and Rosenschein, 2008; Michalak et al., 2010; Rahwan et al., 2011], as it has important applications and inspires new theoretical and computational challenges. Existing work on coalition structure generation focuses on characteristic function games (CFGs), i.e., games in which the outcome obtained by a coalition is not influenced by agents outside the coalition. 1

1 Recently, a coalition structure generation algorithm has been proposed in games with "externalities" (i.e., possible influences be-

The prevailing assumption in CSG algorithms is that coalition structures are disjoint. However, there exist many realistic scenarios in which this assumption does not hold [Chalkiadakis et al., 2010]. For example, in multi-sensor systems, where sensors coordinate their movements to monitor particular targets of interest, the performance can be improved by allowing the sensors to form overlapping coalitions [Dang et al., 2006].

A second prevailing assumption in existing CSG algorithms is that every agent is unique, i.e., such works do not consider situations where some agents are identical. Again, the ability to differentiate between identical and non-identical agents can often improve performance. For example, in disaster response scenarios, one should distinguish between a fire brigade and an ambulance (as they are aimed for different activities), but may be indifferent between two ambulances with equal capabilities. The theory of coalition structure generation has been extended only recently to such domains [Aziz and de Keijzer, 2011; Ueda et al., 2011].

The standard CFG representation explicitly lists the values of all the possible coalitions and requires space that is exponential in the number of agents. However, in many classes of games, there exists additional structure (such as identical agents) that can be exploited, and well-crafted representation schemes can significantly improve performance [Deng and Papadimitriou, 1994; Ieong and Shoham, 2006; Elkind et al., 2009; Aadithya et al., 2011]. However, the majority of works in this line of research focused on computing solution concepts, rather than solving the coalition structure generation problem.

To date, with very few exceptions (e.g., [Shehory and Kraus, 1998; Dang and Jennings, 2006]) the incorporation of tasks is absent from the research on coalition structure generation. The advantage of incorporating tasks is that it allows for capturing a much wider range of applications. In particular, many real-world applications involve a set of tasks to be achieved, where the agents need to form coalitions since (some of) those tasks cannot be performed by an individual agent, or can be achieved more efficiently by a group of agents (compared to an individual). However, the disadvantage of incorporating tasks is that it makes the optimization problems (such as coalition structure generation) significantly harder to solve. This is because the value of a coalition does

tween co-existing coalitions) [Rahwan et al., 2012].

not depend solely on the identities of its members; it depends on the tasks being achieved by the coalition. As such, a coalition does not necessarily have a single value. Instead, it can have a different value for every task.

Our Contribution

We formulate a unified approach for modelling different types of coalitional games in task-based settings. In particular, we formulate the coalition structure generation problem as a network flow problem-a problem widely studied in the combinatorial optimization literature, with many important applications in the real world [Schrijver, 2003]. More specifically:

• We propose a new representation of coalitional games, namely coalition-flow networks (CF-NETs), where the coalition formation process is represented as the process of directing the flow through a network with edge-capacity constraints. We show that CF-NETs are an appropriate representation for several important classes of coalitional games, such as conventional (nonoverlapping) coalitional games, overlapping coalitional games, and coalitional games with agent types. Importantly, to the best of our knowledge, this is the first representation with which one can easily and efficiently switch between cases with overlapping/non-overlapping coalitions, with/without agent types. In addition, we show how CF-NETs allow for the succinct storage of certain, potentially useful patterns.
• We show that under the CF-NET representation, the coalition structure generation problem in a task-based setting can be reformulated as a mathematical program related to the well-known production-transportation problem [Tuy et al., 1996; Holmberg and Tuy, 1999; Hochbaum and Hong, 1996].
• We provide an anytime approximation technique for the CSG problem, which provides worst-case guarantees on the quality of the solutions produced. Using numerical simulations, we show that our algorithm scales to thousands of agents. For example, for n = 5000 agents, it finds solutions within 75-85% of the optimum in a matter of seconds.

Related Work

Researchers have attempted to circumvent the intractability of the characteristic function form by developing alternative representations, which are more compact and allow efficient computations. These representations can be divided into two main categories:

1. The representation is guaranteed to be succinct, but is not fully expressive (i.e., it cannot represent any arbitrary characteristic function game) [Deng and Papadimitriou, 1994; Wooldridge and Dunne, 2006].
2. The representation is fully expressive, but is only succinct for some problem instances [Ieong and Shoham, 2006; Elkind et al., 2009; Conitzer and Sandholm, 2004b]). Our CF-NET representation scheme falls in this category.

Most previous work focuses on the computation of solution concepts, such as the Shapley value [Deng and Papadimitriou, 1994; Ieong and Shoham, 2006; Elkind et al., 2009; Conitzer and Sandholm, 2004b], the core [Conitzer and Sandholm, 2004a; 2004b], the bargaining set, and the kernel [Greco et al., 2009]. On the other hand, the coalition structure generation problem has recently attracted attention, with most of the studies focusing on characteristic function games [Rahwan et al., 2009].

Among the very few works that consider overlapping coalitions, we mention the works by Shehory and Kraus [1996] and Dang et al. [2006]. The former only proposes a greedy algorithm for a subclass of these games, whereas the latter makes heavy use of several strong assumptions placed on the characteristic function. Recently, Chalkiadakis et al. [2010] introduced a formal model of overlapping coalition formation, in which an agent can participate in multiple coalitions simultaneously, by contributing a portion of its resources to each coalition containing it.

Our CF-NET representation is designed for the purpose of solving the coalition structure generation problem efficiently. The only other representation designed with this problem in mind is due to Ohta et al. [2009]. However, unlike our representation, theirs does not incorporate tasks, and does not consider games with agent types or overlapping coalitions.

The basic idea of applying network flows to model coalitional games has been examined before, for example by Kalai and Zemel [1982] and by Bachrach and Rosenschein [2009]. However, the fundamental difference is that, in those papers, the units of flow can be thought of as utility units (so the solution to a network flow problem influences the value of a coalition). In our representation, what flows in the network is "agents", so solving a flow problem returns a coalition structure. This is precisely what gives flexibility to our framework, allowing for overlapping coalitions, or identical agents, to be considered whenever needed.

2 Preliminaries

In this section, we provide the standard definitions for the classes of coalitional games studied in this work.

We define a task-based characteristic function game, TCFG, as a coalitional game given by a tuple 〈A,K, v〉, where

• A = {a1, . . . , an} is a set of agents;
• K = {k1, . . . , kq} is a set of tasks;
• v : 2A ×K → R is a function that assigns a value to every pair (C, ki), where C is a coalition and ki is a task.

In this paper, we assume that every performed task is performed by exactly one coalition. The possibility of having a group of agents that does not perform any tasks can easily be incorporated by adding a single dummy task. On the other hand, the possibility of having a single coalition perform multiple tasks can be incorporated by allowing overlapping coalitions (in which case every performed task is performed by a single, not necessarily unique, coalition).

An implicit assumption is that every agent can participate in exactly one coalition. When an agent is allowed to belong to multiple coalitions simultaneously, the tuple 〈A, v〉

defines a task-based coalitional game with overlapping coalitions, denoted by TCFG o . In such a game, each agent can be a member of up to 2n-1 coalitions. In reality, this number is reasonable only if coordination costs are low and the number of available resources is sufficiently large.

Thus, the definition can naturally be extended to a taskbased resource-constrained coalitional game with overlapping coalitions (TCFG rco ). In such a game, each agent ai ∈ A has an upper bound on the number of coalitions it can join, which can be interpreted as a a limit on the resources that can be employed by an agent to perform tasks. In this setting, a game is formally defined by a tuple 〈A, r, v〉, where A and v are defined as above, and the function r : A → {1, . . . , 2n-1} assigns to every agent its resource constraints. 2 Note that the TCFG o and TCFG representations are special cases of TCFG rco , where the number of coalitions that an agent can join is maximal (2n-1 ) and minimal (1), respectively.

Next, we formalize task-based coalitional games with agent types. Let A and v be defined as above and T = {t1, . . . , tm : m ≤ n} a set of types, such that each agent in A is associated with one type in T. Let t : A → T be a function that returns the type of any given agent. An important situation to model in such games is that of two agents with the same type bringing the same marginal contribution to any coalition they belong to. That is, given a type tk ∈ T , for any two agents ai, aj of type tk and any coalition C ⊆ A\{ai, aj}, the following holds: v (C ∪ {ai})-v(C) = v (C ∪ {aj}) - v(C).

Recall that the conventional TCFG representation can be used to represent (albeit not concisely) the agent-type setting. Clearly, however, the game can be represented more concisely by considering the values of coalitions as a function of the types (rather than the identities of the agents). To this end, we define coalitional games with agent types.

Definition 1 A task-based coalitional game with agent types (TCFG at ) is a tuple 〈A, T, t, T , vat 〉, where:

• A = {a1, . . . , an} is a set of agents;
• T = {t1, . . . , tm≤n} is a set of agent types;
• t : A → T is a function that returns the type of any agent, ai ∈ A;
• T = T1 ∪ · · · ∪ Tm is a multi-set of agent types, such that Tk = {tk, · · · , tk}, where |Tk| = |{ai ∈ A : t(ai) = tk}|, ∀k ∈ {1, · · · ,m};
• K = {k1, . . . , kq} is a set of tasks;
• vat : 2T ×2K →R is a characteristic function of agent types.

3 The CF-NET Representation

Next, we introduce the framework of coalition-flow networks (CF-NETs) to represent the classes of coalitional games discussed above.

2 The above definitions of overlapping coalitional games can be viewed as a special case of a highly theoretical construct of Chalkiadakis et al. [2010], where each agent can devote a unit of resource to an infinite number of (possibly identical) coalitions.

Definition 2 A coalition-flow network (CF-NET) is a tuple 〈N, E, X , Y, Z〉, where (1) (N, E) is an acyclic digraph with a set of nodes N and a set of directed edges E, and (2) X , Y and Z are sets of constraints. In particular:

1. The set of nodes, N, is the union of the following disjoint sets:
2. {S,G} contains the source node S from which the "flow" is pushed into the network and the sink node G towards which the flow needs to be directed.
3. N a is the set of agent nodes: each agent (or type) is represented by exactly one such node. As such, |N a | = n.
4. N k is the set of task nodes: each task is represented by exactly one such node. Thus, |N k | = q.
5. The set of edges is E = ({S}×N a )∪E′ ∪(N k ×{G}), where E′ ⊆ {(ni, nj) : ni ∈ N a , nj ∈ N k }.
6. The set of constraints is X ∪Y ∪Z, where X = {Xi : i = 1 . . . n}, Y = {Yij : i = 1 . . . n, j = 1 . . . q}, and Z = {Zj : j = 1 . . . q}, which restrict the possible values of the flow through the edges in {S} × N a , E′ and N k × {G}, respectively. In particular:
7. Xi represents the permitted multiplicities of agent ai (or the permitted numbers of agents whose type is ti) in the game.
8. Yij represents the permitted multiplicities of agent ai (or permitted numbers of agents of type ti) that will perform task kj .
9. Zj represents the sizes of the coalition that will perform task kj .

An illustration of the CF-NET representation can be found Figure 1). Now, based on the network structure (N,E) defined above, and the constraints X ∪ Y ∪ Z imposed on the flow through the edges, we introduce next the notion of CFflow. Intuitively, the CF-flow depicts the coalition formation process. Analogously to the flow in the network, the process of directing the flow from the source node to the sink node (through the agent/type nodes and the task nodes) can be interpreted as the process of determining which coalition should perform each task.

Definition 3 A coalition formation flow (CF-flow) in a CFNET 〈N,E,X, Y,Z〉 is a function f : E → R with the following properties:

1. f(S, ni) ∈ X, ∀ni ∈ N a .

Let (x, y, z) be an instantiation of a CF-flow f in a CF-NET 〈N, E, X , Y, Z〉, such that xi = f(S, ni) for ni ∈ N a , yij = f(ni, nj) for (ni, nj) ∈ E′ , and zj = f(nj, G) for nj ∈ N k . Then, from Definition 3, we have:

Given a CF-flow, we define next the values of the coalitions constructed by it. To this end, we equip a CF-NET with three valuation functions as follows:

Definition 4 Given a CF-NET 〈N, E, X , Y, Z〉, let c, d, g be the valuation functions defined, respectively, on {S} × N a , E′ and N k × {G}, such that:

• For all (S, ni) ∈ {S}×N a , ci = c(S, ni) represents the value of a singleton coalition of agent ai (or an agent of type ti).
• For all (ni, nj) ∈ E′ , dij = d(ni, nj) is the contribution of agent ai (or an agent of type ti) to task kj.
• For all (nj,G) ∈ N k × {G}, gj(zj) = g(nj,G) is a synergy function, where zj ∈ Zj is the size of the coalition performing task kj . 3

That is, the value of a coalition C performing task kj is given as:

The first advantage of CF-NETs is their ability to represent any of the four classes of games discussed above, (i.e. TCFG, TCFG o , TCFG rco , and TCFG at ). This can be done simply by setting the appropriate X , Y, and Z. In more detail,

• In TCFG, ∀ai ∈ A,Xi = {1}, ∀ai ∈ A, ∀kj ∈ K, Yij = {0, 1}, and ∀kj ∈ K, Zj = {0, . . . , n};
• In TCFG o , ∀ai ∈ A,Xi = {1, . . . , 2n-1}, ∀ai ∈ A, ∀kj ∈ K, Yij = {0, 1}, and ∀kj ∈ K,Zj = {0, . . . , n};
• In TCFG rco , ∀ai ∈ A,Xi = {1, . . . , r(ai)}, ∀ai ∈ A, ∀kj ∈ K, Yij = {0, 1}, and ∀kj ∈ K,Zj = {{0, . . . , n}};
• In TCFG at , ∀ai ∈ A,Xi = {|Ti|}, ∀ai ∈ A, ∀kj ∈ K, Yij = {0, . . . , |Ti|}, and ∀kj ∈ K,Zj = {0, . . . ,m}.

Next, we discuss expressiveness.

Proposition 1 Every coalitional game that can be modelled as a TCFG, TCFG o , TCFG rco and/or TCFG at , can also be represented as a CF-NET.

3 Throughout the paper this is assumed that gj(0) = 0.

Proof : We demonstrate that, for any arbitrary coalitional game under consideration, there exists a CF-NET representation that uniquely defines this game. Specifically:

1. TCFG: Our aim is to construct CF-NET representing an arbitrary game 〈A,K, v〉. First, we create a one-to-one function I : 2A ×K → {1, . . . , 2n × q}. Now, for every coalition C ∈ 2A and task kj ∈ K, we create a hypothetical task wI(C,kj) which is connected to all the agents in C and none of the agents in A\C. Furthermore, for every ai ∈ C, we set Xi = {1}, Yi,I(C,kj) = {0, 1}, and di,I(C,kj) = 0. We also set ZI(C,kj) = {0, |C|}, and set gI(C,kj) (|C|) = v(C, kj) and gI(C,kj) (0) = 0.
2. TCFG o /TCFG rco : This case is similar to the previous one. The difference is only in the definition of Xi, which is now given by Xi = {1, . . . , 2n-1} in the case of TCFG o , or by Xi = {1, . . . , r(ai)} in the case of TCFG rco .
3. TCFG at : Here, agent nodes depict available types of agents. That is, every node ni ∈ N a represents a type ti. This case is similar to TCFG case, except that we now set Xi = {|Ti|} and Yi,I(C,kj ) = {0, |C ∩ Ti|}.

✷

The constructs in the proof of Proposition 1 imply that CF-NETs are no less concise than the corresponding TCFG, TCFG o /TCFG rco and TCFG at representations. Indeed, the edges do not need to be explicitly represented; for every hypothetical task wx it is possible to identify to it simply by using the inverse of function I (which in turn can be concisely represented).

Observe that, for certain patterns often encountered in coalitional games, CF-NETs provide much more concise representations. For instance, suppose there exist additional requirements for coalitions to be formed, such as certain agents being incompatible with each other, or constraints on the coalition sizes. In these cases, one can simply exclude "infeasible" coalitions from the set of coalition nodes. This only decreases the size of the representation, which for certain game classes makes CF-NETs exponentially more concise than the corresponding characteristic function representations.

Next we prove our main technical result, demonstrating the computational power of the CF-NET representation in the coalition structure generation problem.

4 Coalition Structure Generation in CF-NETs

In this section, we formally define the coalition structure generation (CSG) problem and propose an approximation method for solving it on CF-NETs. Our technique utilizes the advantages of the CF-NET representation to produce anytime solutions and estimate their quality.

The CSG Problem

First, we make explicit the notion of a coalition structure for each of the classes TCFG, TCFG o , TCFG rco and TCFG at .

1. TCFG: A coalition structure, π, is a partition of the agents:

1. TCFG o : Similar to TCFG, except that coalitions can now overlap. A coalition structure, πo , is defined as:

1. TCFG rco : In this case, each agent ai ∈ A can belong to at most r(ai) coalitions simultaneously:

1. TCFG at : Coalitions are multi-sets of types, rather than sets of agents as in previous cases. Let my(x) denote the multiplicity of element x in multi-set y; then:

Let Πx denote the sets of all possible coalition structures in TCFGx , where index x is either empty or stands for "o", "rco" or "at". The CSG problem in TCFG x is to find an optimal coalition structure, πxOPT , that maximizes the sum of coalition values:

where vx = vat if TCFG at , and vi = v, otherwise.

Solving the CSG Problem in CF-NETs

We now formalize the CSG problem in terms of CF-NETs. Here, since the value of a coalition performing a task is defined by (2), the value of a coalition structure is:

For ease of exposition, we focus next on the nonoverlapping model. However, we emphasize the fact that our method can be easily extended to games with overlapping coalitions or with agent types (by defining Xi, Yij and Zj accordingly).

For all i, j, we have Xi = {1}, Yij = {0, 1} and Zj = {0, . . . , n}. The coalition structure generation problem can then be formulated as a mathematical program:

Note that if the synergy functions gj are linear, the problem is equivalent to the classical maximum network flow problem and can be solved efficiently [Cormen et al., 2001]. However, for non-linear synergies, CSG becomes a non-linear integer programming problem, which is generally NP-hard [Sandholm et al., 1999]. In this paper, we solve/approximate CSG for general synergy functions.

First, observe that our problem is related to the productiontransportation problem from Operations Research [Tuy et al., 1996; Holmberg and Tuy, 1999], which also has a network flow interpretation. Here, the non-linear terms gj(zj) can be viewed as the production part that the decision makers have to decide upon. Once the production z has been fixed, the problem becomes a standard transportation problem - of finding (x, y) - and can be solved efficiently. However, solving for optimal (x, y) and z simultaneously is nontrivial [Hochbaum and Hong, 1996].

Therefore, in this work we develop an approximation technique for CSG. Our method has two advantages: it gives an anytime algorithm and it provides upper and lower bounds on the optimal value; as a result, one can quantify how far the solution provided is from the optimal solution. Specifically, we use constraint relaxation and duality to modify the mathematical program as follows.

Relax the constraint (3) zi = ∑ni=1 yij in CSG and consider the corresponding dual problem:

Now, for each fixed λ, consider the inner problem:

By replacing every xi with ∑qj=1 yij and noticing that h(λ)) is now separable in y and z, we can show that h(λ) = ∑ni=1 h1i(λ) + ∑qj=1 h2j (λj ), where:

Finally, by simplifying h1i(λ) to h1i(λ) = max{0,maxj(dij + λj)}, we get a one variable integer programming problem, which can be easily solved.

Thus, for each fixed λ, we can compute h(λ) very efficiently. Notice that minλ h(λ) provides an upper bound on CSG (duality theory) and hence any choice of λ gives an upper bound (but we are interested in the smallest one, minλ h(λ)). Notice also that h(λ) is a piece-wise linear function on λ with possible jumps. We then can solve the problem minλ h(λ) using a sub-gradient based method for updating λ, i.e., we reduce λj if (zj - ∑ni=1 yij) < 0 and increase λj otherwise. Although we might not be able to solve minλ h(λ) to optimality, a sub-optimal solution still provides us with an upper bound on CSG.

Finally, lower bounds are obtained. First, for each λ, the inner problem can be solved to find its optimal solution on (x, y, z). This solution is a feasible solution to CSG and hence its objective value provides a lower bound. Another method for producing a lower bound is to fix the optimal z found in the inner problem and then solve the transportation problem to find the corresponding optimal (x, y). This will give another feasible solution and hence, a new lower bound. 4

5 Performance Evaluation

We perform numerical tests on the algorithm for various settings with the number of agents n varying between 100 and 5000 and the number of tasks q varying between 50 and 200. For each combination of (n, q), we generate 100 random samples using random seeds between 1 and 100. In total, we have tested the algorithm with 2000 random instances. On each instance, the parameters c and d are generated uniformly, i.e., dij ∼ U[0, 1]. The synergy function gj(zj) is also a random discrete function of the following form:

where ϵji ∼ U[0, 1] are uniform random variables. This means the synergy function gj is the sum of uniform random variables and the coalition value increase by ϵjs when the coalition size increases from s - 1 to s. By creating 100 random instances, we can test the robustness of the algorithm when input data varies 5 .

Figure 2 shows the performance of the algorithm when the number of agents varies between 100 and 5000, while the number of tasks is fixed at 100. Sub-figure (A) shows the total computational time, sub-figure (B) shows the number of iteration, while sub-figure (C) shows the optimality bound between the feasible coalition structure found and the worst upper bound. We can see a linear trend in the computational time from sub-figure (A) with less than three minutes 6 to solve the largest and the worst instance (among 600 random instances for this case). The linear trend in the computational time can be explained by the fact that the number of arithmetic operations in each iteration grows linearly, while the number of iterations (shown in sub-figure (B)) does not change much.

4 With the obtained bounds, it is possible to extend the algorithm in the future by incorporating branch-and-bound techniques to improve solution quality.

5 For each pair of (n, q), we will present box plots that show the statistics among 100 random instances generated with the middle red horizontal lines showing the medians, the boxes showing the 25 and 75 percentiles, and the red crosses showing the outliers.

6 All the numerical tests appear in this manuscript are performed on a personal computer, Intel® Xeon® CPU W3520 @2.67GHz with 12GB RAM and under Windows 7 operation system. The code was written and tested on Matlab R2012a.

Sub-figure (C) shows the guaranteed bound between the feasible coalition structure found and the optimality. Notice that these bounds are guaranteed despite the fact that we don't know the optimal coalition structures thanks to the availability of the upper bounds derived by the algorithm. This also means that the actual optimality bounds could be higher than the average optimality bounds between 75-81% that appear in sub-figure (C).

Figure 3 shows the performance of the algorithm when the number of agents varies is fixed at n = 2000, while the number of tasks varies between 50 and 200. We can see a very similar linear trend in the computational time in sub-figure (A) and the optimality bounds between 75-81% in sub-figure (C). The total computational time for the largest instance is less than 35 seconds.

Figures 4, 5 show the same set of statistics as in Figures 2, 3 except that the CFG rco games now allow each players to join up to 5 coalitions. The guaranteed optimality bounds vary between 76-85% on these instances. We can also see a linear trend in the computational time as the number of players and the number of tasks increase and the algorithm takes less than 90 seconds for the worst instance.

6 Conclusions

We introduced CF-NETs, a representation scheme for coalitional games in task-based settings, which is inspired by network flows. We examined its qualities with respect to conventional coalitional games with non-overlapping coalitions, (resource-constrained) overlapping coalitional games, and coalitional games with agent types. We utilized the advantages of this representation to develop an approximation technique for coalition structure generation, which applies to all these game classes and allows to effectively solve large instances of the problem.

Our work can be extended in several ways. It would be interesting to extend the CF-NET framework with components that would allow to capture game patterns other than those considered in this paper. Furthermore, we are keen on testing the properties of the CF-NET representation with respect to computing different solution concepts such as the Shapley value and the core.

Acknowledgements

We would like to thank the anonymous IJCAI reviewers for valuable feedback. Tomasz Michalak was supported by the European Research Council under Advanced Grant 291528 ("RACE"). Talal Rahwan and Nicholas R. Jennings were supported by the ORCHID Project, funded by EPSRC (Engineering and Physical Research Council) under the grant EP/I011587/1.