Source author record

Michael Wooldridge

Michael Wooldridge appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Catalog footprint

What is connected

16works
7topics
4close collaborators

Actions

Connect this record

Log in to claim

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

16 published item(s)

preprint2026arXiv

The Attacker in the Mirror: Breaking Self-Consistency in Safety via Anchored Bipolicy Self-Play

Self-play red team is an established approach to improving AI safety in which different instances of the same model play attacker and defender roles in a zero-sum game, i.e., where the attacker tries to jailbreak the defender; if self-play converges to a Nash equilibrium, the model is guaranteed to respond safely within the settings of the game. Although the parameter sharing enforced by the use of the same model for the two roles improves stability and performance, it introduces fundamental theoretical and architectural limitations. We show that the set of Nash equilibria that can be reached corresponds to a broad class of behaviours that includes trivial always refuse strategies and oracle-like defenders, thus limiting practical applicability. We then show that when attacker and defender share and update the same base model, the dynamics collapse to self-consistency, so that attacks do not enforce adversarial pressure on the defender. In response, we propose Anchored Bipolicy Self-Play, which trains distinct role-specific LoRA adapters on top of a frozen base model, thereby maintaining stable optimisation while preserving adversarial pressure through explicit role separation. In relation to standard self-play, we show up to 100x greater parameter efficiency than finetuning and consistent improvements in safety compared to self-play fine-tuned models. We evaluate on Qwen2.5-{3B, 7B,14B}-IT models across widely used safety benchmarks, showing improved robustness without loss of reasoning ability. Cross-play experiments further show that our attacker and defender models are superior to self-play in terms of adversarial defence and safety.

preprint2023arXiv

Cooperative Concurrent Games

In rational verification, the aim is to verify which temporal logic properties will obtain in a multi-agent system, under the assumption that agents ("players") in the system choose strategies for acting that form a game theoretic equilibrium. Preferences are typically defined by assuming that agents act in pursuit of individual goals, specified as temporal logic formulae. To date, rational verification has been studied using non-cooperative solution concepts - Nash equilibrium and refinements thereof. Such non-cooperative solution concepts assume that there is no possibility of agents forming binding agreements to cooperate, and as such they are restricted in their applicability. In this article, we extend rational verification to cooperative solution concepts, as studied in the field of cooperative game theory. We focus on the core, as this is the most fundamental (and most widely studied) cooperative solution concept. We begin by presenting a variant of the core that seems well-suited to the concurrent game setting, and we show that this version of the core can be characterised using ATL*. We then study the computational complexity of key decision problems associated with the core, which range from problems in PSPACE to problems in 3EXPTIME. We also investigate conditions that are sufficient to ensure that the core is non-empty, and explore when it is invariant under bisimilarity. We then introduce and study a number of variants of the main definition of the core, leading to the issue of credible deviations, and to stronger notions of collective stable behaviour. Finally, we study cooperative rational verification using an alternative model of preferences, in which players seek to maximise the mean-payoff they obtain over an infinite play in games where quantitative information is allowed.

preprint2022arXiv

On the Complexity of Rational Verification

Rational verification refers to the problem of checking which temporal logic properties hold of a concurrent multiagent system, under the assumption that agents in the system choose strategies that form a game-theoretic equilibrium. Rational verification can be understood as a counterpart to model checking for multiagent systems, but while classical model checking can be done in polynomial time for some temporal logic specification languages such as CTL, and polynomial space with LTL specifications, rational verification is much harder: the key decision problems for rational verification are 2EXPTIME-complete with LTL specifications, even when using explicit-state system representations. Against this background, our contributions in this paper are threefold. First, we show that the complexity of rational verification can be greatly reduced by restricting specifications to GR(1), a fragment of LTL that can represent a broad and practically useful class of response properties of reactive systems. In particular, we show that for a number of relevant settings, rational verification can be done in polynomial space and even in polynomial time. Second, we provide improved complexity results for rational verification when considering players' goals given by mean-payoff utility functions; arguably the most widely used approach for quantitative objectives in concurrent and multiagent systems. Finally, we consider the problem of computing outcomes that satisfy social welfare constraints. To this end, we consider both utilitarian and egalitarian social welfare and show that computing such outcomes is either PSPACE-complete or NP-complete.

