A joint project of the Graduate School, Peabody College, and the Jean & Alexander Heard Library

Title page for ETD etd-03262012-154004

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
  • coalition structure generation
  • multi-agent
  • coalition formation
Date of Defense 2012-03-22
Availability unrestricted
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.

  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

Browse All Available ETDs by ( Author | Department )

If you have more questions or technical problems, please Contact LITS.