Quand l’informatique rencontre les sciences économiques

Ces deux problématiques ont en commun de concerner différents usagers (les automobilistes, les citoyens et citoyennes), chacun ayant ses propres intérêts (arriver le plus vite chez soi, avoir ses projets préférés sélectionnés dans le budget de la ville). Elles ont aussi en commun d’être la cible de recherches mêlant informatique et concepts issus des sciences économiques. Commençons par un peu d’histoire contemporaine.

Du XX^e siècle au XXI^e siècle

Au XX^e siècle, s’est développée l’optimisation combinatoire, un domaine de l’informatique dont le but est de concevoir des méthodes qui trouvent la meilleure solution parmi un ensemble de solutions possibles. Cet ensemble est souvent très grand — le nombre de solutions est en général exponentiel par rapport à la taille de la donnée, par exemple par rapport au nombre de villes pour le plus court chemin, de projets pour le budget participatif, etc. —, et il s’agit de trouver rapidement la meilleure solution, sans avoir à examiner toutes les solutions. Par exemple, il peut s’agir de trouver le chemin le plus court parmi un ensemble de chemins reliant deux villes (c’est ce que font les GPS). Le mathématicien néerlandais Edsger Dijkstra publia en 1959 un algorithme résolvant ce problème (cet algorithme, désormais bien connu des étudiants en informatique, s’appelle l’algorithme de Dijkstra). D’autres problèmes étudiés à cette époque consistaient par exemple à trouver le meilleur ordre dans lequel fabriquer des pièces dans une usine, pour maximiser la production. Dans tous les cas, il s’agissait d’optimiser un critère pour satisfaire une seule personne. Au mieux, il pouvait s’agir d’optimiser plusieurs critères parfois contradictoires — on parle alors d’optimisation combinatoire multicritère. Dans ce cas cependant, les critères étaient alors ceux d’une même personne désireuse de minimiser la longueur d’un trajet et le coût des péages, par exemple : l’algorithme trouve les solutions de bon compromis et l’automobiliste doit alors décider parmi ces solutions laquelle il ou elle préfère.

Pendant ce temps, en économie se développait la théorie des jeux, qui ne s’intéresse pas seulement aux jeux de société mais qui modélise toute situation dans laquelle des individus interagissent, chacun devant prendre une décision — choisir une stratégie —, les stratégies des uns ayant des conséquences sur les autres. Le mathématicien et économiste américain John Nash énonça ainsi vers 1950 un célèbre théorème : il existe toujours, dans de telles situations, une solution d’équilibre, c’est-à-dire une situation dans laquelle personne n’a intérêt à changer de stratégie si les autres ne changent pas de stratégie — une telle situation s’appelle désormais un équilibre de Nash.

Le début des années 2000 fut marqué par l’avènement d’Internet, réseau partagé par de multiples entités ayant chacune ses propres intérêts. Il n’était plus possible d’optimiser un critère sans tenir compte des actions des autres entités. En informatique, c’est ainsi que naquit le domaine de la théorie des jeux algorithmique, qui emprunte des concepts à la théorie des jeux et à l’économie.

Quand chacun fait des choix pour optimiser son propre objectif

Dans des situations où plusieurs entités interagissent, chacune voulant optimiser son propre objectif, les chercheurs et chercheuses en informatique s’intéressent à des situations stables, dans lesquelles aucune entité n’a intérêt à changer de stratégie : des équilibres de Nash. Leur objectif ? Analyser dans quelle mesure, dans une situation d’équilibre donnée, le comportement individualiste des entités peut détériorer l’efficacité globale du système.

Considérons par exemple des automobilistes sur un réseau routier. Chaque automobiliste souhaite rejoindre le plus rapidement possible sa destination et prendra le chemin le plus rapide, étant donné ce que font les autres (si une route est surchargée, un automobiliste pourra avoir intérêt à en emprunter une autre). Commençons par une situation où les choses peuvent très mal se passer. Si les automobilistes doivent traverser une intersection et que la circulation n’est pas régie par des feux tricolores ou des agents de police, il est possible d’arriver à des situations où le comportement des automobilistes est très défavorable à la circulation globale. La photo ci-dessous illustre une telle situation : les automobilistes ne peuvent avancer que très lentement, alors qu’en se coordonnant, le débit serait bien plus important.

Un embouteillage à Skopje (vidéo sur Youtube).

