Sebastian Stein

TAAS Journal 2026 Journal Article

Client–Master Multiagent Deep Reinforcement Learning for Task Offloading in Mobile Edge Computing

• Tesfay Zemuy Gebrekidan
• Sebastian Stein
• Timothy Norman

As mobile applications grow in complexity, there is an increasing need to perform computationally intensive tasks. However, User Devices (UDs), such as tablets and smartphones, have limited capacity to carry out the required computations. Task offloading in Mobile Edge Computing (MEC) is a strategy that meets this demand by distributing tasks between UDs and servers. Deep Reinforcement Learning (DRL) is a promising solution for this strategy because it can adapt to dynamic changes and minimize online computational complexity. However, the combination of continuous-valued soft constraints and discrete-valued hard constraints on UDs and MEC servers poses significant challenges for designing efficient DRL algorithms. Existing DRL-based task-offloading algorithms focus on the constraints of the UDs, assuming the availability of enough resources on the server. Moreover, existing Multiagent DRL (MADRL)-based task-offloading algorithms are homogeneous agents and consider homogeneous constraints as a penalty in their reward function. We propose a novel Client–Master MADRL (CMMADRL) algorithm for task offloading in MEC that uses client agents at the UDs to decide on their resource requirements and a master agent at the server to make a combinatorial action selection based on the decision of the UDs. CMMADRL is shown to achieve up to 59% improvement in performance over existing benchmark and heuristic algorithms.

AAMAS Conference 2026 Conference Paper

EVMapSim: A Network-level Electric Vehicle Charging Simulator

• Prokopis Georgiou
• Jayati Deshmukh
• Vahid Yazdanpanah
• Sebastian Stein
• Enrico Gerding

Long-distance electric vehicle (EV) travel depends critically on charging infrastructure reliability. When stations fail or queues form unexpectedly, drivers face increased range anxiety and risk of getting stranded. In this demonstration paper, we present EVMap- Sim, a discrete-event simulator for modelling EV navigation and charging behaviour at a national scale. We demonstrate 10, 000+ vehiclestraversingtheUKroadnetwork, eachmakingreal-timechargingdecisionswhileencounteringinfrastructurefailures. EVMapSim supports three failure scenarios, enabling analysis of how infrastructure resilience affects driver outcomes, including wait times, route deviations, and stranding rates.

AAMAS Conference 2026 Conference Paper

The Triad of Identity, Trust and Responsibility in Multi-Agent Systems

• Jayati Deshmukh
• Vahid Yazdanpanah
• Sebastian Stein
• Sarvapali D. Ramchurn

The design of autonomous AI agents that behave responsibly and foster trust in open multi-agent systems remains a fundamental challenge. Traditional game-theoretical approaches largely assume self-interested behaviour, yet real-world collaborations among humans often rely on prosocial considerations that extend beyond individual utility. To address this, for the first time in this paper, we investigate the triad of identity, responsibility, and trust as core elements shaping responsible multi-agent behaviour. We propose a novel agent model, building on the notion of Computational Transcendence, which equips agents with an elastic sense of identity, enabling them to incorporate the welfare of others into their decisionmaking. Our framework integrates subjective (identity-based) and objective (experience-based and reputation-based) components of trust. UsingIteratedPrisoner’sDilemma(IPD)simulationsondifferent network structures, we analyse how varying levels of identity and trust affect responsible behaviour. Results demonstrate that the interplay of these three concepts can promote emergent responsibility, mitigate exploitation, and sustain long-term cooperation in dynamic multi-agent environments. We argue that this triadic perspectiveprovidesaprincipledfoundationfordesigningtrustworthy, responsible, and identity/value aware agents with implications for future human–AI collaboration.

AAMAS Conference 2025 Conference Paper

Adaptive Microtolling in Competitive Online Congestion Games via Multiagent Reinforcement Learning

• Behrad Koohy
• Sebastian Stein
• Enrico Gerding

Efficient urban traffic management remains a critical challenge, yet traditional congestion games fail to capture the dynamic and competitive nature of real-world transportation systems. We introduce the Multi-Market Routing Problem (MMRP), an online and oligopolistic extension that models competition amongst route providers utilising adaptive microtolling strategies to influence driver behaviour and mitigate congestion. We formally define the MMRP, highlighting the computational complexity of solving the MMRP, and use an adapted version of Proximal Policy Optimisation (PPO) to improve update stability in multiagent environments to address this problem in online settings. Our empirical analysis demonstrates that our PPO-based approach not only matches the performance of existing benchmarks but also significantly enhances equity, reduces travel times for users, and increases profitability for providers.

AAMAS Conference 2025 Conference Paper

Serious Games for Ethical Preference Elicitation

• Jayati Deshmukh
• Zijie Liang
• Vahid Yazdanpanah
• Sebastian Stein
• Savapali D. Ramchurn

Autonomous agents acting on behalf of humans must act according to those humans’ ethical preferences. However, ethical preferences are latent and abstract, and thus it is challenging to elicit them. To address this, we present a serious game that helps elicit ethical preferences in a more dynamic and engaging way than traditional methods, such as questionnaires or simple dilemmas.

