Output details

Anytime coalition structure generation in multi-agent systems with positive or negative externalities

Significance of output:

<22>This is the first coalition structure generation algorithm for the broadly applicable class of games with externalities. The problem of forming coalitions of agents becomes much more realistic and challenging when considering the possibility of having coexisting coalitions influencing each other. Our algorithm, the first for such settings, is currently being used as the basis for a key demonstrator in the ORCHID programme grant in the domain of the smart grid. Results are a mixture of analytical and empirical; the worst-case bound of the algorithm is proved analytically and an average case analysis is performed empirically.