Adaptive Coalition Structure Generation in Cooperative Multiagent Systems

In multiagent systems a coalition structure is a collection of pair-wise disjoint subsets of agents whose union yields the entire population. Given a characteristic function quantifying the worth of agent subsets, searching for optimal coalition structures (i.e. where the sum of subsets’ worth is maximal) is a well-known NP-hard combinatorial optimization problem. While existing algorithms (either deterministic or stochastic) deal with time-invariant goal functions, the focus here is on dynamic settings, where the worth of agent subsets possibly varies over time in an unknown and unpredictable fashion. The aim is to design an adaptive dynamic process generating coalition structures with high worth most of the times. To this end, detecting variations in the worth of agent subsets becomes crucial. The proposed method takes into account such (possible) changes by intensifying the exploration activity whenever they are detected. The performance with respect to the worth of optimal coalition structures is evaluated through simulations.