Arrow Research search

Author name cluster

Nicholas Jennings

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

30 papers
1 author row

Possible papers

30

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.

PDF Details DOI

NeurIPS Conference 2019 Conference Paper

Streaming Bayesian Inference for Crowdsourced Classification

  • Edoardo Manino
  • Long Tran-Thanh
  • Nicholas Jennings

A key challenge in crowdsourcing is inferring the ground truth from noisy and unreliable data. To do so, existing approaches rely on collecting redundant information from the crowd, and aggregating it with some probabilistic method. However, oftentimes such methods are computationally inefficient, are restricted to some specific settings, or lack theoretical guarantees. In this paper, we revisit the problem of binary classification from crowdsourced data. Specifically we propose Streaming Bayesian Inference for Crowdsourcing (SBIC), a new algorithm that does not suffer from any of these limitations. First, SBIC has low complexity and can be used in a real-time online setting. Second, SBIC has the same accuracy as the best state-of-the-art algorithms in all settings. Third, SBIC has provable asymptotic guarantees both in the online and offline settings.

PDF Details

AAAI Conference 2017 Conference Paper

The Dollar Auction with Spiteful Players

  • Marcin Waniek
  • Long Tran-Thanh
  • Tomasz Michalak
  • Nicholas Jennings

The dollar auction is an auction model used to analyse the dynamics of conflict escalation. In this paper, we analyse the course of an auction when participating players are spiteful, i. e. , they are motivated not only by their own profit, but also by the desire to hurt the opponent. We investigate this model for the complete information setting, both for the standard scenario and for the situation where auction starts with nonzero bids. Our results give us insight into the possible effects of meanness onto conflict escalation.

PDF Details

AAAI Conference 2016 Conference Paper

An Algorithm to Coordinate Measurements Using Stochastic Human Mobility Patterns in Large-Scale Participatory Sensing Settings

  • Alexandros Zenonos
  • Sebastian Stein
  • Nicholas Jennings

Participatory sensing is a promising new low-cost approach for collecting environmental data. However, current large-scale environmental participatory sensing campaigns typically do not coordinate the measurements of participants, which can lead to gaps or redundancy in the collected data. While some work has considered this problem, it has made several unrealistic assumptions. In particular, it assumes that complete and accurate knowledge about the participants future movements is available and it does not consider constraints on the number of measurements a user is willing to take. To address these shortcomings, we develop a computationally-efficient coordination algorithm (Bestmatch) to suggest to users where and when to take measurements. Our algorithm exploits human mobility patterns, but explicitly considers the inherent uncertainty of these patterns. We empirically evaluate our algorithm on a real-world human mobility and air quality dataset and show that it outperforms the state-of-the-art greedy and pull-based proximity algorithms in dynamic environments.

PDF Details

AAAI Conference 2015 Conference Paper

Balanced Trade Reduction for Dual-Role Exchange Markets

  • Dengji Zhao
  • Sarvapali Ramchurn
  • Enrico Gerding
  • Nicholas Jennings

We consider dual-role exchange markets, where traders can offer to both buy and sell the same commodity in the exchange but, if they transact, they can only be either a buyer or a seller, which is determined by the market mechanism. To design desirable mechanisms for such exchanges, we show that existing solutions may not be incentive compatible, and more importantly, cause the market maker to suffer a significant deficit. Hence, to combat this problem, following McAfee’s trade reduction approach, we propose a new trade reduction mechanism, called balanced trade reduction, that is incentive compatible and also provides flexible trade-offs between efficiency and deficit.

PDF Details

AAAI Conference 2015 Conference Paper

Crowdsourcing Complex Workflows under Budget Constraints

  • Long Tran-Thanh
  • Trung Dong Huynh
  • Avi Rosenfeld
  • Sarvapali Ramchurn
  • Nicholas Jennings

We consider the problem of task allocation in crowdsourcing systems with multiple complex workflows, each of which consists of a set of inter-dependent micro-tasks. We propose Budgeteer, an algorithm to solve this problem under a budget constraint. In particular, our algorithm first calculates an efficient way to allocate budget to each workflow. It then determines the number of inter-dependent micro-tasks and the price to pay for each task within each workflow, given the corresponding budget constraints. We empirically evaluate it on a well-known crowdsourcing-based text correction workflow using Amazon Mechanical Turk, and show that Budgeteer can achieve similar levels of accuracy to current benchmarks, but is on average 45% cheaper.

PDF Details

AAAI Conference 2015 Conference Paper

On the Convergence of Iterative Voting: How Restrictive Should Restricted Dynamics Be?

  • Svetlana Obraztsova
  • Evangelos Markakis
  • Maria Polukarov
  • Zinovi Rabinovich
  • Nicholas Jennings

