Paradoxe de Braess

En théorie des jeux le Paradoxe de Braess, du nom du mathématicien Dietrich Braess, stipule que l'ajout d'une nouvelle capacité à un réseau lorsque les entités se déplaçant choisissent leur route individuellement peut, dans certain cas, réduire la performance globale. Cela provient du fait que l'équilibre de Nash d'un tel système n'est pas nécessairement optimal.

Le paradoxe s'énonce ainsi : "Etant donnés le nombre de véhicules partant de chaque point d'un réseau routier, et leur destination, on cherche à estimer la distribution du flot de circulation. Le fait qu'une voie soit préférable à une autre dépend non seulement de la qualité de la voie, mais également de la densité du flux. Si chaque conducteur emprunte le chemin qui lui paraît le plus favorable, les temps de trajet résultant ne sont pas nécessairement les plus faibles. De plus (cela est montré par un exemple), une extension du réseau routier peut entraîner une redistribution du réseau qui résulte en des temps de trajet plus longs."

La raison en est que, dans une situation d'équilibre de Nash, les conducteurs n'ont aucun intérêt à changer de route. Si le système n'est pas dans un équilibre de Nash, les conducteurs doivent pouvoir individuellement améliorer leur temps de trajet respectif en empruntant d'autres routes. Dans le cas du paradoxe de Braess, les conducteurs vont continuer à basculer jusqu'à atteindre un équilibre de Nash, en dépit d'une réduction de la performance globale.

Si les fonctions de latence sont linéaires, l'ajout d'une voie ne peut allonger le temps de trajet total à l'équilibre que d'un facteur 4/3 au maximum^[1].

Exemple

Considérons un réseau comme le montre le diagramme ci-contre, sur lequel 4000 conducteurs souhaitent passer du point Start au point End. Le temps de trajet sur la voie Start-A est égal au nombre de voyageurs (T) divisé par 100, and sur la voie Start-B; et l'identique pour les routes opposées du schéma. Si la voie en pointillé n'existe pas (le réseau possède 4 voies), le temps pour effectuer Start-A-End avec a véhicules devrait être $\tfrac{a}{100} + 45$. Et le temps pour effectuer Start-B-End avec b véhicules devrait être $\tfrac{b}{100} + 45$. Si l'une des routes était plus courtes, ce ne serait pas un équilibre de Nash : un conducteur rationnel opterait pour la route la plus courte. Comme il y a 4000 conducteurs, le fait que a + b = 4000 peut être utilisé pour en déduire que a = b = 2000 quand le système est à l'équilibre. Par conséquent, chaque trajet dure $\tfrac{2000}{100} + 45 = 65$ minutes.

Maintenant, supposons que la ligne en pointillé est un axe avec un temps de parcours tellement court qu'il en est négligeable. Dans cette situation, tous les conducteurs vont choisir Start-A plutôt que Start-B, car Start-A prendra seulement $\tfrac{T}{100} = \tfrac{4000}{100} = 40$ minutes au pire, alors que Start-B prendra à coup sûr 45 minutes. Une fois au point A, tout conducteur rationnel choisira la route "gratuite" vers B, et de là continuera vers End, car là encore, A-End prendra à coup sûr 45 minutes alors que A-B-End prendra au plus $0 + \tfrac{4000}{100} = 40$ minutes. Le temps de trajet de chaque conducteur est donc de $\tfrac{4000}{100} + \tfrac{4000}{100} = 80$ minutes, un temps supérieur aux 65 minutes requises lorsque la ligne rapide A-B n'existait pas. Aucun conducteur n'a intérêt à changer, car les deux routes initiales (Start-A-End et Start-B-End) prennent maintenant toutes les deux 85 minutes. Si tous les conducteurs se mettaient d'accord pour ne pas utiliser la liaison A-B, chacun en bénéficierait, par une réduction de son trajet de 15 minutes. Toutefois, parce qu'un conducteur individuel aura toujours intérêt à prendre la voie A-B, la distribution socialement optimale n'est pas stable, et le paradoxe de Braess se produit.

