Michael Wooldridge

JAAMAS Journal 2026 Journal Article

A Roadmap of Agent Research and Development

• Nicholas R. Jennings
• Katia Sycara
• Michael Wooldridge

Abstract This paper provides an overview of research and development activities in the field of autonomous agents and multi-agent systems. It aims to identify key concepts and applications, and to indicate how they relate to one-another. Some historical context to the field of agent-based computing is given, and contemporary research directions are presented. Finally, a range of open issues and future challenges are highlighted.

JAAMAS Journal 2026 Journal Article

Game Theory and Decision Theory in Multi-Agent Systems

• Simon Parsons
• Michael Wooldridge

Abstract In the last few years, there has been increasing interest from the agent community in the use of techniques from decision theory and game theory. Our aims in this article are firstly to briefly summarize the key concepts of decision theory and game theory, secondly to discuss how these tools are being applied in agent systems research, and finally to introduce this special issue of Autonomous Agents and Multi-Agent Systems by reviewing the papers that appear.

JAAMAS Journal 2026 Journal Article

Sarit Kraus, Strategic Negotiation in Multiagent Environments, MIT Press, 2001; ISBN: 0-262-11264-7

• Michael Wooldridge

JAAMAS Journal 2026 Journal Article

Semantic Issues in the Verification of Agent Communication Languages

• Michael Wooldridge

Abstract This article examines the issue of developing semantics for agent communication languages. In particular, it considers the problem of giving a verifiable semantics for such languages—a semantics where conformance (or otherwise) to the semantics could be determined by an independent observer. These problems are precisely defined in an abstract formal framework. Using this framework, a number of example agent communication frameworks are defined. A discussion is then presented, of the various options open to designers of agent communication languages, with respect the problem of verifying conformance.

JAAMAS Journal 2026 Journal Article

The dMARS Architecture: A Specification of the Distributed Multi-Agent Reasoning System

• MARK D'INVERNO
• Michael Luck
• Michael Wooldridge

Abstract The Procedural Reasoning System (PRS) is the best established agent architecture currently available. It has been deployed in many major industrial applications, ranging from fault diagnosis on the space shuttle to air traffic management and business process control. The theory of PRS-like systems has also been widely studied: within the intelligent agents research community, the belief-desire-intention (BDI) model of practical reasoning that underpins PRS is arguably the dominant force in the theoretical foundations of rational agency. Despite the interest in PRS and BDI agents, no complete attempt has yet been made to precisely specify the behaviour of real PRS systems. This has led to the development of a range of systems that claim to conform to the PRS model, but which differ from it in many important respects. Our aim in this paper is to rectify this omission. We provide an abstract formal model of an idealised dMARS system (the most recent implementation of the PRS architecture), which precisely defines the key data structures present within the architecture and the operations that manipulate these structures. We focus in particular on dMARS plans, since these are the key tool for programming dMARS agents. The specification we present will enable other implementations of PRS to be easily developed, and will serve as a benchmark against which future architectural enhancements can be evaluated.

JAAMAS Journal 2026 Journal Article

The Gaia Methodology for Agent-Oriented Analysis and Design

• Michael Wooldridge
• Nicholas R. Jennings
• David Kinny

Abstract This article presents Gaia: a methodology for agent-oriented analysis and design. The Gaia methodology is both general, in that it is applicable to a wide range of multi-agent systems, and comprehensive, in that it deals with both the macro-level (societal) and the micro-level (agent) aspects of systems. Gaia is founded on the view of a multi-agent system as a computational organisation consisting of various interacting roles. We illustrate Gaia through a case study (an agent-based business process management system).

IS Journal 2026 Journal Article

Top 10 Most Influential Papers in Artificial Intelligence Since 2000

• Bo An
• Sarit Kraus
• Michael Wooldridge

To commemorate the 70th anniversary of artificial intelligence (AI), IEEE Intelligent Systems has identified the 10 most impactful articles in AI published since 2000, marking the field’s evolution from its 1956 origins into a foundational pillar of modern science. The selection process combined rigorous quantitative indicators with the informed judgment of a panel of distinguished experts. The resulting list reflects a broad consensus on the milestones that have redefined AI, spanning the diverse and multifaceted landscape of the discipline. Together, these landmark articles laid the foundations for modern AI and continue to influence its evolution.

NeurIPS Conference 2025 Conference Paper

Emergent Risk Awareness in Rational Agents under Resource Constraints

• Daniel Jarne Ornia
• Nicholas Bishop
• Joel Dyer
• Wei-Chen Lee
• Anisoara Calinescu
• Doyne Farmer
• Michael Wooldridge

Advanced reasoning models with agentic capabilities (AI agents) are deployed to interact with humans and to solve sequential decision‑making problems under (often approximate) utility functions and internal models. When such problems have resource or failure constraints where action sequences may be forcibly terminated once resources are exhausted, agents face implicit trade‑offs that reshape their utility-driven (rational) behaviour. Additionally, since these agents are typically commissioned by a human principal to act on their behalf, asymmetries in constraint exposure can give rise to previously unanticipated misalignment between human objectives and agent incentives. We formalise this setting through a survival bandit framework, provide theoretical and empirical results that quantify the impact of survival‑driven preference shifts, identify conditions under which misalignment emerges and propose mechanisms to mitigate the emergence of risk-seeking or risk-averse behaviours. As a result, this work aims to increase understanding and interpretability of emergent behaviours of AI agents operating under such survival pressure, and offer guidelines for safely deploying such AI systems in critical resource‑limited environments.

AAMAS Conference 2025 Conference Paper

Equilibrium Selection via Communication Partition

• Wei-Chen Lee
• Alessandro Abate
• Michael Wooldridge

Coordinating the behaviour of self-interested agents in the presence of multiple Nash equilibria is a major research challenge for multiagent systems. Pre-game communication between all the players can aid coordination in cases where the Pareto-optimal payoff is unique, but can lead to deadlocks when there are multiple payoffs on the Pareto frontier. We consider a communication partition where only players within the same coalition can communicate with each other. We show that under some natural assumptions about symmetry and the conditions under which players within the same coalition can reach an agreement about their joint actions, certain communication partitions can induce socially optimal outcomes in singleton congestion games. This game is a reasonable model for a decentralised, anonymous system where players are required to choose from a range of identical resources, and incur costs that are increasing and convex in the total number of players sharing the same resource. The communication partition can be seen as a mechanism for inducing efficient outcomes in this context.

AAAI Conference 2025 Conference Paper

Language-Models-as-a-Service: Overview of a New Paradigm and its Challenges

• Emanuele La Malfa
• Aleksandar Petrov
• Simon Frieder
• Christoph Weinhuber
• Ryan Burnell
• Raza Nazar
• Anthony Cohn
• Nigel Shadbolt

Some of the most powerful language models currently are proprietary systems, accessible only via (typically restrictive) web or software programming interfaces. This is the LanguageModels-as-a-Service (LMaaS) paradigm. In contrast with scenarios where full model access is available, as in the case of open-source models, such closed-off language models present specific challenges for evaluating, benchmarking, and testing them. This paper has two goals: on the one hand, we delineate how the aforementioned challenges act as impediments to the accessibility, reproducibility, reliability, and trustworthiness of LMaaS. We systematically examine the issues that arise from a lack of information about language models for each of these four aspects. We conduct a detailed analysis of existing solutions, put forth a number of recommendations, and highlight directions for future advancements. On the other hand, it serves as a synthesized overview of the licences and capabilities of the most popular LMaaS.

NeurIPS Conference 2025 Conference Paper

Large Language Models Miss the Multi-agent Mark

• Emanuele La Malfa
• Gabriele La Malfa
• Samuele Marro
• Jie Zhang
• Elizabeth Black
• Michael Luck
• Philip Torr
• Michael Wooldridge

Recent interest in Multi-Agent Systems of Large Language Models (MAS LLMs) has led to an increase in frameworks leveraging multiple LLMs to tackle complex tasks. However, much of this literature appropriates the terminology of MAS without engaging with its foundational principles. In this position paper, we highlight critical discrepancies between MAS theory and current MAS LLMs implementations, focusing on four key areas: the social aspect of agency, environment design, coordination and communication protocols, and measuring emergent behaviours. Our position is that many MAS LLMs lack multi-agent characteristics such as autonomy, social interaction, and structured environments, and often rely on oversimplified, LLM-centric architectures. The field may slow down and lose traction by revisiting problems the MAS literature has already addressed. Therefore, we systematically analyse this issue and outline associated research opportunities; we advocate for better integrating established MAS concepts and more precise terminology to avoid mischaracterisation and missed opportunities.

IJCAI Conference 2024 Conference Paper

A Strategic Analysis of Prepayments in Financial Credit Networks

• Hao Zhou
• Yongzhao Wang
• Konstantinos Varsos
• Nicholas Bishop
• Rahul Savani
• Anisoara Calinescu
• Michael Wooldridge

In financial credit networks, prepayments enable a firm to settle its debt obligations ahead of an agreed-upon due date. Prepayments have a transformative impact on the structure of networks, influencing the financial well-being (utility) of individual firms. This study investigates prepayments from both theoretical and empirical perspectives. We first establish the computational complexity of finding prepayments that maximize welfare, assuming global coordination among firms in the financial network. Subsequently, our focus shifts to understanding the strategic behavior of individual firms in the presence of prepayments. We introduce a prepayment game where firms strategically make prepayments, delineating the existence of pure strategy Nash equilibria and analyzing the price of anarchy (stability) within this game. Recognizing the computational challenges associated with determining Nash equilibria in prepayment games, we use a simulation-based approach, known as empirical game-theoretic analysis (EGTA). Through EGTA, we are able to find Nash equilibria among a carefully-chosen set of heuristic strategies. By scrutinizing the equilibrium behavior of firms, we outline the characteristics of high-performing strategies for strategic prepayments and establish connections between our empirical and theoretical findings.

IJCAI Conference 2024 Conference Paper

Endogenous Energy Reactive Modules Games: Modelling Side Payments among Resource-Bounded Agents

• Julian Gutierrez
• David Hyland
• Muhammad Najib
• Giuseppe Perelli
• Michael Wooldridge

We introduce Energy Reactive Modules Games (ERMGs), an extension of Reactive Modules Games (RMGs) in which actions incur an energy cost (which may be positive or negative), and the choices that players make are restricted by the energy available to them. In ERMGs, each action is associated with an energy level update, which determines how their energy level is affected by the performance of the action. In addition, agents are provided with an initial energy allowance. This allowance plays a crucial role in shaping an agent’s behaviour, as it must be taken into consideration when one is determining their strategy: agents may only perform actions if they have the requisite energy. We begin by studying rational verification for ERMGs and then introduce Endogenous ERMGs, where agents can choose to transfer their energy to other agents. This exchange may enable equilibria that are impossible to achieve without such transfers. We study the decision problem of whether a stable outcome exists under both the Nash equilibrium and Core solution concepts.

KR Conference 2024 Conference Paper

Incentive Design for Rational Agents

• David Hyland
• Munyque Mittelmann
• Aniello Murano
• Giuseppe Perelli
• Michael Wooldridge

We introduce Incentive Design: a new class of problems for equilibrium verification in multi-agent systems. In our model, agents attempt to maximize their utility functions, which are expressed as formulae in LTL[F], a quantitative extension of Linear Temporal Logic with functions computable in polynomial time. We assume agents are rational, in the sense that they adopt strategies consistent with game theoretic solution concepts such as Nash equilibrium. For each solution concept we consider, we analyze the problems of verifying whether an incentive scheme achieves a societal objective and finding one that does so, whether it be social welfare or any other aggregate measure of collective well-being. We study both static and dynamic incentive schemes, showing that the latter are more powerful than the former. Finally, we solve the incentive verification and synthesis problems for all the solution concepts we consider, and analyze their complexity.

NeurIPS Conference 2024 Conference Paper

Interventionally Consistent Surrogates for Complex Simulation Models

• Joel Dyer
• Nicholas Bishop
• Yorgos Felekis
• Fabio Massimo Zennaro
• Anisoara Calinescu
• Theodoros Damoulas
• Michael Wooldridge

Large-scale simulation models of complex socio-technical systems provide decision-makers with high-fidelity testbeds in which policy interventions can be evaluated and what-if scenarios explored. Unfortunately, the high computational cost of such models inhibits their widespread use in policy-making settings. Surrogate models can address these computational limitations, but to do so they must behave consistently with the simulator under interventions of interest. In this paper, we build upon recent developments in causal abstractions to develop a framework for learning interventionally consistent surrogate models for large-scale, complex simulation models. We provide theoretical results showing that our proposed approach induces surrogates to behave consistently with high probability with respect to the simulator across interventions of interest, facilitating rapid experimentation with policy interventions in complex systems. We further demonstrate with empirical studies that conventionally trained surrogates can misjudge the effect of interventions and misguide decision-makers towards suboptimal interventions, while surrogates trained for interventional consistency with our method closely mimic the behaviour of the original simulator under interventions of interest.

JAIR Journal 2024 Journal Article

Language-Models-as-a-Service: Overview of a New Paradigm and its Challenges

• Emanuele La Malfa
• Aleksandar Petrov
• Simon Frieder
• Christoph Weinhuber
• Ryan Burnell
• Raza Nazar
• Anthony Cohn
• Nigel Shadbolt

Some of the most powerful language models currently are proprietary systems, accessible only via (typically restrictive) web or software programming interfaces. This is the Language-Models-as-a-Service (LMaaS) paradigm. In contrast with scenarios where full model access is available, as in the case of open-source models, such closed-off language models present specific challenges for evaluating, benchmarking, and testing them. This paper has two goals: on the one hand, we delineate how the aforementioned challenges act as impediments to the accessibility, reproducibility, reliability, and trustworthiness of LMaaS. We systematically examine the issues that arise from a lack of information about language models for each of these four aspects. We conduct a detailed analysis of existing solutions, put forth a number of recommendations, and highlight directions for future advancements. On the other hand, it serves as a synthesized overview of the licences and capabilities of the most popular LMaaS.

JAIR Journal 2024 Journal Article

Learning to Resolve Social Dilemmas: A Survey

• Shaheen Fatima
• Nicholas R. Jennings
• Michael Wooldridge

Social dilemmas are situations of inter-dependent decision making in which individual rationality can lead to outcomes with poor social qualities. The ubiquity of social dilemmas in social, biological, and computational systems has generated substantial research across these diverse disciplines into the study of mechanisms for avoiding deficient outcomes by promoting and maintaining mutual cooperation. Much of this research is focused on studying how individuals faced with a dilemma can learn to cooperate by adapting their behaviours according to their past experience. In particular, three types of learning approaches have been studied: evolutionary game-theoretic learning, reinforcement learning, and best-response learning. This article is a comprehensive integrated survey of these learning approaches in the context of dilemma games. We formally introduce dilemma games and their inherent challenges. We then outline the three learning approaches and, for each approach, provide a survey of the solutions proposed for dilemma resolution. Finally, we provide a comparative summary and discuss directions in which further research is needed.

IJCAI Conference 2024 Conference Paper

Learning to Resolve Social Dilemmas: A Survey (Abstract Reprint)

• Shaheen Fatima
• Nicholas Jennings
• Michael Wooldridge

Social dilemmasare situations of inter-dependent decision making in which individualrationality can lead to outcomes with poor social qualities. The ubiquity of social dilem-mas in social, biological, and computational systems has generated substantial researchacross these diverse disciplines into the study of mechanisms for avoiding deficient outcomes by promoting and maintaining mutual cooperation. Much of this research is focused on studying how individuals faced with a dilemma can learn to cooperate by adapting their behaviours according to their past experience. In particular, three types of learning approaches have been studied: evolutionary game-theoretic learning, reinforcement learning, and best-response learning. This article is a comprehensive integrated survey of these learning approaches in the context of dilemma games. We formally introduce dilemma games and their inherent challenges. We then outline the three learning approaches and, for eachapproach, provide a survey of the solutions proposed for dilemma resolution. Finally, we provide a comparative summary and discuss directions in which further research is needed.

AAMAS Conference 2024 Conference Paper

Population Synthesis as Scenario Generation for Simulation-based Planning under Uncertainty

• Joel Dyer
• Arnau Quera-Bofarull
• Nicholas Bishop
• J. Doyne Farmer
• Anisoara Calinescu
• Michael Wooldridge

