HEYMANN Benjamin

Notre article concerne le calcul des équilibres de Nash des enchères au premier prix avec des valeurs corrélées. Bien qu'il existe plusieurs méthodes de calcul des équilibres pour les enchères avec des valeurs indépendantes, la corrélation des valeurs des enchérisseurs introduit des complications significatives qui rendent les méthodes existantes insatisfaisantes en pratique. Notre contribution est un pas en avant pour combler cette lacune : inspiré par le processus de jeu fictif de Brown et Robinson, nous présentons une heuristique d'apprentissage - que nous appelons enchère fictive (FB) - pour estimer les équilibres de Bayes-Nash des enchères au premier prix avec des valeurs corrélées, et nous évaluons la performance de cette heuristique sur plusieurs exemples pertinents.

La séparation d de Pearl est une notion fondamentale pour étudier l'indépendance conditionnelle entre les variables aléatoires. Nous définissons la séparation conditionnelle topologique et nous montrons qu'elle est équivalente à la séparation d, étendue au-delà des graphes acycliques, qu'ils soient finis ou infinis.

La d-séparation de Pearl est une notion fondamentale pour étudier l'indépendance conditionnelle entre les variables aléatoires sur les graphes acycliques dirigés. Pearl a défini la d-séparation de deux sous-ensembles conditionnellement à un troisième. Nous montrons comment la d-séparation peut être étendue au-delà des graphes acycliques et peut être exprimée et caractérisée comme une relation binaire entre sommets.

Nous proposons une alternative à la représentation arborescente des jeux de forme extensive. Les jeux en forme de produit représentent l'information avec des σ-fields sur un ensemble de produits, et ne nécessitent pas une description explicite de la temporalité du jeu, contrairement aux jeux en forme extensive sur des arbres. Cette représentation englobe les jeux avec un continuum d'actions, de hasard et de joueurs, ainsi que les jeux pour lesquels l'ordre de jeu ne peut être déterminé à l'avance. Nous adaptons et prouvons le théorème de Kuhn - concernant l'équivalence entre les stratégies mixtes et comportementales sous un rappel parfait - pour les jeux en forme de produit avec des ensembles d'actions continus.

La résolution optimale d'un problème de bandit à bras multiples souffre de la malédiction de la dimensionnalité. En effet, le recours à la programmation dynamique conduit à une croissance exponentielle du temps de calcul, à mesure que le nombre de bras et l'horizon augmentent. Nous introduisons une heuristique de décomposition-coordination, DeCo, qui transforme le problème initial en problèmes de bandit à un bras coordonnés en parallèle. En conséquence, nous obtenons un temps de calcul qui est essentiellement linéaire dans le nombre de bras. En outre, la décomposition fournit une limite inférieure théorique sur le regret. Pour le cas du bandit à deux bras, la programmation dynamique fournit la solution exacte, qui est presque égalée par l'heuristique DeCo. De plus, dans les simulations numériques avec jusqu'à 100 tours et 20 armes, DeCo surpasse les algorithmes classiques (échantillonnage de Thompson et limite supérieure de confiance de Kullback-Leibler) et correspond presque à la limite inférieure théorique du regret pour 20 armes.

L'inférence des conséquences potentielles d'un événement non observé est une question scientifique fondamentale. À cette fin, le célèbre do-calcul de Pearl fournit un ensemble de règles d'inférence permettant de déduire une probabilité d'intervention à partir d'une probabilité d'observation. Dans ce cadre, les relations causales primitives sont codées comme des dépendances fonctionnelles dans un modèle causal structurel (SCM), qui est généralement représenté dans un graphe acyclique dirigé (DAG) en l'absence de cycles. Dans cet article, en revanche, nous capturons la causalité sans référence aux graphes ou aux dépendances fonctionnelles, mais avec des champs d'information et le modèle intrinsèque de Witsenhausen. Les trois règles du do-calcul se réduisent à une condition suffisante unique pour l'indépendance conditionnelle, la séparation topologique, qui présente des avantages théoriques et pratiques intéressants par rapport à la d-séparation. Grâce à cette règle unique, nous pouvons traiter des systèmes qui ne peuvent pas être représentés par des DAG, par exemple des systèmes comportant des cycles et/ou des bords "parasites". Nous traitons un exemple qui ne peut être traité - dans la mesure de nos connaissances - avec les outils de la littérature actuelle. Nous expliquons également pourquoi, en présence de cycles, la théorie de l'inférence causale peut nécessiter différents outils, selon que les variables aléatoires sont discrètes ou continues.

