Near-Optimal Anytime Coalition Structure Generation
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 articipate 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 particular sizes. 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.0043% of the time to find the optimal value by the state of the art dynamic programming (DP) algorithm (for 20 agents), using 33% less memory. URL: http://www.ecs.soton.ac.uk/~sdr/mypubs/accepted/anytimeCoalition.pdf
Cite
Text
Rahwan et al. "Near-Optimal Anytime Coalition Structure Generation." International Joint Conference on Artificial Intelligence, 2007.Markdown
[Rahwan et al. "Near-Optimal Anytime Coalition Structure Generation." International Joint Conference on Artificial Intelligence, 2007.](https://mlanthology.org/ijcai/2007/rahwan2007ijcai-near/)BibTeX
@inproceedings{rahwan2007ijcai-near,
title = {{Near-Optimal Anytime Coalition Structure Generation}},
author = {Rahwan, Talal and Ramchurn, Sarvapali D. and Dang, Viet Dung and Jennings, Nicholas R.},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2007},
pages = {2365-2371},
url = {https://mlanthology.org/ijcai/2007/rahwan2007ijcai-near/}
}