AAMAS Conference 2024 Conference Paper

Adaptive Incentive Engineering in Citizen-Centric AI

• Behrad Koohy
• Jan Buermann
• Vahid Yazdanpanah
• Pamela Briggs
• Paul Pschierer-Barnfather
• Enrico Gerding
• Sebastian Stein

Adaptive incentives are a valuable tool shown to improve the efficiency of complex multiagent systems and could produce win-win situations for all stakeholders. However, their application usage is very limited, partly due to a significant gap between the literature and practice. We argue that overcoming this gap requires addressing four open research challenges. First, the dynamic, volatile and uncertain nature of environments needs to be fully considered. Second, social factors including user acceptance, fairness, ethical considerations and trust have to match end users’ expectations and needs. Third, the evaluation of mechanisms and systems has to be robust and focused on real-world outcomes and stakeholder requirements. Finally, all this has to be built on a reliable theoretical foundation. In order to overcome these open challenges in adaptive incentive engineering, tools from the fields of mechanism design and game theory can be used. This will help to achieve the opportunities adaptive incentives can provide to real-world practical environments, producing better AI systems for the benefit of all.

AAMAS Conference 2024 Conference Paper

Combinatorial Client-Master Multiagent Deep Reinforcement Learning for Task Offloading in Mobile Edge Computing

• Tesfay Zemuy Gebrekidan
• Sebastian Stein
• Timothy J. Norman

Deep reinforcement learning (DRL) is gaining popularity in taskoffloading problems because it can adapt to dynamic changes and minimize online computational complexity. However, the various types of continuous and discrete resource constraints on user devices (UDs) and mobile edge computing (MEC) servers pose challenges to the design of an efficient DRL-based task-offloading strategy. Existing DRL-based task-offloading algorithms focus on the constraints of the UDs, assuming the availability of enough storage resources on the server. Moreover, existing multiagent DRL (MADRL)–based task-offloading algorithms are homogeneous agents and consider homogeneous constraints as a penalty in their reward function. In this work, we propose a novel combinatorial client-master MADRL (CCM_MADRL) algorithm for task offloading in mobile edge computing (CCM_MADRL_MEC) that allows UDs to decide their resource requirements and the server to make a combinatorial decision based on the UDs’ requirements. CCM_MADRL_MEC is the first MADRL approach in task offloading to consider server storage capacity in addition to the constraints of the UDs. By taking advantage of the combinatorial action selection, CCM_MADRL_MEC has shown superior convergence over existing benchmark and heuristic algorithms.

AAMAS Conference 2024 Conference Paper

Deep Reinforcement Learning with Coalition Action Selection for Online Combinatorial Resource Allocation with Arbitrary Action Space

• Tesfay Zemuy Gebrekidan
• Sebastian Stein
• Timothy J. Norman

Current DRL algorithms typically assume a fixed number of possible actions and sequentially select one action at a time, making them inefficient for resource allocation problems with arbitrarily large action spaces. Sequential action selection requires updating the state for every action selected, which increases the depth of the decision, the state space, the uncertainty, and the number of executions. This affects the convergence of the algorithm and slows the execution speed. Additionally, current DRL algorithms are not efficient for online resource allocation problems with an arbitrary number of task arrivals per time step because they assume a fixed number of actions. To address these challenges, we propose a novel coalition action selection approach that enables the DRL algorithm to simultaneously select a coalition of an arbitrary number of actions from a set with an arbitrary number of possible actions. By making simultaneous decisions at each time step, coalition action selection avoids the computational cost and large state space caused by the sequential decision that updates the state multiple times. We evaluate the performance and complexity of coalition action selection and sequential action selection approaches using an online combinatorial resource allocation problem. The results demonstrate that the coalition action selection approach retains close performance to the offline optimal for various online traffic demand arrival rates of the online combinatorial resource allocation problem, while the performance of the sequential action selection approach decreases as the size of the problem increases. The experiments also demonstrate that coalition action selection has much lower computational complexity than sequential action selection.

AAMAS Conference 2024 Conference Paper

EVtonomy: A Personalised Route Planner for Electric Vehicles

• Alexandry Augustin
• Elnaz Shafipour
• Sebastian Stein

With the continuing growth of the electric vehicle (EV) market, planning long road trips should be a seamless and hassle-free experience for EV owners. Dedicated EV route planning apps have emerged recently as indispensable assistants providing essential mapping and data services. However, EV owners still face a number of challenges when planning their routes to prevent unnecessary delays or expenses. These challenges are not yet fully addressed with current EV planning apps. This paper introduces EVtonomy, an app that assigns an intelligent agent to each driver capable of planning personalised journeys. Specifically, the agent provides routes and charging stop recommendations aligned with the EV owner’s individual preferences in terms of trip duration, including both driving time and the time spent charging the car, along with the total charging costs.

AAMAS Conference 2024 Conference Paper

Online Decentralised Mechanisms for Dynamic Ridesharing

• Nicos Protopapas
• Vahid Yazdanpanah
• Enrico H. Gerding
• Sebastian Stein