Agent-based models have the potential to become instrumental tools in real-world decision-making, equipping policy-makers with the ability to experiment with high-fidelity representations of complex systems. Such models often rely crucially on the generation of synthetic populations with which the model is simulated, and their behaviour can depend strongly on the population’s composition. Existing approaches to synthesising populations attempt to model distributions over agent-level attributes on the basis of data collected from a real-world population. Unfortunately, these approaches are of limited utility when data is incomplete or altogether absent – such as during novel, unprecedented circumstances – so that considerable uncertainty regarding the characteristics of the population being modelled remains, even after accounting for any such data. What is therefore needed in these cases are tools to simulate and plan for the possible future behaviours of the complex system that can be generated by populations that are consistent with this remaining uncertainty. To this end, we frame the problem of synthesising populations in agent-based models as a problem of scenario generation. The framework that we present is designed to generate synthetic populations that are on the one hand consistent with any persisting uncertainty, while on the other hand matching closely a target, user-specified scenario that the decision-maker would like to explore and plan for. We propose and compare two generic approaches to generating synthetic populations that produce target scenarios, and demonstrate through simulation studies that these approaches are able to automatically generate synthetic populations whose behaviours match the target scenario, thereby facilitating simulation-based planning under uncertainty.

AAMAS Conference 2024 Conference Paper

Private Agent-Based Modeling

• Ayush Chopra
• Arnau Quera-Bofarull
• Nurullah Giray-Kuru
• Michael Wooldridge
• Ramesh Raskar

The practical utility of agent-based models in decision-making relies on their capacity to accurately replicate populations while seamlessly integrating real-world data streams. Yet, the incorporation of such data poses significant challenges due to privacy concerns. To address this issue, we introduce a paradigm for private agentbased modeling wherein the simulation, calibration, and analysis of agent-based models can be achieved without centralizing the agents’ attributes or interactions. The key insight is to leverage techniques from secure multi-party computation to design protocols for decentralized computation in agent-based models. This ensures the confidentiality of the simulated agents without compromising on simulation accuracy. We showcase our protocols on a case study with an epidemiological simulation comprising over 150, 000 agents. We believe this is a critical step towards deploying agent-based models to real-world applications.

AAMAS Conference 2024 Conference Paper

Rational Verification with Quantitative Probabilistic Goals

• David Hyland
• Julian Gutierrez
• Krishna Shankaranarayanan
• Michael Wooldridge

We study the rational verification problem for multi-agent systems in a setting where agents have quantitative probabilistic goals. We use concurrent stochastic games to model multi-agent systems and assume players desire to maximise the probability of satisfying their goals, specified using Linear Temporal Logic (LTL). The main decision problem in this setting is whether a given LTL formula is almost surely satisfied on some pure Nash equilibrium of a given game. We prove that this problem is undecidable in the general case, and then characterise the complexity of this problem under various restrictions on strategies. We also study the problem of deciding whether a given strategy profile is a Nash equilibrium in a given game and show that, unlike the previous verification problem, this question is decidable for several common strategy models.

AAAI Conference 2024 Conference Paper

Reasoning about Causality in Games (Abstract Reprint)

• Lewis Hammond
• James Fox
• Tom Everitt
• Ryan Carey
• Alessandro Abate
• Michael Wooldridge

Causal reasoning and game-theoretic reasoning are fundamental topics in artificial intelligence, among many other disciplines: this paper is concerned with their intersection. Despite their importance, a formal framework that supports both these forms of reasoning has, until now, been lacking. We offer a solution in the form of (structural) causal games, which can be seen as extending Pearl's causal hierarchy to the game-theoretic domain, or as extending Koller and Milch's multi-agent influence diagrams to the causal domain. We then consider three key questions: i) How can the (causal) dependencies in games – either between variables, or between strategies – be modelled in a uniform, principled manner? ii) How may causal queries be computed in causal games, and what assumptions does this require? iii) How do causal games compare to existing formalisms? To address question i), we introduce mechanised games, which encode dependencies between agents' decision rules and the distributions governing the game. In response to question ii), we present definitions of predictions, interventions, and counterfactuals, and discuss the assumptions required for each. Regarding question iii), we describe correspondences between causal games and other formalisms, and explain how causal games can be used to answer queries that other causal or game-theoretic models do not support. Finally, we highlight possible applications of causal games, aided by an extensive open-source Python library.

JAIR Journal 2024 Journal Article

Selfishly Prepaying in Financial Credit Networks

• Hao Zhou
• Yongzhao Wang
• Konstantinos Varsos
• Nicholas Bishop
• Rahul Savani
• Anisoara Calinescu
• Michael Wooldridge

In financial credit networks, prepayments enable a firm to settle its debt obligations ahead of an agreed-upon due date. Prepayments have a transformative impact on the structure of networks, influencing the financial well-being (utility) of individual firms. This study investigates prepayments from both theoretical and empirical perspectives. We first establish the computational complexity of finding prepayments that maximize welfare, assuming global coordination among firms in the financial network. Subsequently, our focus shifts to understanding the strategic behavior of individual firms in the presence of prepayments. We introduce a prepayment game where firms strategically make prepayments, delineating the existence of pure strategy Nash equilibria and analyzing the price of anarchy (stability) within this game. Recognizing the computational challenges associated with determining Nash equilibria in prepayment games, we use a simulation-based approach, known as empirical game-theoretic analysis (EGTA). Through EGTA, we are able to find Nash equilibria among a carefully-chosen set of heuristic strategies. By examining the equilibrium behavior of firms, we outline the characteristics of high-performing strategies for strategic prepayments and establish connections between our empirical and theoretical findings.

AIJ Journal 2023 Journal Article

Cooperative concurrent games

• Julian Gutierrez
• Szymon Kowara
• Sarit Kraus
• Thomas Steeples
• Michael Wooldridge

AAMAS Conference 2023 Conference Paper

Don't Simulate Twice: One-Shot Sensitivity Analyses via Automatic Differentiation

• Arnau Quera-Bofarull
• Ayush Chopra
• Joseph Aylett-Bullock
• Carolina Cuesta-Lazaro
• Anisoara Calinescu
• Ramesh Raskar
• Michael Wooldridge

Agent-based models (ABMs) are a promising tool to simulate complex environments. Their rapid adoption requires scalable specification, efficient data-driven calibration, and validation through sensitivity analyses. Recent progress in tensorized and differentiable ABM design (GradABM) has enabled fast calibration of million-size populations, however, validation through sensitivity analysis is still computationally prohibitive due to the need for running the model a large number of times. Here, we present a novel methodology that uses automatic differentiation to perform a sensitivity analysis on a calibrated ABM without requiring any further simulations. The key insight is to leverage gradients of a GradABM to compute exact partial derivatives of any model output with respect to an arbitrary combination of parameters. We demonstrate the benefits of this approach on a case study of the first wave of COVID-19 in London, where we investigate the causes of variations in infections by age, socio-economic index, ethnicity, and geography. Finally, we also show that the same methodology allows for the design of optimal policy interventions. The code to reproduce the presented results is made available on GitHub 1.

AAMAS Conference 2023 Conference Paper

k -Prize Weighted Voting Game

• Wei-Chen Lee
• David Hyland
• Alessandro Abate
• Edith Elkind
• Jiarui Gan
• Julian Gutierrez
• Paul Harrenstein
• Michael Wooldridge

We introduce a natural variant of weighted voting games, which we refer to as 𝑘-Prize Weighted Voting Games. Such games consist of 𝑛 players with weights, and 𝑘 prizes, of possibly differing values. The players form coalitions, and the 𝑖-th largest coalition (by the sum of weights of its members) wins the 𝑖-th largest prize, which is then shared among its members. We present four solution concepts to analyse the games in this class, and characterise the existence of stable outcomes in games with three players and two prizes, and in games with uniform prizes. We then explore the efficiency of stable outcomes in terms of Pareto optimality and utilitarian social welfare. Finally, we study the computational complexity of finding stable outcomes.

AAAI Conference 2023 Conference Paper

Multi-Unit Auctions for Allocating Chance-Constrained Resources

• Anna Gautier
• Bruno Lacerda
• Nick Hawes
• Michael Wooldridge

Sharing scarce resources is a key challenge in multi-agent interaction, especially when individual agents are uncertain about their future consumption. We present a new auction mechanism for preallocating multi-unit resources among agents, while limiting the chance of resource violations. By planning for a chance constraint, we strike a balance between worst-case approaches, which under-utilise resources, and expected-case approaches, which lack formal guarantees. We also present an algorithm that allows agents to generate bids via multi-objective reasoning, which are then submitted to the auction. We then discuss how the auction can be extended to non-cooperative scenarios. Finally, we demonstrate empirically that our auction outperforms state-of-the-art techniques for chance-constrained multi-agent resource allocation in complex settings with up to hundreds of agents.

AAMAS Conference 2023 Conference Paper

Optimal Coalition Structures for Probabilistically Monotone Partition Function Games

• Shaheen Fatima
• Michael Wooldridge

We define probabilistically monotone partition function games, a subclass of the well-known partition function games in which we introduce uncertainty. We provide a constructive proof that an exact optimum can be found using a greedy approach, present an algorithm for finding an optimum, and analyze its time complexity.

IJCAI Conference 2023 Conference Paper

Principal-Agent Boolean Games

• David Hyland
• Julian Gutierrez
• Michael Wooldridge

We introduce and study a computational version of the principal-agent problem -- a classic problem in Economics that arises when a principal desires to contract an agent to carry out some task, but has incomplete information about the agent or their subsequent actions. The key challenge in this setting is for the principal to design a contract for the agent such that the agent's preferences are then aligned with those of the principal. We study this problem using a variation of Boolean games, where multiple players each choose valuations for Boolean variables under their control, seeking the satisfaction of a personal goal formula. In our setting, the principal can only observe some subset of these variables, and the principal chooses a contract which rewards players on the basis of the assignments they make for the variables that are observable to the principal. The principal's challenge is to design a contract so that, firstly, the principal's goal is achieved in some or all Nash equilibrium choices, and secondly, that the principal is able to verify that their goal is satisfied. In this paper, we formally define this problem and completely characterise the computational complexity of the most relevant decision problems associated with it.

AIJ Journal 2023 Journal Article

Reasoning about causality in games

• Lewis Hammond
• James Fox
• Tom Everitt
• Ryan Carey
• Alessandro Abate
• Michael Wooldridge

AAMAS Conference 2023 Conference Paper

Risk-Constrained Planning for Multi-Agent Systems with Shared Resources

• Anna Gautier
• Marc Rigter
• Bruno Lacerda
• Nick Hawes
• Michael Wooldridge

Planning under uncertainty requires complex reasoning about future events, and this complexity increases with the addition of multiple agents. One problem faced when considering multi-agent systems under uncertainty is the handling of shared resources. Adding a resource constraint limits the actions that agents can take, forcing collaborative decision making on who gets to use what resources. Prior work has considered different formulations, such as satisfying a resource constraint in expectation or ensuring that a resource constraint is met some percent of the time. However, these formulations of constrained planning ignore important distributional information about resource usage. Namely, they do not consider how bad the worst cases can get. In this paper, we formulate a risk-constrained shared resource problem and aim to limit the risk of excessive use of such resources. We focus on optimising for reward while constraining the Conditional Value-at-Risk (CVaR) of the shared resource. While CVaR is well studied in the single-agent setting, we consider the challenges that arise from the state and action space explosion in the multi-agent setting. In particular, we exploit risk contributions, a measure introduced in finance research which quantifies how much individual agents affect the joint risk. We present an algorithm that uses risk contributions to iteratively update single-agent policies until the joint risk constraint is satisfied. We evaluate our algorithm on two synthetic domains.

AIJ Journal 2022 Journal Article

Defense coordination in security games: Equilibrium analysis and mechanism design

• Jiarui Gan
• Edith Elkind
• Sarit Kraus
• Michael Wooldridge

AAMAS Conference 2022 Conference Paper

Multiagent Model-based Credit Assignment for Continuous Control

• Dongge Han
• Chris Xiaoxuan Lu
• Tomasz Michalak
• Michael Wooldridge

Deep reinforcement learning (RL) has recently shown great promise in robotic continuous control tasks. Nevertheless, prior research in this vein center around the centralized learning setting that largely relies on the communication availability among all the components of a robot. However, agents in the real world often operate in a decentralised fashion without communication due to latency requirements, limited power budgets and safety concerns. By formulating robotic components as a system of decentralised agents, this work presents a decentralised multiagent reinforcement learning framework for continuous control. To this end, we first develop a cooperative multiagent PPO framework that allows for centralized optimisation during training and decentralised operation during execution. However, the system only receives a global reward signal which is not attributed towards each agent. To address this challenge, we further propose a generic game-theoretic credit assignment framework which computes agent-specific reward signals. Last but not least, we also incorporate a model-based RL module into our credit assignment framework, which leads to significant improvement in sample efficiency. Finally, we empirically demonstrate the effectiveness of our framework on Mujoco locomotion control tasks.

AAMAS Conference 2022 Conference Paper

Negotiated Path Planning for Non-Cooperative Multi-Robot Systems

• Anna Gautier
• Alex Stephens
• Bruno Lacerda
• Nick Hawes
• Michael Wooldridge

As autonomous systems are deployed at a large scale in both public and private spaces, robots owned and operated by competing organisations will be required to interact. Interactions in such settings will be inherently non-cooperative. In this paper, we address the problem of non-cooperative multi-agent path finding. We design an auction mechanism that allows a group of agents to reach their goals whilst minimising the total cost of the system. In particular, we aim to design a mechanism such that rational agents are incentivised to participate. Our privileged knowledge auction consists of a modified combinatorial Vickrey-Clarke-Groves auction. Our approach limits the initial number of bids in the Vickrey-Clarke-Groves auction, then uses the privileged knowledge of the auctioneer to identify and solve path conflicts. In order to maintain agent autonomy in the non-cooperative system, individual agents are provided with final say over paths. The mechanism provides a heuristic method to maximise social welfare whilst remaining computationally efficient. We also consider single-agent bid generation and propose a similarity metric to use in dissimilar shortest path generation. We then show this bid generation method increases the success likelihood of both the limited-bid VCG auction and our novel approach on synthetic data. Our experiments with synthetic data outperform existing work on the non-cooperative problem.

JAAMAS Journal 2022 Journal Article

Optimal coalition structures for probabilistically monotone partition function games

• Shaheen Fatima
• Michael Wooldridge

Abstract For cooperative games with externalities, the problem of optimally partitioning a set of players into disjoint exhaustive coalitions is called coalition structure generation, and is a fundamental computational problem in multi-agent systems. Coalition structure generation is, in general, computationally hard and a large body of work has therefore investigated the development of efficient solutions for this problem. However, the existing methods are mostly limited to deterministic environments. In this paper, we focus attention on uncertain environments. Specifically, we define probabilistically monotone partition function games, a subclass of the well-known partition function games in which we introduce uncertainty. We provide a constructive proof that an exact optimum can be found using a greedy approach, present an algorithm for finding an optimum, and analyze its time complexity.

IS Journal 2022 Journal Article

Understanding Mechanism Design—Part 3 of 3: Mechanism Design in the Real World: The VCG Mechanism

• Anna Gautier
• Michael Wooldridge

In the first two parts of this short series, we learned how mechanism design can be used in theory to engineer systems that achieve desirable properties by anticipating how rational agents will act, and then designing the rules accordingly. In particular, we focused on the Vickrey–Clarke–Groves (VCG) mechanism that results in a welfare maximizing outcome by incentivizing agents to tell the truth about how much they prefer each outcome. Now, let's explore how the VCG mechanisms may be used to solve real-world problems.

IS Journal 2022 Journal Article

Welcome to Big AI

• Michael Wooldridge

My college office in Oxford overlooks a narrow, ancient street called New College Lane; directly opposite my office window is a handsome 17th-century house that was the home of Edmond Halley—he of the comet fame—who became Savilian Professor of Geometry at Oxford in 1703. On top of the house is an odd shed-like structure: it was Halley's observatory. It serves as a daily reminder to me that, 300 years ago, world-changing science could be done in your own home, with facilities no fancier than a garden shed. Fast forward to April 2019, and the first-ever pictures of a black hole, which made front-page headlines across the globe. The Event Horizon Telescope that generated the astonishing images is as far from Halley's modest observatory as one could imagine: a global network of radio telescopes, in a collaboration involving 13 core partners and dozens of affiliates—supported by a lot of very advanced computer technology, and a big budget. You can still discover a comet from your garden shed, but for the most part, astronomy today is Big Science.

AAMAS Conference 2021 Conference Paper

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