L'inférence des conséquences potentielles d'un événement non observé est une question scientifique fondamentale. À cette fin, le célèbre do-calcul de Pearl fournit un ensemble de règles d'inférence pour dériver une probabilité d'intervention à partir d'une probabilité d'observation. Dans ce cadre, les relations causales primitives sont codées sur un graphe acyclique dirigé (DAG), ce qui peut être limitatif pour certaines applications. Dans cet article, nous capturons la causalité sans référence à un graphe et nous étendons les règles du do-calcul aux systèmes qui ne possèdent pas un ordre causal fixe. À cette fin, nous introduisons un nouveau cadre qui s'appuie sur la théorie développée par Witsenhausen pour le contrôle stochastique multi-agent. La correspondance entre les graphes et le modèle intrinsèque dit de Witsenhausen est naturelle : les primitives du problème sont les champs d'information des agents. Les variables aléatoires sont synthétisées par les agents dont les stratégies encodent les contraintes informationnelles. Dans l'ensemble, notre cadre offre un langage plus riche que les DAGs et fournit un do-calcul généralisé.

Nous abordons le problème de l'amélioration des stratégies des enchérisseurs dans les enchères de maximisation des revenus en fonction des antécédents. Nous introduisons une méthode simple et générique pour concevoir de nouvelles stratégies d'enchères si le vendeur utilise les enchères passées pour optimiser son mécanisme. Cette stratégie fonctionne avec des distributions de valeurs générales, avec des enchérisseurs asymétriques et pour différents mécanismes de maximisation des revenus. En outre, elle peut être rendue robuste aux erreurs d'approximation d'échantillon de la part du vendeur. Il en résulte une forte augmentation de l'utilité pour les soumissionnaires, qu'ils aient une connaissance totale ou partielle de leurs concurrents. Dans le cas où l'acheteur n'a aucune information sur la concurrence, nous proposons une stratégie simple et agnostique qui est robuste aux changements de mécanisme et à l'optimisation locale (par opposition à globale) des prix de réserve par le vendeur. Dans des exemples de type manuel, par exemple avec des distributions de valeurs uniformes et deux enchérisseurs, cette stratégie sans information latérale et indépendante du mécanisme produit une augmentation énorme de 57% de l'utilité de l'acheteur pour des enchères paresseuses à second prix sans réserve. Dans le cas symétrique i.i.d, nous montrons l'existence et l'unicité d'un équilibre de Nash dans la classe de stratégies que nous considérons pour les enchères paresseuses à second prix, ainsi que les stratégies d'ombrage explicites correspondantes. Notre approche fonctionne également pour les enchères de Myerson par exemple. A cet équilibre de Nash, l'utilité de l'acheteur est la même que dans une enchère à second prix sans réserve. Notre approche donne également des solutions optimales lorsque les acheteurs sont limités dans la classe des stratégies d'ombrage qu'ils peuvent utiliser, une contrainte réaliste dans les applications pratiques. Le cœur de notre approche est de voir les enchères optimales en pratique comme un jeu de Stackelberg où l'acheteur est le leader, car il est le premier à bouger (ici enchérir) alors que le vendeur est le suiveur car il n'a aucune information préalable sur l'enchérisseur.

