Weighted Congestion Games
Abstract
We characterize the Price of Anarchy (POA) in weighted congestion games, as a function of the allowable resource cost functions. Our results provide as thorough an understanding of this quantity as is already known for nonatomic and unweighted congestion games, and take the form of universal (cost function-independent) worst-case examples. One noteworthy by-product of our proofs is the fact that weighted congestion games are “tight,” which implies that the worst-case price of anarchy with respect to pure Nash equilibria, mixed Nash equilibria, correlated equilibria, and coarse correlated equilibria are always equal (under mild conditions on the allowable cost functions). Another is the fact that, like nonatomic but unlike atomic (unweighted) congestion games, weighted congestion games with trivial structure already realize the worst-case POA, at least for polynomial cost functions.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Oct 28, 2014
- Source ID
- 10.1145/2629666
Entities
People
- Kshipra Bhawalkar
- Martin Gairing
- Tim Roughgarden
Organizations
- Air Force Office of Scientific Research
- Alfred P. Sloan Foundation
- Division of Computing and Communication Foundations
- German Academic Exchange Service
- Office of Naval Research
- Stanford University
- University of Liverpool