最坏情况具有限界的联盟结构生成

Coalition Structure Generation with Worst-Case Finite Bound from the Optimal Guarantees

联盟形成是多Agent系统中的一个关键问题.寻求能极大化联盟值总和的最优联盟结构是NP-完全的.Sandholm等人已经证明要建立最坏情况下的限界k,搜索联盟结构图的最底两层是必要且是充分的,在搜索联盟结构图的最底两层之后如何进一步搜索,是个长期以来未能解决的问题.Dang等人给出的算法,对于奇数限界k≥3,在搜索最底两层及顶层后,进一步搜索最大联盟的势不小于n(k-1)/(k+1)的所有联盟结构,是迄今所知的第1个不以层为搜索单位的算法,对于较小的限界明显地优于Sandholm等人给出的算法.文中深刻分析了联盟结构间的关系,提出的算法在搜索最底两层后,只需进一步搜索最大联盟的势等于n(k-1)/(k+1)的所有联盟结构,从而使需要搜索的联盟结构数大大减少,并进一步将搜索某些层最大联盟的势等于n(k-1)/(k+1)的联盟结构巧妙地改为搜索联盟结构数更少的相应层,使需要搜索的联盟结构数进一步减少,较大地改进了Sandholm等人和Dang等人的工作.

Coalition formation is a key topic in multi-agent systems. However, finding the optimal coalition structure is NP-complete. Sandhoim et al. show that it is necessary and sufficientto 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 the lowest two levels of the coalition structure graph is a problem which hasn＇t been resolved for a long time. Dang et al. have presented an algorithm： for the odd bound k≥3, those coalition structures are further searched whose biggest coalition＇s cardinality is not less than [ n（k- 1）/（k＋1）], which is the first algorithm known whose searching unit is not level and it is obviously faster than that of Sandholm et al for the smaller bound. The authors analyze the relations among coalition structures deeply and present an algorithm that only needs to search those coalition structures whose biggest coalition＇s cardinality is equal to [ n（k- 1）/（k＋1）] to decrease largely the number of coalition structures needed to be searched. Moreover, the algorithm is improved to search skillfully those corresponding levels whose coalition structures are fewer than some of those coalition structures whose biggest coalition＇s cardinality is equal to [ n（k- 1）/（k＋1）], therefore decreasing further the number of coalition structures needed to be searched and improving largely the work of Sandholm et al. and Dang et al.