Ridesharing services promise an exciting new future for urban mobility. A carefully designed ridesharing system will decrease congestion levels and increase air quality. However, an effective system needs to capture online demand, where users do not schedule their trips in advance, but instead appear and ask for a ride right away. Such online demands require rerouting to be efficient. We call this setting with online demands and available rerouting “dynamic ridesharing” and propose a market-based mechanism where the prospective riders are provided with a menu of choices between several available cars. Our algorithm incentivises users to share their rides and guarantees riders’ utility by properly compensating riders whose routes change during their journey. We provide numerical results, comparing our algorithm against natural benchmarks representing real-world ridesharing services for several cases and with respect to efficiency, fairness, and environmental impact.

JAAMAS Journal 2024 Journal Article

Personalised electric vehicle charging stop planning through online estimators

• Elnaz Shafipour
• Sebastian Stein
• Selin Ahipasaoglu

Abstract In this paper, we address the problem of finding charging stops while travelling in electric vehicles (EVs) using artificial intelligence (AI). Choosing a charging station is challenging, because drivers have very heterogeneous preferences in terms of how they trade off the features of various alternatives (for example, regarding the time spent driving, charging costs, waiting times at charging stations, and the facilities provided at the charging stations). The key problem here is eliciting the diverse preferences of drivers, assuming that these preferences are typically not fully known a priori, and then planning stops based on each driver’s preferences. Our approach to solving this problem is to develop an intelligent personal agent that learns preferences gradually over multiple interactions. This study proposes a new technique that utilises a small-scale discrete choice experiment as a method of interacting with the driver in order to minimise the cognitive burden on the driver. Using this method, drivers are presented with a variety of routes with possible combinations of charging stops depending on the agent’s latest belief about their preferences. In subsequent iterations, the personal agent will continue to learn and refine its belief about the driver’s preferences, suggesting more personalised routes that are closer to the driver’s preferences. Based on real preference data from EV drivers, we evaluate our novel algorithm and show that, after only a few queries, our method quickly converges to the optimal routes for EV drivers [This paper is an extended version of an ECAI workshop short paper (Shafipour Yourdshahi et al. , in: ECAI 2023 workshops, Kraków, Poland, 2023)].

AAMAS Conference 2023 Conference Paper

Citizen-Centric Multiagent Systems

• Sebastian Stein
• Vahid Yazdanpanah

Advances in multiagent systems (MAS) have the potential to solve critical societal challenges. For example, MAS techniques for efficient resource allocation can help us implement cleaner and more efficient forms of on-demand mobility; social choice methods can support us in deciding how to trade off energy use and comfort in smart buildings; and task coordination methods can be used to respond to disasters in an effective and resilient manner. However, the benefits of these approaches can only be realised if citizen end users are able to trust these emerging multiagent systems. To achieve this, a citizen-centric approach needs to be taken. This places citizens at the heart of the design, development and deployment of trustworthy multiagent systems. We present open research challenges in this area, put forward key application domains for citizen-centric MAS (C-MAS) and discuss collaborative research opportunities.

AAMAS Conference 2023 Conference Paper

The Influence Maximisation Game

• Sukankana Chakraborty
• Sebastian Stein
• Ananthram Swami
• Matthew Jones
• Lewis Hill

The problem of influence maximisation investigates efficient ways in which external influence (typically limited by resources) can be applied to a social network to maximise control over the global behaviours of a population. It is an effective tool that finds its application in many real-world scenarios, for instance it can be used to gather intelligence in crowdsourcing activities and to incentivise people to adopt desirable public policies. While the problem has been studied extensively in theoretical settings, many of these approaches can be expensive and inefficient to apply in the real world, particularly when considering an unknown or irrational competitor. The influence maximisation game was designed to bridge this gap between theory and the practical application of this knowledge. In this experiment, human subjects are presented with networks where they can employ their own tactics to maintain maximum influence against a competitor (which in this case is an AI agent). We aim to determine how people strategise to spread influence in the real world. In particular, we determine if people always act rationally in these settings or if their strategies are inherently biased —in which case we aim to identify inexpensive, yet effective strategies that can outperform these biased strategies. Observing how people strategise in the real world can help us modify our theoretical results for more efficient practical applications.

IJCAI Conference 2022 Conference Paper

A Polynomial-time Decentralised Algorithm for Coordinated Management of Multiple Intersections

• Tatsuya Iwase
• Sebastian Stein
• Enrico H. Gerding
• Archie Chapman

Autonomous intersection management has the potential to reduce road traffic congestion and energy consumption. To realize this potential, efficient algorithms are needed. However, most existing studies locally optimize one intersection at a time, and this can cause negative externalities on the traffic network as a whole. Here, we focus on coordinating multiple intersections, and formulate the problem as a distributed constraint optimisation problem (DCOP). We consider three utility design approaches that trade off efficiency and fairness. Our polynomial-time algorithm for coordinating multiple intersections reduces the traffic delay by about 41 percentage points compared to independent single intersection management approaches.

IJCAI Conference 2021 Conference Paper

A Polynomial-time, Truthful, Individually Rational and Budget Balanced Ridesharing Mechanism

• Tatsuya Iwase
• Sebastian Stein
• Enrico H. Gerding