Nous énonçons et prouvons le théorème d'équivalence de Kuhn pour une nouvelle représentation des jeux, la forme intrinsèque. Tout d'abord, nous introduisons les jeux de forme intrinsèque où l'information est représentée par des σ-fields sur un ensemble produit. Dans ce but, nous adaptons aux jeux la représentation intrinsèque que Witsenhausen a introduite en théorie du contrôle. Ces jeux intrinsèques ne nécessitent pas une description explicite de la temporalité du jeu, contrairement aux jeux de forme extensive sur les arbres. Deuxièmement, nous prouvons, pour cette nouvelle représentation plus générale des jeux, que les stratégies comportementales et mixtes sont équivalentes sous rappel parfait (théorème de Kuhn). Comme la forme intrinsèque remplace la structure arborescente par une structure produit, la manipulation de l'information est plus facile. Cela fait de la forme intrinsèque un nouvel outil précieux pour l'analyse des jeux avec information.

Dans les enchères de publicité par affichage, une opportunité d'affichage unique peut déclencher de nombreuses demandes d'enchères envoyées au même acheteur. La duplication des demandes d'enchères est un problème : les agents d'enchères programmatiques peuvent enchérir contre eux-mêmes. Dans un cadre simplifié d'enchères unifiées au second prix, la solution optimale pour l'enchérisseur consiste à randomiser l'offre, ce qui est assez inhabituel. Nos résultats motivent le passage récent à une enchère unifiée au premier prix en montrant qu'une enchère unifiée au second prix aurait pu être préjudiciable à tous les participants.

Une grande partie de l'inventaire publicitaire en ligne est vendue aux enchères en temps réel. Les algorithmes d'enchères doivent estimer précisément la valeur de chaque affichage. De nombreux modèles d'enchères estiment cette valeur comme la probabilité qu'une vente soit attribuée à cet affichage, mais cette approche ne tient pas compte du fait qu'un utilisateur peut se voir présenter une séquence de plusieurs affichages. En mélangeant les outils du raisonnement causal et de l'apprentissage par renforcement pour modéliser cette séquence d'enchères, nous dérivons une règle simple pour améliorer cette estimation. Nous testons le changement en ligne dans un environnement de production et les résultats valident l'approche. Nous pensons que cette méthodologie pourrait être adaptée pour s'attaquer au problème notoirement difficile de la construction d'un enchérisseur incrémental.

L'attribution - le mécanisme qui attribue des crédits de conversion aux interactions marketing individuelles - est l'un des principaux sujets de recherche en marketing numérique. En effet, l'attribution est utilisée partout dans le marketing en ligne, que ce soit pour les décisions budgétaires ou pour la conception des soumissionnaires algorithmiques sur lesquels l'annonceur s'appuie pour acheter son inventaire. Pourtant, il reste encore à trouver une définition de l'attribution qui fasse l'unanimité dans la communauté du marketing. Dans cet article, nous nous concentrons sur le problème rencontré par un enchérisseur qui est soumis à une boîte noire d'attribution décidée par l'annonceur et qui doit la convertir en une offre. Ceci introduit naturellement un second niveau d'attribution, réalisé en interne par l'enchérisseur. Nous formalisons d'abord un concept de solution souvent utilisé implicitement pour cette tâche. Ensuite, nous caractérisons la solution de ce problème que nous appelons l'attribution interne de base. De plus, nous montrons qu'elle peut être calculée à l'aide d'une méthode à point fixe. Il est intéressant de noter que l'attribution centrale est basée sur une notion de marginalité qui diffère des définitions précédemment utilisées telles que la marginalité contrefactuelle.

Nous présentons un algorithme pour gérer l'optimisation sur un horizon long d'un micro-réseau électrique incluant un système de stockage d'énergie par batterie. Alors que la batterie est un composant important et coûteux du micro-réseau, son processus de vieillissement n'est souvent pas pris en compte par le système de gestion de l'énergie, principalement en raison des défis de modélisation et de calcul. Nous abordons l'aspect informatique par une nouvelle approche combinant la programmation dynamique, la décomposition et les techniques de relaxation. Nous illustrons cette méthode de "poids adaptatif" par des simulations numériques d'un modèle de micro-réseau fictif. Par rapport à une résolution directe par programmation dynamique, notre algorithme réduit le temps de calcul de plus d'un ordre de grandeur, peut être parallélisé et permet des implémentations en ligne. Nous pensons que cette approche peut être utilisée pour d'autres applications présentant des variables rapides et lentes.

