Jouer avec le système

Vous et un complice d'un cambriolage majeur avez été arrêtés par les flics et êtes interrogés dans des pièces séparées. Si vous gardez tous les deux le silence sur le crime, vous encourez chacun un an de prison pour une accusation moindre. Si vous couinez tous les deux, vous aurez chacun cinq ans. Mais si un seul de vous couine, celui-là sera gratuit tandis que l'autre aura 10 ans. Si vous ne savez pas ce que fera votre complice, quelle est la décision rationnelle ?

Asuman Ozdaglar

Cette énigme, connue sous le nom de dilemme du prisonnier, est l'exemple le plus connu de jeu, au sens technique employé par les théoriciens des jeux. La théorie des jeux est une manière mathématique de décrire le raisonnement stratégique, et le dilemme du prisonnier illustre les trois exigences fondamentales des situations qu'elle englobe : le jeu doit impliquer plusieurs agents (ici, les deux complices) ; chacun doit prendre une décision (crier ou ne pas crier) ; et chaque décision doit comporter un gain quantifiable (les peines de prison) qui varie en fonction des décisions des autres agents.

La théorie des jeux est un élément essentiel de la recherche en économie depuis 1950, lorsque John Nash, qui a enseigné au MIT de 1951 à 1959 et est le sujet du film Un bel esprit , a publié le papier séminal qui lui vaudra le prix Nobel d'économie. À mesure que la théorie des jeux a mûri, elle est devenue encore plus centrale dans ce domaine. Au cours des huit dernières années, le prix Nobel a été décerné à trois reprises à des théoriciens du jeu, pour avoir mis en lumière, entre autres, la logique de la dissuasion nucléaire, les circonstances dans lesquelles les marchés libres peuvent et ne peuvent pas maximiser le bien-être public, et les meilleures solutions aux problèmes d'appariement—organes et patients, médecins résidents et hôpitaux, etc.

Mais récemment, la théorie des jeux a également attiré l'attention en ingénierie et en informatique. Les chercheurs l'utilisent pour analyser des problèmes épineux tels que l'optimisation de la circulation ou la prévention des pannes.

Asuman Ozdaglar, SM '98, PhD '03, professeur de génie électrique et d'informatique, affirme que l'essor d'Internet a rendu cela nécessaire. Historiquement, les ingénieurs des réseaux de communication ont dû faire face à un large éventail de questions techniques, telles que les contraintes de puissance et les mérites relatifs de la centralisation ou de la décentralisation. Mais avec Internet, ils ont soudainement dû faire face à l'action humaine aussi.

Si un abonné Comcast à Boston et un abonné EarthLink à San Francisco échangent des données, leurs transmissions transitent sur des réseaux gérés par plusieurs fournisseurs différents : Comcast, EarthLink et d'autres entre les deux. L'ensemble de l'opération repose à la fois sur la collaboration et la concurrence de ces différentes parties, explique Ozdaglar. Comment concevez-vous des protocoles qui inciteront réellement les gens à collaborer ? En d'autres termes : pourquoi Internet fonctionne-t-il alors qu'il est constitué de réseaux individuels ? La théorie des jeux permet de répondre à ce genre de question.

Cependant, lorsque les ingénieurs ont commencé à appliquer la théorie des jeux à des questions relevant de leur domaine, ils se sont également rendu compte que les outils de leur métier étaient applicables aux questions en suspens de la théorie des jeux. En effet, parmi la poignée de chercheurs du Département de génie électrique et informatique (EECS) qui travaillent de manière intensive sur la théorie des jeux, tous ont consacré un temps considérable à des questions plus généralement traitées par les sciences sociales.

Aller une fois
Le professeur EECS Constantinos Daskalakis en est un bon exemple. En 2008, il a remporté le prix de thèse de l'Association for Computing Machinery en montrant comment des techniques issues de l'informatique théorique pouvaient apporter un éclairage nouveau sur l'un des concepts centraux de la théorie des jeux : l'équilibre.

Constantinos Daskalakis

L'équilibre est l'idée qui a valu à Nash son prix Nobel, et l'équilibre de Nash est le type d'équilibre le plus couramment étudié. Il décrit un équilibre de stratégies qu'aucun joueur d'un jeu n'a de motif pour changer unilatéralement. L'exemple le plus basique d'un équilibre de Nash implique ce qu'on appelle le jeu de tir au but. Au soccer, un coup de pied de pénalité donne à un joueur offensif un tir franc au but, seul le gardien de but défendant. Le ballon se déplace si rapidement que le gardien de but doit deviner dans quel sens plonger avant qu'il ne soit frappé. Dans la version théorique des jeux, si les deux joueurs choisissent la même moitié du but, le gardien de but gagne ; s'ils choisissent des moitiés différentes, le tireur gagne.