Ridesharing has great potential to improve transportation efficiency while reducing congestion and pollution. To realize this potential, mechanisms are needed that allocate vehicles optimally and provide the right incentives to riders. However, many existing approaches consider restricted settings (e. g. , only one rider per vehicle or a common origin for all riders). Moreover, naive applications of standard approaches, such as the Vickrey-Clarke-Groves or greedy mechanisms, cannot achieve a polynomial-time, truthful, individually rational and budget balanced mechanism. To address this, we formulate a general ridesharing problem and apply mechanism design to develop a novel mechanism which satisfies all four properties and whose social cost is within 8. 6% of the optimal on average.

AAMAS Conference 2021 Conference Paper

Responsibility Research for Trustworthy Autonomous Systems

• Vahid Yazdanpanah
• Enrico H. Gerding
• Sebastian Stein
• Mehdi Dastani
• Catholijn M. Jonker
• Timothy J. Norman

To develop and effectively deploy Trustworthy Autonomous Systems (TAS), we face various social, technological, legal, and ethical challenges in which different notions of responsibility can play a key role. In this work, we elaborate on these challenges, discuss research gaps, and show how the multidimensional notion of responsibility can play a role to bridge them. We argue that TAS requires operational tools to represent and reason about responsibilities of humans as well as AI agents. We review major challenges to which responsibility reasoning can contribute, highlight open research problems, and argue for the application of multiagent responsibility models in a variety of TAS domains.

AAMAS Conference 2019 Conference Paper

A Truthful Online Mechanism for Allocating Fog Computing Resources

• Fan Bi
• Sebastian Stein
• Enrico Gerding
• NICK JENNINGS
• Tom La Porta

AAMAS Conference 2018 Conference Paper

Adaptive Incentive Selection for Crowdsourcing Contests

• Nhat V. Q. Truong
• Sebastian Stein
• Long Tran-Thanh
• Nicholas R. Jennings

JAIR Journal 2018 Journal Article

Coordinating Measurements in Uncertain Participatory Sensing Settings

• Alexandros Zenonos
• Sebastian Stein
• Nicholas R. Jennings

Environmental monitoring allows authorities to understand the impact of potentially harmful phenomena, such as air pollution, excessive noise, and radiation. Recently, there has been considerable interest in participatory sensing as a paradigm for such large-scale data collection because it is cost-effective and able to capture more fine-grained data than traditional approaches that use stationary sensors scattered in cities. In this approach, ordinary citizens (non-expert contributors) collect environmental data using low-cost mobile devices. However, these participants are generally self-interested actors that have their own goals and make local decisions about when and where to take measurements. This can lead to highly inefficient outcomes, where observations are either taken redundantly or do not provide sufficient information about key areas of interest. To address these challenges, it is necessary to guide and to coordinate participants, so they take measurements when it is most informative. To this end, we develop a computationally-efficient coordination algorithm (adaptive Best-Match) that suggests to users when and where to take measurements. Our algorithm exploits probabilistic knowledge of human mobility patterns, but explicitly considers the uncertainty of these patterns and the potential unwillingness of people to take measurements when requested to do so. In particular, our algorithm uses a local search technique, clustering and random simulations to map participants to measurements that need to be taken in space and time. We empirically evaluate our algorithm on a real-world human mobility and air quality dataset and show that it outperforms the current state of the art by up to 24% in terms of utility gained.

AAMAS Conference 2018 Conference Paper

Price-based Online Mechanisms for Settings with Uncertain Future Procurement Costs and Multi-unit Demand

• Keiichiro Hayakawa
• Enrico H. Gerding
• Sebastian Stein
• Takahiro Shiga

We examine the use of online mechanism design in settings where consumers have multi-unit demand, goods are procured and allocated over time, and future procurement costs are uncertain and only become known at the time of allocation. An important application with such characteristics is demand response, where electricity wholesale prices depend on overall demand and the availability of renewables. We formulate this as a mechanism design problem and focus specifically on the property that the mechanism does not revoke any allocated items. In this setting, we characterise a class of price-based mechanisms that guarantee dominant-strategy incentive compatibility, individual rationality, and no cancellation. We present three specific such mechanisms in this domain and evaluate them in an electric vehicle charging setting. By using extensive numerical simulations, we show that a mechanism based on the first-come first-served principle performs well in settings where future procurement costs can be estimated reliably or supply is very tight, while a responsive mechanism performs very well when the estimated procurement costs are highly uncertain and supply is not as tight. We moreover show that a well-defined pricebased mechanism can lead to high profits for the operator of the mechanism in many real-world situations.

TIST Journal 2017 Journal Article

A Comfort-Based Approach to Smart Heating and Air Conditioning

• Frederik Auffenberg
• Stephen Snow
• Sebastian Stein
• Alex Rogers

