La congestion routière
Deux routes mènent de A à B. Chaque automobiliste prend celle qui lui paraît la plus rapide, mais plus une route est choisie, plus elle ralentit. Chacun suit son intérêt, et la somme de ces choix raisonnables n'est pas la meilleure organisation possible pour tous.
Le jeu, en une phrase et une formule
Un jeu de congestion est un jeu où chaque joueur choisit une ressource (ici une route) et où le coût d'une ressource augmente avec le nombre de joueurs qui l'utilisent. On décrit chaque route par son temps de parcours, qui dépend du nombre x de voitures qui l'empruntent :
a est le temps à vide (route déserte), en minutes ; c est le nombre de minutes perdues par chaque conducteur pour chaque tranche de 1 000 voitures supplémentaires. Dans tout le cahier, la route du bas est la vallée (autoroute courte mais vite saturée), celle du haut est le plateau (départementale plus longue, qui encaisse mieux le trafic).
| Route | Temps à vide a | Sensibilité c (min par 1 000 voitures) | Avec 3 000 voitures |
|---|---|---|---|
| Vallée | 20 min | 10 | 50 min |
| Plateau | 35 min | 5 | 50 min |
Deux questions guident toute la page. Où la foule finit-elle par se répartir quand chacun choisit pour lui-même ? Et cette répartition est-elle celle qui ferait gagner le plus de temps à l'ensemble des conducteurs ? Les curseurs de la planche 2 modifient ces réglages pour toutes les planches à la fois.
Le matin des départs
Les automobilistes partent l'un après l'autre. Chacun regarde combien de voitures sont déjà engagées sur chaque route et prend celle qui, en comptant sa propre voiture, sera la plus rapide. Personne ne se concerte, personne ne pense aux autres.
L'équilibre de Wardrop : des temps égaux
Imposons une répartition et demandons-nous si les conducteurs en sont satisfaits. Si la vallée est plus lente que le plateau, certains la quittent ; si elle est plus rapide, d'autres la rejoignent. Le mouvement ne s'arrête que lorsque les deux routes utilisées demandent le même temps : c'est le premier principe de John Glen Wardrop (1952).
(Si ce nombre sort de l'intervalle [0 ; N], tout le monde prend la même route : celle qui reste la plus rapide même pleine.)
Les réglages des deux routes (valables pour toute la page)
Le coût pour tous : l'équilibre n'est pas l'optimum
Changeons de point de vue : un ingénieur qui répartirait lui-même les voitures chercherait à rendre minimal le temps total passé sur les routes, c'est-à-dire le temps moyen par conducteur. Le second principe de Wardrop décrit cet optimum collectif. Il n'égalise pas les temps, mais les coûts marginaux : ce qu'ajoute au total une voiture de plus, y compris le retard qu'elle inflige aux autres.
Le second terme, x × temps′(x), est l'externalité : la gêne qu'un conducteur impose à ceux qui partagent sa route. Il ne la paie pas et ne la voit pas ; c'est tout le problème.
Apprendre jour après jour
Dans la réalité, personne ne calcule l'équilibre : on l'atteint (ou non) par l'habitude. Chaque soir, les conducteurs comparent les temps de la journée, et une partie de ceux qui étaient sur la route la plus lente décident de changer le lendemain. Le nombre de changements est proportionnel à l'écart de temps observé.
La réactivité s est la part des conducteurs qui changent de route pour chaque minute d'écart. Le nombre κ décide de tout : si κ < 1, l'écart à l'équilibre fond régulièrement ; si 1 < κ < 2, la foule dépasse l'équilibre et revient en oscillant ; si κ > 2, chaque correction est plus forte que l'erreur et le va-et-vient ne s'éteint jamais.
Le prix de l'anarchie, et le péage qui le rachète
On appelle prix de l'anarchie le rapport entre le temps moyen à l'équilibre et le temps moyen à l'optimum (Koutsoupias et Papadimitriou, 1999). Combien coûte, au pire, de laisser chacun choisir ? Et peut-on corriger l'équilibre sans rien imposer, seulement en changeant les prix ?
Faisons payer la vallée d'un péage τ, exprimé en minutes (avec une valeur du temps, il devient des euros). Les conducteurs comparent désormais temps + péage. Arthur Cecil Pigou l'avait vu dès 1912 : si le péage est égal à l'externalité calculée à l'optimum, l'équilibre devient l'optimum.
Le cas le plus défavorable est l'exemple même de Pigou. Le plateau prend toujours 60 minutes ; la vallée ne prend rien quand elle est vide et 60 minutes quand tout le monde l'emprunte, avec une montée en pd (p = part du trafic). À l'équilibre, tout le monde prend la vallée : elle n'est jamais plus lente que le plateau. Le temps moyen vaut donc 60 minutes, alors qu'on pourrait faire bien mieux.
Théorème de Tim Roughgarden et Éva Tardos (2002) : dès que les temps de parcours sont affines (de la forme a + cx, comme dans tout ce cahier), le prix de l'anarchie ne dépasse jamais 4/3, quel que soit le réseau. Mettons-le à l'épreuve : on tire au hasard des milliers de faisceaux de k routes parallèles, puis on lance une recherche obstinée du pire réseau possible à deux routes.
Repères historiques
- 1912Arthur Cecil Pigou, Wealth and Welfare : deux routes, l'une étroite mais bonne, l'autre large mais médiocre. Il montre que la libre circulation surcharge la bonne route et propose une taxe pour la soulager. Repris en 1920 dans The Economics of Welfare.
- 1924Frank Knight répond que si la bonne route appartenait à un propriétaire privé, son péage produirait de lui-même la bonne répartition.
- 1952John Glen Wardrop, ingénieur britannique, énonce ses deux principes : temps égaux sur les routes utilisées (équilibre des usagers) et temps total minimal (optimum du système).
- 1956Martin Beckmann, Charles McGuire et Christopher Winsten montrent que l'équilibre minimise une fonction potentiel : il devient calculable sur de grands réseaux.
- 1962Anthony Downs observe que les nouvelles voies rapides se remplissent jusqu'à retrouver la congestion de départ.
- 1968Dietrich Braess découvre qu'ajouter une route à un réseau peut allonger le trajet de tout le monde.
- 1975Singapour met en place le premier péage urbain de congestion.
- 1999Elias Koutsoupias et Christos Papadimitriou proposent de mesurer le coût du pire équilibre ; l'expression « prix de l'anarchie » suit en 2001.
- 2002Tim Roughgarden et Éva Tardos démontrent la borne 4/3 pour tous les réseaux à temps affines.
- 2003Londres instaure son péage de congestion ; Stockholm suit, à l'essai en 2006 puis de façon permanente en 2007.
Ce qu'il faut retenir
L'équilibre égalise les temps
Quand chacun choisit pour lui-même, la foule s'arrête là où toutes les routes utilisées prennent le même temps. Personne n'y gagne à changer seul : c'est un équilibre de Nash, que la foule atteint sans calcul, à condition de ne pas réagir trop vivement.
L'optimum égalise les coûts marginaux
Pour le bien commun, il faut compter aussi le retard que chaque voiture inflige aux autres. L'optimum envoie moins de monde sur la route sensible à la congestion, quitte à rendre certains trajets plus longs que d'autres.
L'écart se mesure et se corrige
Le prix de l'anarchie mesure ce que coûte la liberté de choix : jamais plus d'un tiers de temps en trop quand les temps sont affines, sans limite quand la saturation est brutale. Un péage égal à l'externalité suffit à aligner l'intérêt de chacun sur celui de tous.
Pour aller plus loin
Le paradoxe de Braess. Avec plus de deux routes, l'égoïsme peut faire pire que de choisir une mauvaise répartition : ouvrir un raccourci peut rallonger le trajet de tous. Il est traité en détail dans la planche signature de la page « Le plus court chemin ».
Conducteurs imparfaitement informés. Si chacun perçoit les temps avec une erreur aléatoire, on obtient un équilibre « stochastique » (modèle logit), où la route la plus lente garde toujours quelques fidèles. Quand l'erreur tend vers zéro, on retrouve l'équilibre de Wardrop.
Conducteurs en nombre fini. Robert Rosenthal (1973) a montré que tout jeu de congestion à joueurs discrets possède un potentiel, donc au moins un équilibre de Nash pur : c'est ce que réalise la matinée de la planche 1.
L'heure de départ. William Vickrey (1969) a étudié le choix de l'heure plutôt que celui de la route : un péage qui varie au cours de la matinée peut supprimer la file d'attente sans réduire le nombre de voyageurs.
La courbe du Bureau of Public Roads. Les ingénieurs utilisent souvent temps = t₀ (1 + 0,15 (x/capacité)⁴), d'où l'intérêt du degré 4 dans l'onglet « Le pire cas » : le prix de l'anarchie peut alors atteindre 2,151.