Minimum Search to Establish Worst-Case Guarantees in Coalition Structure Generation

Rahwan, Talal; Michalak, Tomasz P.; Jennings, Nicholas R.

doi:10.5591/978-1-57735-516-8/IJCAI11-066

Minimum Search to Establish Worst-Case Guarantees in Coalition Structure Generation

Talal Rahwan, Tomasz P. Michalak, Nicholas R. Jennings

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 338-342.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-066

Abstract

Coalition formation is a fundamental research topic in multi-agent systems. In this context, while it is desirable to generate a coalition structure that maximizes the sum of the values of the coalitions, the space of possible solutions is often too large to allow exhaustive search. Thus, a fundamental open question in this area is the following: Can we search through only a subset of coalition structures, and be guaranteed to find a solution that is within a desirable bound beta from optimum? If so, what is the minimum such subset? To date, the above question has only been partially answered by Sandholm et al. in their seminal work on anytime coalition structure generation Sandholm et al. (AIJ 1999). More specifically, they identified minimum subsets to be searched for two particular bounds: β = n and β = [n/2]. Nevertheless, the question remained open for other values of β. In this paper, we provide the complete answer to this question.

Talal Rahwan, Tomasz P. Michalak, and Nicholas R. Jennings. 2011. Minimum Search to Establish Worst-Case Guarantees in Coalition Structure Generation. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 338–342. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-066

@inproceedings{ijcai2011p66,
  title     = {Minimum Search to Establish Worst-Case Guarantees in Coalition Structure Generation},
  author    = {Rahwan, Talal and Michalak, Tomasz P. and Jennings, Nicholas R.},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {338--342},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-066},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-066},
}

TY  - CPAPER
TI  - Minimum Search to Establish Worst-Case Guarantees in Coalition Structure Generation
AU  - Rahwan, Talal
AU  - Michalak, Tomasz P.
AU  - Jennings, Nicholas R.
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 338
EP  - 342
DO  - 10.5591/978-1-57735-516-8/IJCAI11-066
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-066
ER  -