Mathematical Programming Games

Dans de nombreux contextes de prise de décision, un agent égoïste cherche à optimiser son bénéfice compte tenu de certaines contraintes situationnelles. Mathématiquement, la tâche du décideur est souvent formulée comme un problème d'optimisation dont la solution fournit une recommandation prescriptive sur la meilleure décision. Cependant, la prise de décision est rarement une tâche individuelle : chaque décideur égoïste interagit souvent avec d'autres décideurs ayant des intérêts similaires. Cette thèse discute et propose une nouvelle perspective pour capturer la dynamique de la prise de décision stratégique impliquant plusieurs agents résolvant des problèmes d'optimisation. Nous explorons les opportunités offertes par l'interaction entre l'optimisation -en nous concentrant sur la programmation en nombres entiers mixtes (MIP) -et la théorie algorithmique des jeux (AGT) en les analysant à travers le prisme d'un cadre unifié, capable d'intégrer des éléments des deux disciplines. Nous introduisons une taxonomie pour les jeux de programmation mathématique (MPGs), des jeux non coopératifs simultanés où le problème de décision de chaque agent est un problème d'optimisation exprimant un ensemble hétérogène et éventuellement complexe de contraintes. Nous développons nos contributions en considérant l'équilibre de Nash comme le principal concept de solution et fondons notre recherche sur le principe suivant : dans les MPGs, la plausibilité des équilibres de Nash découle de la disponibilité d'outils efficaces pour les calculer et les sélectionner. En conséquence, nous fournissons des algorithmes originaux et des cadres théoriques pour caractériser, calculer et sélectionner les équilibres de Nash dans les MPGs. Tout d'abord, nous abordons le problème du calcul et de la sélection des équilibres dans les jeux de programmation en nombres entiers (IPGs), à savoir les MPGs où chaque joueur résout un programme paramétré en nombres entiers. En introduisant des concepts tels que l'inégalité d'équilibre, l'oracle de séparation d'équilibre, et la fermeture d'équilibre, nous permettons à des outils archétypiques de la programmation en nombres entiers d'acquérir un rôle dans la théorie des jeux. Nous concevons ZERO Regrets, un algorithme de plans coupants pour calculer et sélectionner les équilibres dans les IPGs. Nous testons l'algorithme sur un jeu d'AGT et sur une extension multi-agents du problème du sac à dos, et nous fournissons de nouveaux résultats théoriques et informatiques sur l'efficacité de leurs équilibres. Ensuite, nous présentons Cut-and-Play, un algorithme permettant de calculer les équilibres des jeux réciproquement bilinéaires (RBGs), une classe de MPGs où l'objectif de chaque joueur est linéaire par rapport à ses variables et contient des termes bilinéaires entre ses variables et celles de ses adversaires. L'algorithme calcule les équilibres en exploitant une série d'approximations du problème d'optimisation de chaque joueur et en s'appuyant sur des méthodes de branchement et de plans coupants. Notre approche algorithmique est générale, extensible, et elle s'intègre aux solveurs de programmation mathématique existants. En pratique, elle surpasse les meilleurs algorithmes en termes de temps de calcul et d'efficacité des équilibres. Troisièmement, nous analysons une classe de MPGs parmi les leaders des jeux de Stackelberg (c'est-à-dire des jeux séquentiels leader-followers) et leur application aux marchés de l'énergie. Nous prouvons qu'il est Σp2 difficile de décider si le jeu admet un équilibre, et nous introduisons un algorithme pour calculer et sélectionner ces équilibres. De plus, nous fournissons une étude pratique sur le marché de l'énergie chilien-argentin et offrons des perspectives de gestion basées sur les informations fournies par les équilibres. Enfin, nous présentons ZERO, une bibliothèque C++ modulaire et extensible pour expérimenter avec des RBGs. ZERO fournit une boîte à outils complète d'interfaces de modélisation pour concevoir des RBGs, et des algorithmes pour trouver leurs équilibres de Nash. Notre engagement envers le code source ouvert vise à favoriser le développement futur, méthodologique et pratique, dans le domaine des RBGs.