Heureusement, de telles situations sont assez rares. Au début des années 2000, Tim Roughgarden, un chercheur en informatique américain, s’est intéressé au temps moyen de trajet quand des usagers se partagent un réseau routier. Pour chaque tronçon de route, il a modélisé le temps de trajet entre les deux extrémités comme une fonction \( ax+b\), où \(x\) est le nombre de voitures circulant sur la route, et \(a\) et \(b\) sont des nombres qui caractérisent le temps de trajet sur ce tronçon : le temps minimal de trajet est \(b\), et ce temps augmente (surtout si \(a\) est important) quand le nombre de voitures augmente. Il a prouvé que, quel que soit le réseau routier et les points de départ et de destination des automobilistes, le fait que chaque automobiliste choisisse le chemin le plus rapide dans sa situation augmente le temps de trajet moyen d’au plus un facteur \(\frac{1}{3}\) (environ \(33\%\)), par rapport à la même situation dans laquelle il y aurait une personne qui coordonnerait et dirait à chaque automobiliste quelle route emprunter. Les internautes s’intéressant à ce sujet pourront voir le cours de Claire Mathieu sur la théorie des jeux algorithmique au Collège de France (12/12/2017) pour en savoir plus. Ce nombre, qui mesure la perte d’efficacité du système due au comportement individualiste des usagers et à leur absence de coordination, s’appelle le prix de l’anarchie. Si, pour une situation étudiée, le prix de l’anarchie est bas, c’est très bien : l’individualisme des usagers (ici les automobilistes) et l’absence de coordination entre eux, ne nuit pas à l’efficacité du système (ici le temps de trajet moyen). Si au contraire le prix de l’anarchie est élevé, il faut trouver le moyen d’inciter les usagers à se comporter autrement. Dans notre cas, le fait que chaque automobiliste choisisse sa propre route augmente le temps de trajet moyen d’au plus \(33\%\) : ce n’est pas si gênant. Supposons que l’on veuille quand même faire baisser le temps de trajet moyen de chaque automobiliste.

Attention, construire une nouvelle route n’est pas toujours la meilleure solution ! Il est même possible que, au contraire, la construction d’une route augmente le temps moyen de trajet ! C’est le paradoxe de Braess, du nom du mathématicien allemand Dietrich Braess l’ayant mis en évidence. Ainsi, par exemple à Stuttgart en Allemagne, après des investissements sur le réseau routier en 1969, la situation ne s’est pas améliorée jusqu’à ce qu’une section de route nouvellement construite soit fermée au trafic. D’autres exemples sont indiqués sur la page Wikipedia sur le paradoxe de Braess.

Avant de construire une nouvelle route, il faut ainsi bien étudier la situation, et des solutions plus simples peuvent souvent être utiles pour réguler le trafic. Cela peut consister en des systèmes d’aide à la circulation (de type Bison Futé) indiquant aux automobilistes quelles routes emprunter pour que le trafic soit le plus fluide possible. Cela peut également être un système de péages, comme c’est le cas du système de péage électronique E-ZPass à New-York : les automobilistes ont une carte chargée qui est débitée lorsqu’ils passent sur certaines routes, ou au contraire créditée lorsqu’ils passent par d’autres routes. Mettre de bons prix (positifs ou négatifs) aux tronçons de route peut inciter les automobilistes à ne pas se précipiter sur la route a priori la plus rapide. D’autres solutions sont possibles, et c’est souvent le cas dans ce type de situations : le but est de changer les « règles du jeu » pour inciter les usagers à changer de stratégie. La seule limite pour cela est notre imagination !

Nous avons vu un exemple où des usagers se comportent de manière à optimiser leur propre objectif, chacun de son côté. Que se passe-t-il maintenant quand ces usagers ont chacun des préférences sur un choix qui doit être pris en commun ?

Quand chacun a une préférence sur des choix impactant tout le monde

Considérons par exemple les budgets participatifs, proposés par des municipalités de plus en plus nombreuses, de New-York à Paris, en passant par Porto Alegre. D’après le site participatorybudgeting.org, plus de 7000 villes ont ainsi utilisé un budget participatif ces dernières années.

Budget participatif à Paris (site de la ville).

