MURI Algorithms, Learning, and Game Theory: The Foundations of Multi-Agent Systems
Abstract
The proposed work focuses on the intersection of Game Theory, Algorithms, and Learning, with a particularemphasis on complex strategic games (CSGs) that involve multiple players, evolving parameters,incomplete information, and various objectives. The researchers aim to lay the theoretical foundations andexpand the practical applications of multi-agent decision-making and learning within the context of thesechallenging games.Over the past decade, Game Theory, Algorithms, and Learning have witnessed significant convergence,driven by developments in deep learning. This convergence is evident in various areas, including adversarialrobustness, generative model training (e.g., GANs), multi-agent reinforcement learning, and solvingcomplex games like Go, Diplomacy, and Stratego using min-max tree search and regret minimization techniques.However, the researchers highlight several complexities that remain inadequately addressed in realworldgames, particularly those with military applications. These complexities include games with morethan two diverse players, evolving parameters, multi-objective payoffs, incomplete information, coalitions,information gathering, deception, and non-zero-sum outcomes. Such challenges are of great importancein military science, where diverse player roles and the potential for collusion and information sharing addnovel dimensions to game analysis.In CSGs, players often face multi-objective decision-making, where various costs and benefits must beconsidered, such as casualties, economic costs, geopolitical advantage, and reputation damage. These complexobjectives may require different optimization approaches, either through concave combining functionsor individual multi-objective optimization. Additionally, CSGs typically involve multiple rounds, makingthem more dynamic and less amenable to traditional equilibrium concepts like Bayesian Nash equilibrium.Instead, they are better analyzed as trajectories of dynamical systems, such as stochastic replicator dynamics.CSGs are characterized by Bayesian aspects, as players have partial information about their opponentsand constantly update their information sets. Incorrect information and the potential for deception furthercomplicate analysisand prediction. These unique features of CSGs present both opportunities for foundationalresearch and challenges for Algorithms andLearning.To address these issues, this research project assembles a qualified and diverse team of experts in GameTheory, Algorithms, and Learning. The project#s dual objectives are to develop the theoretical foundationsof CSGs and explore their practical applications in games with a limited number of players (more than twobut small), such as Diplomacy and Stratego. The researchers aim to advance our understanding of CSGs,which have not been comprehensively studied due to their complex nature, combining various challengingelements that pose new and exciting research questions at the intersection of these three fields.Approved for Public Release
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Jan 13, 2025
- Source ID
- N000142512116
Entities
People
- Christos Papadimitriou
Organizations
- Office of Naval Research
- Trustees of Columbia University in the City of New York
- United States Navy