L'état d'équilibre pour ce jeu est que les deux joueurs choisissent une direction au hasard sur n'importe quel coup de pied donné, mais pour s'assurer que, dans l'ensemble, ils choisissent les deux directions avec une fréquence égale. Dans ce cas, ils gagneront chacun la moitié du temps, et aucun d'eux ne pourra améliorer ses chances en s'écartant de cette stratégie. Par exemple, si le gardien de but commençait soudainement à suivre la même direction à chaque fois et que le tireur s'en tenait à la stratégie d'origine, le pourcentage de victoires du gardien resterait simplement le même. Cependant, un tireur qui a remarqué le changement pourrait gagner chaque coup de pied en allant dans la direction opposée à chaque fois, donc le gardien de but n'a aucune incitation à faire ce changement.

Mais le jeu de tir au but est l'un des jeux les plus simples. Trouver des équilibres pour des jeux même un peu plus complexes peut être extrêmement difficile. Dans sa thèse, Daskalakis a prouvé que pour certaines situations qui peuvent être décrites par la théorie des jeux, l'équilibre de Nash est si difficile à calculer que tous les ordinateurs du monde ne pourraient pas le trouver au cours de la vie de l'univers. Dans ces cas, soutient Daskalakis, les humains ne l'ont probablement pas non plus trouvé par essais et erreurs. Cela signifie que les théoriciens des jeux ont besoin d'outils analytiques autres que l'équilibre de Nash s'ils veulent espérer décrire le monde réel.

Heureusement, de la même manière que l'informatique a développé une batterie de techniques pour déterminer la complexité des calculs tels que ceux qui produisent les équilibres de Nash, elle a également développé une batterie de techniques pour identifier des solutions approximatives à des problèmes autrement insolubles. Daskalakis et ses étudiants, par exemple, ont pu en trouver un pour un problème d'économie qui existait depuis 30 ans.

