Liste des articles
Vue 1622 fois
28 février 2024

Optimisation des modèles d'allocation de l'eau : Damien Berriaud (ECL2019) lauréat du concours Veolia « Ecological Transformation Awards »

Doctorant à l’École polytechnique fédérale de Zurich (ETH) en génie électrique et technologies de l’information, Damien Berriaud (ECL2019) a été récompensé en décembre dernier du prix spécial du jury des Ecological Transformation Awards de Veolia, pour ses travaux sur les mécanismes de karma comme solution décentralisée et efficace, au problème d’allocation des ressources en eaux.  Entre théorie des jeux, algorithmes distribués et équilibre de Nash, Damien revient dans le détail sur sa démarche et les applications possibles par rapport aux problématiques de juste allocation des ressources.


Bonjour Damien. Peux-tu nous présenter en quelques lignes ton parcours depuis ton entrée à Centrale Lyon, jusqu’à ta thèse à l’ETH ?

Mes deux années à Centrale m’ont offert la possibilité d’explorer différents domaines scientifiques. Certains enseignements ont bien sûr résonné plus que d’autres : je me suis découvert un goût pour les sciences de l’information et l’électronique, et j’ai confirmé un attrait de longue date pour les mathématiques appliquées. Afin de creuser davantage certains domaines qui avaient éveillé ma curiosité, comme l’informatique quantique ou l’intelligence artificielle, j’ai choisi de troquer ma dernière année lyonnaise contre deux zurichoises et j’ai entamé un master en génie électrique et techniques de l’information à l’ETH. Là-bas, j’ai pu choisir mes cours plus ou moins librement parmi un grand panel de choix : théorie de l’information, théorie des graphes, IA probabiliste, algorithmes quantiques, théorie des jeux, ou encore algorithmes distribués pour n’en citer que quelques-uns.

J’ai enfin eu l’occasion de mener trois projets de recherches différents : un stage d’été en informatique au CERN, un projet de semestre en théorie du choix social, et enfin mon mémoire de fin d’étude entre apprentissage et théorie des jeux. Ces expériences fructueuses m’ont convaincu de poursuivre mes études et j’ai entamé début janvier un doctorat dans un des labos qui m’avaient accueilli.

En décembre dernier, tu as participé à un concours organisé par Veolia qui réunissait les travaux de fin d’année d’élèves de Grandes Ecoles et d’universités venus des 4 coins du monde, avec comme fil conducteur de favoriser la transformation écologique. Peux-tu nous pitcher en quoi consiste ton projet et comment concrètement peut-il s’appliquer à des problématiques de transition ?

Mon projet prend sa source dans un exercice de théorie des jeux lors duquel je suis tombé sur le concept loufoque de jeux de karma. Le but de l’exercice était d’optimiser le contentement d’une population d’automobilistes arrivant tous les jours à différentes intersections avec des urgences aléatoires. Chaque jour, les conducteurs placent, en fonction de leur urgence, une mise de karma, une monnaie artificielle sans valeur réelle. La plus haute mise obtient la priorité à l’intersection en échange d’un paiement, tandis que les autres usagers doivent s’arrêter, mais reçoivent une compensation sous la forme de karma.

Intuitivement, le karma incarne un moyen d’échanger l’accès immédiat à une ressource contre la promesse de son accès futur. En choisissant des règles de paiement et de redistribution appropriées, on peut s’assurer d’aligner les intérêts personnels et sociétaux à l’équilibre de Nash du mécanisme. Cette notion de théorie des jeux, rendue célèbre par le mathématicien et économiste éponyme, caractérise une population d’agents égoïstes et rationnels au sein de laquelle nul n’a intérêt à changer de stratégie individuellement.

Intrigué par ces mécanismes promettant d’allier équité et efficacité, j’ai contacté le doctorant en charge de l’exercice, Ezzat Elokda, afin de réaliser mon mémoire de fin d’étude sous sa supervision. Il m’a alors proposé d’étudier les stratégies de mise que les joueurs devraient adopter avec le peu d’information à leur disposition, et d’analyser les conditions garantissant la convergence de leur apprentissage conjoint vers l’équilibre de Nash du jeu. En identifiant une stratégie très simple avec des garanties théoriques, individuelles et collectives, mon travail, disponible sur Arxiv au lien suivant, ouvre la porte à l’adoption pratique de mécanismes de karma.

 

