On the Inefficiency of Atomic Routing Games over Parallel Links
Sur l'inefficacité des jeux de routage atomiques sur des liens parallèles
Résumé
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)$, whereas the latency function of "expensive" links is of the form $c_2 \phi(x)$, where $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)$ 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 \emph{Price of Anarchy} is probably an overly pessimistic performance measure for non-cooperative routing games, as advocated in the above-mentioned works.
Plusieurs travaux récents sur les jeux de routage non atomiques suggèrent que la dégradation des performances du routage égoïste par rapport au routage optimal est globalement faible et loin du pire cas. Dans ce travail, nous étudions la dégradation des performances induite par le manque de coordination dans un jeu de routage atomique sur des liens parallèles dans lequel il y a deux types de liens. La fonction de latence des liens "bon marché" est de la forme $c_1 \phi(x)$, tandis que la fonction de latence des liens "coûteux" est de la forme $c_2 \phi(x)$, où $c_2>c_1$. Nous obtenons une caractérisation explicite des configurations de flux optimales et d'équilibre, et établissons des conditions suffisantes sur la fonction de latence $\phi(x)$ sous lesquelles les pires conditions de trafic se produisent lorsque tous les utilisateurs ont la même demande en trafic et que la demande totale est telle que les liens "coûteux" sont marginalement utilisés par le routage égoïste. Nous obtenons également des résultats partiels sur la pire configuration de réseau pour l'inefficacité du routage égoïste. Dans l'ensemble, nos résultats suggèrent que le pire scénario pour l'inefficacité du routage égoïste correspond à des conditions de trafic très spécifiques et à des configurations de réseau très asymétriques, et donc que le \emph{Prix de l'anarchie} est probablement une mesure de performance trop pessimiste pour les jeux de routage non coopératifs, comme le suggèrent les travaux susmentionnés.
Fichier principal
main.pdf (713.59 Ko)
Télécharger le fichier
main (1).pdf (713.59 Ko)
Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)