We study convergence properties of iterative voting procedures. Such procedures are defined by a voting rule and a (restricted) iterative process, where at each step one agent can modify his vote towards a better outcome for himself. It is already known that if the iteration dynamics (the manner in which voters are allowed to modify their votes) are unrestricted, then the voting process may not converge. For most common voting rules this may be observed even under the best response dynamics limitation. It is therefore important to investigate whether and which natural restrictions on the dynamics of iterative voting procedures can guarantee convergence. To this end, we provide two general conditions on the dynamics based on iterative myopic improvements, each of which is sufficient for convergence. We then identify several classes of voting rules (including Positional Scoring Rules, Maximin, Copeland and Bucklin), along with their corresponding iterative processes, for which at least one of these conditions hold.

PDF Details

AAAI Conference 2015 Conference Paper

Towards Optimal Solar Tracking: A Dynamic Programming Approach

  • Athanasios Aris Panagopoulos
  • Georgios Chalkiadakis
  • Nicholas Jennings

The power output of photovoltaic systems (PVS) increases with the use of effective and efficient solar tracking techniques. However, current techniques suffer from several drawbacks in their tracking policy: (i) they usually do not consider the forecasted or prevailing weather conditions; even when they do, they (ii) rely on complex closed-loop controllers and sophisticated instruments; and (iii) typically, they do not take the energy consumption of the trackers into account. In this paper, we propose a policy iteration method (along with specialized variants), which is able to calculate near-optimal trajectories for effective and efficient day-ahead solar tracking, based on weather forecasts coming from online providers. To account for the energy needs of the tracking system, the technique employs a novel and generic consumption model. Our simulations show that the proposed methods can increase the power output of a PVS considerably, when compared to standard solar tracking techniques.

PDF Details

AAAI Conference 2014 Conference Paper

Efficient Buyer Groups for Prediction-of-Use Electricity Tariffs

  • Valentin Robu
  • Meritxell Vinyals
  • Alex Rogers
  • Nicholas Jennings

Current electricity tariffs do not reflect the real cost that customers incur to suppliers, as units are charged at the same rate, regardless of how predictable each customer’s consumption is. A recent proposal to address this problem are prediction-of-use tariffs. In such tariffs, a customer is asked in advance to predict her future consumption, and is charged based both on her actual consumption and the deviation from her prediction. Prior work (Vinyals et al. 2014) studied the cost game induced by a single such tariff, and showed customers would have an incentive to minimize their risk, by joining together when buying electricity as a grand coalition. In this work we study the efficient (i. e. costminimizing) structure of buying groups for the more realistic setting when multiple, competing prediction-ofuse tariffs are available. We propose a polynomial time algorithm to compute efficient buyer groups, and validate our approach experimentally, using a large-scale data set of domestic electricity consumers in the UK.

PDF Details

AAAI Conference 2014 Conference Paper

Regret-Based Multi-Agent Coordination with Uncertain Task Rewards

  • Feng Wu
  • Nicholas Jennings

Many multi-agent coordination problems can be represented as DCOPs. Motivated by task allocation in disaster response, we extend standard DCOP models to consider uncertain task rewards where the outcome of completing a task depends on its current state, which is randomly drawn from unknown distributions. The goal of solving this problem is to find a solution for all agents that minimizes the overall worst-case loss. This is a challenging problem for centralized algorithms because the search space grows exponentially with the number of agents and is nontrivial for existing algorithms for standard DCOPs. To address this, we propose a novel decentralized algorithm that incorporates Max-Sum with iterative constraint generation to solve the problem by passing messages among agents. By so doing, our approach scales well and can solve instances of the task allocation problem with hundreds of agents and tasks.

PDF Details

AAAI Conference 2012 Conference Paper

A Hybrid Algorithm for Coalition Structure Generation

  • Talal Rahwan
  • Tomasz Michalak
  • Nicholas Jennings

The current state-of-the-art algorithm for optimal coalition structure generation is IDP-IP—an algorithm that combines IDP (a dynamic programming algorithm due to Rahwan and Jennings, 2008b) with IP (a tree-search algorithm due to Rahwan et al. , 2009). In this paper we analyse IDP-IP, highlight its limitations, and then develop a new approach for combining IDP with IP that overcomes these limitations.

PDF Details

AAAI Conference 2012 Conference Paper

Cooperative Virtual Power Plant Formation Using Scoring Rules

  • Valentin Robu
  • Ramachandra Kota
  • Georgios Chalkiadakis
  • Alex Rogers
  • Nicholas Jennings