preprint2021arXiv

Equilibrium Refinements for Multi-Agent Influence Diagrams: Theory and Practice

Multi-agent influence diagrams (MAIDs) are a popular form of graphical model that, for certain classes of games, have been shown to offer key complexity and explainability advantages over traditional extensive form game (EFG) representations. In this paper, we extend previous work on MAIDs by introducing the concept of a MAID subgame, as well as subgame perfect and trembling hand perfect equilibrium refinements. We then prove several equivalence results between MAIDs and EFGs. Finally, we describe an open source implementation for reasoning about MAIDs and computing their equilibria.

preprint2021arXiv

Multi-Agent Reinforcement Learning with Temporal Logic Specifications

In this paper, we study the problem of learning to satisfy temporal logic specifications with a group of agents in an unknown environment, which may exhibit probabilistic behaviour. From a learning perspective these specifications provide a rich formal language with which to capture tasks or objectives, while from a logic and automated verification perspective the introduction of learning capabilities allows for practical applications in large, stochastic, unknown environments. The existing work in this area is, however, limited. Of the frameworks that consider full linear temporal logic or have correctness guarantees, all methods thus far consider only the case of a single temporal logic specification and a single agent. In order to overcome this limitation, we develop the first multi-agent reinforcement learning technique for temporal logic specifications, which is also novel in its ability to handle multiple specifications. We provide correctness and convergence guarantees for our main algorithm - ALMANAC (Automaton/Logic Multi-Agent Natural Actor-Critic) - even when using function approximation. Alongside our theoretical results, we further demonstrate the applicability of our technique via a set of preliminary experiments.

preprint2020arXiv

Automated Temporal Equilibrium Analysis: Verification and Synthesis of Multi-Player Games

In the context of multi-agent systems, the rational verification problem is concerned with checking which temporal logic properties will hold in a system when its constituent agents are assumed to behave rationally and strategically in pursuit of individual objectives. Typically, those objectives are expressed as temporal logic formulae which the relevant agent desires to see satisfied. Unfortunately, rational verification is computationally complex, and requires specialised techniques in order to obtain practically useable implementations. In this paper, we present such a technique. This technique relies on a reduction of the rational verification problem to the solution of a collection of parity games. Our approach has been implemented in the Equilibrium Verification Environment (EVE) system. The EVE system takes as input a model of a concurrent/multi-agent system represented using the Simple Reactive Modules Language (SRML), where agent goals are represented as Linear Temporal Logic (LTL) formulae, together with a claim about the equilibrium behaviour of the system, also expressed as an LTL formula. EVE can then check whether the LTL claim holds on some (or every) computation of the system that could arise through agents choosing Nash equilibrium strategies; it can also check whether a system has a Nash equilibrium, and synthesise individual strategies for players in the multi-player game. After presenting our basic framework, we describe our new technique and prove its correctness. We then describe our implementation in the EVE system, and present experimental results which show that EVE performs favourably in comparison to other existing tools that support rational verification.

preprint2020arXiv

Equilibria for Games with Combined Qualitative and Quantitative Objectives

The overall aim of our research is to develop techniques to reason about the equilibrium properties of multi-agent systems. We model multi-agent systems as concurrent games, in which each player is a process that is assumed to act independently and strategically in pursuit of personal preferences. In this article, we study these games in the context of finite-memory strategies, and we assume players' preferences are defined by a qualitative and a quantitative objective, which are related by a lexicographic order: a player first prefers to satisfy its qualitative objective (given as a formula of Linear Temporal Logic) and then prefers to minimise costs (given by a mean-payoff function). Our main result is that deciding the existence of a strict epsilon Nash equilibrium in such games is 2ExpTime-complete (and hence decidable), even if players' deviations are implemented as infinite-memory strategies.

preprint2020arXiv

Multi-Player Games with LDL Goals over Finite Traces

