On the Inefficiency of Atomic Splittable Routing Games over Parallel Links

Abstract 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)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>c</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mi>ϕ</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>x</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> , whereas the latency function of "expensive" links is of the form $$c_2 \phi (x)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>c</mml:mi> <mml:mn>2</mml:mn> </mml:msub> <mml:mi>ϕ</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>x</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> , where $$c_2&gt;c_1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>c</mml:mi> <mml:mn>2</mml:mn> </mml:msub> <mml:mo>&gt;</mml:mo> <mml:msub> <mml:mi>c</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:mrow> </mml:math> . We obtain an explicit characterization of the optimal and equilibrium flow configurations, and establish sufficient conditions on the latency function $$\phi (x)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ϕ</mml:mi> <mml:mo>(</mml:mo> <mml:mi>x</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> 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.