Coalition Structure Generation with the Graphic Processor Unit

Abstract

Coalition Structure Generation—the problem of finding the optimal set of coalitions— has received considerable attention in recent AI literature. The fastest exact algorithm to solve this problem is IDP-IP, due to Rahwan et al. (2012). This algorithm is a hybrid of two previous algorithms, namely IDP and IP. As such, it is desirable to speed up IDP as this will, in turn, improve upon the state-of-the-art. In this paper, we present IDPG—the first coalition structure generation algorithm based on the Graphics Processing Unit (GPU). This follows a promising, new algorithm design paradigm that can provide significant speed ups. We show that IDPG is faster than IDP by two orders of magnitude.