En 1981, Roger Myerson de l'Université de Chicago a montré comment structurer une vente aux enchères pour un seul article de sorte que si tous les enchérisseurs adoptaient les stratégies d'enchères dans leur meilleur intérêt, le vendeur réaliserait le plus grand profit. Ce travail lui a valu le prix Nobel 2007. Cela a également soulevé une question connexe : quelle est la meilleure façon de structurer une vente aux enchères pour plusieurs articles ? (Dans le jargon des économistes, tout marché avec un seul vendeur et plusieurs acheteurs compte comme une enchère ; une enchère Christie's en est une, mais les ventes dans un magasin de détail le sont aussi.) C'est une question d'une complexité si grande qu'il n'y a pas de description succincte pour le enchère qui vous donne le profit optimal, dit Daskalakis. Pour maximiser les revenus sur plusieurs articles, le vendeur doit probablement vendre chaque article à un prix inférieur au prix le plus élevé que quelqu'un serait prêt à payer. Mais la remise varie en fonction de facteurs tels que le mélange d'articles vendus et les populations d'où proviennent les acheteurs.

L'informatique offre une nouvelle perspective sur le problème, ce que Daskalakis appelle la perspective d'approximation. Peut-être que vous ne parvenez pas à trouver l'enchère optimale, dit-il, mais une enchère qui garantit 99% des meilleurs revenus est également une bonne enchère. Daskalakis et ses étudiants ont montré que pour tout marché à plusieurs articles, l'enchère idéale, celle qui maximise les revenus du vendeur, peut être approximée par une combinaison des résultats d'enchères plus simples.

Une approche quelque peu différente des problèmes d'enchères caractérise le travail du professeur d'ingénierie Silvio Micali. Lui et Shafi Goldwasser, professeur à l'EECS, sont les plus récents récipiendaires du prix Turing, la plus haute distinction en informatique. En grande partie, le prix honore leur travail sur les preuves dites interactives, dans lesquelles un questionneur avec des ressources de calcul limitées essaie d'obtenir le résultat d'un calcul d'un interlocuteur peu fiable avec des ressources de calcul illimitées. Un exemple est une preuve à connaissance nulle, dans laquelle l'un des participants établit la possession d'une information, comme une clé cryptographique, sans révéler de quoi il s'agit. Les preuves à connaissance nulle sont utilisées pour sécuriser les transactions entre les institutions financières, et plusieurs startups ont été fondées pour les commercialiser.

Micali poursuit plusieurs projets de recherche sur la théorie des jeux, mais l'un d'entre eux est très proche dans l'esprit des preuves à connaissance nulle. Dans de nombreuses enchères publiques, comme, par exemple, lorsque le gouvernement fédéral vend aux enchères du spectre radioélectrique inutilisé à des entreprises de télécommunications, le commissaire-priseur est tenu de divulguer les offres de tous les participants dans un souci de transparence. Pour une entreprise qui participe à une telle vente aux enchères et perd, c'est vraiment le pire de tous les résultats possibles, dit Micali. Vos concurrents savent maintenant à quel point vous appréciez cette chose, à partir de laquelle ils peuvent déduire la taille de la clientèle que vous servez ou la technologie dont vous disposez.

Ainsi, le groupe de Micali développe des enchères dans lesquelles les participants peuvent divulguer publiquement suffisamment d'informations sur leurs offres pour décider d'un gagnant, sans révéler les offres eux-mêmes. Je pense que cela finira par devenir courant dans la théorie des jeux, dit Micali. Vous ne pouvez pas vraiment avoir une science significative du comportement humain sans tenir compte de la vie privée.

Qui contrôle ?
Pour de nombreuses situations qui peuvent être exprimées sous forme de jeux, l'équilibre de Nash peut être, comme Daskalakis l'a montré, presque impossible à calculer. Mais cela ne veut pas dire que le comportement des joueurs est aléatoire. Considérez une grille de rues de la ville où les conducteurs prennent d'innombrables décisions à des dizaines d'intersections. Même si les conducteurs n'évaluent pas toutes les conséquences possibles des décisions alternatives, ils adoptent toujours des stratégies simples - disons, si vous êtes resté assis trop longtemps, tournez dans une rue latérale. Selon Munther Dahleh, directeur associé d'EECS, l'analyse de tels systèmes rapproche la théorie des jeux de son propre domaine, la théorie du contrôle, qui étudie les stratégies de contrôle des systèmes dynamiques tels que les membres des robots et les ailes des avions. Nous avons une vision différente de ces problèmes, dit Dahleh. Au lieu d'imposer la notion d'équilibre et de dire « Quelles stratégies les gens joueraient-ils sous cet équilibre ? », nous regardons le comportement dynamique contrôlé et posons la question « Quelle notion d'équilibre émerge ? »

Dahleh a en effet appliqué les outils de la théorie des jeux à l'analyse des flux de trafic, en étudiant les types de tracés routiers qui peuvent le mieux s'adapter à la fermeture d'itinéraires particuliers. Son approche s'applique également à d'autres systèmes dynamiques à grande échelle, comme le réseau électrique.

Chaque jour, les producteurs d'électricité - les exploitants de centrales nucléaires, de centrales au charbon, de parcs éoliens, etc. Les services publics qui fournissent l'électricité ont également des administrateurs qui décident, sur la base de la demande attendue des consommateurs, la quantité d'électricité à acheter auprès de chaque fournisseur. La production et la consommation d'électricité doivent correspondre exactement ou les conséquences sont désastreuses.

En utilisant les outils de la théorie des jeux pour analyser les incitations des fournisseurs d'électricité et des consommateurs, Dahleh et Mardavij Roozbehani, PhD '08, chercheur principal au Laboratoire des systèmes d'information et de décision, ont montré que les compteurs intelligents à domicile, qui peuvent fournir informations sur les prix au comptant sur le marché de l'électricité et laisser les consommateurs différer les tâches ménagères énergivores jusqu'à ce qu'elles soient les plus abordables, pourraient en fait provoquer des pics de demande qui feraient chuter l'ensemble du réseau.

Dahleh a également collaboré avec Ozdaglar et son mari, l'économiste du MIT Daron Acemoglu, pour analyser comment l'information se propage à travers les populations. Le jeu dans ce cas est celui dans lequel les gens évaluent la vérité ou la fausseté des informations qui leur parviennent, alors qu'ils s'efforcent de maximiser l'exactitude de leurs propres croyances.

Ce sont des questions qui ont été étudiées à la fois en sociologie et en économie, dit Ozdaglar. Traditionnellement, cependant, ces enquêtes partent du principe que toute personne d'une population donnée peut recevoir des informations directement de toute autre personne. Ce que proposent les ingénieurs, soutient Ozdaglar, ce sont des outils bien rodés pour analyser la structure sous-jacente du réseau de la population. La plupart des gens, par exemple, ne reçoivent en fait la plupart de leurs informations que de quelques voisins immédiats du réseau - et ils attribuent différentes probabilités à l'exactitude des revendications des différents voisins.

Dans le passé, je pense que les sciences sociales et l'économie traitaient les problèmes différemment des ingénieurs, dit Dahleh. Maintenant, nous parlons tous de réseaux sociaux – décisions dans les réseaux sociaux, dynamique sur les réseaux – donc je pense que les deux domaines convergent.

cacher