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.
