Coalition Structure Generation in Characteristic Function Games

Abstract

Cooperation among self-interested agents offers the potential to realize goals unachievable by any agent alone. However, determining the optimal manner in which agents should cooperate is a computationally difficult problem. Two questions naturally arise: ``Which groups of agents should cooperate in order to maximize their earnings?' and ``How should the resulting earnings be split between the agents?'

This dissertation presents a number of approximation algorithms for coalition structure generation when agents are group rational. The presented algorithms improve upon the existing state-of-the-art in coalition structure generation by guaranteeing solutions along with constant factor lower bounds on the quality of the solutions in less than the time required to solve the problem exactly. This dissertation is also the first to present approximation algorithms for coalition structure generation tailored to monotonic domains. The complexity of the coalition structure generation problem is also studied in games where the number of agent types is small.

Optimally coordinating multiple agents becomes even more challenging when the agents are self-interested. Self-interested agents are not guaranteed to converge to social welfare maximizing states, as such states are not necessarily stable. This dissertation studies the stability-optimality relationship and demonstrates that both optimal and suboptimal coalition structures can be the most stable. The stability-optimality relationship restricted to certain natural classes of coalitional games is also studied.