Worst-Case-Optimal Anytime Coalition Structure Generation Export

@inproceedings{sandholm98a, abstract = {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 exhaustive search for the optimal one. But then, can the coalition structure found via a partial search be guaranteed to be within a bound from optimum? 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.}, address = {Menlo Park, CA}, author = {Sandholm, Tuomas and Larson, Kate and Andersson, Martin and Shehory, Onn and Tohm\'{e}, F.}, booktitle = {Proceedings of {AAAI-98}}, citeulike-article-id = {1585563}, citeulike-linkout-0 = {http://jmvidal.cse.sc.edu/library/sandholm98a.pdf}, keywords = {bibtex-import, coalitions, multiagent}, month = {July}, pages = {43--56}, posted-at = {2007-08-23 14:42:21}, priority = {2}, publisher = {{AAAI} Press}, title = {Worst-Case-Optimal Anytime Coalition Structure Generation}, url = {http://jmvidal.cse.sc.edu/library/sandholm98a.pdf}, year = {1998} }

TY - CONF ID - sandholm98a L3 - citeulike-article-id:1585563 N2 - 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 exhaustive search for the optimal one. But then, can the coalition structure found via a partial search be guaranteed to be within a bound from optimum? 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. AD - Menlo Park, CA EP - 56 TI - Worst-Case-Optimal Anytime Coalition Structure Generation PB - {AAAI} Press T2 - Proceedings of {AAAI-98} SP - 43 KW - bibtex-import KW - coalitions KW - multiagent AU - Sandholm, Tuomas AU - Larson, Kate AU - Andersson, Martin AU - Shehory, Onn AU - Tohm\'{e}, F PY - 1998/July// UR - http://jmvidal.cse.sc.edu/library/sandholm98a.pdf ER -