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.

Abstract

In many decision-making settings, a selfish agent seeks to optimize its benefit given some situational constraints. Mathematically, the decision-maker's task is often formulated as an optimization problem whose solution provides a prescriptive recommendation on the best decision. However, decision-making is rarely an individual task: each selfish decision-maker often interacts with other similarly self-interested decision-makers. This thesis discusses and proposes a novel perspective to capture the dynamics of multi-agent strategic decision-making involving multiple agents solving optimization problems. We explore the opportunities offered by the interplay of Mathematical Optimization –specifically Mixed-Integer Programming (MIP) –and Algorithmic Game Theory (AGT) by analyzing them through the lenses of a unified framework capable of integrating elements of the two disciplines. We introduce the taxonomy of Mathematical Programming Games (MPGs), simultaneous non-cooperative games where each agent decision problem is an optimization problem expressing a heterogeneous and possibly complex set of constraints. We develop our contributions considering the Nash equilibrium as the primary solution concept and ground our research in the following principle: in MPGs, the plausibility of Nash equilibria stems from the availability of efficient tools to compute and select them. Accordingly, we provide original algorithms and theoretical frameworks to characterize, compute and select Nash equilibria in MPGs. First, we tackle the problem of computing and selecting equilibria in Integer Programming Games (IPGs), namely MPGs where each player solves a parametrized integer program. By devising concepts such as equilibrium inequality, equilibrium separation oracle, and equilibrium closure, we let archetypical tools of integer programming acquire a game-theoretic role. We design ZERO Regrets, a cutting plane algorithm for computing and selecting equilibria in IPGs. We test the algorithm on a game from AGT and a multi-agent extension of the knapsack problem and further provide novel theoretical and computational results on the efficiency of equilibria. Second, we introduce Cut-and-Play, an algorithm to compute equilibria for ReciprocallyBilinear Games (RBGs), a class of MPGs where each player's objective is linear in its variables and contains bilinear terms among the player's variables and its opponents' ones. The algorithm computes equilibria by exploiting a series of approximations of each player's optimization problem and leveraging branching and cutting plane methods. Our algorithmic approach is general and extensible, and it integrates with existing mathematical programming solvers; in practice, it outperforms the state-of-the-art algorithms in both computing times and equilibria efficiency. x Third, we analyze a class of MPGs among the leaders of Stackelberg Games (i.e., sequential leader-followers games) and their application in energy markets. We prove it is Σp2-hard to decide if the game admits an equilibrium and introduce an algorithm for computing and selecting equilibria. Further, we provide a real-world study on the Chilean-Argentinian energy market and deliver managerial insights based on the information equilibria provide. Finally, we present ZERO, a modular and extensible C++ library for experimenting with RBGs. ZERO provides a comprehensive toolkit of modeling interfaces to design RBGs, and several algorithms to compute their Nash equilibria. Our commitment to open-source aims at fostering methodological and practical advancements in the area of MPGs