Hayrapetyan, Tardos and Wexler recently introduced a framework to study the impact of collusion in congestion games on the quality of Nash equilibria. We adopt their framework to network games and focus on the well established price of anarchy as a measure of this impact. We first investigate nonatomic network games with coalitions. For this setting, we prove upper bounds on the price of anarchy for polynomial latencies, which improve upon the current best ones except for affine latencies. Second, we consider discrete network games with coalitions. In discrete network games, a finite set of players is assumed each of which controlling a discrete amount of flow. We present tight bounds on the price of anarchy for polynomial latencies, which improve upon the previous best ones except for the affine and linear case. In particular, we show that these upper bounds coincide with the known upper bounds for weighted congestion games. As we do not use the network structure for any of our results but only rely on variational inequalities characterizing a Nash equilibrium, the derived bounds are also valid for the more general case of nonatomic and weighted congestion games with coalitions. Additionally, all our results imply bounds on the price of collusion proposed by Hayrapetyan et al.
Citation
Tobias Harks Institute of Mathematics Technical University Berlin Germany
Article
View The Impact of Collusion on the Price of Anarchy in Nonatomic and Discrete Network Games