Linear Dynamic Logic on finite traces LDLf is a powerful logic for reasoning about the behaviour of concurrent and multi-agent systems. In this paper, we investigate techniques for both the characterisation and verification of equilibria in multi-player games with goals/objectives expressed using logics based on LDLf. This study builds upon a generalisation of Boolean games, a logic-based game model of multi-agent systems where players have goals succinctly represented in a logical way. Because LDLf goals are considered, in the settings we study -- Reactive Modules games and iterated Boolean games with goals over finite traces -- players' goals can be defined to be regular properties while achieved in a finite, but arbitrarily large, trace. In particular, using alternating automata, the paper investigates automata-theoretic approaches to the characterisation and verification of (pure strategy Nash) equilibria, shows that the set of Nash equilibria in multi-player games with LDLf objectives is regular, and provides complexity results for the associated automata constructions.

preprint2019arXiv

A Game-Theoretic Algorithm for Link Prediction

Predicting edges in networks is a key problem in social network analysis and involves reasoning about the relationships between nodes based on the structural properties of a network. In particular, link prediction can be used to analyse how a network will develop or - given incomplete information about relationships - to discover "missing" links. Our approach to this problem is rooted in cooperative game theory, where we propose a new, quasi-local approach (i.e., one which considers nodes within some radius k) that combines generalised group closeness centrality and semivalue interaction indices. We develop fast algorithms for computing our measure and evaluate it on a number of real-world networks, where it outperforms a selection of other state-of-the-art methods from the literature. Importantly, choosing the optimal radius k for quasi-local methods is difficult, and there is no assurance that the choice is optimal. Additionally, when compared to other quasi-local methods, ours achieves very good results even when given a suboptimal radius k as a parameter.

preprint2019arXiv

Monte Carlo Techniques for Approximating the Myerson Value -- Theoretical and Empirical Analysis

Myerson first introduced graph-restricted games in order to model the interaction of cooperative players with an underlying communication network. A dedicated solution concept -- the Myerson value -- is perhaps the most important normative solution concept for cooperative games on graphs. Unfortunately, its computation is computationally challenging. In particular, although exact algorithms have been proposed, they must traverse all connected coalitions of the graph of which there may be exponentially many. In this paper, we consider the issue of approximating the Myerson value for arbitrary graphs and characteristic functions. While Monte Carlo approximations have been proposed for the related concept of the Shapley value, their suitability for the Myerson value has not been studied. Given this, we evaluate and compare (both theoretically and empiraclly) three Monte Carlo sampling methods for the Myerson value: conventional method of sampling permutations; a new, hybrid algorithm that combines exact computations and sampling; and sampling of connected coalitions. We find that our hybrid algorithm performs very well and also significantly improves on the conventional methods.

preprint2015arXiv

Boolean Hedonic Games

We study hedonic games with dichotomous preferences. Hedonic games are cooperative games in which players desire to form coalitions, but only care about the makeup of the coalitions of which they are members; they are indifferent about the makeup of other coalitions. The assumption of dichotomous preferences means that, additionally, each player's preference relation partitions the set of coalitions of which that player is a member into just two equivalence classes: satisfactory and unsatisfactory. A player is indifferent between satisfactory coalitions, and is indifferent between unsatisfactory coalitions, but strictly prefers any satisfactory coalition over any unsatisfactory coalition. We develop a succinct representation for such games, in which each player's preference relation is represented by a propositional formula. We show how solution concepts for hedonic games with dichotomous preferences are characterised by propositional formulas.

preprint2014arXiv

A Measure of Synergy in Coalitions

When the performance of a team of agents exceeds our expectations or fall short of them, we often explain this by saying that there was some synergy in the team---either positive (the team exceeded our expectations) or negative (they fell short). Our aim in this article is to develop a formal and principled way of measuring synergies, both positive and negative. Using characteristic function cooperative games as our underlying model, we present a formal measure of synergy, based on the idea that a synergy is exhibited when the performance of a team deviates from the norm. We then show that our synergy value is the only possible such measure that satisfies certain intuitive properties. We then investigate some alternative characterisations of this measure.

