Le prix-de-l’anarchie

ou la bonne gestion des réseaux de communication

Piste verte Le 6 juillet 2009  - Ecrit par  Étienne Ghys Voir les commentaires (12)

En 1990, à l’occasion de la « journée de la Terre », la municipalité de New York décida de fermer la 42-ème rue à la circulation [1]. Cette rue étant l’une des plus animées de Manhattan, on pensait que cette fermeture ne manquerait pas de ralentir la circulation et de provoquer des embouteillages supplémentaires. C’est le contraire qui se passa : le fait de fermer la 42-ème rue rendit la circulation plus fluide ! C’était l’une des premières fois où l’on voyait se réaliser « en vrai » un phénomène mis en évidence de manière théorique en 1968 par un universitaire allemand : le paradoxe de Braess.

Deux paradoxes

Pour expliquer cela, nous allons commencer par décrire un autre phénomène découvert par A.C. Pigou — un économiste — en 1920 [2]. Supposons que deux villes $A$ et $B$, de part et d’autre d’un fleuve, soient reliées par deux routes. La première est excellente, très large, mais elle fait malheureusement un grand détour : il faut une heure pour la parcourir, et ceci quel que soit le nombre de véhicules qui l’empruntent (dans des limites raisonnables, par exemple jusqu’à 1000 véhicules par heure). La seconde passe par un pont très étroit et très court, et on peut le parcourir en quelques instants à peine, à condition d’être seul sur le pont. Mais plus le nombre de personnes qui empruntent le pont augmente, plus la circulation devient encombrée, et plus le temps de passage augmente. Pour faire simple, supposons que si $x$ milliers d’automobilistes/heure se présentent sur le pont, le temps de passage est de $x$ heures. Par exemple, pour 300 véhicules/heure, c’est-à-dire 0,3 milliers/heure, le temps de passage est de 0,3 heures, c’est-à-dire 18 minutes.

Supposons maintenant que 1000 automobilistes/heure souhaitent aller de $A$ à $B$. On peut envisager deux scénarios différents.

1- Le comportement égoïste. Chaque automobiliste choisit sa route comme il le souhaite.
Ici, c’est clair : comme de toutes façons moins de 1000 véhicules/heure passent par le pont, on met moins d’une heure pour traverser le pont, et il est donc toujours préférable de prendre le pont plutôt que la route longue. Tout le monde optera pour le pont si bien que tout le monde mettra une heure pour aller de $A$ à $B$.

2- Le comportement social. La municipalité, ou la police, peut forcer certains automobilistes à prendre telle ou telle route, par exemple en fermant une barrière temporairement sur le pont. Supposons par exemple qu’on force la moitié des 1000 véhicules/heure à prendre la route longue. Alors, 500 véhicules/heure mettront une heure pour parcourir la route longue mais les 500 autres prendront le pont et ne mettront que 30 minutes ! Le temps moyen de passage entre $A$ et $B$, dans cette option « policière », est donc de 45 minutes.

C’est la remarque de Pigou : un système de communication régulé de manière « centralisée », imposant des comportements à certains individus, peut circuler beaucoup mieux qu’un système dans lequel chacun peut choisir son comportement comme bon lui semble. L’« optimum social » est (parfois) bien meilleur que l’« optimum libéral ». Pas vraiment une surprise. L’union fait la force...

Passons au paradoxe de Braess illustré sur la figure suivante [3].

Deux routes joignent $A$ et $B$. L’une passe par un point $C$ et l’autre par un point $D$. Les tronçons $AD$ et $CB$ sont de bonne qualité mais longs : il faut une heure pour les parcourir. Les tronçons $DB$ et $AC$ sont comme le pont de Pigou : s’ils sont parcourus par $x$ milliers de véhicules/heure, il faut $x$ heures pour les parcourir. S’il y a 1000 véhicules/heure qui se présentent en $A$ et qui souhaitent aller en $B$, la symétrie des deux routes montre que les automobilistes vont choisir les deux routes à égalité et que tout le monde mettra une heure plus une demi-heure pour aller de $A$ à $B$.

Supposons maintenant que la municipalité décide d’améliorer la circulation en créant un nouveau tronçon hyper rapide qui connecte $C$ et $D$, tellement rapide que le temps mis pour le parcourir est négligeable, quel que soit le nombre de véhicules. Observons maintenant le comportement égoïste. Puisque nous savons qu’il y a 1000 véhicules/heure sur les routes, les tronçons $DB$ et $AC$ sont toujours plus rapides que $AD$ et $CB$. Un automobiliste partant de $A$ préférera toujours $AC$ à $AD$ et, une fois arrivé en $C$, il préférera utiliser la nouvelle route $CD$ puis $DB$ plutôt que d’emprunter $CB$. Tous les automobilistes auront le désir de prendre le chemin $AC-CD-DB$ et puisque tous s’engouffrent sur le même chemin, ils vont tous mettre un temps égal à une heure plus une heure, soit deux heures pour aller de $A$ à $B$.

La municipalité, voulant arranger les choses en créant un nouveau tronçon, a en fait tout compliqué. Il fallait une heure trente pour aller de $A$ à $B$, et il faut maintenant deux heures...

On peut renverser l’argument. Si le réseau initial contient le passage $CD$, et si on décide de le fermer, comme pour la 42 ème rue, la situation s’améliore et tout le monde gagne une demi-heure. C’est le paradoxe de Braess, mis en évidence en 1968. Il faut bien noter que ce paradoxe suppose un comportement égoïste : il n’aurait bien sûr pas lieu avec un comportement social.

Un peu de théorie

Les données