• Lewis Hammond
• James Fox
• Tom Everitt
• Alessandro Abate
• Michael Wooldridge

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.

TIST Journal 2021 Journal Article

How Members of Covert Networks Conceal the Identities of Their Leaders

• Marcin Waniek
• Tomasz P. Michalak
• Michael Wooldridge
• Talal Rahwan

Centrality measures are the most commonly advocated social network analysis tools for identifying leaders of covert organizations. While the literature has predominantly focused on studying the effectiveness of existing centrality measures or developing new ones, we study the problem from the opposite perspective, by focusing on how a group of leaders can avoid being identified by centrality measures as key members of a covert network. More specifically, we analyze the problem of choosing a set of edges to be added to a network to decrease the leaders’ ranking according to three fundamental centrality measures, namely, degree, closeness, and betweenness. We prove that this problem is NP-complete for each measure. Moreover, we study how the leaders can construct a network from scratch, designed specifically to keep them hidden from centrality measures. We identify a network structure that not only guarantees to hide the leaders to a certain extent but also allows them to spread their influence across the network.

LAMAS&SR Workshop 2021 Workshop Paper

Mean-Payoff Games with Omega-Regular Specifications

• Thomas Steeples
• Julian Gutierrez
• Michael Wooldridge

Multi-player mean-payoff games are a natural formalism for modelling the behaviour of concurrent and multi-agent systems with self-interested players. Players in such a game traverse a graph, while trying to maximise a mean-payoff function that depends on the plays so generated. As with all games, the equilibria that could arise may have undesirable properties. However, as system designers, we typically wish to ensure that equilibria in such systems correspond to desirable system behaviours, for example, satisfying certain safety or liveness properties. One natural way to do this would be to specify such desirable properties using temporal logic. Unfortunately, the use of temporal logic specifications causes game theoretic verification problems to have very high computational complexity. To this end, we consider 𝜔-regular specifications, which offer a concise and intuitive way of specifying desirable behaviours of a system. The main results of this work are characterisation and complexity bounds for the problem of determining if there are equilibria that satisfy a given 𝜔-regular specification in a multiplayer mean-payoff game in a number of computationally relevant game-theoretic settings.

AAMAS Conference 2021 Conference Paper

Mean-Payoff Games with ω-Regular Specifications

• Thomas Steeples
• Julian Gutierrez
• Michael Wooldridge

Multi-player mean-payoff games are a natural formalism to model concurrent and multi-agent systems with self-interested players. Players in such a game traverse a graph, while trying to maximise a mean-payoff function that depends on the plays so generated. As with all games, the equilibria that could arise may have undesirable properties. However, as system designers, we typically wish to ensure that equilibria in such systems correspond to desirable system behaviours, for example, satisfying certain safety or liveness properties. One natural way to do this would be to specify such desirable properties using temporal logic. Unfortunately, the use of temporal logic specifications causes game theoretic verification problems to have very high computational complexity. To this end, we consider ω-regular specifications, which offer a concise and intuitive way of specifying desirable behaviours of a system. The main results of this work are characterisation and complexity bounds for the problem of determining if there are equilibria that satisfy a given ω-regular specification in a multi-player mean-payoff game in a number of computationally relevant game-theoretic settings.

AAMAS Conference 2021 Conference Paper

Multi-Agent Reinforcement Learning with Temporal Logic Specifications

• Lewis Hammond
• Alessandro Abate
• Julian Gutierrez
• Michael Wooldridge

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.

KR Conference 2021 Conference Paper

Rational Verification for Probabilistic Systems

• Julian Gutierrez
• Lewis Hammond
• Anthony W. Lin
• Muhammad Najib
• Michael Wooldridge

Rational verification is the problem of determining which temporal logic properties will hold in a multi-agent system, under the assumption that agents in the system act rationally, by choosing strategies that collectively form a game-theoretic equilibrium. Previous work in this area has largely focussed on deterministic systems. In this paper, we develop the theory and algorithms for rational verification in probabilistic systems. We focus on concurrent stochastic games (CSGs), which can be used to model uncertainty and randomness in complex multi-agent environments. We study the rational verification problem for both non-cooperative games and cooperative games in the qualitative probabilistic setting. In the former case, we consider LTL properties satisfied by the Nash equilibria of the game and in the latter case LTL properties satisfied by the core. In both cases, we show that the problem is 2EXPTIME-complete, thus not harder than the much simpler verification problem of model checking LTL properties of systems modelled as Markov decision processes (MDPs).

AIJ Journal 2020 Journal Article

Artificial Intelligence requires more than deep learning — but what, exactly?

• Michael Wooldridge

AIJ Journal 2020 Journal Article

Automated temporal equilibrium analysis: Verification and synthesis of multi-player games

• Julian Gutierrez
• Muhammad Najib
• Giuseppe Perelli
• Michael Wooldridge

IS Journal 2020 Journal Article

Through the Veil of Ignorance: Understanding Social Welfare

• Michael Wooldridge

The most common perspective of game theory is that of an individual decision-maker, who attempts to make a decision about what to do in an attempt to bring about the most preferred outcome for themselves. Such decision making in game theory is distinguished from conventional optimization problems by the fact that the consequences of an individual’s decision will depend not just on their choice, but on the choices made by others. This motivates the development of solution concepts for the game theory, of which Nash equilibrium is the best-known. These solution concepts attempt to characterize how rational agents would make choices in such situations. But there is another way of thinking about games, as follows. Suppose, instead of being a player within the game, you were a benevolent omniscient external entity, who was able to simply choose the outcome for the game.

IS Journal 2020 Journal Article

Understanding Mechanism Design––Part 1 of 3

• Michael Wooldridge

Reports on the concept of mechanism design. In most settings of multiagent decision making, the individual decision makers have no choice but to accept the “rules of encounter. ” They must decide how to act as best they can in pursuit of their personal preferences while obeying the rules of the game. And indeed, this type of situation is by far the most commonly studied scenario in game theory. But sometimes in the real world, we are not a player within a game–– we are the designer of the game. This situation is increasingly common in computing and AI. For example, if you build an online marketplace like eBay, then you are creating a system in which self-interested agents will interact according to the rules that you create. To pick another example, consider an online academic peer-reviewing system of the type that is now routinely used to manage the reviewing process for academic conferences.

AAMAS Conference 2019 Conference Paper

Computing Optimal Coalition Structures in Polynomial Time

• Shaheen Fatima
• Michael Wooldridge

The optimal coalition structure determination problem is in general computationally hard. In this article, we identify some problem instances for which the space of possible coalition structures has a certain form and constructively prove that the problem is polynomial time solvable. Specifically, we consider games with an ordering over the players and introduce a distance metric for measuring the distance between any two structures. In terms of this metric, we define the property of monotonicity, meaning that coalition structures closer to the optimal, as measured by the metric, have higher value than those further away. Similarly, quasi-monotonicity means that part of the space of coalition structures is monotonic, while part of it is non-monotonic. (Quasi)-monotonicity is a property that can be satisfied by coalition games in characteristic function form and also those in partition function form. For a setting with a monotonic value function and a known player ordering, we prove that the optimal coalition structure determination problem is polynomial time solvable and devise such an algorithm using a greedy approach. We extend this algorithm to quasi-monotonic value functions and demonstrate how its time complexity improves from exponential to polynomial as the degree of monotonicity of the value function increases. We go further and consider a setting in which the value function is monotonic and an ordering over the players is known to exist but ordering itself is unknown. For this setting too, we prove that the coalition structure determination problem is polynomial time solvable and devise such an algorithm.

AAMAS Conference 2019 Conference Paper

Cooperative Concurrent Games

• Julian Gutierrez
• Sarit Kraus
• Michael Wooldridge

In rational verification, one is interested in understanding which temporal logic properties will hold in a concurrent game, under the assumption that players choose strategies that form an equilibrium. Players are assumed to behave rationally in pursuit of individual goals, typically specified as temporal logic formulae. To date, rational verification has only been studied in noncooperative settings. In this paper, we extend the rational verification framework to cooperative games, in which players may form coalitions to collectively achieve their goals. We base our study on the computational model given by concurrent game structures and focus on the core as our basic solution concept. We show the core of a concurrent game can be logically characterised using ATL*, and study the computational complexity of key decision problems associated with the core, which range from problems in PSPACE to problems in 3EXPTIME. We also discuss a number of variants of the main definition of the core, leading to the issue of credible coalition formations, and a possible implementation of the main reasoning framework.

TIST Journal 2019 Journal Article

Enumerating Connected Subgraphs and Computing the Myerson and Shapley Values in Graph-Restricted Games

• Oskar Skibski
• Talal Rahwan
• Tomasz P. Michalak
• Michael Wooldridge

At the heart of multi-agent systems is the ability to cooperate to improve the performance of individual agents and/or the system as a whole. While a widespread assumption in the literature is that such cooperation is essentially unrestricted, in many realistic settings this assumption does not hold. A highly influential approach for modelling such scenarios are graph-restricted games introduced by Myerson [36]. In this approach, agents are represented by nodes in a graph, edges represent communication channels, and a group can generate an arbitrary value only if there exists a direct or indirect communication channel between every pair of agents within the group. Two fundamental solution-concepts that were proposed for such games are the Myerson value and the Shapley value. While an algorithm has been developed to compute the Shapley value in arbitrary graph-restricted games, no such general-purpose algorithm has been developed for the Myerson value to date. With this in mind, we set out to develop for such games a general-purpose algorithm to compute the Myerson value, and a more efficient algorithm to compute the Shapley value. Since the computation of either value involves enumerating all connected induced subgraphs of the game’s underlying graph, we start by developing an algorithm dedicated to this enumeration, and then we show empirically that it is faster than the state of the art in the literature. Finally, we present a sample application of both algorithms, in which we test the Myerson value and the Shapley value as advanced measures of node centrality in networks.

NeurIPS Conference 2019 Conference Paper

Manipulating a Learning Defender and Ways to Counteract

• Jiarui Gan
• Qingyu Guo
• Long Tran-Thanh
• Bo An
• Michael Wooldridge

In Stackelberg security games when information about the attacker's payoffs is uncertain, algorithms have been proposed to learn the optimal defender commitment by interacting with the attacker and observing their best responses. In this paper, we show that, however, these algorithms can be easily manipulated if the attacker responds untruthfully. As a key finding, attacker manipulation normally leads to the defender learning a maximin strategy, which effectively renders the learning attempt meaningless as to compute a maximin strategy requires no additional information about the other player at all. We then apply a game-theoretic framework at a higher level to counteract such manipulation, in which the defender commits to a policy that specifies her strategy commitment according to the learned information. We provide a polynomial-time algorithm to compute the optimal such policy, and in addition, a heuristic approach that applies even when the attacker's payoff space is infinite or completely unknown. Empirical evaluation shows that our approaches can improve the defender's utility significantly as compared to the situation when attacker manipulation is ignored.

AAMAS Conference 2019 Conference Paper

Multi-Agent Hierarchical Reinforcement Learning with Dynamic Termination

• Dongge Han
• Wendelin Boehmer
• Michael Wooldridge
• Alex Rogers

In a multi-agent system, an agent’s optimal policy will typically depend on the policies of other agents. Predicting the behaviours of others, and responding promptly to changes in such behaviours, is therefore a key issue in multi-agent systems research. One obvious possibility is for each agent to broadcast their current intention, for example, the currently executed option in a hierarchical RL framework. However, this approach results in inflexible agents when options have an extended duration. While adjusting the executed option at each step improves flexibility from a single-agent perspective, frequent changes in options can induce inconsistency between an agent’s actual behaviour and its broadcasted intention. In order to balance flexibility and predictability, we propose a dynamic termination Bellman equation that allows the agents to flexibly terminate their options.

IJCAI Conference 2019 Conference Paper

On Computational Tractability for Rational Verification

• Julian Gutierrez
• Muhammad Najib
• Giuseppe Perelli
• Michael Wooldridge

Rational verification involves checking which temporal logic properties hold of a concurrent and multiagent system, under the assumption that agents in the system choose strategies in game theoretic equilibrium. Rational verification can be understood as a counterpart of model checking for multiagent systems, but while 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 more intractable: it is 2EXPTIME-complete with LTL specifications, even when using explicit-state system representations. In this paper 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 most response properties of reactive systems. We also provide improved complexity results for rational verification when considering players' goals given by mean-payoff utility functions -- arguably the most widely used quantitative objective for agents in concurrent and multiagent systems. In particular, we show that for a number of relevant settings, rational verification can be done in polynomial space or even in polynomial time.

AIJ Journal 2019 Journal Article

Łukasiewicz logics for cooperative games

• Enrico Marchioni
• Michael Wooldridge

TAAS Journal 2018 Journal Article

A Measure of Added Value in Groups

• Bedoor K. Alshebli
• Tomasz P. Michalak
• Oskar Skibski
• Michael Wooldridge
• Talal Rahwan

The intuitive notion of added value in groups represents a fundamental property of biological, physical, and economic systems: how the interaction or cooperation of multiple entities, substances, or other agents can produce synergistic effects. However, despite the ubiquity of group formation, a well-founded measure of added value has remained elusive. Here, we propose such a measure inspired by the Shapley value —a fundamental solution concept from Cooperative Game Theory. To this end, we start by developing a solution concept that measures the average impact of each player in a coalitional game and show how this measure uniquely satisfies a set of intuitive properties. Then, building upon our solution concept, we propose a measure of added value that not only analyzes the interactions of players inside their group, but also outside it, thereby reflecting otherwise-hidden information about how these individuals typically perform in various groups of the population.

IS Journal 2018 Journal Article

Agent-Based Modeling for Complex Financial Systems

• James Paulin
• Anisoara Calinescu
• Michael Wooldridge

Todays global financial marketplace is best understood as a complex network of interacting market systems, in which events of world-wide significance unfold on timescales that are barely within the ability of humans to comprehend. Many researchers have concluded that the dynamics of networked market systems are better under-stood as complex adaptive systems, in which independent software components interact without centralized control or oversight.

JAAMAS Journal 2018 Journal Article

Computing optimal coalition structures in polynomial time

• Shaheen Fatima
• Michael Wooldridge

Abstract The optimal coalition structure determination problem is in general computationally hard. In this article, we identify some problem instances for which the space of possible coalition structures has a certain form and constructively prove that the problem is polynomial time solvable. Specifically, we consider games with an ordering over the players and introduce a distance metric for measuring the distance between any two structures. In terms of this metric, we define the property of monotonicity, meaning that coalition structures closer to the optimal, as measured by the metric, have higher value than those further away. Similarly, quasi-monotonicity means that part of the space of coalition structures is monotonic, while part of it is non-monotonic. (Quasi)-monotonicity is a property that can be satisfied by coalition games in characteristic function form and also those in partition function form. For a setting with a monotonic value function and a known player ordering, we prove that the optimal coalition structure determination problem is polynomial time solvable and devise such an algorithm using a greedy approach. We extend this algorithm to quasi-monotonic value functions and demonstrate how its time complexity improves from exponential to polynomial as the degree of monotonicity of the value function increases. We go further and consider a setting in which the value function is monotonic and an ordering over the players is known to exist but ordering itself is unknown. For this setting too, we prove that the coalition structure determination problem is polynomial time solvable and devise such an algorithm.

JAIR Journal 2018 Journal Article

Efficient Computation of Semivalues for Game-Theoretic Network Centrality

• Mateusz K. Tarkowski
• Piotr L. Szczepański
• Tomasz P. Michalak
• Paul Harrenstein
• Michael Wooldridge

Some game-theoretic solution concepts such as the Shapley value and the Banzhaf index have recently gained popularity as measures of node centrality in networks. While this direction of research is promising, the computational problems that surround it are challenging and have largely been left open. To date there are only a few positive results in the literature, which show that some game-theoretic extensions of degree-, closeness- and betweenness-centrality measures are computable in polynomial time, i.e., without the need to enumerate the exponential number of all possible coalitions. In this article, we show that these results can be extended to a much larger class of centrality measures that are based on a family of solution concepts known as semivalues. The family of semivalues includes, among others, the Shapley value and the Banzhaf index. To this end, we present a generic framework for defining game-theoretic network centralities and prove that all centrality measures that can be expressed in this framework are computable in polynomial time. Using our framework, we present a number of new and polynomial-time computable game-theoretic centrality measures.

AIJ Journal 2018 Journal Article

Forming k coalitions and facilitating relationships in social networks

• Liat Sless
• Noam Hazon
• Sarit Kraus
• Michael Wooldridge