preprint2014arXiv

Reasoning About the Transfer of Control

We present DCL-PC: a logic for reasoning about how the abilities of agents and coalitions of agents are altered by transferring control from one agent to another. The logical foundation of DCL-PC is CL-PC, a logic for reasoning about cooperation in which the abilities of agents and coalitions of agents stem from a distribution of atomic Boolean variables to individual agents -- the choices available to a coalition correspond to assignments to the variables the coalition controls. The basic modal constructs of DCL-PC are of the form coalition C can cooperate to bring about phi. DCL-PC extends CL-PC with dynamic logic modalities in which atomic programs are of the form agent i gives control of variable p to agent j; as usual in dynamic logic, these atomic programs may be combined using sequence, iteration, choice, and test operators to form complex programs. By combining such dynamic transfer programs with cooperation modalities, it becomes possible to reason about how the power of agents and coalitions is affected by the transfer of control. We give two alternative semantics for the logic: a direct semantics, in which we capture the distributions of Boolean variables to agents; and a more conventional Kripke semantics. We prove that these semantics are equivalent, and then present an axiomatization for the logic. We investigate the computational complexity of model checking and satisfiability for DCL-PC, and show that both problems are PSPACE-complete (and hence no worse than the underlying logic CL-PC). Finally, we investigate the characterisation of control in DCL-PC. We distinguish between first-order control -- the ability of an agent or coalition to control some state of affairs through the assignment of values to the variables under the control of the agent or coalition -- and second-order control -- the ability of an agent to exert control over the control that other agents have by transferring variables to other agents. We give a logical characterisation of second-order control.

preprint2014arXiv

Towards a Fair Allocation of Rewards in Multi-Level Marketing

An increasing number of businesses and organisations rely on existing users for finding new users or spreading a message. One of the widely used "refer-a-friend" mechanisms offers an equal reward to both the referrer and the invitee. This mechanism provides incentives for direct referrals and is fair to the invitee. On the other hand, multi-level marketing and recent social mobilisation experiments focus on mechanisms that incentivise both direct and indirect referrals. Such mechanisms share the reward for inviting a new member among the ancestors, usually in geometrically decreasing shares. A new member receives nothing at the time of joining. We study fairness in multi-level marketing mechanisms. We show how characteristic function games can be used to model referral marketing, show how the canonical fairness concept of the Shapley value can be applied to this setting, and establish the complexity of finding the Shapley value in each class, and provide a comparison of the Shapley value-based mechanism to existing referral mechanisms.

preprint2013arXiv

The Shapley Axiomatization for Values in Partition Function Games

One of the long-debated issues in coalitional game theory is how to extend the Shapley value to games with externalities (partition-function games). When externalities are present, not only can a player's marginal contribution - a central notion to the Shapley value - be defined in a variety of ways, but it is also not obvious which axiomatization should be used. Consequently, a number of authors extended the Shapley value using complex and often unintuitive axiomatizations. Furthermore, no algorithm to approximate any extension of the Shapley value to partition-function games has been proposed to date. Given this background, we prove in this paper that, for any well-defined measure of marginal contribution, Shapley's original four axioms imply a unique value for games with externalities. As an consequence of this general theorem, we show that values proposed by Macho-Stadler et al., McQuillin and Bolger can be derived from Shapley's axioms. Building upon our analysis of marginal contribution, we develop a general algorithm to approximate extensions of the Shapley value to games with externalities using a Monte Carlo simulation technique.

preprint2011arXiv

Reasoning about Social Choice Functions

We introduce a logic specifically designed to support reasoning about social choice functions. The logic includes operators to capture strategic ability, and operators to capture agent preferences. We establish a correspondence between formulae in the logic and properties of social choice functions, and show that the logic is expressively complete with respect to social choice functions, i.e., that every social choice function can be characterised as a formula of the logic. We prove that the logic is decidable, and give a complete axiomatization. To demonstrate the value of the logic, we show in particular how it can be applied to the problem of determining whether a social choice function is strategy-proof.