TY - JOUR

T1 - Coalition structure generation based on distributed constraint optimization

AU - Ueda, Suguru

AU - Iwasaki, Atsushi

AU - Yokoo, Makoto

AU - Silaghi, Marius C.

AU - Hirayama, Katsutoshi

AU - Matsui, Toshihiro

N1 - Copyright:
Copyright 2011 Elsevier B.V., All rights reserved.

PY - 2011

Y1 - 2011

N2 - Forming effective coalitions is a major research challenge in AI and multi-agent systems. Coalition Structure Generation (CSG) involves partitioning a set of agents into coalitions so that social surplus (the sum of the rewards of all coalitions) is maximized. A partition is called a coalition structure (CS). In traditional works, the value of a coalition is given by a black box function called a characteristic function. In this paper, we propose a novel formalization of CSG, i.e., we assume that the value of a characteristic function is given by an optimal solution of a distributed constraint optimization problem (DCOP) among the agents of a coalition. A DCOP is a popular approach for modeling cooperative agents, since it is quite general and can formalize various application problems in MAS. At first glance, this approach sounds like a very bad idea considering the computational costs, since we need to solve an NP-hard problem just to obtain the value of a single coalition. To optimally solve a CSG, we might need to solve O(2n) DCOP problem instances, where n is the number of agents. However, quite surprisingly, we show that an approximation algorithm, whose computational cost is about the same as solving just one DCOP, can find a CS whose social surplus is at least max(1/[n/2], 1/(w* + 1)) of the optimal CS, where w* is the tree width of a constraint graph. Furthermore, we can generalize this approximation algorithm with a parameter k, i.e., the generalized algorithm can find a CS whose social surplus is at least max(k/[n/2], k/(w* + 1)) of the optimal CS by exploring more search space. These results illustrate that the locality of interactions among agents, which is explicitly modeled in the DCOP formalization, is quite useful in developing efficient CSG algorithms with quality guarantees.

AB - Forming effective coalitions is a major research challenge in AI and multi-agent systems. Coalition Structure Generation (CSG) involves partitioning a set of agents into coalitions so that social surplus (the sum of the rewards of all coalitions) is maximized. A partition is called a coalition structure (CS). In traditional works, the value of a coalition is given by a black box function called a characteristic function. In this paper, we propose a novel formalization of CSG, i.e., we assume that the value of a characteristic function is given by an optimal solution of a distributed constraint optimization problem (DCOP) among the agents of a coalition. A DCOP is a popular approach for modeling cooperative agents, since it is quite general and can formalize various application problems in MAS. At first glance, this approach sounds like a very bad idea considering the computational costs, since we need to solve an NP-hard problem just to obtain the value of a single coalition. To optimally solve a CSG, we might need to solve O(2n) DCOP problem instances, where n is the number of agents. However, quite surprisingly, we show that an approximation algorithm, whose computational cost is about the same as solving just one DCOP, can find a CS whose social surplus is at least max(1/[n/2], 1/(w* + 1)) of the optimal CS, where w* is the tree width of a constraint graph. Furthermore, we can generalize this approximation algorithm with a parameter k, i.e., the generalized algorithm can find a CS whose social surplus is at least max(k/[n/2], k/(w* + 1)) of the optimal CS by exploring more search space. These results illustrate that the locality of interactions among agents, which is explicitly modeled in the DCOP formalization, is quite useful in developing efficient CSG algorithms with quality guarantees.

UR - http://www.scopus.com/inward/record.url?scp=78650994001&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78650994001&partnerID=8YFLogxK

U2 - 10.1527/tjsai.26.179

DO - 10.1527/tjsai.26.179

M3 - Article

AN - SCOPUS:78650994001

SN - 1346-0714

VL - 26

SP - 179

EP - 189

JO - Transactions of the Japanese Society for Artificial Intelligence

JF - Transactions of the Japanese Society for Artificial Intelligence

IS - 1

ER -