|
|
|
|
RI | Publications | Worst-Case-Optimal Anytime Coalition Structure Generation
|
|
Text only version of this site
Worst-Case-Optimal Anytime Coalition Structure Generation
T. Sandholm, K. Larson, M. Andersson, O. Shehory, and F. Tohme
In Proceedings of AAAI-98, July, 1998, pp. 46-53.
Jump to: Download | Abstract | Text Reference | BibTeX Reference
| Download [Help] |
Adobe portable document format (pdf) [205 KB] Compressed postscript (ps.gz) [63 KB]
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
| Abstract |
Coalition formation is one of the key problems 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 exhaustive search for the optimal one. This paper focuses on nding a worst case bound on how good the optimal coalition structure is compared to the best coalition structure that a nonexhaustive search finds.
We show that none of the previous coalition structure generation algorithms can establish any bound because they search fewer nodes than a threshold that we show necessary for establishing a bound. We present an algorithm that establishes a tight bound within this minimal amount of search, and show that any other algorithm would have to search strictly more. The fraction of nodes needed to be searched approaches zero as the number of agents grows.
If additional time remains, our anytime algorithm searches further, and establishes a progressively lower tight bound. Surprisingly, just searching one more node drops the bound in half. As desired, our algorithm lowers the bound rapidly early on, and exhibits diminishing returns to computation. It also drastically outperforms its obvious contenders. Finally, we show how to distribute the desired search across self-interested manipulative agents.
| Text Reference |
T. Sandholm, K. Larson, M. Andersson, O. Shehory, and F. Tohme, "Worst-Case-Optimal Anytime Coalition Structure Generation," In Proceedings of AAAI-98, July, 1998, pp. 46-53.
| BibTeX Reference |
@inproceedings{Sandholm_1998_2565,
author = "T. Sandholm and K. Larson and M. Andersson and Onn Shehory and F. Tohme",
title = "Worst-Case-Optimal Anytime Coalition Structure Generation",
booktitle = "In Proceedings of AAAI-98",
month = "July",
year = "1998",
pages = "46-53"
}