publications

2026

1. ALT

   Sink equilibria and the attractors of learning in games

   Oliver Biggar and Christos Papadimitriou

   In International Conference on Algorithmic Learning Theory, 2026

   Elegant Paper Award Abs

   https://algorithmiclearningtheory.org/alt2026/distinguished-papers/

   Characterizing the limit behavior – that is, the attractors – of learning dynamics is one of the most fundamental open questions in game theory. In recent work on this front, it was conjectured that the attractors of the replicator dynamic are in one-to-one correspondence with the sink equilibria of the game – the sink strongly connected components of a game’s preference graph – and it was established that they do stand in at least one-to-many correspondence with them. Here, we show that the one-to-one conjecture is false. We disprove this conjecture over the course of three theorems: the first disproves a stronger form of the conjecture, while the weaker form is disproved separately in the two-player and N-player (N>2) cases. By showing how the conjecture fails, we lay out the obstacles that lie ahead for characterizing attractors of the replicator, and introduce new ideas with which to tackle them. All three counterexamples derive from an object called a local source – a point lying within the sink equilibrium, and yet which is ‘locally repelling’; we prove that the absence of local sources is necessary, but not sufficient, for the one-to-one property to be true. We complement this with a sufficient condition: we introduce a local property of a sink equilibrium called pseudoconvexity, and establish that when the sink equilibria of a two-player game are pseudoconvex then they precisely define the attractors. Pseudoconvexity generalizes the previous cases – such as zero-sum games and potential games – where this conjecture was known to hold, and reformulates these cases in terms of a simple graph property.

2. On the Complexity of Learning Nash equilibria

   Oliver Biggar, Christos Papadimitriou, and Georgios Piliouras

   arXiv preprint arXiv:2602.16016, 2026

   Abs Website

   We know that the Nash equilibria of a game cannot be computed efficiently unless P=PPAD. But can they be learned? Are there dynamics that (1) can be computed efficiently by the players at each strategy profile and (2) are guaranteed to converge to the Nash equilibria? This is a question as ancient as the Nash equilibrium itself, and antedates by many decades current complexity considerations about it. It was recently proved in MPPS23 that no such dynamics can exist in general; however, the game used in that proof is degenerate, and a strong assumption of uniform convergence to a continuum of Nash equilibria is employed. We point out that both assumptions are necessary for that proof, because Nash-convergent dynamics do exist, which converge to all Nash equilibria in non-degenerate games; in fact we describe two very different families of such dynamics. However, we show that both of these families are intractable to compute locally, unless complexity classes collapse. We formulate a complexity theoretic Impossibility Conjecture: if a locally tractable Nash-convergent dynamic exists then P=PPAD. This is a novel kind of conjecture, combining topology and complexity, because the dynamic is only required to be tractable locally – it could take exponentially many steps to converge, so long as the work done at each step is polynomial. Next, we show that any locally tractable dynamic which possesses a locally tractable Lyapunov function cannot exist unless PPAD=CLS. Finally, for the most general impossibility conjecture, we provide a complexity-theoretic explanation why it may be difficult to settle: we introduce a Proving Game to demonstrate that black-box reductions cannot distinguish between convergent and non-convergent dynamics in polynomial time.

3. Computing stable limit cycles of learning in games

   Oliver Biggar and Christos Papadimitriou

   arXiv preprint arXiv:2602.11315, 2026

   Abs Website

   Many well-studied learning dynamics, such as fictitious play and the replicator, are known to not converge in general N-player games. The simplest mode of non-convergence is cyclical or periodic behavior. Such cycles are fundamental objects, and have inspired a number of significant insights in the field, beginning with the pioneering work of Shapley (1964). However a central question remains unanswered: which cycles are stable under game dynamics? In this paper we give a complete and computational answer to this question for the two best-studied dynamics, fictitious play/best-response dynamics and the replicator dynamic. We show (1) that a periodic sequence of profiles is stable under one of these dynamics if and only it is stable under the other, and (2) we provide a polynomial-time spectral stability test to determine whether a given periodic sequence is stable under either dynamic. Finally, we give an entirely ‘structural’ sufficient condition for stability: every cycle that is a sink equilibrium of the preference graph of the game is stable, and moreover it is an attractor of the replicator dynamic. This result generalizes the famous theorems of Shapley (1964) and Jordan (1993), and extends the frontier of recent work relating the preference graph to the replicator attractors.