AAMAS Conference 2018 Conference Paper

Local Equilibria in Logic-Based Multi-Player Games

• Julian Gutierrez
• Paul Harrenstein
• Thomas Steeples
• Michael Wooldridge

Game theory provides a well-established framework for the analysis and verification of concurrent and multi-agent systems. Typically, the analysis of a multi-agent system involves computing the set of equilibria in the associated multi-player game representing the behaviour of the system. As systems grow larger, it becomes increasingly harder to find equilibria in the game – which represent the rationally stable behaviours of the multi-agent system (the solutions of the game). To address this issue, in this paper, we study the concept of local equilibria, which are defined with respect to (maximal) stable coalitions of agents for which an equilibrium can de found. We focus on the solutions given by the Nash equilibria of Boolean games and iterated Boolean games, two logic-based models for multi-agent systems, in which the players’ goals are given by formulae of propositional logic and LTL, respectively.

AAMAS Conference 2018 Conference Paper

Moral Values in Norm Decision Making

• Marc Serramia
• Maite Lopez-Sanchez
• Juan A. Rodriguez-Aguilar
• Manel Rodriguez
• Michael Wooldridge
• Javier Morales
• Carlos Ansotegui

Most often, both agents and human societies use norms to coordinate their on-going activities. Nevertheless, choosing the ‘right’ set of norms to regulate these societies constitutes an open problem. Firstly, intrinsic norm relationships may lead to inconsistencies in the chosen set of norms. Secondly, and more importantly, there is an increasing demand of including ethical considerations in the decision making process. This paper focuses on choosing the ‘right’ norms by considering moral values together with society’s partial preferences over these values and the extent to which candidate norms promote them. The resulting decision making problem can then be encoded as a linear program, and hence solved by state-ofthe art solvers. Furthermore, we empirically test several optimisation scenarios so to determine the system’s performance and the characteristics of the problem that affect its hardness.

JAAMAS Journal 2018 Journal Article

Off-line synthesis of evolutionarily stable normative systems

• Javier Morales
• Michael Wooldridge
• Maite López-sánchez

Abstract Within the area of multi-agent systems, normative systems are a widely used framework for the coordination of interdependent activities. A crucial problem associated with normative systems is that of synthesising norms that will effectively accomplish a coordination task and that the agents will comply with. Many works in the literature focus on the on-line synthesis of a single, evolutionarily stable norm (convention) whose compliance forms a rational choice for the agents and that effectively coordinates them in one particular coordination situation that needs to be identified and modelled as a game in advance. In this work, we introduce a framework for the automatic off-line synthesis of evolutionarily stable normative systems that coordinate the agents in multiple interdependent coordination situations that cannot be easily identified in advance nor resolved separately. Our framework roots in evolutionary game theory. It considers multi-agent systems in which the potential conflict situations can be automatically enumerated by employing MAS simulations along with basic domain information. Our framework simulates an evolutionary process whereby successful norms prosper and spread within the agent population, while unsuccessful norms are discarded. The outputs of such a natural selection process are sets of codependent norms that, together, effectively coordinate the agents in multiple interdependent situations and are evolutionarily stable. We empirically show the effectiveness of our approach through empirical evaluation in a simulated traffic domain.

AAMAS Conference 2018 Conference Paper

Stackelberg Security Games with Multiple Uncoordinated Defenders

• Jiarui Gan
• Edith Elkind
• Michael Wooldridge

Stackelberg security games have received much attention in recent years. While most existing work focuses on single-defender settings, there are many real-world scenarios that involve multiple defenders (e. g. , multi-national anti-crime actions in international waters, different security agencies patrolling the same area). In this paper, we consider security games with uncoordinated defenders who jointly protect a set of targets, but may have different valuations for these targets; each defender schedules their own resources and selfishly optimizes their own utility. We generalize the standard (single-defender) model of Stackelberg security games to this setting and formulate an equilibrium concept that captures the nature of strategic interaction among the players. We argue that an exact equilibrium may fail to exist, and, in fact, deciding whether it exists is NP-hard. However, under mild assumptions, every multi-defender security game admits an ϵ-equilibrium for every ϵ > 0, and the limit points corresponding to ϵ → 0 can be efficiently approximated.

IS Journal 2017 Journal Article

AI and Economics

• Tomasz P. Michalak
• Michael Wooldridge

The fields of economic theory and artificial intelligence (AI) share many common interests and notions such as utility, probability, and reasoning about other actors in the environment. This common ground has given rise to a wide body of literature at the interface of economic theory and AI whose scope includes algorithmic aspects of cooperative and noncooperative game theory, mechanism design, and computational social choice, just to name a few. This special issue reports the state of the art in theory, algorithms, and applications in this broad area.

AAMAS Conference 2017 Conference Paper

Automating Decision Making to Help Establish Norm-Based Regulations

• Maite Lopez-Sanchez
• Marc Serramia
• Juan A. Rodriguez-Aguilar
• Javier Morales
• Michael Wooldridge

Norms have been extensively proposed as coordination mechanisms for both agent and human societies. Nevertheless, choosing the norms to regulate a society is by no means straightforward. The reasons are twofold. First, the norms to choose from may not be independent (i. e, they can be related to each other). Second, different preference criteria may be applied when choosing the norms to enact. On the one hand, this paper considers norm representation power and cost as alternative preference criteria. On the other hand, it identifies three different norm relationships –namely, generalisation, exclusivity, and substitutability. We show that the decisionmaking problem faced by policy makers can be encoded as a linear program, and hence solved with the aid of state-of-the-art solvers.

IJCAI Conference 2017 Conference Paper

Characterising the Manipulability of Boolean Games

• Paul Harrenstein
• Paolo Turrini
• Michael Wooldridge

The existence of (Nash) equilibria with undesirable properties is a well-known problem in game theory, which has motivated much research directed at the possibility of mechanisms for modifying games in order to eliminate undesirable equilibria, or induce desirable ones. Taxation schemes are a well-known mechanism for modifying games in this way. In the multi-agent systems community, taxation mechanisms for incentive engineering have been studied in the context of Boolean games with costs. These are games in which each player assigns truth-values to a set of propositional variables she uniquely controls in pursuit of satisfying an individual propositional goal formula; different choices for the player are also associated with different costs. In such a game, each player prefers primarily to see the satisfaction of their goal, and secondarily, to minimise the cost of their choice, thereby giving rise to lexicographic preferences over goal-satisfaction and costs. Within this setting, where taxes operate on costs only, however, it may well happen that the elimination or introduction of equilibria can only be achieved at the cost of simultaneously introducing less desirable equilibria or eliminating more attractive ones. Although this framework has been studied extensively, the problem of precisely characterising the equilibria that may be induced or eliminated has remained open. In this paper we close this problem, giving a complete characterisation of those mechanisms that can induce a set of outcomes of the game to be exactly the set of Nash Equilibrium outcomes.

AAMAS Conference 2017 Conference Paper

Evolutionary Synthesis of Stable Normative Systems

• Javier Morales
• Michael Wooldridge
• Juan A. Rodrí guez-Aguilar
• Maite Ló pez-Sá nchez

Normative systems are a widely used framework to coordinate interdependent activities in multi-agent systems. Most research in this area has focused on how to compute normative systems that effectively accomplish a coordination task, as well as additional criteria such as synthesising norms that do not over-regulate a system, and the emergence of norms that remain stable over time. We introduce a framework for the synthesis of stable normative systems that are sufficient and necessary for coordination. Our approach is based on ideas from evolutionary game theory. We simulate multiagent systems in which useful norms are more likely to prosper than useless norms. We empirically show the effectiveness of our approach in a simulated traffic domain.

AIJ Journal 2017 Journal Article

From model checking to equilibrium checking: Reactive modules for rational verification

• Julian Gutierrez
• Paul Harrenstein
• Michael Wooldridge

AAMAS Conference 2017 Conference Paper

Iterated Boolean Games for Rational Verification

• Tong Gao
• Julian Gutierrez
• Michael Wooldridge

Rational verification is the problem of understanding what temporal logic properties hold of a multi-agent system when agents are modelled as players in a game, each acting rationally in pursuit of personal preferences. More specifically, rational verification asks whether a given property, expressed as a temporal logic formula, is satisfied in a computation of the system that might be generated if agents within the system choose strategies for selecting actions that form a Nash equilibrium. We show that, when agents are modelled using the Simple Reactive Modules Language, a widely-used system modelling language for concurrent and multi-agent systems, this problem can be reduced to a simpler query: whether some iterated game—in which players have control over a finite set of Boolean variables and goals expressed as Linear Temporal Logic (LTL) formulae—has a Nash equilibrium. To better understand the complexity of solving this kind of verification problem in practice, we then study the two-player case for various types of LTL goals, present some experimental results, and describe a general technique to implement rational verification using MCMAS, a model checking tool for the verification of concurrent and multi-agent systems.

AAMAS Conference 2017 Conference Paper

Iterated Games with LDL Goals over Finite Traces

• Julian Gutierrez
• Giuseppe Perelli
• Michael Wooldridge

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 setting we study—iterated Boolean games with goals over finite traces (iBGF )—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 games with LDLF objectives is regular, and provides complexity results for the associated automata constructions. CCS Concepts •Computing methodologies → Multi-agent systems;

IJCAI Conference 2017 Conference Paper

Nash Equilibria in Concurrent Games with Lexicographic Preferences

• Julian Gutierrez
• Aniello Murano
• Giuseppe Perelli
• Sasha Rubin
• Michael Wooldridge

We study concurrent games with finite-memory strategies where players are given a Buchi and a mean-payoff objective, which are related by a lexicographic order: a player first prefers to satisfy its Buchi objective, and then prefers to minimise costs, which are given by a mean-payoff function. In particular, we show that deciding the existence of a strict Nash equilibrium in such games is decidable, even if players' deviations are implemented as infinite memory strategies.

AAMAS Conference 2017 Conference Paper

On the Construction of Covert Networks

• Marcin Waniek
• Tomasz P. Michalak
• Talal Rahwan
• Michael Wooldridge

Centrality measures are widely used to identify leaders of covert networks. We study how a group of such leaders can avoid being detected by such measures. More concretely, we study the hardness of choosing a set of edges that can be added to the network in order to decrease the leaders’ ranking according to two fundamental centrality measures, namely degree, and closeness. We prove that this problem is NP-complete for each measure. We then study how the leaders can construct a network from scratch, designed specifically for them to hide in disguise. We identify a network structure that not only guarantees to hide the leaders to a certain extent, but also allows them to spread their influence across the network.

AAAI Conference 2017 Conference Paper

Strategic Social Network Analysis

• Tomasz Michalak
• Talal Rahwan
• Michael Wooldridge

How can individuals and communities protect their privacy against social network analysis tools? How do criminals or terrorists organizations evade detection by such tools? Under which conditions can these tools be made strategy proof? These fundamental questions have attracted little attention in the literature to date, as most social network analysis tools are built around the assumption that individuals or groups in a network do not act strategically to evade such tools. With this in mind, we outline in this paper a new paradigm for social network analysis, whereby the strategic behaviour of network actors is explicitly modeled. Addressing this research challenge has various implications. For instance, it may allow two individuals to keep their relationship secret or private. It may also allow members of an activist group to conceal their membership, or even conceal the existence of their group from authoritarian regimes. Furthermore, it may assist security agencies and counter terrorism units in understanding the strategies that covert organizations use to escape detection, and give rise to new strategy-proof countermeasures.

AIJ Journal 2016 Journal Article

A hybrid exact algorithm for complete set partitioning

• Tomasz Michalak
• Talal Rahwan
• Edith Elkind
• Michael Wooldridge
• Nicholas R. Jennings

KR Conference 2016 Conference Paper

Boolean Hedonic Games

• Haris Aziz
• Paul Harrenstein
• Jérôme Lang
• Michael Wooldridge

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.

AAAI Conference 2016 Conference Paper

Closeness Centrality for Networks with Overlapping Community Structure

• Mateusz Tarkowski
• Piotr Szczepański
• Talal Rahwan
• Tomasz Michalak
• Michael Wooldridge

Certain real-life networks have a community structure in which communities overlap. For example, a typical bus network includes bus stops (nodes), which belong to one or more bus lines (communities) that often overlap. Clearly, it is important to take this information into account when measuring the centrality of a bus stop—how important it is to the functioning of the network. For example, if a certain stop becomes inaccessible, the impact will depend in part on the bus lines that visit it. However, existing centrality measures do not take such information into account. Our aim is to bridge this gap. We begin by developing a new game-theoretic solution concept, which we call the Configuration semivalue, in order to have greater flexibility in modelling the community structure compared to previous solution concepts from cooperative game theory. We then use the new concept as a building block to construct the first extension of Closeness centrality to networks with community structure (overlapping or otherwise). Despite the computational complexity inherited from the Configuration semivalue, we show that the corresponding extension of Closeness centrality can be computed in polynomial time. We empirically evaluate this measure and our algorithm that computes it by analysing the Warsaw public transportation network.

AAMAS Conference 2016 Conference Paper

Expressiveness and Nash Equilibrium in Iterated Boolean Games

• Julian Gutierrez
• Paul Harrenstein
• Giuseppe Perelli
• Michael Wooldridge

We introduce and investigate a novel notion of expressiveness for temporal logics that is based on game theoretic properties of multiagent systems. We focus on iterated Boolean games, where each agent i has a goal γi, represented using (a fragment of) Linear Temporal Logic (LTL). The goal γi captures agent i’s preferences: the models of γi represent system behaviours that would satisfy i, and each player is assumed to act strategically, taking into account the goals of other players, in order to bring about computations satisfying their goal. In this setting, we apply the standard gametheoretic concept of Nash equilibria: the Nash equilibria of an iterated Boolean game can be understood as a (possibly empty) set of computations, each computation representing one way the system could evolve if players chose strategies in Nash equilibrium. Such an equilibrium set of computations can be understood as expressing a temporal property—which may or may not be expressible within a particular LTL fragment. The new notion of expressiveness that we study is then as follows: what LTL properties are characterised by the Nash equilibria of games in which agent goals are expressed in fragments of LTL? We formally define and investigate this notion of expressiveness and some related issues, for a range of LTL fragments.

KR Conference 2016 Conference Paper

ImperfectInformation in Reactive Modules Games

• Julian Gutierrez
• Giuseppe Perelli
• Michael Wooldridge

Reactive Modules is a high-level modelling language for concurrent, distributed, and multi-agent systems, which is used in a number of practical model checking tools. Reactive Modules Games are a game-theoretic extension of Reactive Modules, in which agents in a system are assumed to act strategically in an attempt to satisfy a temporal logic formula representing their individual goal. Reactive Modules Games with perfect information have been closely studied, and the complexity of game theoretic decision problems relating to such games have been comprehensively classified. However, to date, no work has considered the imperfect information case. In this paper we address this gap, investigating Reactive Modules Games in which agents have only partial visibility of their environment.

AAMAS Conference 2016 Conference Paper

k-Coalitional Cooperative Games

• Oskar Skibski
• Szymon Matejczyk
• Tomasz P. Michalak
• Michael Wooldridge
• Makoto Yokoo

AAAI Conference 2016 Conference Paper

Rational Verification: From Model Checking to Equilibrium Checking

• Michael Wooldridge
• Julian Gutierrez
• Paul Harrenstein
• Enrico Marchioni
• Giuseppe Perelli
• Alexis Toumi

Rational verification is concerned with establishing whether a given temporal logic formula ϕ is satisfied in some or all equilibrium computations of a multi-agent system – that is, whether the system will exhibit the behaviour ϕ under the assumption that agents within the system act rationally in pursuit of their preferences. After motivating and introducing the framework of rational verification, we present formal models through which rational verification can be studied, and survey the complexity of key decision problems. We give an overview of a prototype software tool for rational verification, and conclude with a discussion and related work.

AAAI Conference 2015 Conference Paper

A Graphical Representation for Games in Partition Function Form

• Oskar Skibski
• Tomasz Michalak
• Yuko Sakurai
• Michael Wooldridge
• Makoto Yokoo

We propose a novel representation for coalitional games with externalities, called Partition Decision Trees. This representation is based on rooted directed trees, where non-leaf nodes are labelled with agents’ names, leaf nodes are labelled with payoff vectors, and edges indicate membership of agents in coalitions. We show that this representation is fully expressive, and for certain classes of games significantly more concise than an extensive representation. Most importantly, Partition Decision Trees are the first formalism in the literature under which most of the direct extensions of the Shapley value to games with externalities can be computed in polynomial time.

