Automated analysis of strategic interactions

Creating the tools to support strategic reasoning about interactions among human and automated agents in complex and changing environments

Introduction

Current AI increasingly considers that automated agents interact strategically with other agents, both automated and human. Game theory is a formal framework for reasoning about strategic interactions. This project aims to develop a robust and standard framework for working with and analysing game models at scale in an automated way.

We will do this by extending Gambit, the leading software package for working computationally with models in game theory. We envision providing tools to support human analysis of large models, as well as methods for fully automated agents to learn from and adapt their decisions in rich strategic environments.

Explaining the science

Making good decisions in strategic environments is difficult because the full set of possible outcomes may be large, but also because the decisions that others make are relevant to the outcome.  There are two main approaches to analysing decision-making in strategic environments.

Equilibrium computation: Analysis based on various notions of equilibrium generally assume that all agents make forecasts of the decisions of others which are mutually consistent in some sense. Equilibrium concepts have proven useful as an analytical tool; however, they can be expensive to compute and generally do not describe a process by which agents might arrive at an equilibrium.

Learning and adaptation: An alternative approach lets agents learn to improve through trial and error. Agents repeatedly interact with the environment and other agents, and based on the outcome of their decisions they adapt their behaviours in an attempt to improve their performance over time.

This project will provide a suite of tools that will equip agents to reason using both equilibrium analysis and learning processes, to benefit from the strengths of both approaches, and translate them into sound decision-making in practical environments.

Project aims

Aim 1: Developing Gambit

Previously Gambit has focused on games which are played only once and can be represented explicitly using a relatively small game tree or payoff table, and for computing Nash equilibria of these games. Building on this platform, we will develop a conceptual framework for expressing games, including games which are too large to represent explicitly, so that complex strategic interactions can be modelled with the assurance that the game model written down is the one intended by the user. We will extend Gambit to implement this model, which will make it suitable for supporting automated reasoning. We will incorporate recent developments in the algorithmic solution of games, including both exact and approximate equilibria, building upon and contributing to other cutting-edge libraries for scientific computing and mathematical programming.

Aim 2: Solving huge games

When a game is too large to write down and reason about explicitly, one would only have access to the game via simulation of game play, which would consider only a small subset of the strategic plans possible. We will develop methods for analysing such games, e.g., via multi-agent reinforcement learning and query-based algorithms. In doing so we will make progress towards being able to do automated empirical analysis of games which incorporate the richness and complexity of strategic interactions in applications, while staying within the bounds of what is computationally feasible on the timescales required for automated agents.

Applications

We will demonstrate the applicability of our developments through a selection of case studies. These case studies will be drawn from applications in computing science, economics, and/or related fields. These could include--but will not necessarily be limited to-- auctions and competitive bidding, automated pricing in online platforms, defence and security games such as patrolling and cyber defence, health applications, sports modelling, and transportation systems.

Research outputs

Yongzhao Wang, Michael P. Wellman:
Generalized Response Objectives for Strategy Exploration in Empirical Game-Theoretic Analysis. AAMAS 2024: 1892-1900. https://dl.acm.org/doi/10.5555/3635637.3663052

Nelson Vadori, Rahul Savani:
Ordinal Potential-based Player Rating. AISTATS 2024: 118-126. https://proceedings.mlr.press/v238/vadori24a.html

Ariyan Bighashdel, Yongzhao Wang, Stephen McAleer, Rahul Savani, Frans A. Oliehoek:
Policy Space Response Oracles: A Survey. IJCAI 2024: 7951-7961. https://doi.org/10.24963/ijcai.2024/880

Hao Zhou, Yongzhao Wang, Konstantinos Varsos, Nicholas Bishop, Rahul Savani, Anisoara Calinescu, Michael Wooldridge: A Strategic Analysis of Prepayments in Financial Credit Networks. IJCAI 2024: 3040-3048. https://doi.org/10.24963/ijcai.2024/337

Yongzhao Wang, Rahul Savani, Anri Gu, Chris Mascioli, Theodore Turocy, Michael Wellman: Market Making with Learned Beta Policies. ICAIF 2024 (to appear).

Anri Gu, Yongzhao Wang, Chris Mascioli, Mithun Chakraborty, Rahul Savani, Theodore Turocy, Michael Wellman: The Effect of Liquidity on the Spoofability of Financial Markets. ICAIF 2024 (to appear).

Chris Mascioli, Anri Gu, Yongzhao Wang, Mithun Chakraborty, Michael Wellman: A Financial Market Simulation Environment for Trading Agents Using Deep Reinforcement Learning. ICAIF 2024 (to appear).

Organisers

Researchers and collaborators