Network formation games with local coalitions

The quality of Nash equilibria in network formations games has recently been analyzed in the case of uncoordinated players. In this paper we study how the price of anarchy of network formation games with Shapley cost allocation is affected by allowing locally coordinated coalitions of players. In a distributed setting not all users can communicate and form coalitions, at least they have to know that the others exist. Here, we assume that the users can form a coalition when they share a resource, i.e., in our case a group of users that share an edge can form a coalition. We show that this assumption is strong enough to decrease the price of anarchy from (k) to (log k) in the one terminal undirected case, where every vertex node is associated with a player and k is the number of players. Whereas in the directed or multi terminal case local communication does not necessary lead to a better price of anarchy. We additionally show that in the directed case the price of stability increases from (log k) to (k). Copyright © 2007 ACM.