In this article, we address the interrelated challenges of predicting user comfort and using this to reduce energy consumption in smart heating, ventilation, and air conditioning (HVAC) systems. At present, such systems use simple models of user comfort when deciding on a set-point temperature. Being built using broad population statistics, these models generally fail to represent individual users’ preferences, resulting in poor estimates of the users’ preferred temperatures. To address this issue, we propose the Bayesian Comfort Model (BCM). This personalised thermal comfort model uses a Bayesian network to learn from a user’s feedback, allowing it to adapt to the users’ individual preferences over time. We further propose an alternative to the ASHRAE 7-point scale used to assess user comfort. Using this model, we create an optimal HVAC control algorithm that minimizes energy consumption while preserving user comfort. Through an empirical evaluation based on the ASHRAE RP-884 dataset and data collected in a separate deployment by us, we show that our model is consistently 13.2% to 25.8% more accurate than current models and how using our alternative comfort scale can increase our model’s accuracy. Through simulations we show that using this model, our HVAC control algorithm can reduce energy consumption by 7.3% to 13.5% while decreasing user discomfort by 24.8% simultaneously.

AAMAS Conference 2017 Conference Paper

Adaptive Pricing Mechanisms for On-Demand Mobility

• Maciej Drwal
• Enrico Gerding
• Sebastian Stein
• Keiichiro Hayakawa
• Hironobu Kitaoka

We consider on-demand car rental systems for public transportation. In these systems, demands are often unbalanced across different parking stations, necessitating costly manual relocations of vehicles. To address this so-called “deadheading” effect and maximise the operator’s revenue, we propose two novel pricing mechanisms. These adaptively adjust the prices between origin and destination stations depending on their current occupancy, probabilistic information about the customers’ valuations and estimated relocation costs. In so doing, the mechanisms incentivise drivers to help rebalance the system and place a premium on trips that lead to costly relocations. We evaluate the mechanisms in a series of experiments using real historical data from an existing on-demand mobility system in a French city. We show that our mechanisms achieve an up to 64% increase in revenue for the operator and at the same time up to 36% fewer relocations.

IJCAI Conference 2017 Conference Paper

Evaluating Market User Interfaces for Electric Vehicle Charging using Bid2Charge

• Sebastian Stein
• Enrico H. Gerding
• Adrian Nedea
• Avi Rosenfeld
• Nicholas R. Jennings

We consider settings where electric vehicle drivers participate in a market mechanism to charge their vehicles. Existing work typically assumes that participants are fully rational and can report their charging preferences accurately. However, this may not be reasonable in settings with non-experts. To explore this, we design a novel game called Bid2Charge and compare a fully expressive interface that covers the entire space of preferences to two restricted interfaces that offer fewer possible reports. We show that restricting the users' preferences significantly reduces deliberation times while also leading to an increase in utility by up to 70%.

JAIR Journal 2017 Journal Article

Market Interfaces for Electric Vehicle Charging

• Sebastian Stein
• Enrico H. Gerding
• Adrian Nedea
• Avi Rosenfeld
• Nicholas R. Jennings

We consider settings where owners of electric vehicles (EVs) participate in a market mechanism to charge their vehicles. Existing work on such mechanisms has typically assumed that participants are fully rational and can report their preferences accurately via some interface to the mechanism or to a software agent participating on their behalf. However, this may not be reasonable in settings with non-expert human end-users.Thus, our overarching aim in this paper is to determine experimentally if a fully expressive market interface that enables accurate preference reports is suitable for the EV charging domain, or, alternatively, if a simpler, restricted interface that reduces the space of possible options is preferable. In doing this, we measure the performance of an interface both in terms of how it helps participants maximise their utility and how it affects deliberation time. Our secondary objective is to contrast two different types of restricted interfaces that vary in how they restrict the space of preferences that can be reported. To enable this analysis, we develop a novel game that replicates key features of an abstract EV charging scenario. In two experiments with over 300 users, we show that restricting the users' preferences significantly reduces the time they spend deliberating (by up to half in some cases). An extensive usability survey confirms that this restriction is furthermore associated with a lower perceived cognitive burden on the users. More surprisingly, at the same time, using restricted interfaces leads to an increase in the users' performance compared to the fully expressive interface (by up to 70%). We also show that some restricted interfaces have the desirable effect of reducing the energy consumption of their users by up to 20% while achieving the same utility as other interfaces. Finally, we find that a reinforcement learning agent displays similar performance trends to human users, enabling a novel methodology for evaluating market interfaces.

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.

AAMAS Conference 2016 Conference Paper

Bid2Charge: Market User Interface Design for Electric Vehicle Charging

• Sebastian Stein
• Enrico H. Gerding
• Adrian Nedea
• Avi Rosenfeld
• Nicholas R. Jennings

We consider settings where owners of electric vehicles (EVs) participate in a market mechanism to charge their vehicles. Existing work on such mechanisms has typically assumed that participants are fully rational and can report their preferences accurately to the mechanism or to a software agent participating on their behalf. However, this may not be reasonable in settings with non-expert human end-users. To explore this, we compare a fully expressive interface that covers the entire space of preferences to two restricted interfaces that reduce the space of possible options. To enable this analysis, we develop a novel game that replicates key features of an abstract EV charging scenario. In two extensive evaluations with over 300 users, we show that restricting the users’ preferences significantly reduces the time they spend deliberating. More surprisingly, it also leads to an increase in their utility compared to the fully expressive interface (up to 70%). Finally, we find that a reinforcement learning agent displays similar performance trends, enabling a novel methodology for evaluating market interfaces.

