Multi-agent Simulation Framework for Large-Scale Coalition Formation

Coalition formation, a key factor in multi-agent cooperation, can be solved optimally for at most a few dozen agents. This paper proposes a general approach to find suboptimal solutions for a large-scale coalition formation problem containing thousands of agents using multi-agent simulation. We model coalition formation as an iterative process in which agents join and leave coalitions, and we propose several valuation functions that assign values to the coalitions. We propose several coalition selection strategies that agents may use to decide whether or not to leave their current coalition and which coalition to join. We also show how these valuation functions and coalition selection strategies represent specific coalition formation applications. Finally, we show almost-optimal performance of our algorithms in small-scale scenarios by comparing our solutions with an optimal solution, and we show stable performance in a large-scale setting in which searching for the optimal solution is not feasible.