vendredi 28 août 2009

Billet de rentrée : retour de vacances, prévisions de Bison Futé et concours de beauté


Il est temps de se remettre au travail et, pour cela, quel meilleur moyen que de parler de ses vacances ? Tout le monde sait bien que, quand on a rien à dire, on raconte ses vacances...
En fait, plus précisément de retour de vacances…
En effet, récemment, après quelques semaines de repos bien méritées, j’ai, comme quasiment tous les vacanciers, été soumis à la torture – physique, nerveuse et psychologique – du retour de vacances impliquant de traverser la France entière du sud au nord au volant de mon véhicule favori.
Or, ces retours estivaliers (tous comme les départs) génèrent, c’est bien connu, des pointes de trafic dantesques dont on ressort accessoirement avec des envies de meurtre à l’égard de son prochain automobiliste, mais en tout cas épuisé nerveusement…
Le grand jeu de nombre d’automobilistes est donc d’éviter ces pointes –quand leur contrainte en matière d’arrivée ou de départ n’est pas trop forte.
Dans ce grand jeu impliquant des milliers de joueurs, les prévisions de Bison Futé  - voir ici -de trafic plus généralement, données par un nombre croissant de sites internet) sont censées guider les joueurs automobilistes afin d’aplanir ces pics de trafic. Notre cher icône sioux nous indique ce que seront a priori les journées « rouges », « orange » et « verte », les couleurs étant fonction de l’intensité du trafic sur le réseau en question. Rouge est synonyme de cauchemar et vert de ballade bucolique en gros.
Je me souviens que, même gamin, j’avais un problème avec cette histoire de Bison Futé. En effet, si les automobilistes utilisaient les prévisions pour modifier leur comportement en conséquence (anticiper ou reporter leur départ ou leur retour), logiquement, ces prévisions devaient s’avérer nécessairement fausses ex post. Sauf si l’on suppose que les gens sont idiots ou, plus prosaïquement, qu’ils ont une contrainte absolue en matière d’heure de départ ou d’heure de retour…
Je me disais en conséquence que les ingénieurs du trafic derrière Bison Futé étaient soit des imbéciles, leurs prédictions s’avérant nécessairement fausses du fait de n’avoir pas considéré l’interaction stratégique entre les automobilistes et l’effet de l’information sur les comportements (je ne le disais pas comme cela gamin, mais l’essentiel y était) soit diablement malins et pervers, considérant que l’erreur était un coût à subir au nom de l’intérêt général et de la minimisation des coûts de transport et des coûts d’insécurité…
Donc, il y a quelques jours, notre jeu a été d’éviter les pointes des week-ends de retour sur les axes nord sud, et notamment le samedi, les locations allant en général du samedi après midi au samedi matin. Il s’agissait en gros de décider de décaler notre départ la veille de la fin de la location ou le lendemain. Comme pas mal de personnes choisissent la première solution, nous avons choisi la seconde, celle de partir le dimanche, ce qui, soit dit en passant, a fonctionné parfaitement.
Au-delà de l’anecdote, ce raisonnement spéculatif que nous avons eu sur le comportement des autres automobilistes m’a rappelé le jeu du concours de beauté discuté par J. M .Keynes dans la  Théorie générale..., dans lequel l’objectif d’un concours n’est pas de sélectionner la fille objectivement la plus belle, mais celle qui sera désignée comme étant la plus belle par le plus grand nombre de compétiteurs. C’est un peu le même problème, puisque si on suppose les autres automobilistes rationnels, au moins autant que soi, la question est de savoir ce que les autres vont se figurer comme étant le choix le plus raisonnable.
Ce situation de raisonnement spéculatif (pas dans un sens financier, ici on spécule sur la rationalité des autres) a été testé en économie expérimentale à travers une série d’expériences construites par Nagel, 1995, Unravelling in Guessing Games, American Economic Review, 85 (5) ( voir ici pour une référence plus récente de cet auteur en collaboration avec d'autres) sur la base d’un « jeu de devinette » (très mauvaise traduction de « guessing game »). Dans ce jeu, des sujets doivent désigner un nombre compris entre 0 et 100. Le gagnant d’un prix annoncé à l’avance (x $) est celui qui donne le nombre qui est le plus proche de, par exemple, la moitié de la moyenne des N nombres donnés par les participants. Les perdants gagnent 0 et, en cas d’égalité, les gagnants se partagent le prix .
Différents niveaux de raisonnement sont possibles. Le niveau de rationalité zéro consiste pour un joueur à choisir aléatoirement entre 0 et 100 soit en moyenne 50, sans considérer le choix des autres. Un niveau de rationalité encore plus sophistiqué (niveau 1) consiste à penser que les autres désignant en moyenne 50, je gagnerai en choisissant 25 (0.5*50). Un niveau de rationalité encore plus sophistiqué consiste à penser que si les autres sont de niveau 1, et choisissent 25, je devrai choisir 12.5 (0.5*25). Etc. L’étude de ce type de jeu permet donc d’observer le degré de sophistication des comportements individuels en situation d’interactions stratégique.
Dans un tel jeu, l’équilibre de Nash consiste à donner un nombre égal à 0. En effet, si je suppose que les autres vont donner un chiffre de 50, je dois, pour gagner, donner un nombre de 25. Mais si les autres sont aussi rationnels que moi, ils vont donner un nombre égal à 25. Donc je dois en fait donner un nombre égal à 0.5*25 soit 12.5. Mais si les autres sont aussi rationnels que moi, etc. A l’issue du raisonnement spéculatif, la seule solution rationnelle est de déclarer 0.
Dans un jeu en classe que j’ai fait il y a quelque temps, 9 participants devaient faire ce choix de nombre durant 10 périodes. Le résultat est donné dans le graphique suivant :

 
Au début, la moyenne des nombres choisis par les joueur est autour de  42.5 (proche de 50), Puis, l'interaction se répétant, le nombre choisi en moyenne baisse fortement, comme si les participants réalisaient un apprentissage sur la bonne manière de raisonner dans ce jeu qui consiste à spéculer sur la rationalité des autres participants. Les décisions convergent lentement, mais sûrement, vers l’équilibre de Nash (pour la dernière période, il y a un effet « fin de jeu », mais je n’ai pas d’explication claire sur cette remontée). Ces résultats sont en fait assez proches de ceux obtenus initialement par Nagel, 1995, ce qui prouve la robustesse de ceux-ci.
Pour revenir à mon histoire de Bison Futé, car, lecteur, tu ne vois peut être pas le rapport – en fait j’espère quand même que si - le fait que la stratégie de partir le dimanche (au lieu du samedi) ait fonctionné peut s’expliquer de deux manières (ou par un mix des deux). Soit les automobilistes sont contraints d’arriver avant le lundi absolument, et cela peut expliquer le choix du samedi (niveau 0) ou du vendredi (niveau 1 de rationalité), soit en ayant un niveau de sophistication de type 2, on peut significativement améliorer sa situation. Mais si l’interaction est répétée de manière suffisamment forte avec un groupe d’automobilistes suffisamment homogènes, cette stratégie ne marchera plus, peut être dans dix ans. Cela me laisse le temps d’arrêter complètement de partir en vacances pour arrêter de me prendre la tête (au sens propre et figuré) avec ces histoires de départ/retour de vacances…

dimanche 2 août 2009

Trafic routier, travaux en ville et paradoxe de Braess

Allez, un dernier billet avant les vacances de ce blog ! De toute façon, comme je pars sur les traces de l’expédition Franklin (lecteur, si tu as raté ce formidable billet – c’est ce que m’a dit ma mère - tu peux te rattraper en allant ici), il y a peu de chances que j’ai accès au ouebe pour pouvoir pondre d’autres billets…

Il y a quelques semaines, ma bonne ville de Rennes était pleine de travaux, comme certainement nombre d’autres villes de province qui profitent de  l’arrivée prochaine des vacances estivales pour expédier un certain nombre de chantiers.
La ville, bruissant de ces multiples travaux, assortissait ceux-ci des habituelles restrictions de voirie et autres détournements qui font le plaisir de l’automobiliste au sortir de son lit quand il s’en va gagner sa croute à la sueur de son front au volant de son véhicule favori.
Comme je suis parfois un brin grincheux, j’anticipais alors une congestion routière cauchemardesque dans la ville et, un brin résolu, m’apprêtais à passer des moments interminables dans les bouchons, ce qui, soi-dit en passant, me laisserait du temps pour imaginer toutes les stratégies de torture possibles pour l’intégralité du personnel de la direction de l’équipement et des conseillers municipaux de la Ville de Rennes.
(Lecteur, si, comme moi, tu trouves la phrase précédente trop longue, je t’autorise à la couper avec l’instrument contendant qui te plaira).
Pour autant, comme j’ai pu le constater avec un peu de surprise, cette catastrophe annoncée du point de vue des encombrements n’a pas eu lieu, au contraire. Le trafic était significativement plus fluide qu’aux autres périodes de l’année. Bref, mon temps de parcours était réduit de quelques minutes par rapport à l’habitude…
Un lecteur sagace me dira vite que cette amélioration du trafic venait sans doute du fait que les étudiants n’étaient pratiquement plus là et que, du coup, le trafic local était significativement moins chargé.
C’est possible, mais rien n’est moins sûr. Des tonnes de facteurs peuvent avoir modifié l’état du système. Mais pourquoi ne pas penser au plus simple ? A savoir que la seule modification du système était ces travaux, toutes choses étant égales par ailleurs, et que cette restriction de la capacité pouvait très bien déboucher sur un nouvel équilibre du trafic caractérisé par des temps de parcours réduits !
En effet,  il n’est pas sûr du tout qu’une restriction de la capacité de la voirie –due par exemple à des travaux, mais aussi à des politiques de déplacements urbains – dégrade les conditions de circulation. Cette restriction pourrait même conduire à améliorer les conditions de circulation…
Ce résultat surprenant a été constaté dans certains cas spectaculaires, par exemple à New York en 1990. Le New York Times publia même cet encart à l’époque  :
« In 1990, 42nd Street in New York was closed for Earth Day, and the traffic flow in the area actually improved. An analoguous situation was observed in Stuttgart where a new road was added to downtown, but the traffic flow worsened. Following complaints, the new road was removed. »
(Pour les non anglophones, cela dit en gros que la 42ème rue avait été fermée dans le centre de Big Apple, et que, au lieu d’une catastrophe en termes d’embouteillages, ce fut une amélioration qui fut constatée. Au contraire, à Stuttgart, quand la ville fut dotée d’une nouvelle route, les conditions de trafic se sont tellement dégradées que les autorités décidèrent de supprimer ce nouveau barreau routier)
Ce surprenant résultat avait été en quelque sorte prédit ou avancé, mais uniquement comme une spéculation théorique, par un mathématicien allemand, Dietrich Braess en 1968. Ce résultat a été dès lors qualifié de paradoxe de Braess.
L’intuition est la suivante : supposons qu'un nombre n d’usagers ait le choix entre deux itinéraires, un des ces itinéraires étant éventuellement plus rapide que l’autre. On peut penser que le temps de parcours sur chaque itinéraire est une fonction croissante du nombre d’usagers choisissant cet itinéraire : c’est ce qu’on appelle de la congestion. Si ces usagers sont rationnels, ils vont se répartir entre les deux itinéraires de telle manière que, à l’équilibre du trafic, les temps de parcours seront rigoureusement identiques sur chaque itinéraire et aucun usager n’a alors intérêt à dévier de cet équilibre. C’est ce que, en économie des transports, on appelle l’équilibre de Wardrop, qui est en fait un équilibre de Nash.
Considérons le réseau routier suivant ultra-simple en forme de losange :

source : Rapoport et al. 2005

Sur la figure de gauche (attention, le graphique comporte une erreur, le coût fixe de transport n'est pas de 120 mais de 210!), deux itinéraires sont disponibles, pour aller de O (Origine) à D (Destination), l’un passant par A, l’autre passant par B. Sur chaque itinéraire, le temps de transport est la somme d’un temps fixe (210) et d’un temps variable qui dépend du nombre d’usagers présents sur le même itinéraire. Ainsi, s’il y a 18 usagers en tout, et que nous sommes 16 à passer par A et 2 à passer par B, les 16 sur A subiront un temps de 210 + (16)10 = 370 et les 2 sur B un temps de (2)10 + 210 = 230.
Les lecteurs un peu férus de théorie des jeux peuvent vérifier que, dans ce jeu de coordination, il y a une multiplicité d’équilibres de Nash (en stratégies pures), tous conduisant à une répartition uniforme des usagers sur ce réseau. L’équilibre du trafic est donc caractérisé par 9 usagers sur l’itinéraire A et 9 usagers sur l’itinéraire B. C’est cet équilibre qui minimise le total des coûts de transport, en d’autres termes c’est un optimum de Pareto. Pour cette répartition du trafic, chaque usager subit un temps de déplacement de 210 + (9)10 = 300.
Maintenant, supposons qu’un planificateur mal avisé décide de créer un itinéraire supplémentaire, comme sur la figure de droite ci-dessus. Il maille le réseau en raccordant le point A au point B, de sorte que 3 itinéraires sont maintenant possibles. Son intuition est que ce troisième itinéraire va permettre de décharger les deux autres et d’améliorer globalement les temps de transport. Supposons que le temps de transport de A à B soit nul, pour bien enfoncer le clou.
Tu pourras vérifier, lecteur, en guise de casse-tête en lieu et place du sudoku effectué laborieusement à la plage sous le soleil écrasant, que le nouvel équilibre conduit à ce que tous les usagers passent par le 3ème itinéraire. Le temps pour chaque usager est donc de (18)10 + 0 + (18)10 = 360. Le temps de transport total a donc augmenté et les conditions de circulation ont été dégradées par l’ajout d’un itinéraire supplémentaire. C’est dans ce sens qu’il y a paradoxe. C'est bien un équilibre de Nash car il n'y a pas de déviation profitable. Un joueur qui envisagerait de dévier sur l'un des deux autres itinéraires subirait en effet un coût de 390 (210+10(18) ou 10(18)+210)...
Bref, on connaissait bien quelques confirmations empiriques de ce phénomène bizarre qui veut qu’un meilleur maillage du réseau routier conduise à une dégradation des conditions de circulation et à une augmentation du temps de parcours, mais cela restait limité, et on pouvait dès lors parler de conjecture de Braess. Certains considéraient même le paradoxe de Braess comme une curiosité intellectuelle, mais pas plus tant l’évidence empirique était maigre.
Jusqu’à ce que l’équipe d’Amon Rapoport, de l’université de Tucson, Arizona, réalise une expérience sur ce fameux paradoxe de Braess en 2005 (une version de cette étude a été publiée en 2009 ici). En fait, la figure ci-dessus représente précisément l’expérience réalisée par l’équipe de Rapoport.
Dans un des traitements, les 18 participants choisissent un itinéraire à 40 reprises parmi les deux possibles (figure de gauche) puis à 40 reprises parmi les trois possibles (figure de droite).
Les résultats sont repris ci-dessous :
source : Rapoport et al. 2005

Ces graphiques disent simplement que les participants finissent par se coordonner  sur la répartition du trafic prévue par l’équilibre de Nash (9 sur chaque itinéraire dans le premier jeu, 18 sur le 3ème et aucun sur les deux autres dans le second jeu).
source : Rapoport et al. 2005
Bien évidemment, les gains des participants sont plus faibles dans le jeu avec réseau augmenté que dans le jeu avec réseau de base, comme le montre la figure ci-dessous.
source : Rapoport et al. 2005

En fait, ces expérimentalistes ont observé pour la première fois en laboratoire ce qui restait jusqu’à présent une spéculation intellectuelle. L’intuition géniale de Dietrich Braess s’est donc vue confirmée d’une manière que je trouve particulièrement spectaculaire d’un point de vue empirique. A nombre d'usagers constant, des routes supplémentaires peuvent très bien dégrader la situation du trafic, même sans considérer les coûts économiques de ces routes pour les collectivités qui les entreprennent.
Ce type d'expérience a été réédité par Orzen et al (2007), et Meingold and Pickhardt (2008), qui montrent par exemple qu'un péage trop élevé sur un itinéraire donné peut avoir le même type d'effet et provoquer un paradoxe de Braess, ce sur la base d'expériences de laboratoire.
Pour ma part, je suis intimement persuadé d’avoir observé en juin dans des conditions réelles, au volant de ma voiture, ce paradoxe de Braess dans cette bonne vieille capitale bretonne qui n’en est peut être toujours pas revenue…
PS : remerciements à un blogger commentateur d'un billet précédent qui m'a donné l'idée de ce billet, le paradoxe de Braess me fascinant depuis longtemps.