Virtual Power Plants (VPPs) are fast emerging as a suitable means of integrating small and distributed energy resources (DERs), like wind and solar, into the electricity supply network (Grid). VPPs are formed via the aggregation of a large number of such DERs, so that they exhibit the characteristics of a traditional generator in terms of predictability and robustness. In this work, we promote the formation of such “cooperative” VPPs (CVPPs) using multi-agent technology. In particular, we design a payment mechanism that encourages DERs to join CVPPs with large overall production. Our method is based on strictly proper scoring rules and incentivises the provision of accurate predictions from the CVPPs—and in turn, the member DERs—which aids in the planning of the supply schedule at the Grid. We empirically evaluate our approach using the real-world setting of 16 commercial wind farms in the UK. We show that our mechanism incentivises real DERs to form CVPPs, and outperforms the current state of the art payment mechanism developed for this problem.

PDF Details

AAAI Conference 2012 Conference Paper

Delivering the Smart Grid: Challenges for Autonomous Agents and Multi-Agent Systems Research

  • Alex Rogers
  • Sarvapali Ramchurn
  • Nicholas Jennings

Restructuring electricity grids to meet the increased demand caused by the electrification of transport and heating, while making greater use of intermittent renewable energy sources, represents one of the greatest engineering challenges of our day. This modern electricity grid, in which both electricity and information flow in two directions between large numbers of widely distributed suppliers and generators — commonly termed the ‘smart grid’ — represents a radical reengineering of infrastructure which has changed little over the last hundred years. However, the autonomous behaviour expected of the smart grid, its distributed nature, and the existence of multiple stakeholders each with their own incentives and interests, challenges existing engineering approaches. In this challenge paper, we describe why we believe that artificial intelligence, and particularly, the fields of autonomous agents and multi-agent systems are essential for delivering the smart grid as it is envisioned. We present some recent work in this area and describe many of the challenges that still remain.

PDF Details

AAAI Conference 2012 Conference Paper

Knapsack Based Optimal Policies for Budget–Limited Multi–Armed Bandits

  • Long Tran-Thanh
  • Archie Chapman
  • Alex Rogers
  • Nicholas Jennings

In budget–limited multi–armed bandit (MAB) problems, the learner’s actions are costly and constrained by a fixed budget. Consequently, an optimal exploitation policy may not be to pull the optimal arm repeatedly, as is the case in other variants of MAB, but rather to pull the sequence of different arms that maximises the agent’s total reward within the budget. This difference from existing MABs means that new approaches to maximising the total reward are required. Given this, we develop two pulling policies, namely: (i) KUBE; and (ii) fractional KUBE. Whereas the former provides better performance up to 40% in our experimental settings, the latter is computationally less expensive. We also prove logarithmic upper bounds for the regret of both policies, and show that these bounds are asymptotically optimal (i. e. they only differ from the best possible regret by a constant factor).

PDF Details

AAAI Conference 2012 Conference Paper

Optimizing Payments in Dominant-Strategy Mechanisms for Multi-Parameter Domains

  • Lachlan Dufton
  • Victor Naroditskiy
  • Maria Polukarov
  • Nicholas Jennings

In AI research, mechanism design is typically used to allocate tasks and resources to agents holding private information about their values for possible allocations. In this context, optimizing payments within the Groves class has recently received much attention, mostly under the assumption that agent’s private information is single-dimensional. Our work tackles this problem in multi-parameter domains. Specifically, we develop a generic technique to look for a best Groves mechanism for any given mechanism design problem. Our method is based on partitioning the spaces of agent values and payment functions into regions, on each of which we are able to define a feasible linear payment function. Under certain geometric conditions on partitions of the two spaces this function is optimal. We illustrate our method by applying it to the problem of allocating heterogeneous items.

PDF Details

AAAI Conference 2011 Conference Paper

A Distributed Anytime Algorithm for Dynamic Task Allocation in Multi-Agent Systems

  • Kathryn Macarthur
  • Ruben Stranders
  • Sarvapali Ramchurn
  • Nicholas Jennings

We introduce a novel distributed algorithm for multi-agent task allocation problems where the sets of tasks and agents constantly change over time. We build on an existing anytime algorithm (fast-max-sum), and give it significant new capabilities: namely, an online pruning procedure that simplifies the problem, and a branch-and-bound technique that reduces the search space. This allows us to scale to problems with hundreds of tasks and agents. We empirically evaluate our algorithm against established benchmarks and find that, even in such large environments, a solution is found up to 31% faster, and with up to 23% more utility, than state-of-the-art approximation algorithms. In addition, our algorithm sends up to 30% fewer messages than current approaches when the set of agents or tasks changes.

PDF Details

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.