AIJ Journal 2015 Journal Article

Coalition structure generation: A survey

• Talal Rahwan
• Tomasz P. Michalak
• Michael Wooldridge
• Nicholas R. Jennings

IS Journal 2015 Journal Article

Defeating Terrorist Networks with Game Theory

• Tomasz P. Michalak
• Talal Rahwan
• Oskar Skibski
• Michael Wooldridge

This column discusses the problem of identifying key members of a terrorist network. Game-theoretic centrality measures offer solutions but also raise computational challenges. The authors present a survey of this work and show how some of the computational challenges can be overcome.

AAAI Conference 2015 Conference Paper

Efficient Computation of Semivalues for Game-Theoretic Network Centrality

• Piotr Szczepański
• Mateusz Tarkowski
• Tomasz Michalak
• Paul Harrenstein
• Michael Wooldridge

Solution concepts from cooperative game theory, such as the Shapley value or the Banzhaf index, have recently been advocated as interesting extensions of standard measures of node centrality in networks. While this direction of research is promising, the computation of game-theoretic centrality can be challenging. In an attempt to address the computational issues of game-theoretic network centrality, we present a generic framework for constructing game-theoretic network centralities. We prove that all extensions that can be expressed in this framework are computable in polynomial time. Using our framework, we present the first game-theoretic extensions of weighted and normalized degree centralities, impact factor centrality, distance-scaled and normalized betweenness centrality, and closeness and normalized closeness centralities.

JAAMAS Journal 2015 Journal Article

Majority bargaining for resource division

• Shaheen Fatima
• Michael Wooldridge

Abstract We address the problem of how a set of agents can decide to share a resource, represented as a unit-sized pie. The pie can be generated by the entire set but also by some of its subsets. We investigate a finite horizon non-cooperative bargaining game, in which the players take it in turns to make proposals on how the resource should for this purpose be allocated, and the other players vote on whether or not to accept the allocation. Voting is modelled as a Bayesian weighted voting game with uncertainty about the players’ weights. The agenda, (i. e. , the order in which the players are called to make offers), is defined exogenously. We focus on impatient players with heterogeneous discount factors. In the case of a conflict, (i. e. , no agreement by the deadline), no player receives anything. We provide a Bayesian subgame perfect equilibrium for the bargaining game and conduct an ex-ante analysis of the resulting outcome. We show that the equilibrium is unique, computable in polynomial time, results in an instant Pareto optimal outcome, and, under certain conditions provides a foundation for the core and also the nucleolus of the Bayesian voting game. In addition, our analysis leads to insights on how an individual’s bargained share is influenced by his position on the agenda. Finally, we show that, if the conflict point of the bargaining game changes, then the problem of determining the non-cooperative equilibrium becomes NP-hard even under the perfect information assumption. Our research also reveals how this change in conflict point impacts on the above mentioned results.

TAAS Journal 2015 Journal Article

Online Automated Synthesis of Compact Normative Systems

• Javier Morales
• Maite López-sánchez
• Juan A. Rodriguez-Aguilar
• Wamberto Vasconcelos
• Michael Wooldridge

Most normative systems make use of explicit representations of norms (namely, obligations, prohibitions, and permissions) and associated mechanisms to support the self-regulation of open societies of self-interested and autonomous agents. A key problem in research on normative systems is that of how to synthesise effective and efficient norms. Manually designing norms is time consuming and error prone. An alternative is to automatically synthesise norms. However, norm synthesis is a computationally complex problem. We present a novel online norm synthesis mechanism, designed to synthesise compact normative systems. It yields normative systems composed of concise (simple) norms that effectively coordinate a multiagent system (MAS) without lapsing into overregulation. Our mechanism is based on a central authority that monitors a MAS, searching for undesired states. After detecting undesirable states, the central authority then synthesises norms aimed to avoid them in the future. We demonstrate the effectiveness of our approach through experimental results.

JAAMAS Journal 2015 Journal Article

Power and welfare in bargaining for coalition structure formation

• Shaheen Fatima
• Tomasz P. Michalak
• Michael Wooldridge

Abstract We investigate a noncooperative bargaining game for partitioning n agents into non-overlapping coalitions. The game has n time periods during which the players are called according to an exogenous agenda to propose offers. With probability \(\delta \), the game ends during any time period \(t<n\). If it does, the first t players on the agenda get a chance to propose but the others do not. Thus, \(\delta \) is a measure of the degree of democracy within the game (ranging from democracy for \(\delta =0\), through increasing levels of authoritarianism as \(\delta \) approaches 1, to dictatorship for \(\delta =1\) ). We determine the subgame perfect equilibrium (SPE) and study how a player’s position on the agenda affects his bargaining power. We analyze the relation between the distribution of power of individual players, the level of democracy, and the welfare efficiency of the game. We find that purely democratic games are welfare inefficient and that introducing a degree of authoritarianism into the game makes the distribution of power more equitable and also maximizes welfare. These results remain invariant under two types of player preferences: one where each player’s preference is a total order on the space of possible coalition structures and the other where each player either likes or dislikes a coalition structure. Finally, we show that the SPE partition may or may not be core stable.

IS Journal 2015 Journal Article

Thinking Backward with Professor Zermelo

• Michael Wooldridge

This column discusses extensive form games and shows how backward induction can be used to analyze such games. It also discusses some of the apparent paradoxes that can arise when using backward induction to analyze games.

KR Conference 2014 Conference Paper

Reasoning about Equilibria in Game-like Concurrent Systems

• Julian Gutierrez
• Paul Harrenstein
• Michael Wooldridge

the assumption that they act rationally and strategically in pursuit of their goals. In this paper, we present a branching time logic that is explicitly intended for this purpose. Specifically, we provide a logic for reasoning about the equilibrium properties of game-like concurrent systems. Equilibrium concepts are the best-known and most widely applied analytical tools in the game theory literature, and of these Nash equilibrium is the best-known (Osborne and Rubinstein 1994). A Nash equilibrium is an outcome that obtains because no player has a rational incentive to deviate from it. If we consider Nash equilibrium in the context of game-like concurrent systems, then it is natural to ask which computations (runs, histories,...) will be generated in equilibrium? In (Gutierrez, Harrenstein, and Wooldridge 2013), this question was investigated using the Iterated Boolean Games (iBG) model. In this model, each player is assumed to control a set of Boolean variables, and the game is played over an infinite sequence of rounds, where at each round every player chooses values for its variables. Each player has a goal, expressed as an LTL formula, and acts strategically in pursuit of this goal. Given this, some computations of a game can be identified as being the result of Nash equilibrium strategies, and (Gutierrez, Harrenstein, and Wooldridge 2013) suggested that the key questions in the strategic analysis of the system are whether a given LTL formula holds in some or all equilibrium computations. While the iBG model of (Gutierrez, Harrenstein, and Wooldridge 2013) is useful for the purposes of exposition, it is not a realistic model of concurrent programs. Moreover, (Gutierrez, Harrenstein, and Wooldridge 2013) provides no language for reasoning about the equilibria of systems: such reasoning must be carried out at the meta-level. This paper fills those gaps. First, we present a computational model that is more appropriate for modelling concurrent systems than the iBG model. In this model, the goals (and thus preferences) of players are given as temporal logic formulae that the respective player aspires to satisfy. After exploring some properties of this model, we introduce Equilibrium Logic (EL) as a formalism for reasoning about the equilibria of such systems. EL is a branching time logic that provides a new path quantifier [NE]ϕ, which asserts that ϕ holds on all Nash equilibrium computations of the system. Thus, EL supports reasoning about equilibria directly in the object language. We then investigate some properties of this logic. Our aim is to develop techniques for reasoning about gamelike concurrent systems, where the components of the system act rationally and strategically in pursuit of logicallyspecified goals. We first present a computational model for such systems, and investigate its properties. We then define and investigate a branching-time logic for reasoning about the equilibrium properties of such systems. The key operator in this logic is a path quantifier [NE]ϕ, which asserts that ϕ holds on all Nash equilibrium computations of the system.

IS Journal 2014 Journal Article

The Negotiation Game

• Shaheen Fatima
• Sarit Kraus
• Michael Wooldridge

Here, the authors consider some of the main ideas underpinning attempts to build automated negotiators--computer programs that can effectively negotiate on our behalf.

TIST Journal 2013 Journal Article

Building and using social structures

• Elisabetta Erriquez
• Wiebe van der Hoek
• Michael Wooldridge

This article investigates the conjecture that agents who make decisions in scenarios where trust is important can benefit from the use of a social structure, representing the social relationships that exist between agents. We propose techniques that can be used by agents to initially build and then progressively update such a structure in the light of experience. We describe an implementation of our techniques in the domain of the Agent ART testbed: we take two existing agents for this domain (“Simplet” and “Connected”) and compare their performance with versions that use our social structure (“SocialSimplet” and “SocialConnected”). We show that SocialSimplet and SocialConnected outperform their counterparts with respect to the quality of the interactions, the number of rounds won in a competition, and the total utility gained.

IS Journal 2013 Journal Article

Game Theory and Evolution

• Steve Phelps
• Michael Wooldridge

Key concepts are described from the area now known as evolutionary game theory, while also introducing some important applications of these concepts.

AIJ Journal 2013 Journal Article

Incentive engineering for Boolean games

• Michael Wooldridge
• Ulle Endriss
• Sarit Kraus
• Jérôme Lang

AAMAS Conference 2013 Conference Paper

IRON: A Machine for the Automated Synthesis of Normative Systems

• Javier Morales
• Maite Lopez-Sanchez
• Juan A. Rodriguez-Aguilar
• Michael Wooldridge
• Wamberto Vasconcelos

The automated synthesis of norms for coordination of multi-agent systems remains an open and complex problem. In this paper we present the Intelligent Robust On-line Norm Synthesis Machine (IRON), a system whose goal is the automated synthesis of norms. IRON is capable of synthesising norms that are at the same time effective (to ensure coordination) and necessary (to avoid overregulation). IRON has been tested on a simulated traffic scenario to successfully synthesise norms that help cars avoid collisions. IRON is equipped with visualization features that provide support for an intuitive and informed monitoring of the synthesis process.

IJCAI Conference 2013 Conference Paper

Iterated Boolean Games

• Julian Gutierrez
• Paul Harrenstein
• Michael Wooldridge

Iterated games are well-known in the game theory literature. We study iterated Boolean games. These are games in which players repeatedly choose truth values for Boolean variables they have control over. Our model of iterated Boolean games assumes that players have goals given by formulae of Linear Temporal Logic (LTL), a formalism for expressing properties of state sequences. In order to model the strategies that players use in such games, we use a finite state machine model. After introducing and formally defining iterated Boolean games, we investigate the computational complexity of their associated game-theoretic decision problems as well as semantic conditions characterising classes of LTL properties that are preserved by pure strategy Nash equilibria whenever they exist.

IS Journal 2013 Journal Article

The Joy of Matching

• Paul Harrenstein
• David Manlove
• Michael Wooldridge

Here, the authors discuss matching problems and how the Gale-Shapley algorithm solves them, while also explaining some matching techniques.

IJCAI Conference 2013 Conference Paper

Verifiable Equilibria in Boolean Games

• Thomas Ågotnes
• Paul Harrenstein
• Wiebe van der Hoek
• Michael Wooldridge

This work is motivated by the following concern. Suppose we have a game exhibiting multiple Nash equilibria, with little to distinguish them except that one of them can be verified while the others cannot. That is, one of these equilibria carries sufficient information that, if this is the outcome, then the players can tell that an equilibrium has been played. This provides an argument for this equilibrium being played, instead of the alternatives. Verifiability can thus serve to make an equilibrium a focal point in the game. We formalise and investigate this concept using a model of Boolean games with incomplete information. We define and investigate three increasingly strong types of verifiable equilibria, characterise the complexity of checking these, and show how checking their existence can be captured in a variant of modal epistemic logic.

AAMAS Conference 2012 Conference Paper

A Logic of Revelation and Concealment

• Wiebe van der Hoek
• Petar Iliev
• Michael Wooldridge

The last decade has been witness to a rapid growth of interest in logics intended to support reasoning about the interactions between knowledge and action. Typically, logics combining dynamic and epistemic components contain ontic actions (which change the state of the world, e. g. , switching a light on) or epistemic actions (which affect the information possessed by agents, e. g. , making an announcement). We introduce a new logic for reasoning about the interaction between knowledge and action, in which each agent in a system is assumed to perceive some subset of the overall set of Boolean variables in the system; these variables give rise to epistemic indistinguishability relations, in that two states are considered indistinguishable to an agent if all the variables visible to that agent have the same value in both states. In the dynamic component of the logic, we introduce actions $r(p, i)$ and $c(p, i)$: the effect of $r(p, i)$ is to reveal variable $p$ to agent $i$; the effect of $c(p, i)$ is to conceal $p$ from $i$. By using these dynamic operators, we can represent and reason about how the knowledge of agents changes when parts of their environment are concealed from them, or by revealing parts of their environment to them. Our main technical result is a sound and complete axiomatisation for our logic.

AIJ Journal 2012 Journal Article

Anytime coalition structure generation in multi-agent systems with positive or negative externalities

• Talal Rahwan
• Tomasz Michalak
• Michael Wooldridge
• Nicholas R. Jennings

IS Journal 2012 Journal Article

Computation and the prisoner's dilemma

• Michael Wooldridge

Ideas from computer science can help solve the problem of cooperation in the prisoner's dilemma, and can lead to rational cooperation in natural variants of this problem.

IS Journal 2012 Journal Article

Cooperative Game Theory: Basic Concepts and Computational Challenges

• Georgios Chalkiadakis
• Edith Elkind
• Michael Wooldridge

Cooperative game theory studies situations in which agents can benefit by working together. This article outlines the key concepts of cooperative game theory, and discusess the challenges that arise in applying these in AI applications.

IS Journal 2012 Journal Article

Does Game Theory Work?

• Michael Wooldridge

Given the current level of international interest in game theory and its applications in AI and computer science, it seems worth pausing to consider whether game theory actually works. This article considers the evidence available in support of the two most common interpretations of game theory: the descriptive interpretation, which considers game theory as trying to predict actual behavior, and the normative interpretation, which considers game theory as providing advice on how to act optimally.

AIJ Journal 2012 Journal Article

On the evaluation of election outcomes under uncertainty

• Noam Hazon
• Yonatan Aumann
• Sarit Kraus
• Michael Wooldridge

IS Journal 2012 Journal Article

The Triumph of Rationality

• Michael Wooldridge

Over the past decade, concepts and techniques from game theory have been both influential and successful in AI - and indeed, in computer science generally.

AAMAS Conference 2012 Conference Paper

Towards Tractable Boolean Games

• Paul Dunne
• Michael Wooldridge

Boolean games are a compact and expressive class of games, based on propositional logic. However, Boolean games are computationally complex: checking for the existence of pure Nash equilibria in Boolean games is $\Sigma^p_2$-complete, and it is co-NP-complete to check whether given a given outcome for a Boolean game is a pure Nash equilibrium. In this paper, we consider two possible avenues to tractability in Boolean games. First, we consider the development of alternative solution concepts for Boolean games. We introduce the notion of $k$-bounded Nash equilibrium, meaning that no agent can benefit from deviation by altering fewer than $k$ variables. After motivating and discussing this notion of equilibrium, we give a logical characterisation of a class of Boolean games for which $k$-bounded equilibria correspond to Nash equilibria. That is, we precisely characterise a class of Boolean games for which all Nash equilibria are in fact $k$-bounded Nash equilibria. Second, we consider classes of Boolean games for which computational problems related to Nash equilibria are easier than in the general setting. We first identify some restrictions on games that make checking for beneficial deviations by individual players computationally tractable, and then show that certain types of \emph{socially desirable} equilibria can be hard to compute even when the standard decision problems for Boolean games are easy. We conclude with a discussion of related work and possible future work.

AAMAS Conference 2011 Conference Paper

An Abstract Framework for Reasoning About Trust

• Elisabetta Erriquez
• Wiebe van der Hoek
• Michael Wooldridge

We present an abstract framework that allows agents to form coalitions with agents that they believe to be trustworthy. In contrast to many other models, we take the notion of distrust to be our key social concept. We use a graph theoretic model to capture the distrust relations within a society, and use this model to formulate several notions of mutually trusting coalitions. We then investigate principled techniques for how the information present in our distrust model can be aggregated to produce individual measures of how trustworthy an agent is considered to be by a society.

AAAI Conference 2011 Conference Paper

