טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentSergey Kuniavsky
SubjectCoalitional Congestion Games
DepartmentDepartment of Industrial Engineering and Management
Supervisors Professor Smorodinsky Rann
Mr. Rothblum Uriel (Deceased)
Full Thesis textFull thesis text - English Version


Abstract

In this thesis we study Coalitional Congestion Games (CCG), a family of non-cooperative games which is a natural extension of the well studied family of Congestion Games.

Coalitional Congestion Games are similar to congestion games, replacing individual agents with coalitions of agents as the

players of the game. Thus, a Congestion game and a coalition structure over the agents induce a Coalitional Congestion Game. A strategy for a coalition is the any combination of the strategies available to all of its members in the underlying Congestion Game. The utility of a coalition is the sum of its members' utilities.


CCG model similar situations as do Congestion Games, namely communication networks, transportation, flows, load balancing, routing and more. However, the new model better suits situations where the decision making is

granted to a set of agents. For example, a transportation game played among a few fleet managers instead of among the drivers or routing games played among internet domains instead of individual computers.


The main research questions we address are derived from the literature on congestion games and can be roughly partitioned into two sets:


·        Congestion games often have compelling properties, such as the existence of pure NE. We investigate under which circumstances do these properties carry over to CCG.

·        What are the social welfare implications of working with coalitions, as opposed to endowing individual agents on the one hand, or the grand coalition  on the other hand. In a way, this extends the literature on the Price of Anarchy the Price of Collusion.