PDF Details

AAAI Conference 2011 Conference Paper

Decentralised Control of Micro-Storage in the Smart Grid

  • Thomas Voice
  • Perukrishnen Vytelingum
  • Sarvapali Ramchurn
  • Alex Rogers
  • Nicholas Jennings

In this paper, we propose a novel decentralised control mechanism to manage micro-storage in the smart grid. Our approach uses an adaptive pricing scheme that energy suppliers apply to home smart agents controlling micro-storage devices. In particular, we prove that the interaction between a supplier using our pricing scheme and the actions of selfish micro-storage agents forms a globally stable feedback loop that converges to an efficient equilibrium. We further propose a market strategy that allows the supplier to reduce wholesale purchasing costs without increasing the uncertainty and variance for its aggregate consumer demand. Moreover, we empirically evaluate our mechanism (based on the UK grid data) and show that it yields savings of up to 16% in energy cost for consumers using storage devices with average capacity 10 kWh. Furthermore, we show that it is robust against extreme system changes.

PDF Details

AAAI Conference 2010 Conference Paper

A Decentralised Coordination Algorithm for Mobile Sensors

  • Ruben Stranders
  • Francesco Delle Fave
  • Alex Rogers
  • Nicholas Jennings

We present an on-line decentralised algorithm for coordinating mobile sensors for a broad class of information gathering tasks. These sensors can be deployed in unknown and possibly hostile environments, where uncertainty and dynamism are endemic. Such environments are common in the areas of disaster response and military surveillance. Our coordination approach itself is based on work by Stranders et al. (2009), that uses the max-sum algorithm to coordinate mobile sensors for monitoring spatial phenomena. In particular, we generalise and extend their approach to any domain where measurements can be valued. Also, we introduce a clustering approach that allows sensors to negotiate over paths to the most relevant locations, as opposed to a set of fixed directions, which results in a significantly improved performance. We demonstrate our algorithm by applying it to two challenging and distinct information gathering tasks. In the first–pursuit-evasion (PE)–sensors need to capture a target whose movement might be unknown. In the second– patrolling (P)–sensors need to minimise loss from intrusions that occur within their environment. In doing so, we obtain the first decentralised coordination algorithms for these domains. Finally, in each domain, we empirically evaluate our approach in a simulated environment, and show that it outperforms two state of the art greedy algorithms by 30% (PE) and 44% (P), and an existing approach based on the Travelling Salesman Problem by 52% (PE) and 30% (P).

PDF Details

AAAI Conference 2010 Conference Paper

A Distributed Algorithm for Optimising over Pure Strategy Nash Equilibria

  • Archie Chapman
  • Alessandro Farinelli
  • Enrique Munoz de Cote
  • Alex Rogers
  • Nicholas Jennings

We develop an efficient algorithm for computing pure strategy Nash equilibria that satisfy various criteria (such as the utilitarian or Nash–Bernoulli social welfare functions) in games with sparse interaction structure. Our algorithm, called Valued Nash Propagation (VNP), integrates the optimisation problem of maximising a criterion with the constraint satisfaction problem of finding a game’s equilibria to construct a criterion that defines a c–semiring. Given a suitably compact game structure, this criterion can be efficiently optimised using message–passing. To this end, we first show that VNP is complete in games whose interaction structure forms a hypertree. Then, we go on to provide theoretic and empirical results justifying its use on games with arbitrary structure; in particular, we show that it computes the optimum >82% of the time and otherwise selects an equilibrium that is always within 2% of the optimum on average.

PDF Details

AAAI Conference 2010 Conference Paper

Convergence to Equilibria in Plurality Voting

  • Reshef Meir
  • Maria Polukarov
  • Jeffrey Rosenschein
  • Nicholas Jennings

Multi-agent decision problems, in which independent agents have to agree on a joint plan of action or allocation of resources, are central to AI. In such situations, agents’ individual preferences over available alternatives may vary, and they may try to reconcile these differences by voting. Based on the fact that agents may have incentives to vote strategically and misreport their real preferences, a number of recent papers have explored different possibilities for avoiding or eliminating such manipulations. In contrast to most prior work, this paper focuses on convergence of strategic behavior to a decision from which no voter will want to deviate. We consider scenarios where voters cannot coordinate their actions, but are allowed to change their vote after observing the current outcome. We focus on the Plurality voting rule, and study the conditions under which this iterative game is guaranteed to converge to a Nash equilibrium (i. e. , to a decision that is stable against further unilateral manipulations). We show for the first time how convergence depends on the exact attributes of the game, such as the tie-breaking scheme, and on assumptions regarding agents’ weights and strategies.

PDF Details
v2026.09.13