TY - JOUR
T1 - Near-optimal anytime coalition structure generation
AU - Rahwan, Talal
AU - Ramchurn, Sarvapali D.
AU - Dang, Viet Dung
AU - Jennings, Nicholas R.
PY - 2006
Y1 - 2006
N2 - 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 participate 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 the same size. 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.0129% of the time to find the optimal value by the state of the art dynamic programming algorithm (for 20 agents).
AB - 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 participate 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 the same size. 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.0129% of the time to find the optimal value by the state of the art dynamic programming algorithm (for 20 agents).
UR - http://www.scopus.com/inward/record.url?scp=84884759554&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84884759554&partnerID=8YFLogxK
M3 - Conference article
AN - SCOPUS:84884759554
SN - 1613-0073
VL - 223
JO - CEUR Workshop Proceedings
JF - CEUR Workshop Proceedings
T2 - 4th European Workshop on Multi-Agent Systems, EUMAS 2006
Y2 - 14 December 2006 through 15 December 2006
ER -