AAMAS Conference 2016 Conference Paper

Minimising the Rank Aggregation Error (Extended Abstract)

• Mathijs M. de Weerdt
• Enrico H. Gerding
• Sebastian Stein

Rank aggregation is the problem of generating an overall ranking from a set of individual votes which is as close as possible to the (unknown) correct ranking. The challenge is that votes are often both noisy and incomplete. Existing work focuses on the most likely ranking for a particular noise model. Instead, we focus on minimising the error, i. e. , the expected distance between the aggregated ranking and the correct one. We show that this results in different rankings, and we show how to compute local improvements of rankings to reduce the error. Extensive experiments on both synthetic data based on Mallows’ model and real data show that Copeland has a smaller error than the Kemeny rule, while the latter is the maximum likelihood estimator.

IJCAI Conference 2016 Conference Paper

Online Mechanism Design for Vehicle-to-Grid Car Parks

• Enrico H. Gerding
• Sebastian Stein
• Sofia Ceppi
• Valentin Robu

Vehicle-to-grid (V2G) is a promising approach whereby electric vehicles (EVs) are used to store excess electricity supply (e. g. , from renewable sources), which is sold back to the grid in times of scarcity. In this paper we consider the setting of a smart car park, where EVs come and go, and can be used for V2G while parked. We develop novel allocation and payment mechanisms which truthfully elicit the EV owners' preferences and constraints, including arrival, departure, required charge, as well as the costs of discharging due to loss of efficiency of the battery. The car park will schedule the charging and discharging of each EV, ensuring the constraints of the EVs are met, and taking into consideration predictions about future electricity prices. Optimally solving the global problem is intractable, and we present three novel heuristic online scheduling algorithms. We show that, under certain conditions, two of these satisfy monotonicity and are therefore truthful. We furthermore evaluate the algorithms using simulations, and we show that some of our algorithms benefit significantly from V2G, achieving positive benefit for the car park even when agents do not pay for using it.

IJCAI Conference 2015 Conference Paper

A Personalised Thermal Comfort Model Using a Bayesian Network

• Frederik Auffenberg
• Sebastian Stein
• Alex Rogers

In this paper, we address the challenge of predicting optimal comfort temperatures of individual users of a smart heating system. At present, such systems use simple models of user comfort when deciding on a set point temperature. These models generally fail to adapt to an individual user’s preferences, resulting in poor estimates of a user’s preferred temperature. To address this issue, we propose a personalised thermal comfort model that uses a Bayesian network to learn and adapt to a user’s individual preferences. Through an empirical evaluation based on the ASHRAE RP-884 data set, we show that our model is consistently 17. 5- 23. 5% more accurate than current models, regardless of environmental conditions and the type of heating system used. Our model is not limited to a single metric but can also infer information about expected user feedback, optimal comfort temperature and thermal sensitivity at the same time, which can be used to reduce energy used for heating with minimal comfort loss.

IJCAI Conference 2015 Conference Paper

Online Mechanisms for Charging Electric Vehicles in Settings with Varying Marginal Electricity Costs

• Keiichiro Hayakawa
• Enrico H. Gerding
• Sebastian Stein
• Takahiro Shiga

We propose new mechanisms that can be used by a demand response aggregator to flexibly shift the charging of electric vehicles (EVs) to times where cheap but intermittent renewable energy is in high supply. Here, it is important to consider the constraints and preferences of EV owners, while eliminating the scope for strategic behaviour. To achieve this, we propose, for the first time, a generic class of incentive mechanisms for settings with both varying marginal electricity costs and multidimensional preferences. We show these are dominant strategy incentive compatible, i. e. , EV owners are incentivised to report their constraints and preferences truthfully. We also detail a specific instance of this class, show that it achieves ≈ 98% of the optimal in realistic scenarios and demonstrate how it can be adapted to trade off efficiency with profit.

AIJ Journal 2014 Journal Article

Efficient crowdsourcing of unknown experts using bounded multi-armed bandits

• Long Tran-Thanh
• Sebastian Stein
• Alex Rogers
• Nicholas R. Jennings

Increasingly, organisations flexibly outsource work on a temporary basis to a global audience of workers. This so-called crowdsourcing has been applied successfully to a range of tasks, from translating text and annotating images, to collecting information during crisis situations and hiring skilled workers to build complex software. While traditionally these tasks have been small and could be completed by non-professionals, organisations are now starting to crowdsource larger, more complex tasks to experts in their respective fields. These tasks include, for example, software development and testing, web design and product marketing. While this emerging expert crowdsourcing offers flexibility and potentially lower costs, it also raises new challenges, as workers can be highly heterogeneous, both in their costs and in the quality of the work they produce. Specifically, the utility of each outsourced task is uncertain and can vary significantly between distinct workers and even between subsequent tasks assigned to the same worker. Furthermore, in realistic settings, workers have limits on the amount of work they can perform and the employer will have a fixed budget for paying workers. Given this uncertainty and the relevant constraints, the objective of the employer is to assign tasks to workers in order to maximise the overall utility achieved. To formalise this expert crowdsourcing problem, we introduce a novel multi-armed bandit (MAB) model, the bounded MAB. Furthermore, we develop an algorithm to solve it efficiently, called bounded ε-first, which proceeds in two stages: exploration and exploitation. During exploration, it first uses εB of its total budget B to learn estimates of the workers' quality characteristics. Then, during exploitation, it uses the remaining ( 1 − ε ) B to maximise the total utility based on those estimates. Using this technique allows us to derive an O ( B 2 3 ) upper bound on its performance regret (i. e. , the expected difference in utility between our algorithm and the optimum), which means that as the budget B increases, the regret tends to 0. In addition to this theoretical advance, we apply our algorithm to real-world data from oDesk, a prominent expert crowdsourcing site. Using data from real projects, including historic project budgets, expert costs and quality ratings, we show that our algorithm outperforms existing crowdsourcing methods by up to 300%, while achieving up to 95 % of a hypothetical optimum with full information.