Constrained Coalition Formation

• Talal Rahwan
• Tomasz Michalak
• Edith Elkind
• Piotr Faliszewski
• Jacek Sroka
• Michael Wooldridge
• Nicholas Jennings

The conventional model of coalition formation considers every possible subset of agents as a potential coalition. However, in many real-world applications, there are inherent constraints on feasible coalitions: for instance, certain agents may be prohibited from being in the same coalition, or the coalition structure may be required to consist of coalitions of the same size. In this paper, we present the first systematic study of constrained coalition formation (CCF). We propose a general framework for this problem, and identify an important class of CCF settings, where the constraints specify which groups of agents should/should not work together. We describe a procedure that transforms such constraints into a structured input that allows coalition formation algorithms to identify, without any redundant computations, all the feasible coalitions. We then use this procedure to develop an algorithm for generating an optimal (welfare-maximizing) constrained coalition structure, and show that it outperforms existing state-of-the-art approaches by several orders of magnitude.

AAMAS Conference 2011 Conference Paper

Decomposing Constraint Systems: Equivalences and Computational Properties

• Wiebe van der Hoek
• Cees Witteveen
• Michael Wooldridge

Distributed systems can often be modeled as a collection of distributed (system) variables whose values are constrained by a set of constraints. In distributed multi-agent systems, the set of variables occurring at a site (subsystem) is usually viewed as controllable by a local agent. This agent assigns values to the variables, and the aim is to provide distributed methods enabling a set of agents to come up with a global assignment (solution) that satisfies all the constraints. Alternatively, the system might be understood as a distributed database. Here, the focus is on ensuring consistency of the global system if local constraints (the distributed parts of the database) change. In this setting, the aim is to determine whether the existence of a global solution can be guaranteed. In other settings (e. g. , P2P systems, sensor networks), the values of the variables might be completely out of control of the individual systems, and the constraints only characterize globally normal states or behavior of the system. In order to detect anomalies, one specifies distributed methods that can efficiently indicate violations of such constraints. The aim of this paper is to show that the following three main problems identified in these research areas are in fact identical: (i) the problem of ensuring that independent agents come up with a global solution; (ii) the problem of ensuring that global consistency is maintained if local constraint stores change; and (iii) the problem of ensuring that global violations can be detected by local nodes. This claim is made precise by developing a decomposition framework for distributed constraint systems and then extracting preservation properties that must satisfied in order to solve the above mentioned problems. Although satisfying the preservation properties seems to require different decomposition modes, our results demonstrate that in fact these decomposition properties are equivalent, thereby showing that the three main problems identified above are identical. We then show that the complexity of finding such decompositions is polynomially related to finding solutions for the original constraint system, which explains the popularity of decomposition applied to tractable constraint systems. Finally, we address the problem of finding optimal decompositions and show that even for tractable constraint systems, this problem is hard.

AAMAS Conference 2011 Conference Paper

Designing Incentives for Boolean Games

• Ulle Endriss
• Sarit Kraus
• J
• eacute; r
• ocirc; me Lang
• Michael Wooldridge

Boolean games are a natural, compact, and expressive class of logic-based games, in which each player exercises unique control over some set of Boolean variables, and has some logical goal formula that it desires to be achieved. A player's strategy set is the set of all possible valuations that may be made to its variables. A player's goal formula may contain variables controlled by other agents, and in this case, it must reason strategically about how best to assign values to its variables. In the present paper, we consider the possibility of overlaying Boolean games with taxation schemes. A taxation scheme imposes a cost on every possible assignment an agent can make. By designing a taxation scheme appropriately, it is possible to perturb the preferences of the agents within a society, so that agents are rationally incentivised to choose some socially desirable equilibrium that would not otherwise be chosen, or incentivised to rule out some socially undesirable equilibria. After formally presenting the model, we explore some issues surrounding it (e. g. , the complexity of finding a taxation scheme that implements some socially desirable outcome), and then discuss possible desirable properties of taxation schemes.

IJCAI Conference 2011 Conference Paper

Incentive Engineering for Boolean Games

• Ulle Endriss
• Sarit Kraus
• J
• eacute; r
• ocirc; me Lang
• Michael Wooldridge

We investigate the problem of influencing the preferences of players within a Boolean game so that, if all players act rationally, certain desirable outcomes will result. The way in which we influence preferences is by overlaying games with taxation schemes. In a Boolean game, each player has unique control of a set of Boolean variables, and the choices available to the player correspond to the possible assignments that may be made to these variables. Each player also has a goal, represented by a Boolean formula, that they desire to see satisfied. Whether or not a player's goal is satisfied will depend both on their own choices and on the choices of others, which gives Boolean games their strategic charac- ter. We extend this basic framework by introducing an external principal who is able to levy a taxation scheme on the game, which imposes a cost on every possible action that a player can choose. By designing a taxation scheme appropriately, it is possible to perturb the preferences of the players, so that they are incentivised to choose some equilibrium that would not otherwise be chosen. After motivating and formally presenting our model, we explore some issues surrounding it, including the complexity of finding a taxation scheme that implements some socially desirable outcome, and then discuss desirable properties of taxation schemes.

AAMAS Conference 2011 Conference Paper

Knowledge and Control

• Wiebe van der Hoek
• Nicolas Troquard
• Michael Wooldridge

Logics of propositional control, such as van der Hoek and Wooldridge's CL-PC, were introduced in order to represent and reason about scenarios in which each agent within a system is able to exercise unique control over some set of system variables. Our aim in the present paper is to extend the study of logics of propositional control to settings in which these agents have incomplete information about the society they occupy. We consider two possible sources of incomplete information. First, we consider the possibility that an agent is only able to "read" a subset of the overall system variables, and so in any given system state, will have partial information about the state of the system. Second, we consider the possibility that an agent has incomplete information about which agent controls which variables. For both cases, we introduce a logic combining epistemic modalities with the operators of CL-PC, investigate its axiomatization, and discuss its properties.

IJCAI Conference 2011 Conference Paper

Manipulating Boolean Games through Communication

• John Grant
• Sarit Kraus
• Michael Wooldridge
• Inon Zuckerman

We address the issue of manipulating games through communication. In the specific setting we consider (a variation of Boolean games), we assume there is some set of environment variables, the value of which is not directly accessible to players; each player has their own beliefs about these variables, and makes decisions about what actions to perform based on these beliefs. The communication we consider takes the form of (truthful) announcements about the value of some environment variables; the effect of an announcement about some variable is to modify the beliefs of the players who hear the announcement so that they accurately reflect the value of the announced variables. By choosing announcements appropriately, it is possible to perturb the game away from certain rational outcomes and towards others. We specifically focus on the issue of stabilisation: making announcements that transform a game from having no stable states to one that has stable configurations.

AAMAS Conference 2011 Conference Paper

On Optimal Agendas for Package Deal Negotiation

• Shaheen Fatima
• Michael Wooldridge
• Nicholas R. Jennings

This paper analyzes bilateral multi-issue negotiation where the issues are indivisible, there are time constraints in the form of deadlines and discount factors. The issues are negotiated using the package deal procedure. The set of issues to be negotiated is called the negotiation agenda. The agenda is crucial since the outcome of negotiation depends on the agenda. This paper therefore looks at the decision making involved in choosing a negotiation agenda. The scenario we look at is as follows. There are m > 2 issues available for negotiation. But from these, an agent must choose g < m issues and negotiate on them. Thus the problem for an agent is to choose an agenda (i. e, a subset of g issues). Clearly, from all possible agendas (i. e. , all possible combinations of g issues), an agent must choose the one that maximizes its expected utility and is therefore its optimal agenda. To this end, this paper presents polynomial time methods for choosing an agent's optimal agenda.

AAMAS Conference 2011 Conference Paper

Scientia Potentia Est

• Thomas
• Aring; gotnes
• Wiebe van der Hoek
• Michael Wooldridge

In epistemic logic, Kripke structures are used to model the distribution of information in a multi-agent system. In this paper, we present an approach to quantifying how much information each particular agent in a system has, or how important the agent is, with respect to some fact represented as a goal formula. It is typically the case that the goal formula is distributed knowledge in the system, but that no individual agent alone knows it. It might be that several different groups of agents can get to know the goal formula together by combining their individual knowledge. By using power indices developed in voting theory, such as the Banzhaf index, we get a measure of how important an agent is in such groups. We analyse the properties of this notion of information-based power in detail, and characterise the corresponding class of voting games. Although we mainly focus on distributed knowledge, we also look at variants of this analysis using other notions of group knowledge. An advantage of our framework is that power indices and other power properties can be expressed in standard epistemic logic. This allows, e. g. , standard model checkers to be used to quantitatively analyse the distribution of information in a given Kripke structure.

AIJ Journal 2011 Journal Article

Weighted argument systems: Basic definitions, algorithms, and complexity results

• Paul E. Dunne
• Anthony Hunter
• Peter McBurney
• Simon Parsons
• Michael Wooldridge

AAMAS Conference 2010 Conference Paper

A Distributed Algorithm for Anytime Coalition Structure Generation

• Tomasz Michalak
• Jacek Sroka
• Talal Rahwan
• Michael Wooldridge
• Peter McBurney
• Nicholas R. Jennings

A major research challenge in multi-agent systems is theproblem of partitioning a set of agents into mutually disjoint coalitions, such that the overall performance of thesystem is optimized. This problem is difficult because thesearch space is very large: the number of possible coalition structures increases exponentially with the number ofagents. Although several algorithms have been proposed totackle this Coalition Structure Generation (CSG) problem, all of them suffer from being inherently centralized, whichleads to the existence of a performance bottleneck and a single point of failure. In this paper, we develop the first decentralized algorithm for solving the CSG problem optimally. In our algorithm, the necessary calculations are distributedamong the agents, instead of being carried out centrally bya single agent (as is the case in all the available algorithmsin the literature). In this way, the search can be carriedout in a much faster and more robust way, and the agentscan share the burden of the calculations. The algorithmcombines, and improves upon, techniques from two existingalgorithms in the literature, namely DCVC and IP, and applies novel techniques for filtering the input and reducing the inter-agent communication load.

AAMAS Conference 2010 Conference Paper

A Logic-Based Representation for Coalitional Games with Externalities

• Tomasz Michalak
• Dorota Marciniak
• Marcin Szamotulski
• Talal Rahwan
• Michael Wooldridge
• Peter McBurney
• Nicholas R. Jennings

We consider the issue of representing coalitional games in multi-agent systems that exhibit externalities from coalition formation, i. e. , systems in which the gain from forming a coalition may be affected by the formation of other co-existing coalitions. Althoughexternalities play a key role in many real-life situations, very littleattention has been given to this issue in the multi-agent system literature, especially with regard to the computational aspects involved. To this end, we propose a new representation which, in the spiritof Ieong and Shoham, is based on Boolean expressions. Theidea behind our representation is to construct much richer expressions that allow for capturing externalities induced upon coalitions. We show that the new representation is fully expressive, at least asconcise as the conventional partition function game representationand, for many games, exponentially more concise. We evaluate theefficiency of our new representation by considering the problem ofcomputing the Extended and Generalized Shapley value, a powerful extension of the conventional Shapley value to games withexternalities. We show that by using our new representation, theExtended and Generalized Shapley value, which has not been studied in the computer science literature to date, can be computed intime linear in the size of the input.

AAMAS Conference 2010 Conference Paper

Combinatorial Auctions with Externalities

• Piotr Krysta
• Tomasz Michalak
• Tuomas Sandholm
• Michael Wooldridge

Although combinatorial auctions have received a great deal of attention from the computer science community over the past decade, research in this domain has focussed on settings in which a bidderonly has preferences over the bundles of goods they themselvesreceive, and is indifferent about how other goods are allocated toother bidders. In general, however, bidders in combinatorial auctions will be subject to externalities: they care about how the goodsthey are not themselves allocated are allocated to others. Our aimin the present work is to study such combinatorial auctions withexternalities from a computational perspective. We first presentour formal model, and then develop a classification scheme for thetypes of externalities that may be exhibited in a bidder's valuationfunction. We develop a bidding language for combinatorial auctions with externalities, which uses weighted logical formulae torepresent bidder valuation functions. We then investigate the properties of this representation: we study the complexity of the winnerdetermination problem, and characterise the complexity of classifying the properties of valuation functions. Finally, we considerapproximation methods for winner determination.

AAAI Conference 2010 Conference Paper

Intentions in Equilibrium

• John Grant
• Sarit Kraus
• Michael Wooldridge

Intentions have been widely studied in AI, both in the context of decision-making within individual agents and in multiagent systems. Work on intentions in multi-agent systems has focused on joint intention models, which characterise the mental state of agents with a shared goal engaged in teamwork. In the absence of shared goals, however, intentions play another crucial role in multi-agent activity: they provide a basis around which agents can mutually coordinate activities. Models based on shared goals do not attempt to account for or explain this role of intentions. In this paper, we present a formal model of multi-agent systems in which belief-desire-intention agents choose their intentions taking into account the intentions of others. To understand rational mental states in such a setting, we formally define and investigate notions of multi-agent intention equilibrium, which are related to equilibrium concepts in game theory.

AAMAS Conference 2010 Conference Paper

Optimal Social Laws

• Thomas
• Aring; gotnes
• Michael Wooldridge

Social laws have proved to be a powerful and theoretically elegantframework for coordination in multi-agent systems. Most existingmodels of social laws assume that a designer is attempting to produce a set of constraints on agent behaviour which will ensure thatsome single overall desirable objective is achieved. However, thisrepresents a gross simplification of the typical situation, where adesigner may have multiple (possibly conflicting) objectives, withdifferent priorities. Moreover, social laws, as well as bringing benefits, also have implementation costs: imposing a social law oftencannot be done at zero cost. We present a model of social lawsthat reflects this reality: it takes into account both the fact that thedesigner of a social law may have multiple differently valued objectives, and that the implementation of a social law is not cost-neutral. In this setting, designing a social law becomes an optimisation problem, in which a designer must take into account boththe benefits and costs of a social law. We investigate the issue ofrepresenting a designer's objectives, characterise the complexity ofthe optimal social law design problem, and consider possible constraints that lead to reductions in computational complexity. Wethen show how the problem of designing an optimal social law canbe formulated as an integer linear program.

AIJ Journal 2010 Journal Article

Solving coalitional resource games

• Paul E. Dunne
• Sarit Kraus
• Efrat Manisterski
• Michael Wooldridge

IJCAI Conference 2009 Conference Paper

• Talal Rahwan
• Tomasz Michalak
• Nicholas R. Jennings
• Michael Wooldridge
• Peter McBurney

Coalition structure generation has received considerable attention in recent research. Several algorithms have been proposed to solve this problem in Characteristic Function Games (CFGs), where every coalition is assumed to perform equally well in any coalition structure containing it. In contrast, very little attention has been given to the more general Partition Function Games (PFGs), where a coalition’s effectiveness may change from one coalition structure to another. In this paper, we deal with PFGs with positive and negative externalities. In this context, we identify the minimum search that is required in order to establish a bound on the quality of the best coalition structure found. We then develop an anytime algorithm that improves this bound with further search, and show that it outperforms the existing state-of-the-art algorithms by orders of magnitude.

AAMAS Conference 2009 Conference Paper

A Logic of Games and Propositional Control

• Nicolas Troquard
• Wiebe van der Hoek
• Michael Wooldridge

We present a logic for reasoning about strategic games. The logic is a modal formalism, based on the Coalition Logic of Propositional Control, to which we add the notions of outcomes and preferences over outcomes. We study the underlying structure of powers of coalitions as they are expressed in their effectivity function, and formalise a collection of solution concepts. We provide a sound and complete axiomatisation for the logic, and we demonstrate its features by applying it to some problems from social choice theory.

AAMAS Conference 2009 Conference Paper

An Analysis of Feasible Solutions for Multi-Issue Negotiation Involving Nonlinear Utility Functions

• Shaheen Fatima
• Michael Wooldridge
• Nicholas R. Jennings