-Nous proposons une nouvelle méthode pour le problème de gestion de l'énergie des micro-réseaux en introduisant une formulation à temps continu et à horizon mobile. Le problème de gestion de l'énergie est formulé comme un problème de contrôle optimal déterministe (OCP). Nous résolvons ce problème à l'aide de deux approches classiques : la méthode directe [1] et le principe de programmation dynamique (DPP) de Bellman [2]. Dans les deux cas, nous utilisons la boîte à outils de contrôle optimal BOCOP [3] pour les simulations numériques. Pour l'approche DPP, nous mettons en œuvre un schéma semi-lagrangien [4] adapté pour gérer l'optimisation des temps de commutation pour les modes marche/arrêt du générateur diesel. L'approche DPP permet une modélisation précise et est peu coûteuse en termes de calcul. Elle trouve l'optimum global en moins de 3 secondes, un temps de calcul similaire à celui de l'approche MILP (Mixed Integer Linear Programming) utilisée dans [5]. Nous obtenons cette performance en introduisant une astuce basée sur le principe du maximum de Pontryagin (PMP). Cette astuce augmente la vitesse de calcul de plusieurs ordres et améliore également la précision de la solution. À des fins de validation, des simulations sont effectuées à l'aide d'ensembles de données provenant d'un micro-réseau isolé réel situé dans le nord du Chili. Les résultats montrent que la méthode DPP est très bien adaptée à ce type de problème par rapport à l'approche MILP.

Nous présentons certains aspects clés de la modélisation des marchés de gros de l'électricité et concentrons plus particulièrement notre attention sur les enchères et la conception de mécanismes. Certains des résultats découlant de ces modèles sont le calcul d'une allocation optimale pour l'opérateur de système indépendant, l'étude des équilibres (existence et unicité en particulier) et la conception de mécanismes pour augmenter le surplus social. D'un point de vue plus général, ce domaine de recherche fournit des indices pour discuter de la manière dont le marché de gros de l'électricité devrait être réglementé. Nous commençons par une introduction générale et présentons ensuite certains résultats obtenus récemment par les auteurs. Nous exposons également brièvement certains travaux connexes en cours. À titre d'exemple, une section est consacrée au calcul de la fonction de réponse de l'opérateur de système indépendant pour un cadre binodal symétrique avec des fonctions de coût de production linéaires par morceaux.

Nous proposons une nouvelle méthode pour le problème de gestion de l'énergie des micro-réseaux en introduisant une formulation non linéaire, à temps continu et à horizon glissant. La méthode est sans linéarisation et donne une solution optimale globale avec des contrôles en boucle fermée. Elle permet la modélisation des commutateurs. Nous formulons le problème de gestion de l'énergie comme un problème de contrôle optimal déterministe (OCP). Nous résolvons (OCP) avec deux approches classiques : la méthode directe et le principe de programmation dynamique de Bellman (DPP). Dans les deux cas, nous utilisons la boîte à outils de contrôle optimal Bocop pour les simulations numériques. Pour l'approche DPP, nous mettons en œuvre un schéma semi-lagrangien adapté à l'optimisation des temps de commutation pour les modes marche/arrêt du générateur diesel. L'approche DPP permet une modélisation précise et est peu coûteuse en termes de calcul. Elle trouve l'optimum global en moins d'une seconde, un temps de calcul similaire à celui nécessaire avec une approche de programmation linéaire mixte en nombres entiers utilisée dans les travaux précédents. Nous obtenons ce résultat en introduisant une "astuce" basée sur le principe du maximum de Pontryagin. Cette astuce réduit le temps de calcul de plusieurs ordres et améliore la précision de la solution. À des fins de validation, nous avons effectué des simulations sur des ensembles de données provenant d'un micro-réseau isolé réel situé dans le nord du Chili. Le résultat montre que la méthode DPP est très bien adaptée à ce type de problème.Projet iCODE : "Systèmes à grande échelle et réseaux intelligents : prise de décision distribuée". Programme Gaspar Monge pour l'Optimisation et la Recherche Opérationnelle (PGMO) laboratoire Dauphine CREST EDF R&D Finance des Marches d'Energies CONICYT/FONDAP/1511001.