Quel est le rapport avec la transition écologique dans tout ça ? Dans un monde où les ressources se raréfient, le choix de leur allocation devient une question sociétale de première importance. C’est d’autant plus vrai pour des ressources de première nécessité, comme l’eau ou la nourriture par exemple, pour lesquelles une mauvaise allocation peut se révéler dramatique. En mettant l’équité au premier plan et en implémentant un chacun-son-tour dynamique, les mécanismes de karma constituent une élégante solution, décentralisée et efficace, au problème d’allocation de ces ressources jugées critiques.

Le jury Veolia a récompensé ton projet avec une mention spéciale. Comment ce dernier a t il justifié sa décision ?

Deux facteurs ont sans doute contribué à cette décision. Le premier fut mon choix de présenter les jeux de karma au travers de l’exemple de l’eau. Bien sûr centrale aux activités de VEOLIA, la question de la gestion de l’eau a gagné en importance au cours des deux dernières années, et dans la représentation médiatique, et dans le discours politique (l’exemple des méga-bassines est particulièrement criant). C’est notamment dû à deux étés particulièrement secs, lors desquels les limitations des ressources hydriques en France métropolitaine ont commencé à se manifester dans le quotidien de tout un chacun. C’est aussi le fait d’une situation critique prolongée à Mayotte, avec l’instauration des mois durant de tours d’eau pour prévenir la déplétion des ressources en eau potable. Enfin, sur la scène internationale, on pense également aux sécheresses historiques qui ont frappé l’Afrique du Sud, le Chili, ou encore l’Uruguay, où de l’eau salée a dû être utilisée pour le réseau d’eau potable faute de réserves suffisantes en eau douce.

 

Le second facteur, et peut-être le plus déterminant, fut l’effet de surprise. Les attentes du jury se reflètent sans doute dans le choix des autres lauréats (c.f. le communique officiel de Veolia), avec des projets pratiques répondant à des problématiques ciblées de la transition écologique. Le caractère très théorique de mon travail l’a sans conteste rendu singulier, et s’il est moins directement applicable que ceux des autres candidats, il propose potentiellement un changement de paradigme plus important. Je crois que c’est ce potentiel, ainsi que la prise de risque sous-jacente, que le jury a voulu récompenser par une mention spéciale.

Cérémonie des Trophées de la transformation écologique au siège social de Veolia en décembre 2023

Qu’est-ce que t’apporte ce genre de reconnaissance ?

C’était à ça de me faire gagner un beau vélo ! Blague à part, cela ouvre bien sûr une possibilité de partenariat avec Veolia : il reste fort à faire pour combler le vide entre théorie et pratique, et proposer un mécanisme de karma qui réponde au cahier des charges concret d’un opérateur réseau.

Plus généralement, je crois qu’il n’y a rien de plus excitant pour un théoricien que de voir une idée s’échapper de sa bulle académique et se confronter aux conditions du monde réel. En plus d’établir le dialogue avec un premier acteur économique d’importance, cette reconnaissance donne de la crédibilité et de la visibilité aux mécanismes de karma, et ouvre potentiellement la voie à leur adoption. Et qui sait : peut-être le prochain intéressé sera un lecteur de ces lignes ?

Tes travaux de recherche s’intéressent au choix social computationnel.  Qu’est-ce qui t’intéresse dans cette « approche » ?  

De manière générale, le choix social computationnel est un domaine scientifique à l’intersection de l’informatique théorique, l’économie et la théorie politique, qui étudie la formation de décisions collectives à partir de préférences individuelles. Les procédures de vote, de partage, ou d’allocation constituent le cœur de ce champ d’étude, et sont analysées sous l’angle de leur efficacité, équité, caractère manipulable ou encore leur complexité algorithmique.

Mon attrait pour le choix social s’explique en partie par la variété d’outils que son étude met en jeu. Parfois, cela passe par la simulation du problème afin d’en obtenir une compréhension intuitive ou de vérifier les performances d’un premier algorithme. De temps en temps, on peut directement se lancer dans une preuve et jongler entre analyse, optimisation, théorie des jeux ou des graphes, combinatoire et probabilités. Il n’est cependant pas rare qu’il faille essayer dix approches différentes avant d’obtenir la clef, la bonne idée qui débloque le problème.

 

Mais plus encore que ces outils, je crois que c’est l’enjeu derrière le choix social qui me fascine : nous sommes des animaux sociaux, et pourtant nombre de nos malheurs découlent de notre incapacité à prendre des choix collectivement de manière juste et efficace. Tiens, un exemple très centralien : la procédure de mises pour le « choix » de cours d’approfondissement. Et si je vous disais qu’il existe des solutions plus justes et satisfaisantes que le statu quo (voir cet article par exemple) ?