Les « réseaux de communication » de Pigou ou de Braess peuvent prêter à sourire tant ils sont naïfs. On peut se demander ce qui se passe dans des situations plus proches de la réalité, plus complexes. Le paradoxe de Braess se produit-il souvent et, si oui, quelle est son ampleur ? Si le paradoxe entrait effectivement en action dans des situations concrètes, le contribuable de la région Rhône-Alpes pourrait se poser des questions sur l’opportunité de la construction du Contournement Ouest de Lyon (quelques milliards d’euros).

Quelles sont les données nécessaires pour poser le problème ?

D’abord, il nous faut un ensemble de villes et de routes qui les relient. Voici un exemple (peu réaliste) avec 22 villes :

Remarquez les flèches ; elles indiquent la direction de la circulation. Certaines routes peuvent être en sens unique, ou d’autres peuvent être plus fluides dans un sens que dans l’autre. Il est donc nécessaire de considérer des « routes orientées », quitte à considérer les deux côtés d’une route comme deux routes différentes.

Une deuxième donnée sera importante pour nous. Pour chaque ville de départ $A$ et chaque ville d’arrivée $B$, il nous faut connaître le nombre de véhicules/heure qui souhaitent aller de $A$ vers $B$. Chacun de ces véhicules a plusieurs choix possibles pour aller de $A$ à $B$ (et nous ne considérerons pas les cas un peu stupides où il est impossible d’aller de $A$ à $B$, comme dans ce sketch de Raymond Devos dans lequel un automobiliste se retrouve coincé dans un rond-point sans aucune issue !). Ces choix sont nombreux en général. Nous appellerons « routage » la donnée des choix d’itinéraires de tous les individus. Se donner un routage c’est par exemple dire que parmi les 3000 véhicules/heure qui vont de $A$ à $B$, 1000 choisissent tel chemin , 1500 tel autre et 500 telle troisième possibilité.

Une troisième donnée est importante également. Pour chaque route, il faut connaître le temps qu’on met à la parcourir en fonction du nombre de véhicules/heure. Evidemment, plus il y a de véhicules et plus on met de temps. La forme de cette fonction a été très étudiée, et nous y reviendrons un peu, mais nous allons d’abord simplifier en supposant que ces fonctions sont affines, de la forme $t=ax+b$. On suppose $b\geq 0$ : c’est le temps de parcours « à vide » lorsque la voie est libre. On suppose également $a \geq 0$, ce qui correspond au fait que ce temps croît avec le nombre de véhicules. Nous supposerons donc qu’on peut associer à chaque route des coefficients $a$ et $b$ : certaines routes sont larges et assez insensibles au flot de voitures ($a$ petit) et d’autres sont étroites et sont vite engorgées ($a$ grand).

Maintenant que nous avons les données, quel est le problème ?

Pour chaque routage, on peut compter combien de véhicules empruntent chaque route. Puis, grâce aux fonctions temps, on peut calculer le temps total passé par les automobilistes dans leurs voyages. On a donc une fonction qui associe un temps total à chaque routage.

Il y a beaucoup de choix de routages. Quel est le meilleur ? Cela dépend du sens qu’on donne au mot « meilleur ».

Un optimum social consiste à trouver un routage pour lequel le temps total de transport est aussi petit que possible parmi tous les routages.

Un routage est un optimum égoïste si chacun y trouve son compte. En d’autres termes, c’est un routage qui a la propriété que si un automobiliste change d’itinéraire, sans que les autres en changent, son temps de transport personnel augmente. Nous l’avons vu : le temps total d’un routage égoïste, notons-le T-égoïste, peut être supérieur au temps d’un routage social, notons-le T-social. On parle parfois d’équilibre de Nash ou de Wardrop pour ce que nous appelons ici un routage égoïste.

Voici quelques théorèmes récents. J’indiquerai quelques éléments de preuve plus tard, mais ils rebuteront peut-être les lecteurs de la piste verte. D’abord, deux théorèmes d’existence. Ce n’est pas parce qu’on a une définition d’un objet que cet objet existe et cette preuve d’existence est souvent une étape importante dans la compréhension d’un phénomène.

Théorème 1 : Il existe un optimum social.

Théorème 2 : Il existe un routage égoïste.

Si on laisse chacun décider ce qu’il veut de manière égoïste, le temps T-égoïste peut-il être très supérieur au temps T-social ?
Le théorème suivant est dû à Roughgarden et Tardos (2002) [4]. Il permet d’estimer ce que Koutsoupias et Papadimitriou ont baptisé « le prix-de-l’anarchie » qui est par définition le quotient de T-égoïste et T-social [5].


Une remarque sur la terminologie en mathématiques

Les mathématiciens ont besoin de définir les mots qu’ils emploient avec précision. Souvent, ils puisent leur vocabulaire dans la langue courante : on trouve des corps, des anneaux, des filtres, des faisceaux, des pavés, des boules, des suites, des limites etc. Le plus souvent bien sûr, le mot est choisi pour évoquer le concept qu’il illustre (pavés, boules, suites, limites) mais parfois le lien est lointain ou se perd dans l’histoire (corps, anneaux, filtres, faisceaux). Cela n’a en principe aucune importance : Hilbert affirmait qu’on pourrait dire « verre de bière » et « chaise » au lieu de « point » et « droite » et la géométrie n’en serait pas changée : « par deux verres de bière passe une unique chaise »... Les mathématiciens sont habitués à ces « jeux de mots » et ils prennent garde à ne pas « exporter » leurs résultats dans le sens originel des mots. On ne peut pas nier cependant que le choix d’un bon vocabulaire guide l’intuition du mathématicien et facilite souvent sa compréhension.

