The “Price of Anarchy” Under Nonlinear and Asymmetric Costs

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