Indexed by:
Abstract:
Coalition formation is a key topic in multi-agent systems. One may 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. Furthermore, finding the optimal coalition structure is NP-hard and even finding a sub-optimal solution requires searching an exponential number of solutions. But then, can the coalition structure found via a partial search be guaranteed to be within a bound from optimum? Sandholm et al. show that it suffices to search the lowest two levels of the coalition structure graph in order to establish a worst-case bound Kin). Dang et al. present an algorithm which is obviously faster than that of Sandholm et al, which is the best result known so far. Against this background, the relations among coalition structures are analyzed in depth and a novel anytime algorithm based on cardinality structure is presented, which only has to take a step further and search those coalition structures whose cardinality structure is in the CCS (n, b). Consequently, the algorithms reported are obviously better than that of Sandholm et al. (up to 1035 times faster when n=100, K=2) and Dang et al. (up to 1018 times faster when n=l00, K=3).
Keyword:
Reprint 's Address:
Email:
Version:
Source :
Computer Research and Development
ISSN: 1000-1239
CN: 11-1777/TP
Year: 2008
Issue: 10
Volume: 45
Page: 1756-1762
Cited Count:
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 1
Affiliated Colleges: