The
"Price of Anarchy" under Nonlinear and Asymmetric Costs
In this talk we characterize the "price of
anarchy", i.e., the inefficiency between user and system optimal
solutions, when costs are non-separable, asymmetric and nonlinear, generalizing
earlier work that has addressed "the price of anarchy'' under separable
costs. This generalization models traffic equilibria,
competitive multi-period pricing and competitive supply chains. The bounds established
in this talk are tight and explicitly account for the degree of asymmetry and
nonlinearity of the cost function. We introduce an alternate proof method for
providing bounds that uses ideas from semidefinite
optimization.
Finally,
in the context of multi-period pricing our analysis establishes that user
and system optimal solutions coincide.