Existence d'un équilibre

Soit L_e(x) la formule représentant le coût de x véhicules sur la voie e. Si un graphe du réseau a des arêtes linéaires (de la forme L_e(x) = a_ex + b_e > 0 où a_e et b_e sont des constantes, alors un équilibre existera toujours.

Prenons un graphe linéaire avec e_x conducteurs le long de e. Définissons l'énergie de e, E(e), par :

$\sum_{i=1}^{e_x} L_e(i) = L_e(1) + L_e(2) + ... + L_e(e_x)$

(Si e_x = 0, on pose E(e) = 0). Appelons "énergie totale du graphe" la somme des énergies de toutes les arêtes du graphe.

Si la distribution dans le graphe n'est pas à l'équilibre, il doit donc y avoir au moins un conducteur qui peut changer d'itinéraire pour améliorer son temps de trajet. Notons sa route initiale x₀,x₁,...x_n, et son nouvel itinéraire y₀,y₁,...y_m. Soit E L'énergie totale du graphe, et considérons ce qui se passe lorsque l'itinéraire x₀,x₁,...x_n est supprimé. L'énergie de chaque arête x_i est réduite de L_e(i_x) et donc E est réduite de $\sum_{i=0}^{n} L_e(i_x)$. On notera qu'il s'agit simplement du temps de trajet total nécessaire sur l'ancienne route. En ajoutant le nouvel itinéraire, y₀,y₁,...y_m, E va croître du temps de trajet total du nouvel itinéraire. Puisque le nouvel itinéraire est plus court que l'ancien, E doit décroître. Si nous répétons ce processus, E va continuer à décroître, jusqu'à l'obtention d'un équilibre, puisque E doit rester positif.

Recherche de l'équilibre

La preuve ci-dessus engendre une procédure connue sous le nom de Meilleure réponse, qui aboutit à un équilibre pour un graphe de trafic linéaire et se termine au bout d'un nombre fini d'étapes.L'algorithme est appelé "meilleure réponse" car à chaque étape de l'algorithme, si le graphe n'est pas à l'équilibre, alors il existe au moins un conducteur qui a une meilleure réponse à la stratégie de tous les autres conducteurs, et et choisit donc cette réponse.

Pseudo-code pour la meilleure réponse dynamique :

 Soit P un graphe de trafic.
 tant que P n'est pas à l'équilibre :
   calculer l'énergie potentielle e de P
   pour chaque conducteur c de P:
     pour chaque chemin alternatif p possible pour c:
        calculer l'énergie potentielle n du graphe lorsque c utilise p
        si n < e:
          modifier P de telle sorte que c utilise p
          continuer la boucle tant que

A chaque étape, si un conducteur particulier peut faire mieux en choisissant un autre itinéraire (une "meilleure réponse"), le faire décroît strictement l'énergie du graphe. si aucun conducteur n'a de meilleure réponse, le graphe est à l'équilibre. Puisque l'énergie du graphe décroît strictement à chaque étape, l'algorithme de la meilleure réponse dynamique stoppe forcément.

Écart entre l'équilibre et le trafic optimal

Au pire, le trafic à l'équilibre est deux fois pire que l'optimal social^[1]

Démonstration

Notons S_j le point de départ du véhicule j, et T_j sa destination

Les stratégies possible pour le véhicule j sont les chemins possibles de S_j à T_j

Chaque arête a une fonction de trajet L_e(x) = a_ex + b_e avec $a_e, b_e \geq 0$

L'énergie d'une arête e avec x véhicules est égale à :

   E(e) = Le(1) + Le(2) + ... + Le(x)

Le temps de total passé par tous les conducteurs sur cette arête est égal à :

   T(e) = xLe(x)  (où il y a x termes)

D'une part :

   $E(e) \leq T(e)$

D'autre part :

   $\begin{align} E(e) &= L_e(1) + ... L_e(x) \\ &= a_e(1+2+...+x) + b_e x \\ &= a_e \tfrac{x (x+1)}{2} + b_e x \\ &= x ( a_e \tfrac{x+1}{2} + b_e ) \\ &= \tfrac{1}{2} x ( a_e (x+1) + b_e ) \\ x+1 \geq x{, donc} \\ E(e) &\geq \tfrac{1}{2} x ( a_e x + b_e ) \\ E(e) &\geq \tfrac{1}{2} T(e) \\ \end{align}$

D'où :

   $\tfrac{1}{2}T(e) \leq E(e) \leq T(e)$

Si Z est une distribution de véhicules sur un graphe de trafic, par addition de toutes les arêtes du graphe on obtient :

   $\tfrac{1}{2} CoutSocial(Z) \leq E(Z) \leq CoutSocial(Z)$

Soit, pour une distribution socialement optimale Z et une distribution en équilibre Z' (pour le même graphe) :

$\begin{cases} \tfrac{1}{2} CoutSocial(Z') \leq E(Z') \\ E(Z') \leq E(Z) \\ E(Z) \leq CoutSocial(Z) \\ \end{cases}$

donc $CoutSocial(Z') \leq 2 CoutSocial(Z)$

CQFD.

Rareté du paradoxe de Braess ?

En 1983, Steinberg et Zangwill ont donné, sous des hypothèses raisonnables, des conditions nécessaires et suffisantes pour que le paradoxe de Braess intervienne dans un réseau routier lorsqu'un nouvel itinéraire est ajouté. (Notez que leur résultat s'applique à l'addition de n'importe quel' nouvel itinéraire, pas seulement lorsqu'une seule liaison est ajoutée) Comme corollaire, ils sont parvenus à la conclusion que le paradoxe de Braess a à peu près autant de chances de se produire que de ne pas se produire; leurs résultats s'appliquent sur des situations aléatoires, plutôt que sur des réseaux et des additions planifiés.

• A Seoul (Corée du Sud), une amélioration du trafic autour de la ville a été observée lorsqu'une voie rapide a été supprimée lors du projet de restauration de Cheonggyecheon^[2].
• A Stuttgart (Allemagne), après des investissements sur le réseau routier en 1969, la situation ne s'est pas améliorée jusqu'à ce qu'une section de route nouvellement construite soit à nouveau fermée au trafic^[3].
• En 1990, la fermeture de la 42e rue à New York a réduit la congestion dans cette zone^[4].
• En 2008, Youn, Gastner et Jeong ont pointé du doigt des itinéraires spécifiques à Boston, New York et Londres où cela pouvait effectivement être le cas, et désigné des routes qui pourraient être fermées pour réduire les temps de trajets^[5].
• En 2011, suite à la fermeture de l'Interstate 405, l'absence d'un fort trafic dans une large zone est potentiellement considérée comme l'exemple le plus récent du paradoxe de Braess à l'œuvre.

Voir aussi

• paradoxe de Downs-Thomson
• anomalie de Belady
• Paradoxe de l'enrichissement : L'augmentation de la nourriture disponible dans un écosystème peut introduire une instabilité dynamique, et même mener à l'extinction.
• Demande induite
• Position de Lewis-Mogridge
• Vague de trafic

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Braess's paradox » (voir la liste des auteurs)

1. ↑ ^{a et b} von Ahn L, « Modeling Network Traffic Using Game Theory », Science of the Web: Lecture 10, Carnegie Mellon University, 2008-10-02. Consulté le 2008-11-16
2. ↑ Easley, D and Kleinberg, J: "Networks", page 71. Cornell Store Press, 2008
3. ↑ (en) Knödel W, Graphentheoretische Methoden und ihre Anwendungen, Springer-Verlag, 1969 (ISBN 9783540046684), p. 57–9 
4. ↑ Kolata, Gina : What if They Closed 42d Street and Nobody Noticed?, New York Times (1990-12-25). Consulté le 2008-11-16.
5. ↑ Youn H, Gastner MT, Jeong H, « Price of anarchy in transportation networks: efficiency and optimality control », dans Phys. Rev. Lett., vol. 101, n^o 12, septembre 2008, p. 128701 [lien PMID, lien DOI]