Dans notre situation, les choix des mots « social », « égoïste », « anarchie » rappellent vaguement une idée initiale mais sont très éloignés des sens que ces mots ont en français, qui sont autrement plus riches. « Le mot anarchie est bien souvent utilisé pour décrire le chaos, les guerres civiles et les situations de désordre social. Mais les anarchistes rejettent en général cette conception courante (utilisée dans le langage courant, par les médias et les pouvoirs politiques). Pour eux, au contraire, l’ordre naît de la liberté, tandis que les pouvoirs engendrent le désordre ». On le voit : le mot français couvre un sens bien plus subtil que celui que nous lui donnons dans cet article mathématique, mais au moins le sens mathématique est clair. De même, penser que le mot « social » est associé à une tentative d’optimiser l’intérêt collectif est sans aucun doute caricatural. Parfois (souvent), les mathématiques manquent de subtilité... Mais il est difficile de changer une terminologie bien établie. Pour cette raison, nous avons écrit « prix-de-l’anarchie » comme s’il s’agissait d’un seul mot, qui a priori n’a rien à voir avec le prix de l’anarchie ! En tous les cas, il faut toujours être vigilant lors de l’interprétation d’un modèle mathématique « dans la vraie vie », et les mots utilisés sont bien souvent des pièges dont il faut se garder.


Heureusement, on ne peut pas perdre plus d’un tiers de notre temps à cause de notre égoïsme : le prix-de-l’anarchie ne dépasse pas $4/3$ :

Théorème 3 : T-égoïste $≤ \frac{4}{3}$ . T-social.

Remarquez que dans l’exemple de Pigou, le temps social est de 45 minutes, et le temps égoïste est de 1 heure, c’est-à-dire 4/3 de 45 minutes [6]. L’exemple de Pigou est donc en un certain sens le « pire » cas possible.

Le phénomène de Pigou est-il rare ?

Il est raisonnable de se demander si le cas de Pigou est en quelque sorte un cas exceptionnel ? Peut-être que pour un réseau « normal », le temps social ne diffère pas trop du temps égoïste ? Malheureusement, il n’en est rien. On peut s’en persuader de deux façons.

D’abord, on peut choisir un réseau « au hasard ». On choisit un nombre $N$ élevé de villes, puis pour chaque paire de villes on tire au sort si on met une route entre les deux ou pas, puis on choisit les coefficients $a$ et $b$ de ces routes au hasard. Enfin, on choisit au hasard le nombre de véhicules qui veulent aller entre deux villes. Il faudrait préciser toutes ces notions de « choisir au hasard », et il y a bien sûr beaucoup de façons de le faire, mais nous n’entrerons pas dans ces détails techniques. Pour ces choix aléatoires, on peut calculer T-égoïste et T-social et leur quotient, le prix-de-l’anarchie, et observer le résultat. On peut bien sûr faire des tests sur ordinateurs, mais on peut aussi essayer de démontrer un théorème. C’est ce qu’ont fait Valiant et Roughgarden dans un article publié en 2008 [7] : ils démontrent qu’il faut s’attendre à ce que le prix-de-l’anarchie soit significativement plus grand que 1. Techniquement, ils montrent l’existence d’un nombre $q>1$ tel que si $N$ devient de plus en plus grand, le prix-de-l’anarchie est supérieur $q$ avec une probabilité de plus en plus proche de la certitude.

On peut aussi argumenter du fait que les réseaux qui nous intéressent ne sont pas du tout aléatoires. Trois physiciens, Young, Jeong et Gastner, viennent de publier une étude concrète des situations à Boston, New York et Londres [8]. Les réseaux qu’ils considèrent ne sont pas formés de routes entre des villes mais plutôt de rues qui relient des carrefours ou des places d’une même ville. Par exemple, ils identifient 88 endroits dans Boston et 246 rues qui les connectent. Pour chaque rue, ils utilisent les données fournies par Google Maps pour trouver une bonne approximation du temps en fonction du nombre de véhicules/heure. D’ailleurs, ils ne choisissent pas une fonction $ax+b$ mais une fonction plus proche de la réalité (en fait un polynôme de degré 10) [9]. En ce qui concerne les souhaits des automobilistes, les auteurs font une simplification : ils supposent que tous les automobilistes désirent aller de Harvard Square à Boston Common. Notons $x$ le nombre total de véhicules/heure. Pour chaque $x$, ils peuvent calculer sur ordinateur le temps social, le temps égoïste, et le prix-de-l’anarchie. Voici un graphique extrait de leur article :

Il représente le prix-de-l’anarchie (noté PoA) à Boston en fonction du nombre de véhicules/heure. En bleu et rouge, les mêmes courbes pour Londres et New York. On voit donc que le phénomène de Pigou se présente à Boston : à cause de leur égoïsme, les automobilistes de Boston perdent environ 30% de leur temps, pour $x$ de taille modérée, autour de 10 000 [10].

Le paradoxe de Braess est-il fréquent ?

On peut tester sur les mêmes exemples que précédemment l’apparition du phénomène de Braess. Pour un réseau aléatoire, Valiant et Roughgarden montrent que le paradoxe de Braess se produit avec une probabilité presque sûre si le nombre de villes est grand [11]. En fermant quelques routes bien choisies, on améliore le temps égoïste. De même, dans les exemples de Boston, New York et Londres, les trois physiciens Young, Jeong et Gastner montrent qu’en fermant quelques rues, on améliore le trafic. Pour Boston, ils identifient 6 rues qui ont cette propriété. Mais attention ! les rues en question peuvent dépendre du flot de véhicules. Mais il est tout de même intéressant de savoir que le fait de transformer une rue en rue piétonne peut parfois fluidifier la circulation.

Il ne faudrait pas croire cependant que le paradoxe ne se présente que lorsque les entités qui circulent sur le réseau sont des « êtres raisonnables capables de prendre des décisions dans leur intérêt » [12]. Cohen et Horowitz ont construit des exemples [13] de systèmes physiques, formés de ressorts, de bouts de ficelle (qu’on peut difficilement imaginer comme étant dotés de « raison ») qui présentent le paradoxe : un poids est suspendu quelque part en équilibre et si on coupe l’une des ficelles, le poids monte alors qu’on penserait qu’il devrait descendre !

