A geometric approach to the price of anarchy in nonatomic congestion games

We present a short, geometric proof for the price-of-anarchy results that have recently been established in a series of papers on selfish routing in multicommodity flow networks and on nonatomic congestion games. This novel proof also facilitates two new types of theoretical results: On the one hand...

Full description

Saved in:
Bibliographic Details
Published in:Games and economic behavior 2008-11, Vol.64 (2), p.457-469
Main Authors: Correa, José R., Schulz, Andreas S., Stier-Moses, Nicolás E.
Format: Article
Language:English
Subjects:
Anarchy
Congestion
Congestion games
Cost function
Cost structure
Empirical research
Game theory
Geometry
Network flow problem
Networks
Nonatomic games
Noncooperative games
Noncooperative games Nonatomic games Congestion games Wardrop equilibrium Price of anarchy
Price of anarchy
Pricing
Routing
Studies
Traffic
Traffic congestion
Wardrop equilibrium
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present a short, geometric proof for the price-of-anarchy results that have recently been established in a series of papers on selfish routing in multicommodity flow networks and on nonatomic congestion games. This novel proof also facilitates two new types of theoretical results: On the one hand, we give pseudo-approximation results that depend on the class of allowable cost functions. On the other hand, we derive stronger bounds on the inefficiency of equilibria for situations in which the equilibrium costs are within reasonable limits of the fixed costs. These tighter bounds help to explain empirical observations in vehicular traffic networks. Our analysis holds in the more general context of nonatomic congestion games, which provide the framework in which we describe this work.
ISSN:0899-8256
1090-2473
DOI:10.1016/j.geb.2008.01.001