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

Correa JR; Schulz, AS; Stier-Moses, NE

Abstract

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. © 2008 Elsevier Inc. All rights reserved.

Más información

Título según WOS: A geometric approach to the price of anarchy in nonatomic congestion games
Título según SCOPUS: A geometric approach to the price of anarchy in nonatomic congestion games
Título de la Revista: GAMES AND ECONOMIC BEHAVIOR
Volumen: 64
Número: 2
Editorial: ACADEMIC PRESS INC ELSEVIER SCIENCE
Fecha de publicación: 2008
Página de inicio: 457
Página final: 469
Idioma: English
URL: http://linkinghub.elsevier.com/retrieve/pii/S089982560800033X
DOI:

10.1016/j.geb.2008.01.001

Notas: ISI, SCOPUS