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