Anytime coalition structure generation: an average case study
Coalition formation is a key topic in multiagent systems. One would prefer a coalition structure that maximizes the sum of the values of the coalitions, but often the number of coalition structures is too large to allow for exhaustive search for the optimal one. We present experimental results for three anytime algorithms that search the space of coalition structures. We show that, in the average case, all three algorithms do much better than the recently established theoretical worst case results in Sandholm et al. (1999a). We also show that no one algorithm is dominant. Each algorithm's performance is influenced by the particular instance distribution, with each algorithm outperforming the others for different instances. We present a possible explanation for the behaviour of the algorithms and support our hypothesis with data collected from a controlled experimental run.
No Reference information available - sign in for access.
No Citation information available - sign in for access.
No Supplementary Data.
No Article Media
Document Type: Research Article
Publication date: January 1, 2000