Paradoxe de Braess
En mathématiques, et plus précisément en théorie des jeux, le paradoxe de Braess énonce que l'ajout d'une nouvelle route dans un réseau routier peut réduire la performance globale, lorsque les entités se déplaçant choisissent leur route individuellement. Cela provient du fait que l'équilibre de Nash d'un tel système n'est pas nécessairement optimal. Ce paradoxe a été mis en évidence en 1968 par le mathématicien Dietrich Braess.

Énoncé 
Le paradoxe s'énonce ainsi :

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. On peut rapprocher cette non-optimalité de l'équilibre de Nash au fameux dilemme du prisonnier : l'ajout d'une arête au réseau crée un nouveau jeu qui est un dilemme du prisonnier.

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.

Exemple 

Considérons le réseau décrit dans le diagramme ci-contre, sur lequel  souhaitent passer du point Start au point End. Sur la voie Start-A et la voie B-End, le temps de trajet  est égal au nombre de voyageurs (T) divisé par 100, et sur la voie Start-B et la voie A-End, il est constant à 45 minutes. Si la voie en pointillé n'existe pas (le réseau possède alors 4 voies), le temps pour effectuer Start-A-End avec  véhicules devrait être . Et le temps pour effectuer Start-B-End avec  véhicules devrait être . Si l'une des routes était plus courte, ce ne serait pas un équilibre de Nash : un conducteur rationnel opterait pour la route la plus courte. Comme il y a , le fait que  peut être utilisé pour en déduire que  quand le système est à l'équilibre. Par conséquent, chaque trajet dure  minutes.

Maintenant, ajoutons l'axe représenté par la ligne en pointillé, avec un temps de parcours tellement court qu'il en est négligeable, c'est-à-dire qu'il compte 0. Dans cette situation, tous les conducteurs vont choisir Start-A plutôt que Start-B, car Start-A prendra seulement  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  minutes. Le temps de trajet de chaque conducteur est donc de  minutes, un temps supérieur aux 65 minutes requises si 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  le temps de parcours de la voie  par un véhicule lorsqu'il y a  véhicules sur cette voie.

Prenons un graphe avec  conducteurs sur la voie . Définissons l'énergie de , , par :

 

(Si , on pose ). 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 y avoir au moins un conducteur qui peut changer d'itinéraire pour améliorer son temps de trajet. Notons  sa route initiale et  son nouvel itinéraire. Considérons ce qui se passe lorsque l'itinéraire  est supprimé. L'énergie de chaque arête  est réduite de  et donc  est réduite de . On notera qu'il s'agit simplement du temps de trajet total nécessaire sur l'ancienne route. En ajoutant le nouvel itinéraire, ,  va croître du temps de trajet total du nouvel itinéraire. Puisque le nouvel itinéraire est plus court que l'ancien,  doit décroître. Si nous répétons ce processus,  va continuer à décroître, jusqu'à l'obtention d'un équilibre, puisque  ne peut prendre qu'un nombre fini de valeurs.

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 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

À 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 
Si les fonctions de temps de trajet sont affines,  s'il existe  tels que  alors, au pire, le trafic à l'équilibre est deux fois pire que l'optimal social

Rareté du paradoxe de Braess ? 

 
 À noter cependant qu'une diminution du trafic local n'est pas nécessairement une manifestation du paradoxe de Braess : cela peut simplement traduire que la circulation devient si problématique que les utilisateurs renoncent à leurs déplacements, ce qui n'est pas nécessairement collectivement souhaitable.

Notes et références

Articles connexes 
 Anomalie de Belady
 Constante de Marchetti
 Prix de l'anarchie
 Théorie algorithmique des jeux
 Trafic induit
 Tragédie des biens communs
 
 Paradoxe de Downs-Thomson
  : l'augmentation de la nourriture disponible dans un écosystème peut introduire une instabilité dynamique, et même mener à l'extinction.
 

Théorie des jeux
Braess
Réseau de flot
Volume de transport