Title page for ETD etd-07122012-185135


Type of Document Dissertation
Author Samman, Alfred
URN etd-07122012-185135
Title A New Model for Coalition Formation Games
Degree Doctor of Philosophy (Ph.D.)
Department Computer Science
Advisory Committee
Advisor Name Title
Busch, Konstantin Committee Co-Chair
Kannan, Rajgopal Committee Co-Chair
Zhang, Jian Committee Member
Houston, Andrea Dean's Representative
Keywords
  • bottleneck routing
  • group matching
  • game theory
  • coalition formation
Date of Defense 2012-07-11
Availability unrestricted
Abstract
We present two broad categories of games, namely, group matching games and bottleneck routing games on grids. Borrowing ideas from coalition formation games, we introduce a new category of games which we call group matching games. We investigate how these games perform when agents are allowed to make selfish decisions that increase their individual payoffs versus when agents act towards the social benefit of the game as a whole. The Price of Anarchy (PoA) and Price of Stability (PoS) metrics are used to quantify these comparisons. We show that the PoA for a group matching game is at most kα and the PoS is at most k/α where k is the maximum size of a group and α is a switching cost. Furthermore we show that the PoA and PoS of the games do not change significantly even if we increase γ, the number of groups that an agent is allowed to join.

We also consider routing games on grid network topologies. The social cost is the worst congestion in any of the network edges (bottleneck congestion). Each player's objective is to find a path that minimizes the bottleneck congestion in its path. We show that the price of anarchy in bottleneck games in grids is proportional to the number of bends β that the paths are allowed to take in the grids' space. We present games where the PoA is O(β). We also give a respective lower bound of Ω(β) which shows that our upper bound is within only a poly-log factor from the best achievable price of anarchy. A significant impact of our analysis is that there exist bottleneck routing games with small number of bends which give a poly-log approximation to the optimal coordinated solution that may use an arbitrary number of bends. To our knowledge, this is the first tight analysis of bottleneck games on grids.

Files
  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  dissertation.pdf 1.04 Mb 00:04:48 00:02:28 00:02:09 00:01:04 00:00:05

Browse All Available ETDs by ( Author | Department )

If you have questions or technical problems, please Contact LSU-ETD Support.