Optimization Online


The Impact of Collusion on the Price of Anarchy in Nonatomic and Discrete Network Games

Tobias Harks (harks***at***math.tu-berlin.de)

Abstract: 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.

Keywords: algorithmic game theory, congestion games, nonatomic player, polynomial cost functions

Category 1: Other Topics (Game Theory )

Category 2: Network Optimization

Category 3: Applications -- OR and Management Sciences (Transportation )

Citation: Tobias Harks Institute of Mathematics Technical University Berlin Germany

Download: [PDF]

Entry Submitted: 01/15/2007
Entry Accepted: 01/19/2007
Entry Last Modified: 01/28/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society