mardi 12 mai 2009

Le paradoxe de Braess

L'enfer (des routes) est pavé de bonnes intentions...

"Abondance de biens ne nuit pas". La prochaine fois que vous vous retrouverez dans un embouteillage, un jour de grand week-end, je vous suggère de penser très fort à cette maxime pleine de (faux) bon sens! Il y a en effet fort à parier que le bouchon dans lequel vous êtes coincé soit dû soit à un accident, soit à un rétrécissement de la chaussée un peu plus loin devant vous, quand la route passe de trois à deux voies. Les tronçons à trois voies sont les cauchemars de bison futés!

C'est qu'en matière de circulation routière le mieux est souvent l'ennemi du bien: dès 1968, Dietrich Braess (qui n'a même pas sa page sur Wikipedia en français, quel scandale!) a montré comment ajouter un itinéraire de délestage peut provoquer des congestions et allonger les temps de parcours au lieu de les raccourcir. Un petit modèle explique mieux qu'un long discours ce paradoxe de Braess.

Un petit modèle pour comprendre
Supposez que vous cherchiez à vous déplacer d'une ville (A) à une autre (D) plus vite possible. Deux itinéraires s'offrent à vous, l'un passant par B, l'autre passant par C, chacun composé d'un bout de nationale et d'une route départementale. Le temps de parcours sur les nationales est de 45 minutes quelque soit la circulation. Par contre, comme il y a des feux sur les départementales, le temps de parcours dépend du nombre de voitures X qui l'emprunte: il vaut par exemple X/100 minutes.

Supposons qu'il y ait 4000 voitures souhaitant passer de A à D. Si elles prennent toutes le trajet du haut (ABD) elles mettront 85 minutes. Idem si elles prennent toutes le trajet du bas. La situation optimale sera celle où le trafic s'équilibre entre les deux trajets. Le temps de parcours sera alors de 45 +2000/100 = 65 minutes.

Pour désengorger la circulation, on construit une voie ultra-rapide reliant B et C, dont le temps de parcours est négligeable quelque soit le nombre de véhicules qui l'emprunte (pas très réaliste mais bon c'est un modèle!). Avec cette voie rapide, le temps de parcours entre A et B devrait raccourcir, or c'est l'inverse qui se produit:

Le meilleur trajet pour les 4000 voitures est maintenant (ABCD): départementale - voie rapide - départementale et le temps de trajet passe ainsi de 65 minutes à 80 minutes! Essayez vous même: si une des voitures prenait un autre itinéraire, son trajet serait rallongé de 5 minutes (45+40=85).

