Type of Document Dissertation Author Service, Travis Coe URN etd-03262012-154004 Title Coalition Structure Generation in Characteristic Function Games Degree PhD Department Computer Science Advisory Committee
Advisor Name Title Julie A. Adams Committee Chair Gautam Biswas Committee Member Jerry Spinrad Committee Member Paul Edelman Committee Member Vincent Conitzer Committee Member Keywords
- coalition structure generation
- coalition formation
Date of Defense 2012-03-22 Availability unrestricted AbstractCooperation 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.
Filename Size Approximate Download Time (Hours:Minutes:Seconds)
28.8 Modem 56K Modem ISDN (64 Kb) ISDN (128 Kb) Higher-speed Access ServiceDissertation.pdf 778.80 Kb 00:03:36 00:01:51 00:01:37 00:00:48 00:00:04