IJCAI Conference 2013 Conference Paper

Intention-Aware Routing to Minimise Delays at Electric Vehicle Charging Stations

• Mathijs M. de Weerdt
• Enrico H. Gerding
• Sebastian Stein
• Valentin Robu
• Nicholas R. Jennings

En-route charging stations allow electric vehicles to greatly extend their range. However, as a full charge takes a considerable amount of time, there may be significant waiting times at peak hours. To address this problem, we propose a novel navigation system, which communicates its intentions (i. e. , routing policies) to other drivers. Using these intentions, our system accurately predicts congestion at charging stations and suggests the most efficient route to its user. We achieve this by extending existing time-dependent stochastic routing algorithms to include the battery’s state of charge and charging stations. Furthermore, we describe a novel technique for combining historical information with agent intentions to predict the queues at charging stations. Through simulations we show that our system leads to a significant increase in utility compared to existing approaches that do not explicitly model waiting times or use intentions, in some cases reducing waiting times by over 80% and achieving near-optimal overall journey times.

AAMAS Conference 2012 Conference Paper

A Model-Based Online Mechanism with Pre-Commitment and its Application to Electric Vehicle Charging

• Sebastian Stein
• Enrico Gerding
• Valentin Robu
• NICK JENNINGS

We introduce a novel online mechanism that schedules the allocation of an expiring and continuously-produced resource to self-interested agents with private preferences. A key application of our mechanism is the charging of pure electric vehicles, where owners arrive dynamically over time, and each owner requires a minimum amount of charge by its departure to complete its next trip. To truthfully elicit the agents' preferences in this setting, we introduce the new concept of pre-commitment: Whenever an agent is selected, our mechanism pre-commits to charging the vehicle by its reported departure time, but maintains flexibility about \emph{when} the charging takes place and at \emph{what rate}. Furthermore, to make effective allocation decisions we use a model-based approach by modifying Consensus, a well-known online optimisation algorithm. We show that our pre-commitment mechanism with modified Consensus incentivises truthful reporting. Furthermore, through simulations based on real-world data, we show empirically that the average utility achieved by our mechanism is 93% or more of the offline optimal.

AAMAS Conference 2012 Conference Paper

Decentralised Channel Allocation and Information Sharing for Teams of Cooperative Agents

• Sebastian Stein
• Simon Williamson
• NICK JENNINGS

In a wide range of emerging applications, from disaster management to intelligent sensor networks, teams of software agents can be deployed to effectively solve complex distributed problems. To achieve this, agents typically need to communicate locally sensed information to each other. However, in many settings, there are heavy constraints on the communication infrastructure, making it infeasible for every agent to broadcast all relevant information to everyone else. To address this challenge, we investigate how agents can make good local decisions about what information to send to a set of communication channels with limited bandwidths such that the overall system utility is maximised. Specifically, to solve this problem efficiently in large-scale systems with hundreds or thousands of agents, we develop a novel decentralised algorithm. This combines multi-agent learning techniques with fast decision-theoretic reasoning mechanisms that predict the impact a single agent has on the entire system. We show empirically that our algorithm consistently achieves 85% of a hypothetical centralised optimal strategy with full information, and that it significantly outperforms a number of baseline benchmarks (by up to 600%).

AAMAS Conference 2011 Conference Paper

Online Mechanism Design for Electric Vehicle Charging

• Enrico H. Gerding
• Valentin Robu
• Sebastian Stein
• David C. Parkes
• Alex Rogers
• Nicholas R. Jennings

Plug-in hybrid electric vehicles are expected to place a considerable strain on local electricity distribution networks, requiring charging to be coordinated in order to accommodate capacity constraints. We design a novel online auction protocol for this problem, wherein vehicle owners use agents to bid for power and also state time windows in which a vehicle is available for charging. This is a multi-dimensional mechanism design domain, with owners having non-increasing marginal valuations for each subsequent unit of electricity. In our design, we couple a greedy allocation algorithm with the occasional "burning" of allocated power, leaving it unallocated, in order to adjust an allocation and achieve monotonicity and thus truthfulness. We consider two variations: burning at each time step or on-departure. Both mechanisms are evaluated in depth, using data from a real-world trial of electric vehicles in the UK to simulate system dynamics and valuations. The mechanisms provide higher allocative efficiency than a fixed price system, are almost competitive with a standard scheduling heuristic which assumes non-strategic agents, and can sustain a substantially larger number of vehicles at the same per-owner fuel cost saving than a simple random scheme.