This paper analyzes bilateral multi-issue negotiation between selfinterested agents. Specifically, we consider the case where issues are divisible, there are time constraints in the form of deadlines and discount factors, and the agents have different preferences over the issues. Given these differing preferences, it is possible to reach Pareto-optimal agreements by negotiating all the issues together using a package deal procedure (PDP). However, finding equilibrium strategies for this procedure is not always computationally easy. In particular, if the agents’ utility functions are nonlinear, then equilibrium strategies may be hard to compute. In order to overcome this complexity, we explore two different solutions. The first is to use the PDP for linear approximations of the given nonlinear utilities. The second solution is to use a simultaneous procedure (SP) where the issues are discussed in parallel but independently of each other. We then compare these two solutions both in terms of their computational properties (i. e. , time complexity of computing an approximate equilibrium and the associated error of approximation) and their economic properties (i. e. , the agents’ utilities and social welfare of the resulting outcome). By doing so, we show that an approximate equilibrium for the PDP and the SP can be found in polynomial time. In terms of the economic properties, although the PDP is known to generate Pareto optimal outcomes, we show that, in some cases, which we identify, the SP is better for one of the two agents and also increases the social welfare.

AAMAS Conference 2009 Conference Paper

Boolean Combinations of Weighted Voting Games

• Piotr Faliszewski
• Edith Elkind
• Michael Wooldridge

Weighted voting games are a natural and practically important class of simple coalitional games, in which each agent is assigned a numeric weight, and a coalition is deemed to be winning if the sum of weights of agents in that coalition meets some stated threshold. We study a natural generalisation of weighted voting games called Boolean Weighted Voting Games (BWVGs). BWVGs are intended to model decision-making processes in which components of an overall decision are delegated to committees, with each committee being an individual weighted voting game. We consider the perspective of an individual who has some overall goal that they desire to achieve, represented as a propositional logic formula over the decisions controlled by the various committees. We begin by formulating the framework of BWVGs, and show that BWVGs can provide a succinct representation scheme for simple coalitional games, compared to other representations based on weighted voting games. We then consider the computational complexity of problems such as determining the power of a particular player with respect to some goal, and investigate how the power of a player with respect to the overall goal is related to the power of that player in individual games. We show trade-offs between the complexity of these problems, the nature of underlying Boolean formulas used, and representations of weights (binary versus unary) in our games.

AAMAS Conference 2009 Conference Paper

Hedonic Coalition Nets

• Edith Elkind
• Michael Wooldridge

In hedonic games, players have the opportunity to form coalitions, and have preferences over the coalitions they might join. Such games can be used to model a variety of settings ranging from multi-agent coordination to group formation in social networks. However, the practical application of hedonic games is hindered by the fact that the naive representation for such games is exponential in the number of players. In this paper, we study hedonic coalition nets—a succinct, rule-based representation for hedonic games. This formalism is based on marginal contribution nets, which were developed by Ieong and Shoham for representing coalitional games with transferable utility. We show that hedonic coalition nets are universally expressive, yet are at least as succinct as other existing representation schemes for hedonic games. We then investigate the complexity of many natural decision problems for hedonic coalition nets. In particular, we provide a complete characterisation of the computational difficulty of problems related to coalitional stability for hedonic games represented with hedonic nets.

AAMAS Conference 2009 Conference Paper

Inconsistency Tolerance in Weighted Argument Systems

• Paul E. Dunne
• Anthony Hunter
• Peter McBurney
• Simon Parsons
• Michael Wooldridge

We introduce and investigate a natural extension of Dung’s wellknown model of argument systems in which attacks are associated with a weight, indicating the relative strength of the attack. A key concept in our framework is the notion of an inconsistency budget, which characterises how much inconsistency we are prepared to tolerate: given an inconsistency budget β, we would be prepared to disregard attacks up to a total cost of β. The key advantage of this approach is that it permits a much finer grained level of analysis of argument systems than unweighted systems, and gives useful solutions when conventional (unweighted) argument systems have none. We begin by reviewing Dung’s abstract argument systems, and present the model of weighted argument systems. We then investigate solutions to weighted argument systems and the associated complexity of computing these solutions, focussing in particular on weighted variations of grounded extensions.

JAAMAS Journal 2009 Journal Article

On the logic of preference and judgment aggregation

• Thomas Ågotnes
• Wiebe van der Hoek
• Michael Wooldridge

Abstract Agents that must reach agreements with other agents need to reason about how their preferences, judgments, and beliefs might be aggregated with those of others by the social choice mechanisms that govern their interactions. The emerging field of judgment aggregation studies aggregation from a logical perspective, and considers how multiple sets of logical formulae can be aggregated to a single consistent set. As a special case, judgment aggregation can be seen to subsume classical preference aggregation. We present a modal logic that is intended to support reasoning about judgment aggregation scenarios (and hence, as a special case, about preference aggregation): the logical language is interpreted directly in judgment aggregation rules. We present a sound and complete axiomatisation. We show that the logic can express aggregation rules such as majority voting; rule properties such as independence; and results such as the discursive paradox, Arrow’s theorem and Condorcet’s paradox—which are derivable as formal theorems of the logic. The logic is parameterised in such a way that it can be used as a general framework for comparing the logical properties of different types of aggregation—including classical preference aggregation. As a case study we present a logical study of, including a formal proof of, the neutrality lemma, the main ingredient in a well-known proof of Arrow’s theorem.

AAMAS Conference 2009 Conference Paper

Power in Normative Systems

• Thomas Ågotnes
• Wiebe van der Hoek
• Moshe Tennenholtz
• Michael Wooldridge

Power indices such as the Banzhaf index were originally developed within voting theory in an attempt to rigorously characterise the influence that a voter is able to wield in a particular voting game. In this paper, we show how such power indices can be applied to understanding the relative importance of agents when we attempt to devise a coordination mechanism using the paradigm of social laws, or normative systems. Understanding how pivotal an agent is with respect to the success of a particular social law is of benefit when designing such social laws: we might typically aim to ensure that power is distributed evenly amongst the agents in a system, to avoid bottlenecks or single points of failure. After formally defining the framework and illustrating the role of power indices in it, we investigate the complexity of computing these indices, showing that the characteristic complexity result is #P-completeness. We then investigate cases where computing indices is computationally easy.

AIJ Journal 2009 Journal Article

Reasoning about coalitional games

• Thomas Ågotnes
• Wiebe van der Hoek
• Michael Wooldridge

AIJ Journal 2008 Journal Article

A linear approximation method for the Shapley value

• Shaheen S. Fatima
• Michael Wooldridge
• Nicholas R. Jennings

AAMAS Conference 2008 Conference Paper

A Tractable and Expressive Class of Marginal Contribution Nets and Its Applications

• Edith Elkind
• Leslie Ann Goldberg
• Paul Goldberg
• Michael Wooldridge

Coalitional games raise a number of important questions from the point of view of computer science, key among them being how to represent such games compactly, and how to efficiently compute solution concepts assuming such representations. Marginal contribution nets (MC-nets), introduced by Ieong and Shoham, are one of the simplest and most influential representation schemes for coalitional games. MCnets are a rule-based formalism, in which rules take the form pattern −→ value, where “pattern” is a Boolean condition over agents, and “value” is a numeric value. Ieong and Shoham showed that, for a class of what we will call “basic” MC-nets, where patterns are constrained to be a conjunction of literals, marginal contribution nets permit the easy computation of solution concepts such as the Shapley value. However, there are very natural classes of coalitional game that require an exponential number of such basic MC-net rules. We present read-once MC-nets, a new class of MCnets that is provably more compact than basic MC-nets, while retaining the attractive computational properties of basic MC-nets. We show how the techniques we develop for read-once MC-nets can be applied to other domains, in particular, computing solution concepts in network flow games on series-parallel networks.

AAMAS Conference 2008 Conference Paper

An anytime approximation method for the inverse Shapley value problem

• Shaheen Fatima
• Michael Wooldridge
• NICK JENNINGS

Coalition formation is the process of bringing together two or more agents so as to achieve goals that individuals on their own cannot, or to achieve them more efficiently. Typically, in such situations, the agents have conflicting preferences over the set of possible joint goals. Thus, before the agents realize the benefits of cooperation, they must find a way of resolving these conflicts and reaching a consensus. In this context, cooperative game theory offers the voting game as a mechanism for agents to reach a consensus. It also offers the Shapley value as a way of measuring the influence or power a player has in determining the outcome of a voting game. Given this, the designer of a voting game wants to construct a game such that a player’s Shapley value is equal to some desired value. This is called the inverse Shapley value problem. Solving this problem is necessary, for instance, to ensure fairness in the players’ voting powers. However, from a computational perspective, finding a player’s Shapley value for a given game is #P-complete. Consequently, the problem of verifying that a voting game does indeed yield the required powers to the agents is also #P-complete. Therefore, in order to overcome this problem we present a computationally efficient approximation algorithm for solving the inverse problem. This method is based on the technique of ‘successive approximations’; it starts with some initial approximate solution and iteratively updates it such that after each iteration, the approximate gets closer to the required solution. This is an anytime algorithm and has time complexity polynomial in the number of players. We also analyze the performance of this method in terms of its approximation error and the rate of convergence of an initial solution to the required one. Specifically, we show that the former decreases after each iteration, and that the latter increases with the number of players and also with the initial approximation error.

AAMAS Conference 2008 Conference Paper

Cooperative Boolean Games

• Paul Dunne
• Sarit Kraus
• Wiebe van der Hoek
• Michael Wooldridge

We present and formally investigate Cooperative Boolean Games, a new, natural family of coalitional games that are both compact and expressive. In such a game, an agent’s primary aim is to achieve its individual goal, which is represented as a propositional logic formula over some set of Boolean variables. Each agent is assumed to exercise unique control over some subset of the overall set of Boolean variables, and the set of valuations for these variables corresponds to the set of actions the agent can take. However, the actions available to an agent are assumed to have some cost, and an agent’s secondary aim is to minimise its costs. Typically, an agent must cooperate with others because it does not have sufficient control to ensure its goal is satisfied. However, the desire to minimise costs leads to preferences over possible coalitions, and hence to strategic behaviour. Following an introduction to the formal framework of Cooperative Boolean Games, we investigate solution concepts of the core and stable sets for them. In each case, we characterise the complexity of the associated solution concept, and discuss the surrounding issues. Finally, we present a bargaining protocol for cooperation in Boolean games, and characterise the strategies in equilibrium for this protocol.

AAMAS Conference 2008 Conference Paper

Evaluation of Election Outcomes under Uncertainty

• Noam Hazon
• Yonatan Aumann
• Sarit Kraus
• Michael Wooldridge

We investigate the extent to which it is possible to evaluate the probability of a particular candidate winning an election, given imperfect information about the preferences of the electorate. We assume that for each voter, we have a probability distribution over a set of preference orderings. Thus, for each voter, we have a number of possible preference orderings – we do not know which of these orderings actually represents the voters’ preferences, but we know for each one the probability that it does. We give a polynomial algorithm to solve the problem of computing the probability that a given candidate will win when the number of candidates is a constant. However, when the number of candidates is not bounded, we prove that the problem becomes #P-Hard for the Plurality, Borda, and Copeland voting protocols. We further show that even evaluating if a candidate has any chance to win is NP-Complete for the Plurality voting protocol, in the weighted voters case. We give a polynomial algorithm for this problem when the voters’ weights are equal.

AAMAS Conference 2008 Conference Paper

Quantifying Over Coalitions in Epistemic Logic

• Thomas Agotnes
• Wiebe van der Hoek
• Michael Wooldridge

Some natural epistemic properties which may arise in applications can only be expressed in standard epistemic logic by formulae which are exponentially long in the number of agents in the system. An example is the property “at least m agents know that at most n agents know ϕ”. We present Epistemic Logic with Quantification over Coalitions (ELQC), where the standard common knowledge operator has been replaced allowing expressions of the form hPiC ϕ and [P]C ϕ where P is a coalition predicate, meaning that there is a coalition satisfying P which have common knowledge of ϕ and that all coalitions satisfying P have common knowledge of ϕ, respectively; and similarly for distributed knowledge and everybody-knows. While the language is no more expressive than standard epistemic logic, it is exponentially more succinct. We give a sound and complete axiomatisation for ELQC, and characterise the complexity of its model checking problem.

AAMAS Conference 2008 Conference Paper

Robust Normative Systems

• Thomas Agotnes
• Wiebe van der Hoek
• Michael Wooldridge

Although normative systems, or social laws, have proved to be a highly influential approach to coordination in multi-agent systems, the issue of compliance to such normative systems remains problematic. In all real systems, it is possible that some members of an agent population will not comply with the rules of a normative system, even if it is in their interests to do so. It is therefore important to consider the extent to which a normative system is robust, i. e. , the extent to which it remains effective even if some agents do not comply with it. We formalise and investigate three different notions of robustness and related decision problems. We begin by considering sets of agents whose compliance is necessary and/or sufficient to guarantee the effectiveness of a normative system; we then consider quantitative approaches to robustness, where we try to identify the proportion of an agent population that must comply in order to ensure success, and finally, we consider a more general approach, where we characterise the compliance conditions required for success as a logical formula.

IJCAI Conference 2007 Conference Paper

• Thomas
• Aring; gotnes
• Wiebe van der Hoek
• Michael Wooldridge

We add a limited but useful form of quantification to Coalition Logic, a popular formalism for reasoning about cooperation in game-like multi-agent systems. The basic constructs of Quantified Coalition Logic (QCL) allow us to express properties as "there exists a coalition C satisfying property P such that C can achieve Phi". We give an axiomatization of QCL, and show that while it is no more expressive than Coalition Logic, it is exponentially more succinct. The time complexity of QCL model checking for symbolic and explicit state representations is shown to be no worse than that of Coalition Logic. We illustrate the formalism by showing how to succinctly specify such social choice mechanisms as majority voting, which in Coalition Logic require specifications that are exponentially long in the number of agents.

IJCAI Conference 2007 Conference Paper

• Thomas
• Aring; gotnes
• Wiebe van der Hoek
• Juan A. Rodr
• iacute; guez-Aguilar
• Carles Sierra
• Michael Wooldridge

We introduce Normative Temporal Logic (NTL), a logic for reasoning about normative systems. NTL is a generalisation of the well-known branching-time temporal logic CTL, in which the path quantifiers A ("on all paths. .. ") and E ("on some path") are replaced by the indexed deontic operators O n and P n, where for example "O n Phi" means "Phi is obligatory in the context of normative system n". After defining the logic, we give a sound and complete axiomatisation, and discuss the logic's relationship to standard deontic logics. We present a symbolic representation language for models and normative systems, and identify four different model checking problems, corresponding to whether or not a model is represented symbolically or explicitly, and whether or not we are given an interpretation for the normative systems named in formulae to be checked. We show that the complexity of model checking varies from P-complete up to ExpTime-hard for these variations.

AAMAS Conference 2007 Conference Paper

A Randomized Method for the Shapley Value for the Voting Game

• Shaheen S. Fatima
• Michael Wooldridge
• Nicholas R. Jennings

The Shapley value is one of the key solution concepts for coalition games. Its main advantage is that it provides a unique and fair solution, but its main problem is that, for many coalition games, the Shapley value cannot be determined in polynomial time. In particular, the problem of finding this value for the voting game is known to be #P-complete in the general case. However, in this paper, we show that there are some specific voting games for which the problem is computationally tractable. For other general voting games, we overcome the problem of computational complexity by presenting a new randomized method for determining the approximate Shapley value. The time complexity of this method is linear in the number of players. We also show, through empirical studies, that the percentage error for the proposed method is always less than 20% and, in most cases, less than 5%.

AAMAS Conference 2007 Conference Paper

Approximate and Online Multi-Issue Negotiation

• Shaheen S. Fatima
• Michael Wooldridge
• Nicholas R. Jennings

This paper analyzes bilateral multi-issue negotiation between selfinterested autonomous agents. The agents have time constraints in the form of both deadlines and discount factors. There arem > 1 issues for negotiation where each issue is viewed as a pie of size one. The issues are "indivisible" (i. e. , individual issues cannot be split between the parties; each issue must be allocated in its entirety to either agent). Here different agents value different issues differently. Thus, the problem is for the agents to decide how to allocate the issues between themselves so as to maximize their individual utilities. For such negotiations, we first obtain the equilibrium strategies for the case where the issues for negotiation are known a priori to the parties. Then, we analyse their time complexity and show that finding the equilibrium offers is an NP-hard problem, even in a complete information setting. In order to overcome this computational complexity, we then present negotiation strategies that are approximately optimal but computationally efficient, and show that they form an equilibrium. We also analyze the relative error (i. e. , the difference between the true optimum and the approximate). The time complexity of the approximate equilibrium strategies is O( nm /ε 2 ) where n is the negotiation deadline and ε the relative error. Finally, we extend the analysis to online negotiation where different issues become available at different time points and the agents are uncertain about their valuations for these issues. Specifically, we show that an approximate equilibrium exists for online negotiation and show that the expected difference between the optimum and the approximate is O(√m). These approximate strategies also have polynomial time complexity.