2025

1. Preference graphs: a combinatorial tool for game theory

   Oliver Biggar and Iman Shames

   arXiv preprint arXiv:2502.03546, 2025

   Abs Website

   The preference graph is a combinatorial representation of the structure of a normal-form game. Its nodes are the strategy profiles, with an arc between profiles if they differ in the strategy of a single player, where the orientation indicates the preferred choice for that player. We show that the preference graph is a surprisingly fundamental tool for studying normal-form games, which arises from natural axioms and which underlies many key game-theoretic concepts, including dominated strategies and strict Nash equilibria, as well as classes of games like potential games, supermodular games and weakly acyclic games. The preference graph is especially related to game dynamics, playing a significant role in the behaviour of fictitious play and the replicator dynamic. Overall, we aim to equip game theorists with the tools and understanding to apply the preference graph to new problems in game theory.

2. Faster shortest-path algorithms using the acyclic-connected tree

   Elis Stefansson, Oliver Biggar, and Karl H Johansson

   arXiv preprint arXiv:2504.08667, 2025

   Abs Website

   We provide a method to obtain beyond-worst-case time complexity for any single-source-shortest-path (SSSP) algorithm by exploiting modular structures in graphs. The key novelty is a graph decomposition, called the acyclic-connected (A-C) tree, which breaks up a graph into a recursively nested sequence of strongly connected components in topological order. The A-C tree is optimal in the sense that it maximally decomposes the graph, formalised by a parameter called nesting width, measuring the extent to which a graph can be decomposed. We show how to compute the A-C tree in linear time, allowing it to be used as a preprocessing step for SSSP. Indeed, we transform any SSSP algorithm by first computing the A-C tree, and then running the SSSP algorithm in a careful recursive manner on the A-C tree. We illustrate this with two state-of-the-art algorithms: Dijkstra’s algorithm and the recent sparse graph algorithm of Duan et al., obtaining improved time complexities of O(m+nlog(nw(G))) and O(mα(n)+mlog2/3(nw(G))), respectively, where nw(G)≤n is the nesting width of the graph G, and α(n) is the extremely slow-growing inverse Ackermann function. Some classes of graphs, such as directed acyclic graphs, have bounded nesting width, and we obtain linear-time SSSP algorithms for these graphs.

2024

1. ALT

   The attractor of the replicator dynamic in zero-sum games

   Oliver Biggar and Iman Shames

   In International Conference on Algorithmic Learning Theory, 2024

   Outstanding Paper Award Abs Website

   https://algorithmiclearningtheory.org/alt2024/accepted-papers/

   In this paper we characterise the long-run behaviour of the replicator dynamic in zero-sum games (symmetric or non-symmetric). Specifically, we prove that every zero-sum game possesses a unique global replicator attractor, which we then characterise. Most surprisingly, this attractor depends only on each player’s preference order over their own strategies and not on the cardinal payoff values, defined by a finite directed graph we call the game’s preference graph. When the game is symmetric, this graph is a tournament whose nodes are strategies; when the game is not symmetric, this graph is the game’s response graph. We discuss the consequences of our results on chain recurrence and Nash equilibria.

2. A Behavior Tree-inspired programming language for autonomous agents

   Oliver Biggar and Iman Shames

   arXiv preprint arXiv:2412.08654, 2024

   Abs Website

   We propose a design for a functional programming language for autonomous agents, built off the ideas and motivations of Behavior Trees (BTs). BTs are a popular model for designing agents behavior in robotics and AI. However, as their growth has increased dramatically, the simple model of BTs has come to be limiting. There is a growing push to increase the functionality of BTs, with the end goal of BTs evolving into a programming language in their own right, centred around the defining BT properties of modularity and reactiveness. In this paper, we examine how the BT model must be extended in order to grow into such a language. We identify some fundamental problems which must be solved: implementing ‘reactive’ selection, ’monitoring’ safety-critical conditions, and passing data between actions. We provide a variety of small examples which demonstrate that these problems are complex, and that current BT approaches do not handle them in a manner consistent with modularity. We instead provide a simple set of modular programming primitives for handling these use cases, and show how they can be combined to build complex programs. We present a full specification for our BT-inspired language, and give an implementation in the functional programming language Haskell. Finally, we demonstrate our language by translating a large and complex BT into a simple, unambiguous program.

