Abstract

Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining the best set of agents that should participate in a given team. To this end, in this paper, we present a novel, anytime algorithm for coalition structure generation that is faster than previous anytime algorithms designed for this purpose. Our algorithm can generate solutions that either have a tight bound from the optimal or are optimal (depending on the objective) and works by partitioning the space in terms of a small set of elements that represent structures which contain coalitions of the same size. It then performs an online heuristic search that prunes the space and only considers valid and non-redundant coalition structures. We empirically show that we are able to find solutions that are, in the worst case, 99% efficient in 0.0129% of the time to find the optimal value by the state of the art dynamic programming algorithm (for 20 agents).

Introduction

Coalition formation (CF) is the coming together of distinct, autonomous agents in order to act as a coherent grouping. It has long been studied in cooperative game theory [ 3 ] and has recently become an important topic in multi-agent systems where a team of agents often need to maximise their individual or their collective efficiency. For example, agents often have to form efficient groups to buy goods in bulk or sensors have to decide on how to group together to monitor a given area [ 1 ]. Given a set of agents 1, 2, .., i, .., a ∈ A, the CF process involves three computationally challenging stages: 1. Coalition value calculation: for each subset or coalition C ⊆ A, find the value of each coalition (commonly called the characteristic function) v(C) = Pi∈C vi(C) where vi(C) ∈ < is the value an agent i derives from the coalition. Note here that this requires processing 2a possible coalitions. 2. Coalition structure generation: is the equivent of the complete set partitioning problem [ 6 ].

This means computing the optimal set of coalitions CS∗ = arg maxCS∈CS V (CS), where a coalition structure CS ∈ CS is a partition of A into disjoint exhaustive coalitions, CS is the set of all such partitions (i.e. each agent belongs to exactly one coalition), and V (CS) = PC∈CS v(C). The search space here is O(aa) and ω(a a2 ). 3. Payment calculation: compute the transfers between the agents such that they are incentivised to stay in the coalition to which they are assigned. These payments will depend on the stability concept used (e.g. Bargaining set, Kernel, or the Core) and finding these is usually NP-Complete.

In this paper, we focus on the coalition structure generation problem. Up to now, the most widely used algorithm to solve this problem is due to [ 6, 4 ]. Their algorithm (which runs in Θ(3a)) is guaranteed to find the optimal solution and is based on dynamic programming (DP). However, the DP approach becomes impractical for agents with limited computational power (e.g. computing the optimal CS for 20 agents requires around 3.4 × 109 operations). Moreover, in the dynamic environments that we consider, agents do not typically have sufficient time to perform such calculations and, in many cases, an approach that gives a good approximation, in a reasonable time, is more valuable.

Against this background, this paper describes a novel anytime search algorithm that uses heuristics to to generate the optimal or near-optimal (with a very tight bound) coalition structure. In more detail, the algorithm works by grouping the coalition structures according to the sizes of coalitions they contain (which we here term a configuration). For example, coalition structures {{1}, {2, 3}} and {{3}, {1, 2}} both follow the configuration {1, 2}. Hence, the space of all coalition structures is partitioned into smaller subsets where every element of a given subset have the same configuration. This is different from previous representations used by other anytime algorithms which looked at the space of interconnected coalition structures [ 5, 2 ] (which necessitates searching a much bigger portion of the space than our method to get a good solution). Now, using the list of configurations of coalition structures and by estimating the average and upper bound of the solutions that exist within each configuration in this list, we are able to zoom in on the optimal configuration after searching a relatively minute portion of the search space (typically 3 × 2a−1 coalition structures). Moreover, by refining the upper bound of every other configuration after searching the coalition structures of one configuration, we are able to reduce the time to find the optimal configuration still further by discarding those configurations that have a lower upper bound than the best value found so far.

This paper advances the state of the art in the following ways. First, we provide an anytime algorithm to compute the optimal coalition structure that is faster than any previous (anytime) algorithm designed for this purpose. Second, we provide a novel representation for the search space based on coalition structure configurations. This approach permits the selection of a solution based either on the selection of coalition structures of particular configurations or on the time available to find the solution. Third, our algorithm can provide worst case guarantees on the quality of any computed solution since it can estimate an upper bound for the optimal solution. Finally, our algorithm is empirically shown to give solutions which are, at worst, 99% of the optimal value in 0.0129% of the time (in seconds) it takes the DP approach to find the optimal value (for 20 agents).

Acknowledgements

This research was undertaken as part of the ALADDIN (Autonomous Learning Agents for Decentralised Data and Information Systems) project and is jointly funded by a BAE Systems and EPSRC (Engineering and Physical Research Council) strategic partnership.

References

References

[1] V. D. Dang , R. K. Dash , A. Rogers , and N. R. Jennings . Overlapping coalition formation for efficient data fusion in multi-sensor networks . In 21st National Conference on AI (AAAI , pages 635 - 640 , 2006 .

[2] V. D. Dang and N. R. Jennings . Generating coalition structures with finite bound from the optimal guarantees . In AAMAS , pages 564 - 571 , 2004 .

[3] M. J. Osborne and A. Rubinstein . A Course in Game Theory . MIT Press, Cambridge MA, USA, 1994 .

[4] M. H. Rothkopf , A. Pekec , and R. M. Harstad . Computationally manageable combinatorial auctions . Management Science , 1998 .

[5] T. Sandholm , K. Larson , M. Andersson , O. Shehory , and F. Tohm ´e. Coalition structure generation with worst case guarantees . Artif. Intelligence , 111 ( 1-2 ): 209 - 238 , 1999 .

[6] D. Yun Yeh . A dynamic programming approach to the complete set partitioning problem . BIT , 26 ( 4 ): 467 - 474 , 1986 .