Nous proposons une nouvelle formulation de contrôle stochastique pour le problème de la gestion de l'énergie des micro-réseaux et nous étendons les travaux précédents sur la stratégie à horizon mobile en temps continu à la demande incertaine. Nous modélisons la dynamique de la demande par une équation différentielle stochastique. Nous décomposons cette dynamique en trois termes : une dérive moyenne, un terme de retour à la moyenne dépendant du temps et un bruit brownien. Nous utilisons BOCOPHJB pour les simulations numériques. Cette boîte à outils de contrôle optimal met en œuvre un schéma semi-lagrangien et gère l'optimisation des temps de commutation requis pour les modes marche/arrêt discrets du générateur diesel. Le schéma permet une modélisation précise et est peu coûteux en termes de calcul tant que la dimension de l'état est petite. Comme décrit dans les travaux précédents, nous utilisons une astuce pour réduire la recherche des valeurs de contrôle optimales à six points. Cela permet d'augmenter la vitesse de calcul de plusieurs ordres. Nous comparons cette nouvelle formulation avec l'approche de contrôle déterministe introduite dans [1] en utilisant les données d'un micro-réseau isolé situé dans le nord du Chili.

Nous présentons certains aspects clés de la modélisation des marchés de gros de l'électricité et concentrons plus particulièrement notre attention sur les enchères et la conception de mécanismes. Certains des résultats découlant de ces modèles sont le calcul d'une allocation optimale pour l'opérateur de système indépendant, l'étude des équilibres (existence et unicité en particulier) et la conception de mécanismes pour augmenter le surplus social. D'un point de vue plus général, ce domaine de recherche fournit des indices pour discuter de la manière dont le marché de gros de l'électricité devrait être réglementé. Nous commençons par une introduction générale et présentons ensuite certains résultats obtenus récemment par les auteurs. Nous exposons également brièvement certains travaux connexes en cours. À titre d'exemple, une section est consacrée au calcul de la fonction de réponse de l'opérateur de système indépendant pour un cadre binodal symétrique avec des fonctions de coût de production linéaires par morceaux.

Motivés par le pouvoir de marché sur le marché de l'électricité, nous introduisons un mécanisme conçu dans [1] pour des marchés simplifiés de deux agents avec des fonctions de coût de production linéaires. Dans les enchères d'approvisionnement standard, le pouvoir de marché résultant des pertes de transmission quadratiques permet aux producteurs de faire des offres supérieures à leur valeur réelle (c'est-à-dire à la valeur de l'électricité).

Nous proposons une nouvelle formulation de contrôle stochastique pour le problème de la gestion de l'énergie des micro-réseaux et nous étendons les travaux précédents sur la stratégie à horizon mobile en temps continu à la demande incertaine. Nous modélisons la dynamique de la demande par une équation différentielle stochastique. Nous décomposons cette dynamique en trois termes : une dérive moyenne, un terme de retour à la moyenne dépendant du temps et un bruit brownien. Nous utilisons BOCOPHJB pour les simulations numériques. Cette boîte à outils de contrôle optimal met en œuvre un schéma semi-lagrangien et gère l'optimisation des temps de commutation requis pour les modes marche/arrêt discrets du générateur diesel. Le schéma permet une modélisation précise et est peu coûteux en termes de calcul tant que la dimension de l'état est petite. Comme décrit dans les travaux précédents, nous utilisons une astuce pour réduire la recherche des valeurs de contrôle optimales à six points. Cela permet d'augmenter la vitesse de calcul de plusieurs ordres. Nous comparons cette nouvelle formulation avec l'approche de contrôle déterministe introduite dans [1] en utilisant les données d'un micro-réseau isolé situé dans le nord du Chili.

