中文摘要：

联盟形成是多Agent系统中的一个关键问题．人们寻求能极大化联盟值总和的联盟结构，但通常情况下可能的联盟结构的数目太大，以致不允许进行穷尽搜索而找出最优解．Sandholm等人已经证明，要建立最坏情况下的限界K（n），搜索联盟结构图的最底两层是必要且是充分的．Dang等人给出的算法是所见到的第1个不以层为单位的搜索算法，对于较小的限界明显地优于Sandholm等人给出的算法．深刻分析了联盟结构间的关系，采用更小的搜索粒度（势结构），提出基于势结构的任一时间算法，在搜索最底两层及顶层后，进一步搜索势结构集合CCS（n，b）对应的未搜索过的联盟结构，渐进地给出越来越低的限界，大大改进了Sandholm等人（快10^35倍，当n=100，K=2）和Dang等人（快10^18倍，当n=100，K=3）的工作．

英文摘要：

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 K（n）. 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 10^35 times faster when n=100, K=2） and Dang etal. （ up to 10^18 times faster when n=100, K=3）.