Beaucoup de problèmes

Les questions sont nombreuses et dépassent souvent le cadre strictement mathématique pour prendre un aspect politique. Souhaitons-nous qu’un service public (la municipalité, la police) soit autorisé à nous imposer tous nos choix ? Ou voulons-nous garder notre liberté individuelle ? Des solutions intermédiaires sont possibles, comme par exemple les droits de péages, l’installation de feux rouges etc. Les ordinateurs d’aujourd’hui ont une puissance suffisante pour analyser des grands réseaux et pour optimiser des routages, mais à condition qu’on les programme, et qu’on leur indique ce qu’on cherche à minimiser, et quelles sont les priorités. Ces choix ne seront pas faits par des ordinateurs mais par des humains. Si on vous dit qu’on peut vous faire gagner 30% de vos temps de transport, sachant d’ailleurs que votre voisin gagnera peut-être 50% de son temps de transport, à condition qu’on vous impose un itinéraire, êtes-vous prêts à accepter cette perte de liberté ? Il me semble que la plupart d’entre nous accepteraient cette option, mais si on généralisait la question à d’autres situations de la vie de tous les jours, en nous imposant des choix « pour notre bien », où serait la « bonne » limite ?

Une autre idée serait de concevoir des réseaux pour lesquels le prix-de-l’anarchie est aussi proche de 1 que possible, si bien que les optima sociaux et égoïstes seraient presque les mêmes. Mais pour cela, il faudrait une compréhension de la manière dont le prix-de-l’anarchie dépend de la structure du réseau. On en est encore loin.

Et bien sûr, comme toujours en mathématiques, une méthode peut couvrir de nombreux problèmes. L’important n’est pas toujours de transporter des voitures. Il est parfois utile de faire circuler des informations par exemple dans le cyberespace, sur les « routes virtuelles » de l’Internet. Faut-il créer une liaison haut débit entre Lyon et Paris ? Mais il arrive aussi qu’on tente de faire circuler des idées dans un groupe humain... On voit que le champ d’applications est vaste.

Pour en savoir plus, nous recommandons au lecteur (anglophone) de lire le livre récent de Roughgarden sur le prix-de-l’anarchie [14] ou encore sa conférence au congrès international des mathématiciens, à Madrid en 2006 [15]. Ces deux références sont bien sûr assez mathématisées mais leur lecture est abordable avec un bagage mathématique du niveau du premier cycle universitaire.

Ce ne sont certes pas les mathématiques qui vont nous permettre de faire le choix entre un système libéral et un système centralisé [16]. Mais les quelques idées que nous venons de développer éclairent peut-être un peu le débat.

Quelques preuves

Ce paragraphe quitte probablement la piste verte.

Supposons donc qu’un réseau de communication soit donné ; ses villes, ses routes, et ses « fonctions temps » $ax+b$ associées à chaque route. Supposons également que nous connaissions pour chaque paire de villes le nombre de véhicules/heure qui souhaitent se rendre de l’une à l’autre. Comme expliqué plus haut, un routage est un choix d’itinéraire pour chaque véhicule, depuis son départ jusque sa destination.

Il s’agit dans un premier temps de montrer qu’il existe un routage pour lequel le temps total de transport est minimal. A vrai dire, il nous faudrait être plus précis. Le nombre de véhicules/heure n’est pas nécessairement un nombre entier et il semble naturel de modéliser la situation par un nombre réel positif. Cependant, pour simplifier notre discours — et pour éviter le calcul intégral — nous allons supposer qu’il s’agit de nombres entiers, comme par exemple 23765 véhicules/heure et pas 23789,4567 véhicules/heure.

Mezalor [17], le théorème 1 est presque une évidence. En effet, puisqu’il s’agit de choisir un routage pour un nombre entier de véhicules/heure, il n’y a qu’un nombre fini de façons de le faire. Pour chaque routage, on peut calculer le nombre de véhicules/heure passant sur chaque route, puis le temps de parcours de chaque route, et enfin le temps total de transport. S’il n’y a qu’un nombre fini de routages possibles, il n’y a qu’un nombre fini de temps ainsi obtenus, et il y en a bien un qui est inférieur ou égal à tous les autres. C’est ce qu’il fallait démontrer [18].

Le théorème 2 est bien plus intéressant. Nous avons défini un routage égoïste comme un routage dans lequel chaque individu trouve son compte : il ne peut pas améliorer son propre temps de transport par une action individuelle, c’est-à-dire en changeant son itinéraire. Il n’est pas clair qu’un routage égoïste minimise une quantité globale, et pourtant c’est le cas.


Une parenthèse s’impose. Une grande idée en physique est que la nature est « paresseuse » ; elle tend à choisir les solutions qui minimisent une « énergie ». On appelle cela le principe de moindre action. La lumière par exemple « choisit » le chemin le plus rapide entre deux points [19]. Souvent, le physicien, face à un problème concret, cherche le bon concept d’énergie qu’il s’agira ensuite de minimiser. C’est le cas ici.


Considérons une route joignant deux villes $A$ et $B$ et appelons $T(x)$ le temps de parcours s’il y a $x$ véhicules/heure sur la route. Nous ne supposons pas ici que $T(x)$ est une fonction de la forme $ax+b$ : cela ne servira que dans le théorème 3. Nous supposons seulement qu’il s’agit d’une fonction croissante. Appelons « énergie » d’une route sur laquelle $x$ véhicules/heure sont en train de circuler, le nombre :

\[ E(x)= T(1) + T(2) + T(3) + ... + T(x). \]

Pour chaque routage, nous pouvons calculer le nombre de véhicules/heure sur chaque route, puis l’énergie de chaque route, puis faire la somme de toutes ces énergies. Le total sera appelé « l’énergie du routage ». Le point important du théorème 2 est le suivant :

