The price of anarchy in routing games as a function of the demand
From MaRDI portal
(Redirected from The price of anarchy in routing games as a function of the demand)
Abstract: The price of anarchy has become a standard measure of the efficiency of equilibria in games. Most of the literature in this area has focused on establishing worst-case bounds for specific classes of games, such as routing games or more general congestion games. Recently, the price of anarchy in routing games has been studied as a function of the traffic demand, providing asymptotic results in light and heavy traffic. The aim of this paper is to study the price of anarchy in nonatomic routing games in the intermediate region of the demand. To achieve this goal, we begin by establishing some smoothness properties of Wardrop equilibria and social optima for general smooth costs. In the case of affine costs we show that the equilibrium is piecewise linear, with break points at the demand levels at which the set of active paths changes. We prove that the number of such break points is finite, although it can be exponential in the size of the network. Exploiting a scaling law between the equilibrium and the social optimum, we derive a similar behavior for the optimal flows. We then prove that in any interval between break points the price of anarchy is smooth and it is either monotone (decreasing or increasing) over the full interval, or it decreases up to a certain minimum point in the interior of the interval and increases afterwards. We deduce that for affine costs the maximum of the price of anarchy can only occur at the break points. For general costs we provide counterexamples showing that the set of break points is not always finite.
Recommendations
- When is selfish routing bad? The price of anarchy in light and heavy traffic
- The asymptotic behavior of the price of anarchy
- The price of routing unsplittable flow
- A Sensitivity Analysis of the Price of Anarchy in Nonatomic Congestion Games
- Price of anarchy for highly congested routing games in parallel networks
Cites work
- A geometric approach to the price of anarchy in nonatomic congestion games
- Algorithms, games, and the internet
- Bounding the inefficiency of equilibria in nonatomic congestion games
- Computing all Wardrop equilibria parametrized by the flow demand
- Demand-independent optimal tolls
- Fast, Fair, and Efficient Flows in Networks
- How bad is selfish routing?
- scientific article; zbMATH DE number 1266748 (Why is no real title available?)
- scientific article; zbMATH DE number 956791 (Why is no real title available?)
- Infinite dimensional analysis. A hitchhiker's guide.
- Network topology and the efficiency of equilibrium
- Price of anarchy for highly congested routing games in parallel networks
- Routing games in the wild: efficiency, equilibration and regret. Large-scale field experiments in Singapore
- Selfish Routing in Capacitated Networks
- Selfishness need not be bad
- Sensitivity analysis for the asymmetric network equilibrium problem
- Sensitivity Analysis of Nonlinear Programs and Differentiability Properties of Metric Projections
- Sensitivity of Wardrop equilibria
- Sensitivity of wardrop equilibria: revisited
- The price of anarchy is independent of the network topology
- Traffic assignment problem for a general network
- Wealth Inequality and the Price of Anarchy
- When is selfish routing bad? The price of anarchy in light and heavy traffic
- Worst-case equilibria
Cited in
(2)
This page was built for publication: The price of anarchy in routing games as a function of the demand
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6201916)