AAMAS Conference 2010 Conference Paper

Scalable Mechanism Design for the Procurement of Services with Uncertain Durations

• Enrico Gerding
• Sebastian Stein
• Kate Larson
• Alex Rogers
• Nicholas R. Jennings

In this paper, we study a service procurement problem with uncertainty as to whether service providers are capable of completing agiven task within a specified deadline. This type of setting is often encountered in large and dynamic multi-agent systems, such ascomputational Grids or clouds. To effectively deal with this uncertainty, the consumer may dynamically and redundantly procuremultiple services over time, in order to increase the probability ofsuccess, while at the same time balancing this with the additionalprocurement costs. However, in order to do this optimally, the consumer requires information about the providers' costs and their success probabilities over time. This information is typically held privately by the providers and they may have incentives to misreportthis, so as to increase their own profits. To address this problem, weintroduce a novel mechanism that incentivises self-interested providers to reveal their true costs and capabilities, and we show thatthis mechanism is ex-post incentive compatible, efficient and individually rational. However, for these properties to hold, it generallyneeds to compute the optimal solution, which can be intractable inlarge settings. Therefore, we show how we can generate approximate solutions while maintaining the economic properties of themechanism. This approximation admits a polynomial-time solution that can be computed in seconds even for hundreds of providers, and we demonstrate empirically that it performs as well as theoptimal in typical scenarios. In particularly challenging settings, we show that it still achieves 97\% or more of the optimal.

IJCAI Conference 2009 Conference Paper

• Sebastian Stein
• Enrico Gerding
• Alex Rogers
• Kate Larson
• Nicholas R. Jennings

Emerging service-oriented technologies allow software agents to automatically procure distributed services to complete complex tasks. However, in many application scenarios, service providers demand financial remuneration, execution times are uncertain and consumers have deadlines for their tasks. In this paper, we address these issues by developing a novel approach that dynamically procures multiple, redundant services over time, in order to ensure success by the deadline. Specifically, we first present an algorithm for finding optimal procurement solutions, as well as a heuristic algorithm that achieves over 99% of the optimal and is capable of handling thousands of providers. Using experiments, we show that these algorithms achieve an improvement of up to 130% over current strategies that procure only single services. Finally, we consider settings where service costs are not known to the consumer, and introduce several mechanisms that incentivise providers to reveal their costs truthfully and that still achieve up to 95% efficiency.

AAMAS Conference 2008 Conference Paper

Flexible Service Provisioning with Advance Agreements

• Sebastian Stein
• Terry Payne
• NICK JENNINGS

In this paper, we develop a novel algorithm that allows service consumer agents to automatically select and provision service provider agents for their workflows in highly dynamic and uncertain computational service economies. In contrast to existing work, our algorithm reasons explicitly about the impact of failures on the overall feasibility of a workflow, and it mitigates them by proactively provisioning multiple providers in parallel for particularly critical tasks and by explicitly planning for contingencies. Furthermore, our algorithm provisions only part of its workflow at any given time, in order to retain flexibility and to decrease the potential for missing negotiated service time slots. We show empirically that current approaches are unable to achieve a high utility in such uncertain and dynamic environments; whereas our algorithm consistently outperforms them over a range of environments. Specifically, our approach can achieve up to a 27-fold increase in utility and successfully completes most workflows within a strict deadline, even when the majority of providers do not honour their contracts.

AAAI Conference 2007 Short Paper

Flexible Provisioning of Service Workflows

• Sebastian Stein

AAAI Conference 2007 Conference Paper

Provisioning Heterogeneous and Unreliable Providers for Service Workflows

• Sebastian Stein

Service-oriented technologies enable software agents to dynamically discover and provision remote services for their workflows. Current work has typically assumed these services to be reliable and deterministic, but this is unrealistic in open systems, such as the Web, where they are offered by autonomous agents and are, therefore, inherently unreliable. To address this potential unreliability (in particular, uncertain service durations and failures), we consider the provisioning of abstract workflows, where many heterogeneous providers offer services at differing levels of quality. More specifically, we show that service provisioning is NP-hard, and then devise two heuristic strategies that use service redundancy in a flexible manner to address uncertainty and failure. In empirical experiments, we show that these heuristic strategies can achieve significant improvements over standard approaches in a wide range of environments.

AAMAS Conference 2007 Conference Paper

Provisioning Heterogeneous and Unreliable Providers for Service Workflows

• Sebastian Stein
• Nicholas R. Jennings
• TERRY R. PAYNE

In this paper, we address the problemof provisioning unreliable and heterogeneous service providers for the constituent tasks of abstract workflows. Specifically, we deal with unreliable providers by provisioning multiple service providers redundantly for specific tasks, and we employ a local search mechanism to choose among many heterogeneous providers that offer the same type of service. We empirically show that our strategy can achieve significant improvements over current approaches, and we demonstrate that it works well over a range of environments.