Coalition structure generation algorithm based on cardinality structure with given required bound
Shan-Li Hu · Jisuanji yingyong yanjiu · 2009
Coalition structure generation is a key topic in multi-agent system.Sandholm et al.proved that it was necessary and sufficient to search the lowest two levels of the coalition structure graph in order to establish a worst-case bound k.How to do a further search after? That is a problem which hasn't been resoled for a long time.When practical applications could present required real bound in the worst case,how to attain this bound via partial search? HU Shan-li and SHI Chun-yi gave an optimal searching algorithm whose searching unit was level.Dang et al.and SU She-xiong et al.gave their coalition structure generation algorithms whose searching unit was cardinality structure.New algorithm MCCS proposed that searching all coalition structures corresponding to the set of cardinality structure MCCS(n,k) could attain the given required bound k with more less cardinality structures after searching the lowest two levels and the top level in the coalition structure graph.Finally,comparing to the existing algorithms,it obviously searches less cardinality structures and has some theoretical and practical meaning.