This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Perakis, G. Search for Related Content

The "Price of Anarchy" Under Nonlinear and Asymmetric Costs

Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
georgiap{at}mit.edu

In this paper we characterize the "price of anarchy," i.e., the inefficiency between user and system optimal solutions, when costs are nonseparable, asymmetric and nonlinear, generalizing earlier work that has addressed "the price of anarchy" under separable costs. The results in this paper apply primarily to nonatomic games such as the traffic equilibrium problem, but also in competitive multiperiod pricing and competitive supply chain settings. The bounds established in this paper are tight and explicitly account for the degree of asymmetry and nonlinearity of the cost function. We first provide a proof method for problems with a positive definite Jacobian matrix. Subsequently, we use ideas from semidefinite optimization in order to account for problems with a positive semidefinite Jacobian matrix (where the first approach does not apply). This latter connection also provides a different application of semidefinite optimization.

Key Words: price of anarchy; system and user-optimization; variational inequalities; traffic equilibrium
History: Received: January 17, 2004; revision received: July 28, 2006;

This article has been cited by other articles:

				P. Maille and N. E. Stier-Moses Eliciting Coordination with Rebates Transportation Science, November 1, 2009; 43(4): 473 - 492. [Abstract] [PDF]