Si un routage minimise l’énergie parmi tous les routages, c’est un routage égoïste. Réciproquement, les routages égoïstes minimisent l’énergie.

En voici la preuve. Supposons qu’un seul automobiliste change d’itinéraire et passe d’un itinéraire ancien à un nouveau, avec un temps de transport personnel qui passe de $t_{ancien}$ à $t_{nouveau}$. L’énergie, quant à elle, passe de $E_{ancien}$ à $E_{nouveau}$. Pour chaque route qui était parcourue anciennement, $x$ diminue de $1$ si bien que l’énergie de cette route diminue de $T(x)$, et pour chaque route nouvellement utilisée, l’énergie augmente de $T(x)$ [20]. L’énergie du routage diminue donc d’une quantité égale à la somme des temps de parcours des anciennes routes de l’automobiliste égoïste, et augmente de la somme des temps des nouvelles routes, c’est-à-dire que :

\[E_{nouveau}- E_{ancien} = t_{nouveau}- t_{ancien}.\]

Si l’énergie est minimale pour un routage, c’est que le membre de gauche de l’égalité précédente est positif ou nul, et il en est donc de même pour le membre de droite. Il en résulte que le temps de parcours de l’automobiliste qui a changé d’itinéraire a augmenté. Le routage était donc un optimum égoïste. Nous laisserons au lecteur le plaisir de démontrer l’implication réciproque : si un routage est un optimum égoïste, c’est un minimum de l’énergie.

La démonstration du théorème 2 est terminée : comme il y a un nombre fini de routages, il y en a bien un qui minimise l’énergie, et il y a donc bien un optimum égoïste.

Passons au théorème 3. Hélas, nous le démontrerons pas complètement... Nous allons en démontrer une forme faible dans laquelle $4/3$ est remplacé par $2$. Pour la preuve complète, il faudra aller consulter les références !

Nous considérons donc un optimum égoïste, qui minimise l’énergie, et un optimum social, qui minimise le temps total. Maintenant, nous supposons que pour chaque route, $T(x)= ax +b$ avec $a\geq 0$ et $b \geq 0$. Nous allons commencer par établir l’inégalité que voici :

\[ E(x)= T(1)+T(2)+T(3) + ... + T(x) \geq \frac{1}{2} x T(x). \]

C’est un petit calcul [21] :
\[ (a + b) + (2a + b) + (3a + b) + ... + (x a + b) = a(1+2+3+ ... + x) + b(1+1+1+ ... +1) = a \frac{x(x+1)}{2}+ b x \geq \frac{1}{2} x (ax +b). \]

Si on fait la somme de ces inégalités sur toutes les routes, on obtient que l’énergie $E$ d’un routage est supérieure ou égale à la moitié du temps total de transport.

Bien sûr, nous avons une autre inégalité encore plus facile :

\[ E(x)= T(1)+T(2)+T(3) + ... + T(x) \leq T(x) + T(x) + ... + T(x) = xT(x) \]

puisque $T$ est une fonction croissante. En faisant la somme de ceci sur toutes les routes, on montre que l’énergie d"un routage est inférieure ou égale au temps total de transport.

Ainsi, nous avons encadré l’énergie d’un routage entre la moitié du temps total et le temps total. Il n’est alors pas surprenant que les minima de ces deux quantités soient également encadrés. Voyons les détails.

Comparons deux routages, l’un optimum égoïste, d’énergie E-égoïste et de temps total T-égoïste, et l’autre optimum social, d’énergie E-social et de temps total T-social. Alors, nous avons la chaîne d’inégalités suivantes :

$\frac{1}{2}$ T-egoïste $ \leq$ E-égoïste par la première inégalité que nous avons établie,

E-égoïste $ \leq$ E-social car un optimum égoïste minimise l’énergie,

E-social$\leq $ T-social par notre première inégalité.

Mezalor, nous avons montré que $\frac{1}{2}$ T-égoïste $ \leq$ T-social ou encore que le prix-de-l’anarchie T-égoïste/T-social est inférieur à 2, et c’est ce que nous voulions démontrer (tout au moins dans la version faible puisque notre preuve ne nous donne pas le $4/3$).

Lorsqu’on autorise des temps de passages qui sont des fonctions plus compliquées de $x$, on peut aussi donner une borne supérieure pour le prix-de-l’anarchie. Par exemple, si on considère des polynômes de degré $p$ dont tous les coefficients sont positifs, la borne supérieure est égale à $(1-p(p+1)^{-(p+1)/p})^{-1}$ (notez que pour $p=1$, on retrouve bien le $4/3$).

Article édité par Étienne Ghys

Notes

