A best-first anytime algorithm for computing optimal coalition structures

This work presents a best-first anytime algorithm for computing optimal coalition structures. The approach is novel in that it generates coalition structures based on coalition values, while existing algorithms base their generation on the structure (members and configurations) of coalitions. With our algorithm, coalition structures are generated by repeatedly choosing the best coalition, as determined using a novel metric called agent's contribution to coalition structure that we define. We have compared the performance of our algorithm against that of Rahwan et al [5] using 20 data distributions. Our results show that our algorithm almost always converges on an optimal coalition structure faster (although it terminates later in some cases). Empirically, our algorithm almost always yields better than or as good as Rahwan et al's results at any point in time. Copyright 2008, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.