The “Price of Anarchy” Under Nonlinear and Asymmetric Costs

The “Price of Anarchy” Under Nonlinear and Asymmetric Costs

0.00 Avg rating0 Votes
Article ID: iaor200954128
Country: United States
Volume: 32
Issue: 3
Start Page Number: 614
End Page Number: 628
Publication Date: Aug 2007
Journal: Mathematics of Operations Research
Authors:
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.