[1G. Kolata. What if they closed 42nd Street and nobody noticed ? New York Times, page 38, December 25, 1990.

[2A.C. Pigou : The economics of welfare, Macmillan, 1920.

[3D. Braess : Über ein Paradoxon aus der Verkehrsplanung.
Unternehmensforschung 12, 258 - 268 (1968), consulter ici le site de D. Braess.

[4T. Roughgarden and E. Tardos : How Bad is Selfish Routing ?, FOCS ’00/JACM ’02. Consulter sur la page du premier auteur.

[5Il se trouve que, même s’il est possible qu’il existe plusieurs routages égoïstes, ils correspondent tous au même temps total, si bien que T-égoïste est effectivement bien défini.

[6Le lecteur pourra vérifier lui-même ces deux assertions : c’est immédiat pour le temps égoïste et peut-être un peu moins pour le temps social.

[7G. Valiant and T. Roughgarden : Braess’s Paradox in Large Random Graphs, EC ’06 (version complète Août 08).

[9Ils utilisent la formule suivante $t= \frac{d}{v}(1+ u\left( \frac{x}{c}\right)^{e})$ recommandée par le Bureau of Public Roads, dans laquelle $v$ est la vitesse maximale autorisée (30 miles/heure dans Boston), $d$ est la longueur de la rue, $c$ est la « capacité » de la rue, et $u,e$ sont deux constantes empiriques. En pratique, ils prennent $u=0,2$ et $e=10$, voir la bibliographie de leur article.

[10D’ailleurs, pour des $x$ plus grands, le prix-de-l’anarchie est proche de 1 mais comme la situation est bouchée, personne n’a envie de prendre sa voiture...

[11Techniquement, cette probabilité tend vers 1 quand le nombre de villes tend vers l’infini.

[12D’ailleurs, les automobilistes sont-ils des êtres raisonnables ?

[13Cohen et Horowitz : Paradoxical behaviour of mechanical and electrical networks, Nature, volume 352, 699-700 (1991).

[14T. Roughgarden : Selfish Routing and the Price of Anarchy, MIT Press, 2005.

[15T. Roughgarden : Potential Functions and the Inefficiency of Equilibria (Survey), ICM ’06.

[16Deux mises en garde contre l’exportation trop simpliste des concepts mathématiques valent mieux qu’une : me voilà en train d’assimiler « anarchie » et « système libéral » ! Mais le prix-du-libéralisme serait peut-être plus approprié que le prix-de-l’anarchie ? L’ancien gouverneur de New York Thomas Edmund Dewey ne déclarait-il pas « Le cœur même de notre système repose sur la conception libérale classique qui veut que chaque homme soit son propre maître et que le gouvernement ne soit là que pour garantir la liberté des hommes » ? Comme ce gouverneur a donné son nom à l’un des trois neveux de Donald Duck — celui qui s’appelle Fifi en français — le « prix-de-Fifi » serait peut-être encore une meilleure terminologie ;-)

[17Allusion à une plaisanterie de Godement, auteur de célèbres livres de mathématiques, dans lesquels il se moque de la manie des mathématiciens d’utiliser à tout bout de champ « Mais alors ! » comme s’il s’agissait d’un seul mot.

[18Notez que si on dispose d’une infinité de nombres positifs, il est bien possible qu’aucun d’entre eux ne soit plus petit que tous les autres : pensez par exemple à $1, 1/2, 1/3, ..., 1/n, ...$.

[19Il faudrait être plus précis et parler de chemins qui sont des points critiques pour la durée, mais ceci est une autre histoire.

[20Ce n’est pas tout à fait exact. En fait, l’énergie augmente de $T(x+1)$, mais nous ferons l’hypothèse dite « atomique » selon laquelle chaque individu est microscopique dans la masse totale, c’est-à-dire que $1$ est très petit par rapport à $x$, si bien qu’on peut dire que $T(x+1)$ est très voisin de $T(x)$... On peut rendre cela rigoureux.

[21Rappelons que la somme $1+2+3+ ... + x$ des $x$ premiers entiers est égale à $x(x+1)/2$ : regardez la figure suivante :

Partager cet article

Pour citer cet article :

Étienne Ghys — «Le prix-de-l’anarchie» — Images des Mathématiques, CNRS, 2009

Commentaire sur l'article

  • Le prix-de-l’anarchie

    le 6 juillet 2009 à 12:06, par Ilies Zidane

    Bonjour/bonsoir,
    je vous remercie pour cet excellent article, avec les très bonnes références qui l’accompagnent.
    Je ne connaissait pas ces paradoxes.
    J’ai particulièrement apprécier le brin d’humour, (Raymond Devos), qui caricature bien dans ce sketch, certaines situations, réelles...
    Le seul petit « hic », c’est que je trouve que les modèlent négligent pas mal de choses, et s’éloignent de la réalité.
    Ceci dit, ils apportent certaines réponses, et nous montrent certains phénomènes, et paradoxes fort intéressants.
    Mais ces paradoxes, persistent t-ils avec des modèles plus réalistes ? Ou est ce le fruit d’une simplification ?

    Répondre à ce message
    • Le prix-de-l’anarchie

      le 17 juillet 2009 à 16:31, par flandre

      il est clairement dit dans l’article que le test sur le terrain valide la théorie...

      Répondre à ce message
      • Le prix-de-l’anarchie

        le 18 juillet 2009 à 11:42, par adrienm

        Pas vraiment, la simulation la plus réaliste fut certes réalisée avec des réseaux réels mais le parcours des automobilistes est arbitraire : de Harvard Square à Boston Common.

        C’est déjà pas mal, la difficulté de modélisation étant fonction croissante du réalisme…

        Répondre à ce message
      • Le prix-de-l’anarchie

        le 22 juillet 2009 à 21:24, par Ilies Zidane

        Oui mais ça ne prouve rien.
        Si on se posait des questions légerement differentes, peut être que ce(s) model(s) donne(ront) des réponses differentes de ce qu’on l’on voit dans la réalité. A cause des simplifications. Enfin ça reste juste une opinion personnelle.

        Répondre à ce message
  • Modélisation

    le 28 juillet 2009 à 23:44, par Rémi Peyre

    Bonsoir,

    La question de la modélisation est cruciale en physique (car c’est finalement de la physique que nous faisons là : nous avons un phénomène complexe que nous tâchons de comprendre à partir du fonctionnement de ses parties élémentaires), et vous avez raison de souligner l’importance du choix du modèle. Mais rassurez-vous, il y a longtemps que les chercheurs se posent ce genre de questions.

    Un modèle physique est qualifié de « robuste » quand les résultats qu’il donne restent qualitativement valables (au sens où on observe les mêmes types de phénomènes, mais peut-être pas avec les mêmes intensités) même si le modèle est légèrement faux.

    Il y a plusieurs indices pour savoir si un modèle est robuste. Le premier critère pour juger si un « bébé-modèle » (càd. un modèle ultra simplifié) exhibe bien les mêmes phénomènes qu’une situation plus subtile est de se demander si chaque partie de la situation complexe peut être vue comme une partie du bébé-modèle. Ici, cela semble être le cas : la multitude des routes de campagne peut être considérée comme un tronçon lent mais jamais saturé, alors que les grands boulevards parisiens, au contraire, correspondraient aux routes rapides mais qui saturent vite ! Bien sûr, l’agencement des routes n’est pas forcément le même que dans le bébé-modèle, mais il y a tellement de routes qu’on se dit qu’il y a au moins des endroits où, localement, on ressemble au bébé-modèle.

    Le second est celui de la généricité. En clair, est-ce qu’on a supposé qu’il y avait une propriété du modèle qui était vérifiée très exactement (par exemple, une symétrie parfaite) pour faire nos calculs, ou est-ce qu’une petite modification des paramètres numériques du modèle ne change qu’à la marge les résultats obtenus ? Contrairement à ce qu’on pourrait croire en lisant l’article, on est en fait dans le second cas. Quand M. Ghys utilise que la situation du bébé-modèle est parfaitement symétrique, c’est uniquement pour simplifier les calculs ; on pourrait démontrer qu’en fait, un léger déséquilibre des vitesses ou des longueurs des routes n’entraînerait qu’un léger déséquilibre de la répartition des automobilistes.

    En conclusion, sans même connaître les expériences faites sur ordinateur ou l’histoire de la fermeture de la 42ème rue, on pouvait se douter que le modèle présenté ici était robuste ! Sans compter que la conclusion qu’il nous apporte n’est pas que les voies rapides sont *toujours* mauvaises, mais juste que *parfois*, donner plus de moyens aux gens aboutit à l’anarchie, et que dans ce genre de situation il suffit d’un seul exemple, fût-il un modèle, pour montrer que les choses ne se passent pas systématiquement comme on l’imagine.

    Cordialement.

    Répondre à ce message
  • Le prix-de-l’état

    le 30 juillet 2009 à 12:08, par Faré

    Si l’état est une entité bienveillante et toute puissante au-dessus de la société, dont le prix est nul, alors effectivement, l’état est la solution à tous les problèmes ! Vive le tout-à-l’état !

    Si le l’anarchie, c’est l’absence de règles plutôt que l’absence de chefs, si le libéralisme, c’est l’absence de droits de propriétés sur les routes et les ponts - alors effectivement votre critique porte effectivment sur ce que vous dénoncez.

    Mais il n’est pas besoin de mathématiques aussi avancées que les vôtres pour arriver à des conclusions absurdes à partir de prémisses absurdes. D’où les dangers de modélisations complexes qui ne sont que poudre aux yeux pour détourner l’attention des prémisses que l’on refourgue en contrebande.

    Réponse libérale à votre article : http://fare.livejournal.com/145607.html

    (Et bravo pour la censure sur un site se voulant scientifique !)

    Répondre à ce message
    • Le prix-de-l’état

      le 30 juillet 2009 à 22:59, par Rémi Peyre

      Faré,

      Pour connaître personnellement l’auteur tout en étant moi-même de philosophie libérale, je puis vous garantir que vous faites un procès d’intention absolument injustifié à M. Ghys. Cet article ne vise nullement à critiquer le libéralisme, mais simplement à montrer que certaines décisions peuvent avoir des conséquences paradoxales. Le titre « le prix de l’anarchie » est une formule-choc (car il faut motiver le visiteur à lire l’article) destinée à exprimer le principe général du théorème exposé, rien de plus.

      Je précise que j’ai trouvé l’agressivité de votre ton particulièrement désagréable, surtout envers M. Ghys qui ne compte pas son énergie pour faire accéder librement le plus grand nombre à la culture mathémathique. De brèves excuses seraient les bienvenues.

      Cordialement.

      Répondre à ce message
  • Piège terminologique

    le 31 juillet 2009 à 13:19, par Faré

    En relisant l’article plus en détail, je m’aperçois de l’existence du paragraphe « une remarque sur la terminologie en mathématiques » m’avait jusqu’alors échappé. Ce paragraphe exonère l’auteur, auquel je présente mes plus plates excuses (et je mettrai à jour mon blog).

    En insistant sur la différence sémantique entre les définitions mathématiques arbitraires et les concepts socio-politiques réels, M. Ghys avertit ses lecteurs du piège terminologique présent. M. Ghys ne se fait donc pas complice actif du charlatanisme pigovien dont sont coupables de nombreux parmi les auteurs qu’il cite (voir par exemple l’infâme article de Youn, Gastner et Jeong, ou Pigou lui-même).

    Je peux regretter que ce paragraphe n’ait pas été plus visible (en tête de l’article ?), mais j’aurais dû être plus attentif. Je peux aussi regretter que M. Ghys n’ait pas la capacité d’élucider précisément le piège terminologique et sa solution, mais nul n’est tenu d’être compétent en dehors de sa spécialité. (i.e. il s’agit d’un problème de coordination, indépendamment de la nature étatique ou non du coordinateur, et les hypothèses négligent les coûts de coordination.)

    Toutefois, je note que je ne suis pas le seul lecteur à m’être laissé prendre au piège, et que l’auteur lui-même en est victime, avec ses piques sur le prix-du-libéralisme ou sur l’applicabilité au traffic en région Rhônes-Alpes.

    PS : il y a des logiciels pour créer automatiquement à partir de code LateX des images PNG et/ou du MathML, qui s’afficheront bien sur des navigateurs anciens ou modernes.

    Répondre à ce message
    • Bagout et internet

      le 5 août 2009 à 14:22, par Pierre Lescanne

      Je trouve la réponse de M. Faré et son blog comique par son décalage par rapport au sujet mathématique traité et par son excès. Tout un vocabulaire outré y figure, qui me rappelle un certain auteur pas forcément recommandable.

      Je voudrais par ailleurs noter qu’il n’y aurait pas d’article en ligne, ni de blog sans l’Internet. Or l’Internet s’appuie sur ces théories. Je m’explique : dans Internet il y a des paquets qui circulent sur des canaux et chaque paquet « choisit » sa propre route de façon optimum pour lui, car il n’y a pas de contrôle central qui serait prohibitif et qui serait, tout simplement, impossible à mettre en œuvre. En revanche, si le coût de l’anarchie était exorbitant, l’Internet n’aurait pas le succès qu’il a. Bien sûr, quand un fournisseur d’accès ajoute un nouveau canal, il doit veiller à ce qu’il ne rende pas le système plus lent qu’avant.

      Bref, cela s’applique aux routes en asphalte, mais aussi aux routes virtuelles.

      Pierre Lescanne

      Répondre à ce message
      • Compétence dans la modélisation

        le 11 août 2009 à 21:30, par Faré

        Ah la culpabilité par vague association avec l’auteur anonyme de délits non révélés. Comment puis-je donc me défendre contre une telle accusation ? Je me rends, vous êtes décidément trop fort.

        Quant à votre note, elle va bien dans mon sens : non seulement le coût-de-l’anarchie, qui est proprement dit un coût d’absence de coordination indépendamment du moyen choisi pour ne pas coordonner, est faible (33% dans ce cas artificiel), mais le coût-de-l’état, coût de coordonner spécifiquement par un super-routeur centralisé, est prohibitif. Et s’il fallait à la place de ce coordinateur central ouvrir un marché pour l’échange de compensations, vous découvririez stupéfait qu’il n’y a pas plus Pareto-optimal que l’optimum de Pareto ; mais avant de pouvoir ouvrir un marché, encore faut-il avoir reconnu des droits de propriété individuels, ce qui est à l’opposé de la démarche totalitaire qui suppose que l’état est une entité supérieure propriétaire de tout et tous, justifié à émettre des règles arbitraires sur tout et n’importe quoi.

        Enfin, gros tour de passe-passe implicite dans l’invocation du paradoxe de Braess au cours d’une modélisation d’un réseau routier ou informatique : ce théorème ne s’applique que si (1) un seul couple source-destination compte lors de l’évaluation, et (2) le coordinateur central a le droit de pénaliser arbitrairement la minorité qui suivrait un autre chemin pour favoriser statistiquement la « majorité » qui emprunte le chemin officiel.

        Petit exercice de maths : majorer la perte subie par cette « minorité » négligée dans les hypothèses où des bureaucrates invoquerait ledit paradoxe pour fermer des connexions.

        La première condition s’appliquera concevablement au traffic en heure de pointe (et encore — seulement si le réseau est à la limite de la congestion). Quant à la deuxième, non seulement aucun mathématicien (en tant que tel) n’est compétent pour l’assumer, mais ceux qui seraient compétents pour en discuter, les praxéologues, pourront prouver qu’elle est tout bonnement fausse.

        Il ne suffit pas donc d’invoquer des théorèmes mathématiques pour faire de la science, sinon la numérologie serait la reine des sciences. Encore faut-il savoir de quoi on parle - ce que faisant on se rendrait compte qu’il y a en effet un bon moyen d’employer la logique en sciences sociales :
        http://membres.lycos.fr/marcgrunert/Th%E8sedeGuillaumat.htm

        Répondre à ce message
  • Le prix-de-l’anarchie

    le 24 août 2009 à 09:35, par vincent

    Merci pour cet article didactique.
    Dans l’attente de vous lire de nouveau.

    Répondre à ce message
    • Le prix-de-l’anarchie

      le 29 juin 2011 à 20:10, par Marie-Anne

      Un superbe article réellement intéressant.

      Organiser un syndicat de loterie est une sorte de simple. Tout d’abord, qu’est-ce qu’un syndicat de loterie ? Correctement, il implique simplement que vous allez jouer à la loterie avec une organisation de copains, membres de la famille, des collègues (ou des gens que vous ne savez même pas !) gagner au loto Formant un groupe pour jouer à des jeux de loterie vidéo avec le seul objectif de gagner ! Ou avoir agréable ! Avec un syndicat de loterie traditionnelle, mise en place d’un syndicat de loterie sera assez épuisant. Les billets seront en espèces devraient être prises par les membres du syndicat et le pot de succès dérouler entre tous les membres jouissant, avec le même gain pour correspondre à leur entrée au sein de l’argent de l’achat des billets de gain au loto loterie en premier lieu. Si cela sonne sophistiquée est alors possible. Organiser un syndicat de loterie en utilisant des méthodes traditionelles déconnecté peut prendre une certaine réflexion et l’organisation ! Voici une astuce, c’est plus pour toujours chaque participant dans le syndicat saisir le même montant. Rend fractionnement des gains beaucoup plus facile ! Pourquoi se donner la peine d’organiser un syndicat de loterie ? Beaucoup de gens demandent pourquoi vous aurez même besoin d’aller à la peine de mettre en place un syndicat de loterie en premier lieu ? Principalement des gens jouent dans les syndicats de loterie à la suite d’elles veulent augmenter leurs chances gagner l’euromillion de gagner régulièrement, une meilleure gagner ou même de gagner le jackpot (le grand !). L’objectif de la mise en place d’un syndicat de loterie est de membres du pool entrées et obtenir avec succès plusieurs entrées, mais pour moins d’argent. Il rend parfait sens mathématique, si vous pensez cela. Un fait ici est que vous ne savez pas, une à quatre jackpots de loterie sont acquises par un syndicat
      Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

registros

Cet article fait partie du dossier «Mathématiques de la planète Terre (2013)» voir le dossier

Suivre IDM