An Exact Algorithm for Coalition Structure Generation and Complete Set Partitioning

Abstract

Solving the Coalition Structure Generation problem is a major challenge in cooperative game theory. It involves partitioning the set of agents into subsets (or coalitions) such that the total reward is maximized. We study this problem in Characteristic Function Games, i.e., scenarios where every possible subset of agents is a potential coalition, and the outcome (or value) of every such subset is represented as a single, numerical value on which non-members have no in uence. In this setting, the coalition structure generation problem becomes identical to the Complete Set Partitioning problem, where every subset of elements has a cost, and the goal is to nd a partition in which the sum of subset costs is minimal. This is also identical to the Winner Determination problem in combinatorial auctions when a bid is placed on every possible bundle of goods, and the goal is to nd a partition that maximizes the pro t of the auctioneer. To date, there are two state-of-the-art, exact algorithms for solving this problem: (1) a dynamicprogramming algorithm called DP (Yeh, 1986; Rothkopf et al., 1995) and (2) a tree-search algorithm called IP (Rahwan et al., 2009). Each of these two algorithms has it relative strengths and weaknesses compared to the other. More speci cally, in terms of worst-case performance, DP is signi cantly better as it runs in O(3n) time (given n elements), while IP runs in O(nn) time. However, when tested against popular value distributions, IP was shown to be often faster than DP (by several orders of magnitude in some cases). Furthermore, IP has the advantage of being anytime, meaning that its solution quality improves gradually over time, allowing it to return a valid solution at any moment during its execution. DP, on the other hand, is not an anytime algorithm; it can only return a solution once it has completed its execution. The contribution of this article is twofold. Firstly, we show that some of DP's operations and memory requirements are redundant. Building upon this, we develop ODP|an optimal version of DP that avoids all redundancies. Secondly, we develop a hybrid algorithm, called ODP-IP, that has the best features of its constituent parts, ODP and IP. Speci cally, it is an anytime algorithm just like IP, and runs in O(3n) just like ODP. Better still, when tested against a wide variety of value distributions, ODP-IP is empirically shown to signi cantly outperform both ODP and IP for all distributions.