2023

1. SciRep

   The graph structure of two-player games

   Oliver Biggar and Iman Shames

   Scientific Reports, 2023

   Abs Website

   In this paper, we analyse two-player games by their response graphs. The response graph has nodes which are strategy profiles, with an arc between profiles if they differ in the strategy of a single player, with the direction of the arc indicating the preferred option for that player. Response graphs, and particularly their sink strongly connected components, play an important role in modern techniques in evolutionary game theory and multi-agent learning. We show that the response graph is a simple and well-motivated model of strategic interaction which captures many non-trivial properties of a game, despite not depending on cardinal payoffs. We characterise the games which share a response graph with a zero-sum or potential game respectively, and demonstrate a duality between these sets. This allows us to understand the influence of these properties on the response graph. The response graphs of Matching Pennies and Coordination are shown to play a key role in all two-player games: every non-iteratively-dominated strategy takes part in a subgame with these graph structures. As a corollary, any game sharing a response graph with both a zero-sum game and potential game must be dominance-solvable. Finally, we demonstrate our results on some larger games.

2. ALT

   The replicator dynamic, chain components and the response graph

   Oliver Biggar and Iman Shames

   In International Conference on Algorithmic Learning Theory, 2023

   Abs Website

   In this paper we examine the relationship between the flow of the replicator dynamic, the continuum limit of Multiplicative Weights Update, and a game’s \emphresponse graph. We settle an open problem establishing that under the replicator, \emphsink chain components—a topological notion of long-run outcome of a dynamical system—always exist and are approximated by the \emphsink connected components of the game’s response graph. More specifically, each sink chain component contains a sink connected component of the response graph, as well as all mixed strategy profiles whose support consists of pure profiles in the same connected component, a set we call the \emphcontent of the connected component. As a corollary, all profiles are chain recurrent in games with strongly connected response graphs. In any two-player game sharing a response graph with a zero-sum game, the sink chain component is unique. In two-player zero-sum and potential games the sink chain components and sink connected components are in a one-to-one correspondence, and we conjecture that this holds in all games.

2022

1. TCPS

   On modularity in reactive control architectures, with an application to formal verification

   Oliver Biggar, Mohammad Zamani, and Iman Shames

   ACM Transactions on Cyber-Physical Systems (TCPS), 2022

   Abs Website

   Modularity is a central principle throughout the design process for cyber-physical systems. Modularity reduces complexity and increases reuse of behavior. In this article we pose and answer the following question: how can we identify independent “modules” within the structure of reactive control architectures? To this end, we propose a graph-structured control architecture we call a decision structure and show how it generalizes some reactive control architectures that are popular in Artificial Intelligence (AI) and robotics, specifically Teleo-Reactive programs (TRs), Decision Trees (DTs), Behavior Trees (BTs), and Generalised Behavior Trees (k-BTs). Inspired by the definition of a module in graph theory [16] we define modules in decision structures and show how each decision structure possesses a canonical decomposition into its modules, which can be found in polynomial time. We establish intuitive connections between our proposed modularity and modularity in structured programming. In BTs, k-BTs, and DTs the modules we propose are in a one-to-one correspondence with their subtrees. We show we can naturally characterize each of the BTs, k-BTs, DTs, and TRs by properties of their module decomposition. This allows us to recognize which decision structures are equivalent to each of these architectures in quadratic time. Following McCabe [26], we define a complexity measure called essential complexity on decision structures, which measures the degree to which they can be decomposed into simpler modules. We characterize the k-BTs as the decision structures of unit-essential complexity. Our proposed concept of modules extends to formal verification, under any verification scheme capable of verifying a decision structure. Namely, we prove that a modification to a module within a decision structure has no greater flow-on effects than a modification to an individual action within that structure. This enables verification on modules to be done locally and hierarchically, where structures can be verified and then repeatedly locally modified, with modules replaced by modules while preserving correctness. To illustrate the findings, we present an example of a solar-powered drone completing a reconnaissance-based mission using a decision structure. We use a Linear Temporal Logic-based verification scheme to verify the correctness of this structure and then show how one can repeatedly modify modules while preserving its correctness, and this can be verified by considering only those modules that have been modified.

2. Preference games and sink equilibria

   Oliver Biggar

   2022

2021

