J. Doncel Vicente
Several recent works on nonatomic 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. We establish
sufficient conditions on the latency function of the links 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. 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.
Keywords: Inefficiency, Atomic Routing Games, Price of Anarchy
Scheduled
GT19.GAMES4
November 10, 2023 9:30 AM
CC2: Conference Room