TY - GEN
T1 - Minimum search to establish worst-case guarantees in coalition structure generation
AU - Rahwan, Talal
AU - Michalak, Tomasz
AU - Jennings, Nicholas R.
PY - 2011
Y1 - 2011
N2 - 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 β 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., 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.
AB - 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 β 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., 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.
UR - http://www.scopus.com/inward/record.url?scp=84868268213&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84868268213&partnerID=8YFLogxK
U2 - 10.5591/978-1-57735-516-8/IJCAI11-066
DO - 10.5591/978-1-57735-516-8/IJCAI11-066
M3 - Conference contribution
AN - SCOPUS:84868268213
SN - 9781577355120
T3 - IJCAI International Joint Conference on Artificial Intelligence
SP - 338
EP - 342
BT - IJCAI 2011 - 22nd International Joint Conference on Artificial Intelligence
T2 - 22nd International Joint Conference on Artificial Intelligence, IJCAI 2011
Y2 - 16 July 2011 through 22 July 2011
ER -