Nous présentons notre contribution sur l'optimisation et la régulation de la production d'électricité. La première partie traite du système de gestion de l'énergie (EMS) d'un micro-réseau. Nous formulons le programme EMS comme un problème de contrôle optimal en temps continu et résolvons ensuite ce problème par programmation dynamique en utilisant BocopHJB, un solveur développé pour cette application. Nous montrons qu'une extension de cette formulation à un cadre stochastique est possible. La dernière section de cette partie présente l'algorithme de programmation dynamique à poids adaptatifs, un algorithme pour les problèmes d'optimisation avec différentes échelles de temps. Nous utilisons cet algorithme pour intégrer le vieillissement des batteries dans le SGE.La deuxième partie est consacrée aux marchés de réseau, et en particulier aux marchés de gros de l'électricité. Nous introduisons un mécanisme pour traiter le pouvoir de marché exercé par les producteurs d'électricité, et ainsi augmenter le bien-être des consommateurs. Nous étudions ensuite certaines propriétés mathématiques des problèmes d'optimisation des agents (producteurs et opérateur de système). Dans le dernier chapitre, nous présentons quelques résultats d'existence et d'unicité d'équilibre de Nash pur pour une classe de jeux bayésiens à laquelle appartiennent certains marchés de réseaux. Nous fournissons quelques informations supplémentaires sur BocopHJB (le solveur numérique développé et utilisé dans la première partie de la thèse) dans l'annexe.

Nous présentons notre contribution sur la régulation et l’optimisation de la production d’électricité.La première partie concerne l’optimisation de la gestion d’un micro réseau. Nous formulons le programme de gestion comme un problème de commande optimal en temps continu, puis nous résolvons ce problème par programmation dynamique à l’aide d’un solveur développé dans ce but : BocopHJB. Nous montrons que ce type de formulation peut s’étendre à une modélisation stochastique. Nous terminons cette partie par l’algorithme de poids adaptatifs, qui permet une gestion de la batterie du micro réseau intégrant le vieillissement de celle-ci. L’algorithme exploite la structure à deux échelles de temps du problème de commande.La seconde partie concerne des modèles de marchés en réseaux, et en particulier ceux de l’électricité. Nous introduisons un mécanisme d’incitation permettant de diminuer le pouvoir de marché des producteurs d’énergie, au profit du consommateur. Nous étudions quelques propriétés mathématiques des problèmes d’optimisation rencontrés par les agents du marché (producteurs et régulateur). Le dernier chapitre étudie l’existence et l’unicité des équilibres de Nash en stratégies pures d’une classe de jeux Bayésiens à laquelle certains modèles de marchés en réseaux se rattachent. Pour certains cas simples, un algorithme de calcul d’équilibre est proposé.Une annexe rassemble une documentation sur le solveur numérique BocopHJB.

Le package original Bocop implémente une méthode d'optimisation locale. Le problème de contrôle optimal est approximé par un problème d'optimisation en dimension finie (NLP) utilisant une discrétisation temporelle (l'approche de transcription directe). Le problème NLP est résolu par le logiciel bien connu Ipopt, en utilisant des dérivées exactes éparses calculées par Adol-C. Le second package BocopHJB implémente une méthode d'optimisation globale. Comme pour l'approche de programmation dynamique, le problème de contrôle optimal est résolu en deux étapes. D'abord, nous résolvons l'équation de Hamilton-Jacobi-Bellman satisfaite par la fonction de valeur du problème. Ensuite, nous simulons la trajectoire optimale à partir de toute condition initiale choisie. L'effort de calcul est essentiellement pris par la première étape, dont le résultat, la fonction de valeur, peut être stocké pour les simulations de trajectoire suivantes.