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.
翻译:无政府状态的价格已成为游戏中平衡效率的标准衡量标准标准。 大部分这方面的文献都侧重于为特定类型的游戏, 如路途游戏或更普遍的拥挤游戏, 建立最坏的框框。 最近, 路途游戏的无政府状态价格作为交通需求的一种函数来研究, 提供轻便和重型交通的无约束结果。 本文的目的是研究中间区域需求中非原子路运游戏中的无政府状态价格。 为了实现这一目标, 我们首先为一般的平滑成本建立Warrodrop equilibria 和社会opima 的顺畅性属性。 在折线成本中, 我们显示平衡是一条线性线性线性, 其断线点在需求水平上, 从而改变活动路径。 我们证明这种断线点的数量是有限的, 尽管在网络的大小上可能是指数指数的指数。 将平衡和社会最优化之间的比例法进行解释, 我们为最优流动采取类似的行为。 我们随后证明, 在任何断线点之间, 断线点之间的平衡点是平滑的, 。