1. RAL

   An expressiveness hierarchy of behavior trees and related architectures

   Oliver Biggar, Mohammad Zamani, and Iman Shames

   IEEE Robotics and Automation Letters, 2021

   Abs Website

   In this letter, we provide a formal framework for comparing the expressive power of Behavior Trees (BTs) to other action selection architectures. Taking inspiration from the analogous comparisons of structural programming methodologies, we formalise the concept of ‘expressiveness’. This leads us to an expressiveness hierarchy of control architectures, which includes BTs, Decision Trees (DTs), Teleo-reactive Programs (TRs) and Finite State Machines (FSMs). By distinguishing between BTs with auxiliary variables and those without, we demonstrate the existence of a trade-off in BT design between readability and expressiveness. We discuss what this means for BTs in practice.

2. Modular decomposition of hierarchical finite state machines

   Oliver Biggar, Behzad Zamani, and Iman Shames

   arXiv preprint arXiv:2111.04902, 2021

   Abs Website

   Hierarchical Finite State Machines (HFSMs) are a standard software-modelling concept which extends the classical Finite State Machine (FSM) notion with the useful abstraction of hierarchical nesting. That is, an HFSM is an FSM whose states can be other FSMs. The hierarchy in HFSMs is provided at design time, and can be removed by expanding nested states, allowing HFSMs to inherit the semantics of FSMs. However, because hierarchy is a useful representation of the structure of an FSM, we would like to be able to invert this operation: given an FSM, can we compute equivalent HFSMs? This is the topic of this paper. By adapting the analogous theory of ‘modular decomposition’ from graph theory into automata theory, we are able to compute an efficient representation of the space of equivalent HFSMs to a given one. Specifically, we first define a module of an FSM, which is a collection of nodes which can be treated as a nested FSM. Unlike modules in graphs, some modules in FSMs are lacking in algebraic structure. We identify a simple and natural restriction of the modules, called thin modules, which regain many of the critical properties from modules in graphs. We then construct a linear-space directed graph which uniquely represents every thin module, and hence every equivalent (thin) HFSM. We call this graph the modular decomposition. The modular decomposition makes clear the significant common structure underlying equivalent thin HFSMs. We provide an O(n^2k) algorithm for constructing the modular decomposition of an n-state k-symbol FSM. We demonstrate the applicability of this theory on the following ‘bottleneck’ problem: given an HFSM, find an equivalent one where the size of the largest component FSM is minimised. The modular decomposition gives a simple greedy algorithm for the bottleneck problem on thin HFSMs, which we demonstrate on a wristwatch HFSM example from Harel (1987).

2020

1. RAL

   A framework for formal verification of behavior trees with linear temporal logic

   Oliver Biggar and Mohammad Zamani

   IEEE Robotics and Automation Letters, 2020

   Abs Website

   Despite the current increasing popularity of Behavior Trees (BTs) in the robotics community, there does not currently exist a method to formally verify their correctness without compromising their most valuable traits: modularity, flexibility and reusability. In this letter we present a new mathematical framework in which we formally express Behavior Trees in Linear Temporal Logic (LTL). We show how this framework equivalently represents classical BTs. Then we utilize the proposed framework to construct an algorithm to verify that a given BT satisfies a given LTL specification. We prove that this algorithm is sound. Importantly, we prove that this method does not compromise the flexible design process of BTs, i.e. changes to subtrees can be verified separately and their combination can be assured to be correct. We present an example of the proposed algorithm in use.

2. A principled analysis of behavior trees and their generalisations

   Oliver Biggar, Mohammad Zamani, and Iman Shames

   arXiv preprint arXiv:2008.11906, 2020

   Abs Website

   As complex autonomous robotic systems become more widespread, the need for transparent and reusable Artificial Intelligence (AI) designs becomes more apparent. In this paper we analyse how the principles behind Behavior Trees (BTs), an increasingly popular tree-structured control architecture, are applicable to these goals. Using structured programming as a guide, we analyse the BT principles of reactiveness and modularity in a formal framework of action selection. Proceeding from these principles, we review a number of challenging use cases of BTs in the literature, and show that reasoning via these principles leads to compatible solutions. Extending these arguments, we introduce a new class of control architectures we call generalised BTs or k-BTs and show how they can extend the applicability of BTs to some of the aforementioned challenging BT use cases while preserving the BT principles.