Algorithmic and Tacit Coordination Among Artificial Learners

Un enjeu central dans l’étude des systèmes multi-agents est de comprendre comment des agents égoïstes peuvent collaborer et manifester une intelligence collective afin de maximiser leur bien-être. Cette problématique est particulièrement pertinente dans des scénarios où il existe une tension entre les intérêts individuels et le bien commun. La théorie des jeux offre un cadre solide pour étudier la coordination tacite parmi des agents artificiels dans des contextes non coopératifs. Cette thèse se penche sur les dynamiques complexes menant des équilibres de Nash non Pareto-optimaux vers des stratégies Pareto-optimales, dans le cadre d’un jeu de coordination. Elle s’appuie sur trois études détaillées, chacune explorant des défis et opportunités uniques dans les simulations multi-agents et l’émergence de comportements algorithmiques.Premièrement, nous introduisons un méta-algorithme pour générer des données synthétiques réalistes d’enchères multi-niveaux. Pour relever les défis posés par la nature à haute car-dinalité, multi-niveaux et discrète de ces structures, nous avons recours à une approche d’apprentissage profond hiérarchique basée sur les réseaux antagonistes génératifs et BidNet, un modèle prédictif des distributions d’offres conditionnelles fondé sur des caractéristiques sous-jacentes. Cette avancée facilite le développement et le test de modèles à grande échelle pour des simulations multi-gents. Deuxièmement, nous présentons le Jeu de Markov à Prix Minimum (MPMG), qui, dans des conditions homogènes, étend le Dilemme du Prisonnier à un jeu stochastique. Le MPMG est ensuite peuplé d’agents d’apprentissage par renforcement multi-agents (MARL) afin d’examiner la robustesse de la règle de prix minimum face à la collusion en l’absence de coordination explicite. Nos résultats montrent que les agents non informés parviennent plus facilement à des résultats Pareto-optimaux que leurs homologues plus sophistiqués, ce qui suggère que la coordination tacite, ou collusion tacite, peut émerger de manière accidentelle dans de tels contextes. Enfin, nous proposons le Gradient de Politique d’Équilibre Stratégique (SEPG), une méthode MARL visant à favoriser la coordination tacite dans des environnements non coopératifs sans recours à des mécanismes de communication explicites. Le SEPG, un algorithme acteur-critique basé sur le gradient de politique, combine planification et apprentissage adaptatif en ligne, permettant aux agents de converger vers des stratégies Pareto-optimales dans le MPMG. Nous démontrons que les agents SEPG peuvent atteindre une collusion tout en adoptant des comportements rationnels.

Abstract

A central problem in the study of multi-agent systems concerns elucidating how selfish agents can collaborate and exhibit group intelligence within large-scale decision-making contexts. This issue is particularly reflected in scenarios characterized by a tension between individual and collective welfare. From a methodological perspective, game theory seamlessly integrates algorithmic learning, providing fertile grounds for the study of tacit coordination among artificial learners in non-cooperative settings. This thesis explores the intricate dynamics of transitioning from non-Pareto Nash Equilibria to Pareto-Optimal strategies in the context of a minimum price-ruled coordination game. This research is anchored in three comprehensive studies, each addressing unique challenges and opportunities in agent-based computational simulations and in the study of emergent algorithmic behavior. First, we introduce a meta-algorithm for simulating realistic synthetic multi-level auction data. To overcome the challenges inherent to the high-cardinality, multi-level, and discrete nature of such structures, we employ a hierarchical deep learning approach based on genera-tive adversarial learning and the proposed BidNet, a predictor of conditional bid distributions based on underlying features. This advancement aids in developing and testing large-scale models for agent-based simulations. Second, we introduce the Minimum Price Markov Game (MPMG), which under the condi-tion of homogeneity, extends the Prisoner’s Dilemma to a stochastic game. The MPMG is then populated with Multi-Agent Reinforcement Learning (MARL) agents to examine the robustness of the minimum price rule against collusion when coordination is not engineered. Our findings reveal that uninformed agents coordinate more easily towards Pareto Optimal outcomes than their sophisticated counterparts, meaning that tacit coordination, or tacit collusion, can occur accidentally in such settings. Finally, we devise the Strategic Equilibrium Policy Gradient (SEPG), a MARL method that aims to foster tacit coordination in non-cooperative settings without relying on direct commu-nication mechanisms. The SEPG is an actor-critic policy gradient algorithm that combines planning with adaptive online learning, enabling agents to achieve Pareto Optimal strate-gies in the MPMG. We show that SEPG agents can achieve collusion while demonstrating rational behaviors.