Bien que pas n'étant pas la meilleure, cette situation est un équilibre parfaitement stable ("équilibre de Nash" pour les familiers de la théorie des Jeux) où personne n'a intérêt à changer de stratégie une fois qu'il connaît les choix des autres. Et si dans un monde utopique, la circulation s'établissait comme s'il n'y avait pas de voie rapide et se répartissait comme avant, entre les deux itinéraires ABD et ACD? A ce moment-là, un petit malin serait tenté de gagner du temps en "coupant" par ABCD (son trajet ne lui prendrait que 40 minutes s'il était le seul à tricher): il serait donc rapidement imité par d'autres... et la situation dériverait assez vite jusqu'à ce que tout le monde prenne finalement le parcours ACBD et se retrouve avec un temps de parcours de 80 minutes.

Un mécanisme bien connu en théorie des jeux
Pour les habitués de la théorie des jeux ce paradoxe n'est pas vraiment nouveau: Offrir plus de choix aux joueurs peut parfaitement faire perdre tout le monde! Voici une petite matrice de gains où chaque joueur (A et B) a deux stratégies possibles qu'on appellera "maximiser" ou "minimiser", vous allez voir pourquoi:

Gain de B
Gain de A
A
"maximise"
A
"minimise"
B "maximise"
4
4
5
1
B "minimise"
1
5
3
3

On lit ça comme ça: si A et B "maximisent" ils gagnent tous les deux 4€. Si A "maximise" alors que B "minimise", A gagne 5€ et B gagne 1€. On voit que si A "maximise", B a toujours intérêt à "maximiser". Si A "minimise", B a aussi intérêt à "maximiser" (gain: 5€ plutôt que 3€ s'il "minimise"). Bref,dans tous les cas B a intérêt à "maximiser", et comme la matrice est symétrique, A aussi. Les deux joueurs ont intérêt à "maximiser" dans tous les cas (d'où le nom de cette stratégie ;-).

Maintenant supposons qu'on introduise une troisième stratégie possible, qu'on appellera "ruser", avec la matrice des gains suivants:

Gain de B
Gain de A
A
"maximise"
A
"minimise"
A
"ruse"
B "maximise"
4
4
5
1
-10
10
B "minimise"
1
5
3
3
-10
10
B "ruse"
10
-10
10
-10
-9
-9

Désormais que A "maximise" ou "minimise", B a toujours intérêt à "ruser" (il gagne 10€), et si A "ruse", B a aussi intérêt à le faire (il ne perd que 9€ au lieu d'en perdre 10). B a donc toujours intérêt à "ruser". A aussi car notre matrice est symétrique. L'équilibre s'est maintenant déplacé vers la situation où les deux joueurs "rusent". Avec beaucoup de guillemets car le bilan c'est qu'ils perdent chacun 9€! Voilà comment un choix supplémentaire donné aux joueurs s'avère néfaste pour tout le monde, comme la route .

Et dans la vraie vie?

Théoriques, tous ces modèles? Pas du tout! A New York, par exemple la fermeture provisoire de la 42eme avenue en 1990 a réduit les embouteillages dans cette zone, contrairement à toute attente. A l'inverse, à Stuttgart, le nouvel axe routier censé désengorger le centre-ville a créé tellement d'embouteillages à sa création, qu'il a fallu le fermer pour retrouver un trafic plus fluide. Pareil à Séoul: la méthode la plus efficace pour alléger le trafic a été d'investir près de 400 millions de dollars pour détruire une des voies rapides à la périphérie de la ville.

Il est très difficile de savoir si un axe routier supplémentaire améliore ou dégrade la qualité de la circulation, car les mécanismes du trafic urbain sont affreusement compliqués. La théorie prévoit qu'au pire on multiplie par deux (pas plus) les embouteillages: nous voilà rassurés!

Et à Paris au fait? Je n'ai rien trouvé l'impact de la fermeture des quais les dimanches et lors des opérations Paris-Plage en été. Sauf bien sûr les plaintes des riverains et des automobilistes avant

Plus fort que la mécanique des fluides
Ce qui rend le paradoxe de Braess... paradoxal, c'est qu'on associe instinctivement la circulation routière à un "flot" de voitures, donc soumis aux mêmes principes d'écoulements que les liquides ou les gaz. Or dans un écoulement fluide, plus il y a de chemins possibles, plus l'écoulement est facile: aucun plombier n'a encore vu de système dans lequel ajouter un tuyau d'évacuation boucherait des éviers.

La raison profonde de cette différence entre nous et les molécules d'eau, implicite dans nos modèles, me semble venir du fait que nous cherchons à rejoindre notre but le plus vite possible, compte de ce que les autres font (ou ont intérêt à faire). Dès qu'on spécule de la sorte, nos déplacements collectifs échappent aux règles de la mécanique des fluides et fabriquent des problèmes inédits. Autrement dit notre intelligence est la source de nos embouteillages. Il faut bien que réfléchir ait aussi des petits inconvénients...

Sources (en anglais):
L'article de Wikipedia
Le cours de "science of the Web" sur le sujet (oct 2008)
Ce cours du Californian Institute of Technology (Julian Romero, Caltech, janv 2008)

Billets connexes:
Psychologie de l'incivilité au volant
Le mieux en pire, pour un autre petit exemple d'améliorer les choses en les empirant