AAAI Conference 2007 Conference Paper

Logic for Automated Mechanism Design — A Progress Report

• Michael Wooldridge
• Paul E. Dunne

Over the past half decade, we have been exploring the use of logic in the specification and analysis of computational economic mechanisms. We believe that this approach has the potential to bring the same benefits to the design and analysis of computational economic mechanisms that the use of temporal logics and model checking have brought to the specification and analysis of reactive systems. In this paper, we give a survey of our work. We first discuss the use of cooperation logics such as Alternating-time Temporal Logic (ATL) for the specification and verification of mechanisms such as social choice procedures. We motivate the approach, and then discuss the work we have done on extensions to ATL to support incomplete information, preferences, and quantification over coalitions. We then discuss is the use of ATL-like cooperation logics in the development of social laws.

AAMAS Conference 2007 Conference Paper

Normative System Games

• Thomas Ågotnes
• Wiebe van der Hoek
• Michael Wooldridge

We develop a model of normative systems in which agents are assumed to have multiple goals of increasing priority, and investigate the computational complexity and game theoretic properties of this model. In the underlying model of normative systems, we use Kripke structures to represent the possible transitions of a multiagent system. A normative system is then simply a subset of the Kripke structure, which contains the arcs that are forbidden by the normative system. We specify an agent's goals as a hierarchy of formulae of Computation Tree Logic (CTL), a widely used logic for representing the properties of Kripke structures: the intuition is that goals further up the hierarchy are preferred by the agent over those that appear further down the hierarchy. Using this scheme, we define a model of ordinal utility, which in turn allows us to interpret our Kripke-based normative systems as games, in which agents must determine whether to comply with the normative system or not. We then characterise the computational complexity of a number of decision problems associated with these Kripke-based normative system games; for example, we show that the complexity of checking whether there exists a normative system which has the property of being a Nash implementation is NP-complete.

AAMAS Conference 2007 Conference Paper

On the Relevance of Utterances in Formal Inter-Agent Dialogues

• Simon Parsons
• Peter McBurney
• Elizabeth Sklar
• Michael Wooldridge

Work on argumentation-based dialogue has defined frameworks within which dialogues can be carried out, established protocols that govern dialogues, and studied di erent properties of dialogues. This work has established the space in which agents are permitted to interact through dialogues. Recently, there has been increasing interest in the mechanisms agents might use to choose how to act–the rhetori- cal manoeuvring that they use to navigate through the space defined by the rules of the dialogue. Key in such considerations is the idea of relevance, since a usual requirement is that agents stay focussed on the subject of the dialogue and only make relevant remarks. Here we study several notions of relevance, showing how they can be related to both the rules for carrying out dialogues and to rhetorical manoeuvring.

AAMAS Conference 2007 Conference Paper

Reasoning about Judgment and Preference Aggregation

• Thomas Ågotnes
• Wiebe van der Hoek
• Michael Wooldridge

Agents that must reach agreements with other agents need to reason about how their preferences, judgments, and beliefs might be aggregated with those of others by the social choice mechanisms that govern their interactions. The recently emerging field of judgment aggregation studies aggregation from a logical perspective, and considers how multiple sets of logical formulae can be aggregated to a single consistent set. As a special case, judgment aggregation can be seen to subsume classical preference aggregation. We present a modal logic that is intended to support reasoning about judgment aggregation scenarios (and hence, as a special case, about preference aggregation): the logical language is interpreted directly in judgment aggregation rules. We present a sound and complete axiomatisation of such rules. We show that the logic can express aggregation rules such as majority voting; rule properties such as independence; and results such as the discursive paradox, Arrow's theorem and Condorcet's paradox – which are derivable as formal theorems of the logic. The logic is parameterised in such a way that it can be used as a general framework for comparing the logical properties of different types of aggregation-including classical preference aggregation.

AAMAS Conference 2007 Conference Paper

Web Services Negotiation in an Insurance Grid

• Shamimabi Paurobally
• Chris van Aart
• Valentina Tamma
• Michael Wooldridge
• Peter van Hapert

There are an increasing number of initiatives for the migration of agents research towards new Internet technologies such as the semantic web, Grid, and web services. On the one hand, service oriented Grid architectures need to support dynamic cooperation, negotiation and coordination between web services controlling Grid resources, for efficient resource and task allocation and execution. On the other hand, the Grid can facilitate agent communication, life-cycle management, and access to resources for agents. The insurance sector is one such area that would benefit from the automation brought by multi-agent systems techniques in handling claims and detecting fraudulent cases. In this paper, we discuss our work on facilitating dynamic and adaptive negotiation between web and grid services. We describe our deployed approach in an InsuranceGrid, which manages businesses involved in dealing with car damage claims for a number of insurance companies.

AAMAS Conference 2006 Conference Paper

Declarative Goal Patterns in AgentSpeak

• Jomi H・ner
• Rafael Bordini
• Michael Wooldridge

AAAI Conference 2006 Conference Paper

On the Complexity of Linking Deductive and Abstract Argument Systems

• Michael Wooldridge

We investigate the computational complexity of a number of questions relating to deductive argument systems, in particular the complexity of linking deductive and more abstract argument systems. We start by presenting a simple model of deductive arguments based on propositional logic, and define logical equivalence and defeat over individual arguments. We then extend logical equivalence to sets of arguments, and show that the problem of checking equivalence of argument sets is co-NP-complete. We also show that the problem of checking that an argument set contains no two logically equivalent arguments is NP-complete, while the problem of checking that a set of arguments is maximal (i. e. , that no argument could be added without such an argument being logically equivalent to one that is already present) is co-NPcomplete. We then show that checking whether a digraph over an argument set is sound with respect to the defeat relation is co-NP-complete, while the problem of showing that such a digraph is complete is NP-complete, and the problem of showing both soundness and completeness is Dp -complete.

AAMAS Conference 2006 Conference Paper

On the Complexity of Practical ATL Model Checking

• Wiebe van der Hoek
• Alessio Lomuscio
• Michael Wooldridge

AIJ Journal 2006 Journal Article

On the computational complexity of coalitional resource games

• Michael Wooldridge
• Paul E. Dunne

AAMAS Conference 2006 Conference Paper

On the Logic of Coalitional Games

• Thomas Agotnes
• Wiebe van der Hoek
• Michael Wooldridge

AAMAS Conference 2006 Conference Paper

Reasoning about Action and Cooperation

• Luigi Sauro
• Jelle Gerbrandy
• Wiebe van der Hoek
• Michael Wooldridge

AAMAS Conference 2006 Conference Paper

Temporal Qualitative Coalitional Games

• Thomas Agotnes
• Wiebe van der Hoek
• Michael Wooldridge

JAAMAS Journal 2006 Journal Article

Verifying Multi-agent Programs by Model Checking

• Rafael H. Bordini
• Michael Fisher
• Michael Wooldridge

Abstract This paper gives an overview of our recent work on an approach to verifying multi-agent programs. We automatically translate multi-agent systems programmed in the logic-based agent-oriented programming language AgentSpeak into either Promela or Java, and then use the associated Spin and JPF model checkers to verify the resulting systems. We also describe the simplified BDI logical language that is used to write the properties we want the systems to satisfy. The approach is illustrated by means of a simple case study.

AAMAS Conference 2005 Conference Paper

A Logic for Strategic Reasoning

• Wiebe van der Hoek
• Wojciech Jamroga
• Michael Wooldridge

AAMAS Conference 2005 Conference Paper

An analysis of the Shapley value and its uncertainty for the voting game

• Shaheen Fatima
• Michael Wooldridge
• Nicholas Jennings

EAAI Journal 2005 Journal Article

Guest Editorial

• Gerhard Weiß
• Michael Wooldridge

AAMAS Conference 2005 Conference Paper

Knowledge and Social Laws

• Wiebe van der Hoek
• Mark Roberts
• Michael Wooldridge

AIJ Journal 2005 Journal Article

On the logic of cooperation and propositional control

• Wiebe van der Hoek
• Michael Wooldridge

AAMAS Conference 2005 Conference Paper

On the Meta-Logic of Arguments

• Michael Wooldridge
• Peter McBurney
• Simon Parsons

EAAI Journal 2005 Journal Article

Ontologies for supporting negotiation in e-commerce

• Valentina Tamma
• Steve Phelps
• Ian Dickinson
• Michael Wooldridge

AIJ Journal 2005 Journal Article

The complexity of contract negotiation

• Paul E. Dunne
• Michael Wooldridge
• Michael Laurence

AIJ Journal 2004 Journal Article

An agenda-based framework for multi-issue negotiation

• Shaheen S. Fatima
• Michael Wooldridge
• Nicholas R. Jennings

AIJ Journal 2004 Journal Article

On the computational complexity of qualitative coalitional games

• Michael Wooldridge
• Paul E Dunne

AAMAS Conference 2004 Conference Paper

Optimal negotiation of multiple issues in incomplete information settings

• Shaheen Fatima
• Michael Wooldridge
• Nicholas Jennings

AAMAS Conference 2004 Conference Paper

Preferences in Game Logics

• Sieuwert van Otterloo
• Wiebe van der Hoek
• Michael Wooldridge

AAMAS Conference 2004 Conference Paper

State-Space Reduction Techniques in Agent Verification

• Rafael Bordini
• Michael Fisher
• Willem Visser
• Michael Wooldridge

AAMAS Conference 2003 Conference Paper

Model Checking AgentSpeak

• Rafael H. Bordini
• Michael Fisher
• Carmen Pardavila
• Michael Wooldridge

AAMAS Conference 2003 Conference Paper

Model Checking for ACL Compliance Verification

• Marc-Philippe Huget
• Michael Wooldridge

AAMAS Conference 2003 Conference Paper

On the outcomes of formal inter-agent dialogues

• Simon Parsons
• Michael Wooldridge
• Leila Amgoud

AAMAS Conference 2003 Conference Paper

Optimal Agendas for Multi-Issue Negotiation

• Shaheen Fatima
• Michael Wooldridge
• Nicholas R. Jennings

AAMAS Conference 2003 Conference Paper

Policies for Conversations

• Christos Stergiou
• Geert Arys
• Michael Wooldridge

AAMAS Conference 2002 Conference Paper

An analysis of formal inter-agent dialogues

• Simon Parsons
• Michael Wooldridge
• Leila Amgoud

AAMAS Conference 2002 Conference Paper

Desiderata for Agent Argumentation Protocols

• Peter McBurney
• Simon Parsons
• Michael Wooldridge

AAMAS Conference 2002 Conference Paper

Model checking multiagent systems with MABLE

• Michael Wooldridge
• Michael Fisher
• Mac-Philippe Huget
• Simon Parsons

AAMAS Conference 2002 Conference Paper

The Computational Complexity of Boolean and Stochastic Agent Design Problems

• Paul E. Dunne
• Michael Wooldridge
• Michael Laurence

AAMAS Conference 2002 Conference Paper

Tractable Multiagent Planning for Epistemic Goals

• Wiebe van der Hoek
• Michael Wooldridge

KER Journal 2001 Journal Article

The control of reasoning in resource-bounded agents

• MARTIJN SCHUT
• Michael Wooldridge

Autonomous agents are systems capable of autonomous decision-making in real-time environments. Computation is a valuable resource for such decision-making, and yet the amount of computation that an autonomous agent may carry out will be limited. It follows that an agent must be equipped with a mechanism that enables it to make the best possible use of the computational resources at its disposal. In this paper we review three approaches to the control of computation in resource-bounded agents. In addition to a detailed description of each framework, this paper compares and contrasts the approaches, and lists the advantages and disadvantages of each.

KER Journal 2000 Journal Article

Game theoretic and decision theoretic agents

• Simon Parsons
• Michael Wooldridge

In the last few years, increasing numbers of members of the agent community have been adopting techniques from game theory and decision theory. Broadly speaking, decision theory (Raiffa, 1968) is a means of analysing which of a series of options should be taken when it is uncertain exactly what the result of taking the option will be. Decision theory concentrates on identifying the “best” decision option, where the notion of “best” is allowed to have a number of different meanings, of which the most common is that which maximises the expected utility of the decision maker. Game theory (Binmore, 1992) can be considered as a variant of decision theory in which the outcome of taking a particular decision is dependent upon the actions of another, frequently an opponent which is trying to maximise its own benefit at the cost of the decision maker. Alternatively, game theory can be considered a mechansim for analysing games between two players in which each gets to choose a move from some limited set of options and, depending on what both have chosen, each receives a payout. Since the payout one player receives depends upon the move made by the other then, to maximise its payout, each player needs to take into account the likely move taken by its opponent. From this perspective, decision theory can be considered to be the study of games played against nature, an opponent which does not look to gain the best payout, but rather acts randomly.

KER Journal 1999 Journal Article

Diversity and agent technology

• Michael Wooldridge

When I began studying for my PhD, I knew exactly what field I wanted to work in. It was a subfield of Artificial Intelligence (AI) that was known as Distributed AI (DAI). In DAI, we studied how a number of (semi-)autonomous problem solving systems known as ‘agents’ could be made to cooperate and coordinate their activities to produce effective overall system behaviour (Bond and Gasser, 1988). At the time, not many people were working in distributed AI (only two books had been published on the subject). I found that when I talked about my research, I had to repeatedly explain what ‘agents’ were all about. It was depressing business. More than once, I wished I had gone into a more glamorous area of research - the expert systems people were getting all the glory.

AAAI Conference 1999 Conference Paper

Verifying that Agents Implement a Communication Language

• Michael Wooldridge
• Queen Mary
• Westfield College

In recent years, a number of attempts have been made to develop standardized agent communication languages. A key issue in such languages is that of conformance testing. That is, given a program which claims to semantically conform to some agent communication standard, how can we determine whether or not it does indeed conform to it? In this article, we present an expressive agent communication language, and give a semantics for this language in such a way that verifying semantic conformance becomes a realistic possibility. The techniques we develop draw upon those used to give a semantics to reactive systems in theoretical computer science. To illustrate the approach, we give an example of a simple agent system, and show that it does indeed respect the semantics.

KER Journal 1998 Journal Article

Rationality in Multi-Agent Systems

• KEN BINMORE
• Cristiano Castelfranchi
• JAMES DORAN
• Michael Wooldridge

This report is the result of a panel discussion at the Second UK Workshop on Foundations of Multi-Agent Systems (FOMAS'97). All members of the panel are authors, listed alphabetically.

KER Journal 1997 Journal Article

Formalisms for multi-agent systems

• MARK D'INVERNO
• Michael Fisher
• Alessio Lomuscio
• Michael Luck
• Maarten de Rijke
• Mark Ryan
• Michael Wooldridge

As computer scientists, our goals are motivated by the desire to improve computer systems in some way: making them easier to design and implement, more robust and less prone to error, easier to use, faster, cheaper, and so on. In the field of multi-agent systems, our goal is to build systems capable of flexible autonomous decision making, with societies of such systems cooperating with one-another. There is a lot of formal theory in the area but it is often not obvious what such theories should represent and what role the theory is intended to play. Theories of agents are often abstract and obtuse and not related to concrete computational models.

KER Journal 1996 Journal Article

Reasoning about knowledge by Ronald Fagin, Joseph Y. Halpern, Yoram Moses and Moshe Y. Vardi, MIT Press, Cambridge, MA, 1995, pp 477, $45.00 cloth, ISBN 0-262-06162-7.

• Michael Wooldridge

KER Journal 1995 Journal Article

Intelligent agents: theory and practice

• Michael Wooldridge
• Nicholas R. Jennings

Abstract The concept of an agent has become important in both artificial intelligence (AT) and mainstream computer science. Our aim in this paper is to point the reader at what we perceive to be the most important theoretical and practical issues associated with the design and construction of intelligent agents. For convenience, we divide these issues into three areas (though as the reader will see, the divisions are at times somewhat arbitrary). Agent theory is concerned with the question of what an agent is, and the use of mathematical formalisms for representing and reasoning about the properties of agents. Agent architectures can be thought of as software engineering models of agents; researchers in this area are primarily concerned with the problem of designing software or hardware systems that will satisfy the properties specified by agent theorists. Finally, agent languages are software systems for programming and experimenting with agents; these languages may embody principles proposed by theorists. The paper is not intended to serve as a tutorial introduction to all the issues mentioned; we hope instead simply to identify the most important issues, and point to work that elaborates on them. The article includes a short review of current and potential applications of agent technology.