Nicolás Stier-Moses

A Geometric Approach to the Price of Anarchy in Nonatomic Congestion Games

Coauthor(s): José Correa, Andreas Schulz.

Download:

Adobe Acrobat PDF

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. This novel proof also facilitates two new types of results: On the one hand, we give pseudoapproximation results that depend on the class of allowable cost functions. On the other hand, we derive improved bounds on the inefficiency of Nash equilibria for situations in which the equilibrium travel times are within reasonable limits of the free-flow travel times. These tighter bounds help to explain empirical observations in vehicular traffic networks. Our analysis holds in the more general context of congestion games, which provides the framework in which we describe this work.

The final version of this article can be found at http://dx.doi.org/10.1016/j.geb.2008.01.001.

Source: Games and Economic Behavior
Exact Citation:
Stier-Moses, Nicolás, José Correa, and Andreas Schulz. "A Geometric Approach to the Price of Anarchy in Nonatomic Congestion Games." Games and Economic Behavior 64, no. 2 (November 2008): 457-469.
Volume: 64
Number: 2
Pages: 457-469
Date: 11 2008