<p>Several recent works on non-atomic routing games suggest that the performance degradation of selfish routing with respect to optimal routing is overall low and far from worst-case scenarios. In this work, we study the performance degradation induced by the lack of coordination in an atomic routing game over parallel links in which there are two types of links. The latency function of "cheap" links is of the form <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$c_1 \phi (x)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>c</mi> <mn>1</mn> </msub> <mi>ϕ</mi> <mrow> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, whereas the latency function of "expensive" links is of the form <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$c_2 \phi (x)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>c</mi> <mn>2</mn> </msub> <mi>ϕ</mi> <mrow> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$c_2>c_1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>c</mi> <mn>2</mn> </msub> <mo>></mo> <msub> <mi>c</mi> <mn>1</mn> </msub> </mrow> </math></EquationSource> </InlineEquation>. We obtain an explicit characterization of the optimal and equilibrium flow configurations, and establish sufficient conditions on the latency function <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\phi (x)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ϕ</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> under which the worst traffic conditions occur when all users have the same traffic demand and the total traffic demand is such that "expensive" link are marginally used by selfish routing. We also obtain some partial results on the worst network configuration for the inefficiency of selfish routing. All in all, our results suggest that the worst-case scenario for the inefficiency of selfish routing corresponds to very specific traffic conditions and to highly asymmetric network configurations, and thus that the <i>Price of Anarchy</i> is probably an overly pessimistic performance measure for non-cooperative routing games, as advocated in the above-mentioned works.</p>

On the Inefficiency of Atomic Splittable Routing Games over Parallel Links

期刊论文
出版模式：

开放获取
发表日期：

2025年5月24日

查看全文

Olivier Brun,
Josu Doncel

摘要

Several recent works on non-atomic routing games suggest that the performance degradation of selfish routing with respect to optimal routing is overall low and far from worst-case scenarios. In this work, we study the performance degradation induced by the lack of coordination in an atomic routing game over parallel links in which there are two types of links. The latency function of "cheap" links is of the form $c_1 \phi (x)$ $c_{1} ϕ (x)$ , whereas the latency function of "expensive" links is of the form $c_2 \phi (x)$ $c_{2} ϕ (x)$ , where $c_2>c_1$ $c_{2} > c_{1}$ . We obtain an explicit characterization of the optimal and equilibrium flow configurations, and establish sufficient conditions on the latency function $\phi (x)$ $ϕ (x)$ under which the worst traffic conditions occur when all users have the same traffic demand and the total traffic demand is such that "expensive" link are marginally used by selfish routing. We also obtain some partial results on the worst network configuration for the inefficiency of selfish routing. All in all, our results suggest that the worst-case scenario for the inefficiency of selfish routing corresponds to very specific traffic conditions and to highly asymmetric network configurations, and thus that the Price of Anarchy is probably an overly pessimistic performance measure for non-cooperative routing games, as advocated in the above-mentioned works.