Au final, il n’est pas question d’éliminer la corruption de l’homme par la société – je ne suis pas certain d’être Rousseauiste-, mais seulement de déterminer des gardes-fou pour nos prises de décisions collectives : voila, me semble-t-il, tout l’enjeu du choix social.

Tu as notamment appliqué cette approche pour réfléchir à l’organisation d’un plan de table pour un dîner. Peux-tu nous expliquer en quoi cela consiste ?

En effet, j’ai eu l’occasion de travailler sur le problème suivant, plus léger, mais présent au quotidien : comment asseoir ses convives autour d’une table ronde de telle sorte que nul couple d’individus ne souhaite échanger de place ? Nous avons étudié le problème d’existence de tels arrangements stables, ainsi que la complexité algorithmique nécessaire pour les trouver.

Les mauvaises nouvelles tout d’abord : il existe des instances de préférences très simples (préférences binaires, avec beaucoup de clones) où aucun arrangement n’est stable. Pire encore : déterminer, pour des préférences données, s’il existe un arrangement stable est un problème NP-difficile et requiert un temps de calcul exponentiel (dans l'hypothèse où P≠NP).

Et du côté des bonnes nouvelles alors ? C’est maigre : ajouter des clones ne complexifie pas grandement le problème, et vous n’aurez jamais de soucis si, au lieu d’inviter cinq amis au restaurant, vous venez toujours à quatre ou à six.

Je ne veux pas divulgâcher le reste de nos résultats (l’article complet, récompensé lors de la conférence Web and Interenet Economics 2023, est disponible sur Arxiv pour les curieux), mais je pense que ce projet caractérise bien le côté jeu du choix social, tandis que l’étude des mécanismes de karma se situe plutôt du côté sérieux.

Remise de prix en décembre 2023 lors de la conférence Web and Interenet Economics.

Peux-tu nous parler du doctorat que tu débutes en ce début d’année ?

C’est justement dans le laboratoire qui m’avait accueilli pour ce travail sur les arrangements de table que je viens de commencer mon doctorat. Derrière le nom de DISCO (comprendre « distributed computing») se cachent en réalité trois pôles différents : une première partie de notre groupe étudie les Graph Neural Networks (GNNs) et tente d’étendre les performances singulières des réseaux de neurones profonds aux données sous forme de graphes. L’étude des systèmes distribués occupe une seconde partie du labo, avec les problématiques de consensus décentralisé ou de tolérance aux pannes en son cœur, et les technologies de blockchains pour figure de proue. Enfin, l’analyse théorique des réseaux constitue un dernier pôle de recherche et regroupe les questions du choix social, l’étude des réseaux financiers ou sociaux, ou encore l’analyse des algorithmes distribués.

C’est vers ce dernier pôle que je m’oriente, souhaitant en partie poursuivre mes recherches sur les problèmes d’allocations, mais aussi plus généralement sur les mécanismes d’incitations et les questions démocratiques. L’enjeu derrière est éminemment social et politique : il s’agit au fond de trouver des systèmes d’organisation collective plus justes et efficaces que le statu quo.

Dernière question avant de se quitter. Si on se reparle dans 5 ans, qu’aimerais-tu pouvoir me raconter sur ton début de carrière ?

Ce n’est jamais évident de se projeter « aussi loin » quand on est jeune : des germes de projets à foison, des portes qui s’ouvrent ou se referment au gré du vent, plus de doutes que de certitudes aussi. Je crois toutefois que cet épisode avec Veolia représente bien le devenir que j’aimerais construire : il ne s’agit pas d’obtenir de la reconnaissance pour le fruit de mon travail (bien que cela soit toujours agréable, entendons-nous bien), mais plutôt d’établir un dialogue entre recherche et société et tenter d’apporter des réponses, par la science, aux maux de notre temps.

 

Mais laissons-nous rêver : j’aimerais pouvoir raconter les premiers essais grandeur nature d’un système de karma, en partenariat avec Veolia par exemple. Et tiens, pourquoi pas : un abonnement de transport en commun à base de karma, incitant à la flexibilité et à l'étalement de nos déplacements. Allez, doigts croisés, on se retrouve dans cinq ans.

Auteur

Après son diplôme de Centrale Lyon et un master en génie électrique et techniques de l'information à l'ETH, Damien poursuit actuellement ses études à Zurich avec un Doctorat en informatique théorique et théorie des jeux.

A lire

Commentaires

Aucun commentaire

Vous devez être connecté pour laisser un commentaire. Connectez-vous.