Le concept est le suivant : une municipalité consacre un budget \(B\) à des projets proposés par les citoyens et citoyennes de la ville. Après un appel à projets, les habitants et habitantes de la ville, ayant connaissance du prix de chaque projet proposé, votent pour les projets qui leur plaisent. Une fois les votes connus, la municipalité doit sélectionner un sous-ensemble de projets ne dépassant pas le budget \(B\). Comment faire ? La mairie de Paris, par exemple, qui a utilisé entre 2014 et 2020 un budget de 500 millions d’euros pour ces projets, a une méthode très simple : elle sélectionne les projets lauréats, par ordre décroissant du nombre de voix, jusqu’à atteindre le montant juste inférieur à \(B\) (le budget pivot est accepté selon certaines conditions). Une exception est faite à cette règle quand il n’y a pas assez de budgets sélectionnés parmi les quartiers populaires de la ville — une rallonge est alors accordée pour les projets concernant ces quartiers (cf. le site de la ville dédié au budget participatif).

Cette méthode, naturelle, et utilisée par de nombreuses autres municipalités, pose pourtant quelques problèmes. Un projet très cher peut ainsi être sélectionné aux dépens de 10 projets beaucoup moins chers, et chacun plébiscité par à peine moins de monde que le gros projet. De plus, imaginez qu’un groupe A représentant \(51\%\) de la population plébiscite les mêmes projets, alors qu’un groupe B représentant \(49\%\) de la population plébiscite d’autres projets. À moins que le budget soit très important, tous les projets sélectionnés vont satisfaire les personnes du groupe A, alors que les personnes du groupe B n’auront aucun projet qui leur plaît sélectionné. On aurait pu vouloir une solution plus équitable… Alors, comment faire ? Là encore, l’informatique, aidée des concepts développés en économie, peut être utile. Le choix social est une branche des sciences économiques qui s’intéresse à l’élaboration et à l’analyse de méthodes pour prendre une décision collective. Il peut s’agir par exemple de proposer un mode de scrutin pour une élection, et d’analyser quelles propriétés souhaitables ce mode de scrutin respecte. Il peut aussi s’agir de proposer une façon de partager équitablement des ressources. À partir du début des années 2000, s’est développé un domaine à la frontière du choix social et de l’informatique : le choix social computationnel. Une part importante de ce domaine consiste à utiliser des concepts du choix social de manière à concevoir de « bons » algorithmes résolvant des problèmes de décision collective. Dans ce contexte, ces dernières années, des chercheurs et chercheuses en informatique s’intéressent au problème du budget participatif, afin de concevoir des algorithmes de sélection de projets qui soient à la fois efficaces et équitables.

Revenons par exemple aux deux problèmes que nous avons identifiés pour l’algorithme de sélection de projets utilisé par la mairie de Paris entre autres.

• Premièrement, les projets coûteux sont susceptibles d’être approuvés par beaucoup de monde, et sont ainsi favorisés aux dépens de projets certes approuvés par un peu moins de monde mais beaucoup moins coûteux. Pour éviter ce problème, une méthode assez simple consisterait à demander aux personnes votant de ne pas sélectionner tous les projets qu’elles approuvent, mais uniquement ceux qu’elles préfèreraient voir choisis, étant donné le budget donné. Chaque personne qui vote devrait ainsi approuver un ensemble de projets dont le coût ne dépasse pas le montant total alloué par la mairie au budget participatif. L’algorithme naturel utilisé par la mairie de Paris pourrait alors être utilisé.
• Deuxièmement, les projets sélectionnés pourraient tous être approuvés par une faible majorité, alors qu’une large minorité ne verrait aucun de ses projets favoris sélectionnés. Pour pallier ce problème, des scientifiques s’intéressent à concevoir des algorithmes qui maximisent le nombre de personnes votant ayant au moins un de leurs projets préférés sélectionné.

D’autres algorithmes de sélection de projets, utilisant souvent des notions issues du choix social, ont été proposés ces dernières années, ce qui fait de ce champ de recherche un domaine en plein essor.

Et demain ?

Nous avons vu que l’informatique s’est rapprochée des sciences économiques, en matière de recherche théorique, ce qui lui a permis d’une part de mieux modéliser les comportements humains (équilibres de Nash, par exemple), et d’autre part de bénéficier de notions définies en choix social (équité lors d’un partage de ressources, par exemple). L’informatique — et plus précisément l’optimisation combinatoire — peut ainsi être utile dans des contextes impliquant plusieurs personnes aux intérêts antagonistes. La prochaine étape sera peut-être la diffusion de ces connaissances au sein de la société, afin par exemple d’éviter certains écueils comme le paradoxe de Braess, et de bénéficier d’algorithmes de sélection de projets plus équitables ?