2011
Ramchurn, Sarvapali; Vytelingum, Perukrishnen; Rogers, Alex; Jennings, Nick
Agent-based control for decentralised demand side management in the smart grid Proceedings Article
In: The Tenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011), pp. 5–12, 2011.
@inproceedings{eps271985,
title = {Agent-based control for decentralised demand side management in the smart grid},
author = {Sarvapali Ramchurn and Perukrishnen Vytelingum and Alex Rogers and Nick Jennings},
url = {http://eprints.soton.ac.uk/271985/},
year = {2011},
date = {2011-01-01},
booktitle = {The Tenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011)},
pages = {5--12},
abstract = {Central to the vision of the smart grid is the deployment of smart meters that will allow autonomous software agents, representing the consumers, to optimise their use of devices and heating in the smart home while interacting with the grid. However, without some form of coordination, the population of agents may end up with overly-homogeneous optimised consumption patterns that may generate significant peaks in demand in the grid. These peaks, in turn, reduce the efficiency of the overall system, increase carbon emissions, and may even, in the worst case, cause blackouts. Hence, in this paper, we introduce a novel model of a Decentralised Demand Side Management (DDSM) mechanism that allows agents, by adapting the deferment of their loads based on grid prices, to coordinate in a decentralised manner. Specifically, using average UK consumption profiles for 26M homes, we demonstrate that, through an emergent coordination of the agents, the peak demand of domestic consumers in the grid can be reduced by up to 17% and carbon emissions by up to 6%. We also show that our DDSM mechanism is robust to the increasing electrification of heating in UK homes (i.e. it exhibits a similar efficiency).},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Central to the vision of the smart grid is the deployment of smart meters that will allow autonomous software agents, representing the consumers, to optimise their use of devices and heating in the smart home while interacting with the grid. However, without some form of coordination, the population of agents may end up with overly-homogeneous optimised consumption patterns that may generate significant peaks in demand in the grid. These peaks, in turn, reduce the efficiency of the overall system, increase carbon emissions, and may even, in the worst case, cause blackouts. Hence, in this paper, we introduce a novel model of a Decentralised Demand Side Management (DDSM) mechanism that allows agents, by adapting the deferment of their loads based on grid prices, to coordinate in a decentralised manner. Specifically, using average UK consumption profiles for 26M homes, we demonstrate that, through an emergent coordination of the agents, the peak demand of domestic consumers in the grid can be reduced by up to 17% and carbon emissions by up to 6%. We also show that our DDSM mechanism is robust to the increasing electrification of heating in UK homes (i.e. it exhibits a similar efficiency).
Stranders, Ruben; Ramchurn, Sarvapali; Shi, Bing; Jennings, Nick
CollabMap: Augmenting Maps using the Wisdom of Crowds Proceedings Article
In: Third Human Computation Workshop, 2011.
@inproceedings{eps272478,
title = {CollabMap: Augmenting Maps using the Wisdom of Crowds},
author = {Ruben Stranders and Sarvapali Ramchurn and Bing Shi and Nick Jennings},
url = {http://eprints.soton.ac.uk/272478/},
year = {2011},
date = {2011-01-01},
booktitle = {Third Human Computation Workshop},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Voice, Thomas; Vytelingum, Perukrishnen; Ramchurn, Sarvapali; Rogers, Alex; Jennings, Nick
Decentralised Control of Micro-Storage in the Smart Grid Proceedings Article
In: AAAI-11: Twenty-Fifth Conference on Artificial Intelligence, pp. 1421–1426, 2011, (Event Dates: August 7?11, 2011).
@inproceedings{eps272262,
title = {Decentralised Control of Micro-Storage in the Smart Grid},
author = {Thomas Voice and Perukrishnen Vytelingum and Sarvapali Ramchurn and Alex Rogers and Nick Jennings},
url = {http://eprints.soton.ac.uk/272262/},
year = {2011},
date = {2011-01-01},
booktitle = {AAAI-11: Twenty-Fifth Conference on Artificial Intelligence},
pages = {1421--1426},
abstract = {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.},
note = {Event Dates: August 7?11, 2011},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
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.
Vytelingum, Perukrishnen; Voice, Thomas; Ramchurn, Sarvapali; Rogers, Alex; Jennings, Nick
Theoretical and practical foundations of large-scale agent-based micro-storage in the smart grid Journal Article
In: Journal of Artificial Intelligence Research, vol. 42, pp. 765–813, 2011, (AAMAS 2010 iRobot Best Paper Award).
@article{eps272961,
title = {Theoretical and practical foundations of large-scale agent-based micro-storage in the smart grid},
author = {Perukrishnen Vytelingum and Thomas Voice and Sarvapali Ramchurn and Alex Rogers and Nick Jennings},
url = {http://eprints.soton.ac.uk/272961/},
year = {2011},
date = {2011-01-01},
journal = {Journal of Artificial Intelligence Research},
volume = {42},
pages = {765--813},
abstract = {In this paper, we present a novel decentralised management technique that allows electricity micro-storage devices, deployed within individual homes as part of a smart electricity grid, to converge to profitable and efficient behaviours. Specifically, we propose the use of software agents, residing on the users' smart meters, to automate and optimise the charging cycle of micro-storage devices in the home to minimise its costs, and we present a study of both the theoretical underpinnings and the implications of a practical solution, of using software agents for such micro-storage management. First, by formalising the strategic choice each agent makes in deciding when to charge its battery, we develop a game-theoretic framework within which we can analyse the competitive equilibria of an electricity grid populated by such agents and hence predict the best consumption profile for that population given their battery properties and individual load profiles. Our framework also allows us to compute theoretical bounds on the amount of storage that will be adopted by the population. Second, to analyse the practical implications of micro-storage deployments in the grid, we present a novel algorithm that each agent can use to optimise its battery storage profile in order to minimise its owner's costs. This algorithm uses a learning strategy that allows it to adapt as the price of electricity changes in real-time, and we show that the adoption of these strategies results in the system converging to the theoretical equilibria. Finally, we empirically evaluate the adoption of our micro-storage management technique within a complex setting, based on the UK electricity market, where agents may have widely varying load profiles, battery types, and learning rates. In this case, our approach yields savings of up to 14% in energy cost for an average consumer using a storage device with a capacity of less than 4.5 kWh and up to a 7% reduction in carbon emissions resulting from electricity generation (with only domestic consumers adopting micro-storage and, commercial and industrial consumers not changing their demand). Moreover, corroborating our theoretical bound, an equilibrium is shown to exist where no more than 48% of households would wish to own storage devices and where social welfare would also be improved (yielding overall annual savings of nearly pounds1.5B).},
note = {AAMAS 2010 iRobot Best Paper Award},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
In this paper, we present a novel decentralised management technique that allows electricity micro-storage devices, deployed within individual homes as part of a smart electricity grid, to converge to profitable and efficient behaviours. Specifically, we propose the use of software agents, residing on the users' smart meters, to automate and optimise the charging cycle of micro-storage devices in the home to minimise its costs, and we present a study of both the theoretical underpinnings and the implications of a practical solution, of using software agents for such micro-storage management. First, by formalising the strategic choice each agent makes in deciding when to charge its battery, we develop a game-theoretic framework within which we can analyse the competitive equilibria of an electricity grid populated by such agents and hence predict the best consumption profile for that population given their battery properties and individual load profiles. Our framework also allows us to compute theoretical bounds on the amount of storage that will be adopted by the population. Second, to analyse the practical implications of micro-storage deployments in the grid, we present a novel algorithm that each agent can use to optimise its battery storage profile in order to minimise its owner's costs. This algorithm uses a learning strategy that allows it to adapt as the price of electricity changes in real-time, and we show that the adoption of these strategies results in the system converging to the theoretical equilibria. Finally, we empirically evaluate the adoption of our micro-storage management technique within a complex setting, based on the UK electricity market, where agents may have widely varying load profiles, battery types, and learning rates. In this case, our approach yields savings of up to 14% in energy cost for an average consumer using a storage device with a capacity of less than 4.5 kWh and up to a 7% reduction in carbon emissions resulting from electricity generation (with only domestic consumers adopting micro-storage and, commercial and industrial consumers not changing their demand). Moreover, corroborating our theoretical bound, an equilibrium is shown to exist where no more than 48% of households would wish to own storage devices and where social welfare would also be improved (yielding overall annual savings of nearly pounds1.5B).
2010
Macarthur, Kathryn; Farinelli, Alessandro; Ramchurn, Sarvapali; Jennings, Nick
Efficient, Superstabilizing Decentralised Optimisation for Dynamic Task Allocation Environments Proceedings Article
In: Third International Workshop on: Optimisation in Multi-Agent Systems (OptMas) at the Ninth Joint Conference on Autonomous and Multi-Agent Systems, pp. 25–32, 2010, (Event Dates: 10 May 2010).
@inproceedings{eps268588,
title = {Efficient, Superstabilizing Decentralised Optimisation for Dynamic Task Allocation Environments},
author = {Kathryn Macarthur and Alessandro Farinelli and Sarvapali Ramchurn and Nick Jennings},
url = {http://eprints.soton.ac.uk/268588/},
year = {2010},
date = {2010-01-01},
booktitle = {Third International Workshop on: Optimisation in Multi-Agent Systems (OptMas) at the Ninth Joint Conference on Autonomous and Multi-Agent Systems},
pages = {25--32},
abstract = {Decentralised optimisation is a key issue for multi-agent systems, and while many solution techniques have been developed, few provide support for dynamic environments, which change over time, such as disaster management. Given this, in this paper, we present Bounded Fast Max Sum (BFMS): a novel, dynamic, superstabilizing algorithm which provides a bounded approximate solution to certain classes of distributed constraint optimisation problems. We achieve this by eliminating dependencies in the constraint functions, according to how much impact they have on the overall solution value. In more detail, we propose iGHS, which computes a maximum spanning tree on subsections of the constraint graph, in order to reduce communication and computation overheads. Given this, we empirically evaluate BFMS, which shows that BFMS reduces communication and computation done by Bounded Max Sum by up to 99%, while obtaining 60-88% of the optimal utility.},
note = {Event Dates: 10 May 2010},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Decentralised optimisation is a key issue for multi-agent systems, and while many solution techniques have been developed, few provide support for dynamic environments, which change over time, such as disaster management. Given this, in this paper, we present Bounded Fast Max Sum (BFMS): a novel, dynamic, superstabilizing algorithm which provides a bounded approximate solution to certain classes of distributed constraint optimisation problems. We achieve this by eliminating dependencies in the constraint functions, according to how much impact they have on the overall solution value. In more detail, we propose iGHS, which computes a maximum spanning tree on subsections of the constraint graph, in order to reduce communication and computation overheads. Given this, we empirically evaluate BFMS, which shows that BFMS reduces communication and computation done by Bounded Max Sum by up to 99%, while obtaining 60-88% of the optimal utility.
Ramchurn, S. D.; Polukarov, Mariya; Farinelli, Alessandro; Jennings, Nick; Trong, Cuong
Coalition Formation with Spatial and Temporal Constraints Proceedings Article
In: International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2010), pp. 1181–1188, 2010, (Event Dates: May 2010).
@inproceedings{eps268497,
title = {Coalition Formation with Spatial and Temporal Constraints},
author = {S. D. Ramchurn and Mariya Polukarov and Alessandro Farinelli and Nick Jennings and Cuong Trong},
url = {http://eprints.soton.ac.uk/268497/},
year = {2010},
date = {2010-01-01},
booktitle = {International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2010)},
pages = {1181--1188},
abstract = {The coordination of emergency responders and robots to undertake a number of tasks in disaster scenarios is a grand challenge for multi-agent systems. Central to this endeavour is the problem of forming the best teams (coalitions) of responders to perform the various tasks in the area where the disaster has struck. Moreover, these teams may have to form, disband, and reform in different areas of the disaster region. This is because in most cases there will be more tasks than agents. Hence, agents need to schedule themselves to attempt each task in turn. Second, the tasks themselves can be very complex: requiring the agents to work on them for different lengths of time and having deadlines by when they need to be completed. The problem is complicated still further when different coalitions perform tasks with different levels of efficiency. Given all these facets, we define this as The Coalition Formation with Spatial and Temporal constraints problem (CFSTP).We show that this problem is NP-hard--in particular, it contains the wellknown complex combinatorial problem of Team Orienteering as a special case. Based on this, we design a Mixed Integer Program to optimally solve small-scale instances of the CFSTP and develop new anytime heuristics that can, on average, complete 97% of the tasks for large problems (20 agents and 300 tasks). In so doing, our solutions represent the first results for CFSTP.},
note = {Event Dates: May 2010},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
The coordination of emergency responders and robots to undertake a number of tasks in disaster scenarios is a grand challenge for multi-agent systems. Central to this endeavour is the problem of forming the best teams (coalitions) of responders to perform the various tasks in the area where the disaster has struck. Moreover, these teams may have to form, disband, and reform in different areas of the disaster region. This is because in most cases there will be more tasks than agents. Hence, agents need to schedule themselves to attempt each task in turn. Second, the tasks themselves can be very complex: requiring the agents to work on them for different lengths of time and having deadlines by when they need to be completed. The problem is complicated still further when different coalitions perform tasks with different levels of efficiency. Given all these facets, we define this as The Coalition Formation with Spatial and Temporal constraints problem (CFSTP).We show that this problem is NP-hard--in particular, it contains the wellknown complex combinatorial problem of Team Orienteering as a special case. Based on this, we design a Mixed Integer Program to optimally solve small-scale instances of the CFSTP and develop new anytime heuristics that can, on average, complete 97% of the tasks for large problems (20 agents and 300 tasks). In so doing, our solutions represent the first results for CFSTP.
Ramchurn, Sarvapali; Farinelli, Alessandro; Macarthur, Kathryn; Polukarov, Mariya; Jennings, Nick
Decentralised Coordination in RoboCup Rescue Journal Article
In: The Computer Journal, vol. 53, no. 9, pp. 1–15, 2010.
@article{eps268499,
title = {Decentralised Coordination in RoboCup Rescue},
author = {Sarvapali Ramchurn and Alessandro Farinelli and Kathryn Macarthur and Mariya Polukarov and Nick Jennings},
url = {http://eprints.soton.ac.uk/268499/},
year = {2010},
date = {2010-01-01},
journal = {The Computer Journal},
volume = {53},
number = {9},
pages = {1--15},
publisher = {Oxford Journals},
abstract = {Emergency responders are faced with a number of significant challenges when managing major disasters. First, the number of rescue tasks posed is usually larger than the number of responders (or agents) and the resources available to them. Second, each task is likely to require a different level of effort in order to be completed by its deadline. Third, new tasks may continually appear or disappear from the environment, thus requiring the responders to quickly recompute their allocation of resources. Fourth, forming teams or coalitions of multiple agents from different agencies is vital since no single agency will have all the resources needed to save victims, unblock roads, and extinguish the ?res which might erupt in the disaster space. Given this, coalitions have to be efficiently selected and scheduled to work across the disaster space so as to maximise the number of lives and the portion of the infrastructure saved. In particular, it is important that the selection of such coalitions should be performed in a decentralised fashion in order to avoid a single point of failure in the system. Moreover, it is critical that responders communicate only locally given they are likely to have limited battery power or minimal access to long range communication devices. Against this background, we provide a novel decentralised solution to the coalition formation process that pervades disaster management. More specifically, we model the emergency management scenario defined in the RoboCup Rescue disaster simulation platform as a Coalition Formation with Spatial and Temporal constraints (CFST) problem where agents form coalitions in order to complete tasks, each with different demands. In order to design a decentralised algorithm for CFST we formulate it as a Distributed Constraint Optimisation problem and show how to solve it using the state-of-the-art Max-Sum algorithm that provides a completely decentralised message-passing solution. We then provide a novel algorithm (F-Max-Sum) that avoids sending redundant messages and efficiently adapts to changes in the environment. In empirical evaluations, our algorithm is shown to generate better solutions than other decentralised algorithms used for this problem.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Emergency responders are faced with a number of significant challenges when managing major disasters. First, the number of rescue tasks posed is usually larger than the number of responders (or agents) and the resources available to them. Second, each task is likely to require a different level of effort in order to be completed by its deadline. Third, new tasks may continually appear or disappear from the environment, thus requiring the responders to quickly recompute their allocation of resources. Fourth, forming teams or coalitions of multiple agents from different agencies is vital since no single agency will have all the resources needed to save victims, unblock roads, and extinguish the ?res which might erupt in the disaster space. Given this, coalitions have to be efficiently selected and scheduled to work across the disaster space so as to maximise the number of lives and the portion of the infrastructure saved. In particular, it is important that the selection of such coalitions should be performed in a decentralised fashion in order to avoid a single point of failure in the system. Moreover, it is critical that responders communicate only locally given they are likely to have limited battery power or minimal access to long range communication devices. Against this background, we provide a novel decentralised solution to the coalition formation process that pervades disaster management. More specifically, we model the emergency management scenario defined in the RoboCup Rescue disaster simulation platform as a Coalition Formation with Spatial and Temporal constraints (CFST) problem where agents form coalitions in order to complete tasks, each with different demands. In order to design a decentralised algorithm for CFST we formulate it as a Distributed Constraint Optimisation problem and show how to solve it using the state-of-the-art Max-Sum algorithm that provides a completely decentralised message-passing solution. We then provide a novel algorithm (F-Max-Sum) that avoids sending redundant messages and efficiently adapts to changes in the environment. In empirical evaluations, our algorithm is shown to generate better solutions than other decentralised algorithms used for this problem.
Vytelingum, Perukrishnen; Ramchurn, Sarvapali D.; Voice, Thomas D.; Rogers, Alex; Jennings, Nicholas R.
Trading agents for the smart electricity grid Proceedings Article
In: The Ninth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010), pp. 897–904, 2010, (Event Dates: May 10-14, 2010).
@inproceedings{eps268361,
title = {Trading agents for the smart electricity grid},
author = {Perukrishnen Vytelingum and Sarvapali D. Ramchurn and Thomas D. Voice and Alex Rogers and Nicholas R. Jennings},
url = {http://eprints.soton.ac.uk/268361/},
year = {2010},
date = {2010-01-01},
booktitle = {The Ninth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010)},
pages = {897--904},
abstract = {The vision of the Smart Grid includes the creation of intelligent electricity supply networks to allow efficient use of energy resources, reduce carbon emissions and are robust to failures. One of the key assumptions underlying this vision is that it will be possible to manage the trading of electricity between homes and micro-grids while coping with the inherent real-time dynamism in electricity demand and supply. The management of these trades needs to take into account the fact that most, if not all, of the actors in the system are self-interested and transmission line capacities are constrained. Against this background, we develop and evaluate a novel market-based mechanism and novel trading strategies for the Smart Grid. Our mechanism is based on the Continuous Double Auction (CDA) and automatically manages the congestion within the system by pricing the flow of electricity. We also introduce mechanisms to ensure the system can cope with unforeseen demand or increased supply capacity in real time. Finally, we develop new strategies that we show achieve high market efficiency (typically over 90%).},
note = {Event Dates: May 10-14, 2010},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
The vision of the Smart Grid includes the creation of intelligent electricity supply networks to allow efficient use of energy resources, reduce carbon emissions and are robust to failures. One of the key assumptions underlying this vision is that it will be possible to manage the trading of electricity between homes and micro-grids while coping with the inherent real-time dynamism in electricity demand and supply. The management of these trades needs to take into account the fact that most, if not all, of the actors in the system are self-interested and transmission line capacities are constrained. Against this background, we develop and evaluate a novel market-based mechanism and novel trading strategies for the Smart Grid. Our mechanism is based on the Continuous Double Auction (CDA) and automatically manages the congestion within the system by pricing the flow of electricity. We also introduce mechanisms to ensure the system can cope with unforeseen demand or increased supply capacity in real time. Finally, we develop new strategies that we show achieve high market efficiency (typically over 90%).
Vytelingum, Perukrishnen; Voice, Thomas D.; Ramchurn, Sarvapali D.; Rogers, Alex; Jennings, Nicholas R.
Agent-Based Micro-Storage Management for the Smart Grid Proceedings Article
In: The Ninth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010) - Won the Best Paper Award, pp. 39–46, 2010, (Winner of the Best Paper Award Event Dates: May 10-14, 2010).
@inproceedings{eps268360,
title = {Agent-Based Micro-Storage Management for the Smart Grid},
author = {Perukrishnen Vytelingum and Thomas D. Voice and Sarvapali D. Ramchurn and Alex Rogers and Nicholas R. Jennings},
url = {http://eprints.soton.ac.uk/268360/},
year = {2010},
date = {2010-01-01},
booktitle = {The Ninth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010) - Won the Best Paper Award},
pages = {39--46},
abstract = {The use of energy storage devices in homes has been advocated as one of the main ways of saving energy and reducing the reliance on fossil fuels in the future Smart Grid. However, if micro-storage devices are all charged at the same time using power from the electricity grid, it means a higher demand and, hence, more generation capacity, more carbon emissions, and, in the worst case, breaking down the system due to over-demand. To alleviate such issues, in this paper, we present a novel agent-based micro-storage management technique that allows all (individually-owned) storage devices in the system to converge to profitable, efficient behaviour. Specifically, we provide a general framework within which to analyse the Nash equilibrium of an electricity grid and devise new agent-based storage learning strategies that adapt to market conditions. Taken altogether, our solution shows that, specifically, in the UK electricity market, it is possible to achieve savings of up to 13% on average for a consumer on his electricity bill with a storage device of 4 kWh. Moreover, we show that there exists an equilibrium where only 38% of UK households would own storage devices and where social welfare would be also maximised (with an overall annual savings of nearly GBP 1.5B at that equilibrium).},
note = {Winner of the Best Paper Award Event Dates: May 10-14, 2010},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
The use of energy storage devices in homes has been advocated as one of the main ways of saving energy and reducing the reliance on fossil fuels in the future Smart Grid. However, if micro-storage devices are all charged at the same time using power from the electricity grid, it means a higher demand and, hence, more generation capacity, more carbon emissions, and, in the worst case, breaking down the system due to over-demand. To alleviate such issues, in this paper, we present a novel agent-based micro-storage management technique that allows all (individually-owned) storage devices in the system to converge to profitable, efficient behaviour. Specifically, we provide a general framework within which to analyse the Nash equilibrium of an electricity grid and devise new agent-based storage learning strategies that adapt to market conditions. Taken altogether, our solution shows that, specifically, in the UK electricity market, it is possible to achieve savings of up to 13% on average for a consumer on his electricity bill with a storage device of 4 kWh. Moreover, we show that there exists an equilibrium where only 38% of UK households would own storage devices and where social welfare would be also maximised (with an overall annual savings of nearly GBP 1.5B at that equilibrium).
2009
Rahwan, Talal; Ramchurn, Sarvapali; Jennings, Nicholas; Giovannucci, Andrea
An anytime algorithm for optimal coalition structure generation Journal Article
In: Journal of Artificial Intelligence Research, vol. 34, pp. 521–567, 2009.
@article{eps267179,
title = {An anytime algorithm for optimal coalition structure generation},
author = {Talal Rahwan and Sarvapali Ramchurn and Nicholas Jennings and Andrea Giovannucci},
url = {http://eprints.soton.ac.uk/267179/},
year = {2009},
date = {2009-01-01},
journal = {Journal of Artificial Intelligence Research},
volume = {34},
pages = {521--567},
abstract = {Coalition formation is a fundamental type of interaction that involves the creation of coherent groupings of distinct, autonomous, agents in order to efficiently achieve their individual or collective goals. Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining which of the many possible coalitions to form in order to achieve some goal. This usually requires calculating a value for every possible coalition, known as the coalition value, which indicates how beneficial that coalition would be if it was formed. Once these values are calculated, the agents usually need to find a combination of coalitions, in which every agent belongs to exactly one coalition, and by which the overall outcome of the system is maximized. However, this coalition structure generation problem is extremely challenging due to the number of possible solutions that need to be examined, which grows exponentially with the number of agents involved. To date, therefore, many algorithms have been proposed to solve this problem using different techniques--ranging from dynamic programming, to integer programming, to stochastic search -- all of which suffer from major limitations relating to execution time, solution quality, and memory requirements. With this in mind, we develop an anytime algorithm to solve the coalition structure generation problem. Specifically, the algorithm uses a novel representation of the search space, which partitions the space of possible solutions into sub-spaces such that it is possible to compute upper and lower bounds on the values of the best coalition structures in them. These bounds are then used to identify the sub-spaces that have no potential of containing the optimal solution so that they can be pruned. The algorithm, then, searches through the remaining sub-spaces very efficiently using a branch-and-bound technique to avoid examining all the solutions within the searched subspace(s). In this setting, we prove that our algorithm enumerates all coalition structures efficiently by avoiding redundant and invalid solutions automatically. Moreover, in order to effectively test our algorithm we develop a new type of input distribution which allows us to generate more reliable benchmarks compared to the input distributions previously used in the field. Given this new distribution, we show that for 27 agents our algorithm is able to find solutions that are optimal in 0:175% of the time required by the fastest available algorithm in the literature. The algorithm is anytime, and if interrupted before it would have normally terminated, it can still provide a solution that is guaranteed to be within a bound from the optimal one. Moreover, the guarantees we provide on the quality of the solution are significantly better than those provided by the previous state of the art algorithms designed for this purpose. For example, for the worst case distribution given 25 agents, our algorithm is able to find a 90% efficient solution in around 10% of time it takes to find the optimal solution.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Coalition formation is a fundamental type of interaction that involves the creation of coherent groupings of distinct, autonomous, agents in order to efficiently achieve their individual or collective goals. Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining which of the many possible coalitions to form in order to achieve some goal. This usually requires calculating a value for every possible coalition, known as the coalition value, which indicates how beneficial that coalition would be if it was formed. Once these values are calculated, the agents usually need to find a combination of coalitions, in which every agent belongs to exactly one coalition, and by which the overall outcome of the system is maximized. However, this coalition structure generation problem is extremely challenging due to the number of possible solutions that need to be examined, which grows exponentially with the number of agents involved. To date, therefore, many algorithms have been proposed to solve this problem using different techniques--ranging from dynamic programming, to integer programming, to stochastic search -- all of which suffer from major limitations relating to execution time, solution quality, and memory requirements. With this in mind, we develop an anytime algorithm to solve the coalition structure generation problem. Specifically, the algorithm uses a novel representation of the search space, which partitions the space of possible solutions into sub-spaces such that it is possible to compute upper and lower bounds on the values of the best coalition structures in them. These bounds are then used to identify the sub-spaces that have no potential of containing the optimal solution so that they can be pruned. The algorithm, then, searches through the remaining sub-spaces very efficiently using a branch-and-bound technique to avoid examining all the solutions within the searched subspace(s). In this setting, we prove that our algorithm enumerates all coalition structures efficiently by avoiding redundant and invalid solutions automatically. Moreover, in order to effectively test our algorithm we develop a new type of input distribution which allows us to generate more reliable benchmarks compared to the input distributions previously used in the field. Given this new distribution, we show that for 27 agents our algorithm is able to find solutions that are optimal in 0:175% of the time required by the fastest available algorithm in the literature. The algorithm is anytime, and if interrupted before it would have normally terminated, it can still provide a solution that is guaranteed to be within a bound from the optimal one. Moreover, the guarantees we provide on the quality of the solution are significantly better than those provided by the previous state of the art algorithms designed for this purpose. For example, for the worst case distribution given 25 agents, our algorithm is able to find a 90% efficient solution in around 10% of time it takes to find the optimal solution.
Ramchurn, Sarvapali D.; Mezzetti, Claudio; Giovannucci, Andrea; Rodriguez, Juan A.; Dash, Rajdeep K.; Jennings, Nicholas R.
Trust-based mechanisms for robust and efficient task allocation in the presence of execution uncertainty Journal Article
In: Journal of Artificial Intelligence Research, vol. 35, pp. 1–41, 2009.
@article{eps267288,
title = {Trust-based mechanisms for robust and efficient task allocation in the presence of execution uncertainty},
author = {Sarvapali D. Ramchurn and Claudio Mezzetti and Andrea Giovannucci and Juan A. Rodriguez and Rajdeep K. Dash and Nicholas R. Jennings},
url = {http://eprints.soton.ac.uk/267288/},
year = {2009},
date = {2009-01-01},
journal = {Journal of Artificial Intelligence Research},
volume = {35},
pages = {1--41},
abstract = {Vickrey-Clarke-Groves (VCG) mechanisms are often used to allocate tasks to selfish and rational agents. VCG mechanisms are incentive-compatible, direct mechanisms that are efficient (i.e. maximise social utility) and individually rational (i.e. agents prefer to join rather than opt out). However, an important assumption of these mechanisms is that the agents will always successfully complete their allocated tasks. Clearly, this assumption is unrealistic in many real-world applications where agents can, and often do, fail in their endeavours. Moreover, whether an agent is deemed to have failed may be perceived differently by different agents. Such subjective perceptions about an agent's probability of succeeding at a given task are often captured and reasoned about using the notion of trust. Given this background, in this paper we investigate the design of novel mechanisms that take into account the trust between agents when allocating tasks. Specifically, we develop a new class of mechanisms, called trust-based mechanisms, that can take into account multiple subjective measures of the probability of an agent succeeding at a given task and produce allocations that maximise social utility, whilst ensuring that no agent obtains a negative utility. We then show that such mechanisms pose a challenging new combinatorial optimisation problem (that is NP-complete), devise a novel representation for solving the problem, and develop an effective integer programming solution (that can solve instances with about 2x10^ 5 possible allocations in 40 seconds).},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Vickrey-Clarke-Groves (VCG) mechanisms are often used to allocate tasks to selfish and rational agents. VCG mechanisms are incentive-compatible, direct mechanisms that are efficient (i.e. maximise social utility) and individually rational (i.e. agents prefer to join rather than opt out). However, an important assumption of these mechanisms is that the agents will always successfully complete their allocated tasks. Clearly, this assumption is unrealistic in many real-world applications where agents can, and often do, fail in their endeavours. Moreover, whether an agent is deemed to have failed may be perceived differently by different agents. Such subjective perceptions about an agent's probability of succeeding at a given task are often captured and reasoned about using the notion of trust. Given this background, in this paper we investigate the design of novel mechanisms that take into account the trust between agents when allocating tasks. Specifically, we develop a new class of mechanisms, called trust-based mechanisms, that can take into account multiple subjective measures of the probability of an agent succeeding at a given task and produce allocations that maximise social utility, whilst ensuring that no agent obtains a negative utility. We then show that such mechanisms pose a challenging new combinatorial optimisation problem (that is NP-complete), devise a novel representation for solving the problem, and develop an effective integer programming solution (that can solve instances with about 2x10^ 5 possible allocations in 40 seconds).
van Valkenhoef, Gert; Ramchurn, Sarvapali D.; Vytelingum, Perukrishnen; Jennings, Nicholas R.; Verbrugge, Rinek
Continuous double auctions with execution uncertainty Proceedings Article
In: Workshop on Trading Agent Design and Analysis (TADA-09), 2009.
@inproceedings{eps267329,
title = {Continuous double auctions with execution uncertainty},
author = {Gert van Valkenhoef and Sarvapali D. Ramchurn and Perukrishnen Vytelingum and Nicholas R. Jennings and Rinek Verbrugge},
url = {http://eprints.soton.ac.uk/267329/},
year = {2009},
date = {2009-01-01},
booktitle = {Workshop on Trading Agent Design and Analysis (TADA-09)},
abstract = {We propose a novel variant of the Continuous Double Auction (CDA), the Trust-based CDA (T-CDA), which we demonstrate to be robust to execution uncertainty. This is desirable in a setting where traders may fail to deliver the goods, services or payments they have promised. Specifically, the TCDA provides a mechanism that allows agents to commit to trades they believe will maximize their expected utility. In this paper, we consider agents that use their trust in other agents to estimate the expected utility of a transaction. We empirically evaluate the mechanism, both against the optimal solution given perfect and complete information and against the standard CDA.We show that the T-CDA consistently outperforms the traditional CDA as execution uncertainty increases in the system. Furthermore, we investigate the robustness of the mechanism to unreliable trust information and find that performance degrades gracefully as information quality decreases.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
We propose a novel variant of the Continuous Double Auction (CDA), the Trust-based CDA (T-CDA), which we demonstrate to be robust to execution uncertainty. This is desirable in a setting where traders may fail to deliver the goods, services or payments they have promised. Specifically, the TCDA provides a mechanism that allows agents to commit to trades they believe will maximize their expected utility. In this paper, we consider agents that use their trust in other agents to estimate the expected utility of a transaction. We empirically evaluate the mechanism, both against the optimal solution given perfect and complete information and against the standard CDA.We show that the T-CDA consistently outperforms the traditional CDA as execution uncertainty increases in the system. Furthermore, we investigate the robustness of the mechanism to unreliable trust information and find that performance degrades gracefully as information quality decreases.
2008
Adams, Niall; Field, Martin; Gelenbe, Erol; Hand, David; Jennings, Nicholas; Leslie, David; Nicholson, David; Ramchurn, Sarvapali; Rogers, Alex
Intelligent Agents for Disaster Management Proceedings Article
In: Proceedings of the IARP/EURON Workshop on Robotics for Risky Interventions and Environmental Surveillance (RISE), 2008.
@inproceedings{eps272011,
title = {Intelligent Agents for Disaster Management},
author = {Niall Adams and Martin Field and Erol Gelenbe and David Hand and Nicholas Jennings and David Leslie and David Nicholson and Sarvapali Ramchurn and Alex Rogers},
url = {http://eprints.soton.ac.uk/272011/},
year = {2008},
date = {2008-01-01},
booktitle = {Proceedings of the IARP/EURON Workshop on Robotics for Risky Interventions and Environmental Surveillance (RISE)},
abstract = {ALADDIN [1] is a multi-disciplinary project that is developing novel techniques, architectures, and mechanisms for multi-agent systems in uncertain and dynamic environments. The application focus of the project is disaster management. Research within a number of themes is being pursued and this is considering different aspects of the interaction between autonomous agents and the decentralised system architectures that support those interactions. The aim of the research is to contribute to building more robust multi-agent systems for future applications in disaster management and other similar domains.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
ALADDIN [1] is a multi-disciplinary project that is developing novel techniques, architectures, and mechanisms for multi-agent systems in uncertain and dynamic environments. The application focus of the project is disaster management. Research within a number of themes is being pursued and this is considering different aspects of the interaction between autonomous agents and the decentralised system architectures that support those interactions. The aim of the research is to contribute to building more robust multi-agent systems for future applications in disaster management and other similar domains.
Osborne, Michael A; Rogers, Alex; Ramchurn, Sarvapali; Roberts, Stephen J; Jennings, N. R.
Towards Real-Time Information Processing of Sensor Network Data using Computationally Efficient Multi-output Gaussian Processes Proceedings Article
In: International Conference on Information Processing in Sensor Networks (IPSN 2008), pp. 109–120, 2008, (Event Dates: April 2008).
@inproceedings{eps265122,
title = {Towards Real-Time Information Processing of Sensor Network Data using Computationally Efficient Multi-output Gaussian Processes},
author = {Michael A Osborne and Alex Rogers and Sarvapali Ramchurn and Stephen J Roberts and N. R. Jennings},
url = {http://eprints.soton.ac.uk/265122/},
year = {2008},
date = {2008-01-01},
booktitle = {International Conference on Information Processing in Sensor Networks (IPSN 2008)},
pages = {109--120},
abstract = {In this paper, we describe a novel, computationally efficient algorithm that facilitates the autonomous acquisition of readings from sensor networks (deciding when and which sensor to acquire readings from at any time), and which can, with minimal domain knowledge, perform a range of information processing tasks including modelling the accuracy of the sensor readings, predicting the value of missing sensor readings, and predicting how the monitored environmental variables will evolve into the future. Our motivating scenario is the need to provide situational awareness support to first responders at the scene of a large scale incident, and to this end, we describe a novel iterative formulation of a multi-output Gaussian process that can build and exploit a probabilistic model of the environmental variables being measured (including the correlations and delays that exist between them). We validate our approach using data collected from a network of weather sensors located on the south coast of England.},
note = {Event Dates: April 2008},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
In this paper, we describe a novel, computationally efficient algorithm that facilitates the autonomous acquisition of readings from sensor networks (deciding when and which sensor to acquire readings from at any time), and which can, with minimal domain knowledge, perform a range of information processing tasks including modelling the accuracy of the sensor readings, predicting the value of missing sensor readings, and predicting how the monitored environmental variables will evolve into the future. Our motivating scenario is the need to provide situational awareness support to first responders at the scene of a large scale incident, and to this end, we describe a novel iterative formulation of a multi-output Gaussian process that can build and exploit a probabilistic model of the environmental variables being measured (including the correlations and delays that exist between them). We validate our approach using data collected from a network of weather sensors located on the south coast of England.
Rogers, Alex; Osborne, Michael A; Ramchurn, Sarvapali; Roberts, Stephen J; Jennings, N. R.
Information Agents for Pervasive Sensor Networks Proceedings Article
In: Sixth Annual IEEE International Conference on Pervasive Computing and Communications (PerCom 2008), pp. 294–299, 2008, (Event Dates: March 2008).
@inproceedings{eps264967,
title = {Information Agents for Pervasive Sensor Networks},
author = {Alex Rogers and Michael A Osborne and Sarvapali Ramchurn and Stephen J Roberts and N. R. Jennings},
url = {http://eprints.soton.ac.uk/264967/},
year = {2008},
date = {2008-01-01},
booktitle = {Sixth Annual IEEE International Conference on Pervasive Computing and Communications (PerCom 2008)},
pages = {294--299},
abstract = {In this paper, we describe an information agent, that resides on a mobile computer or personal digital assistant (PDA), that can autonomously acquire sensor readings from pervasive sensor networks (deciding when and which sensor to acquire readings from at any time). Moreover, it can perform a range of information processing tasks including modelling the accuracy of the sensor readings, predicting the value of missing sensor readings, and predicting how the monitored environmental parameters will evolve into the future. Our motivating scenario is the need to provide situational awareness support to first responders at the scene of a large scale incident, and we describe how we use an iterative formulation of a multi-output Gaussian process to build a probabilistic model of the environmental parameters being measured by local sensors, and the correlations and delays that exist between them. We validate our approach using data collected from a network of weather sensors located on the south coast of England.},
note = {Event Dates: March 2008},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
In this paper, we describe an information agent, that resides on a mobile computer or personal digital assistant (PDA), that can autonomously acquire sensor readings from pervasive sensor networks (deciding when and which sensor to acquire readings from at any time). Moreover, it can perform a range of information processing tasks including modelling the accuracy of the sensor readings, predicting the value of missing sensor readings, and predicting how the monitored environmental parameters will evolve into the future. Our motivating scenario is the need to provide situational awareness support to first responders at the scene of a large scale incident, and we describe how we use an iterative formulation of a multi-output Gaussian process to build a probabilistic model of the environmental parameters being measured by local sensors, and the correlations and delays that exist between them. We validate our approach using data collected from a network of weather sensors located on the south coast of England.
2007
Fredrik Espinoza,; Roure, David De; Hamfors, Ola; Hinz, Lucas; Holmberg, Jesper; Jansson, Carl-Gustaf; Jennings, Nick; Luck, Mike; L"onnqvist, Peter; Ramchurn, Sarvapali; Sandin, Anna; Thompson, Mark; Bylund, Markus
Intrusiveness Management for Focused, Efficient, and Enjoyable Activities Book Section
In: The Disappearing Computer: Interaction Design, System Infrastructures and Applications for Smart Environments, pp. 143–160, Springer, 2007.
@incollection{eps265985,
title = {Intrusiveness Management for Focused, Efficient, and Enjoyable Activities},
author = {Fredrik Espinoza, and David De Roure and Ola Hamfors and Lucas Hinz and Jesper Holmberg and Carl-Gustaf Jansson and Nick Jennings and Mike Luck and Peter L"onnqvist and Sarvapali Ramchurn and Anna Sandin and Mark Thompson and Markus Bylund},
url = {http://eprints.soton.ac.uk/265985/},
year = {2007},
date = {2007-01-01},
booktitle = {The Disappearing Computer: Interaction Design, System Infrastructures and Applications for Smart Environments},
pages = {143--160},
publisher = {Springer},
keywords = {},
pubstate = {published},
tppubtype = {incollection}
}
Rahwan, T.; Ramchurn, S. D.; Dang, V. D.; Jennings, N. R.
Near-optimal anytime coalition structure generation Proceedings Article
In: 20th International Joint Conference on Artificial Intelligence (IJCAI), pp. 2365–2371, 2007.
@inproceedings{eps263074,
title = {Near-optimal anytime coalition structure generation},
author = {T. Rahwan and S.D. Ramchurn and V.D. Dang and N. R. Jennings},
url = {http://eprints.soton.ac.uk/263074/},
year = {2007},
date = {2007-01-01},
booktitle = {20th International Joint Conference on Artificial Intelligence (IJCAI)},
pages = {2365--2371},
abstract = {Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining the best set of agents that should participate in a given team. To this end, in this paper, we present a novel, anytime algorithms designed for this purpose. Our algorithm can generate solutions that either have a tight bound from the optimal or are optimal (depending on the objective) and works by partitioning the space in terms of a small set of elements that represent structures which contain coalitions of particular sizes. It then performs an online heuristic search that prunes the space and only considers valid and non-redundant coalition structures. We empirically show that we are able to find solutions that are, in the worst case, 99% efficient in 0.0043% of the time to find the optimal value by the state of the art dynamic programming (DP) algorithm (for 20 agents), using 33% less memory.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining the best set of agents that should participate in a given team. To this end, in this paper, we present a novel, anytime algorithms designed for this purpose. Our algorithm can generate solutions that either have a tight bound from the optimal or are optimal (depending on the objective) and works by partitioning the space in terms of a small set of elements that represent structures which contain coalitions of particular sizes. It then performs an online heuristic search that prunes the space and only considers valid and non-redundant coalition structures. We empirically show that we are able to find solutions that are, in the worst case, 99% efficient in 0.0043% of the time to find the optimal value by the state of the art dynamic programming (DP) algorithm (for 20 agents), using 33% less memory.
Rahwan, Talal; Ramchurn, Sarvapali D.; Dang, Viet D.; Giovannucci, Andrea; Jennings, N. R.
Anytime Optimal Coalition Structure Generation Proceedings Article
In: 22nd Conference on Artificial Intelligence (AAAI), pp. 1184–1190, 2007.
@inproceedings{eps263433,
title = {Anytime Optimal Coalition Structure Generation},
author = {Talal Rahwan and Sarvapali D. Ramchurn and Viet D. Dang and Andrea Giovannucci and N. R. Jennings},
url = {http://eprints.soton.ac.uk/263433/},
year = {2007},
date = {2007-01-01},
booktitle = {22nd Conference on Artificial Intelligence (AAAI)},
pages = {1184--1190},
abstract = {Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining the best groups of agents to select to achieve some goal. To this end, in this paper, we present a novel, optimal anytime algorithm for this coalition structure generation problem that is significantly faster than previous algorithms designed for this purpose. Specifically, our algorithm can generate solutions by partitioning the space of all potential coalitions into sub-spaces that contain coalition structures that are similar, according to some criterion, such that these sub-spaces can be pruned by identifying their bounds. Using this representation, the algorithm then searches through only valid and unique coalition structures and selects the best among them using a branch-and-bound technique. We empirically show that we are able to find solutions that are optimal in 0.082% of the time taken by the state of the art dynamic programming algorithm (for 27 agents) using much less memory (O(2^ n) instead of O(3^ n) for the set of n agents). Moreover, our algorithm is the first to be able to solve the coalition structure generation problem for numbers of agents bigger than 27 in reasonable time (less than 90 minutes for 27 agents as opposed to around 2 months for the best previous solution).},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining the best groups of agents to select to achieve some goal. To this end, in this paper, we present a novel, optimal anytime algorithm for this coalition structure generation problem that is significantly faster than previous algorithms designed for this purpose. Specifically, our algorithm can generate solutions by partitioning the space of all potential coalitions into sub-spaces that contain coalition structures that are similar, according to some criterion, such that these sub-spaces can be pruned by identifying their bounds. Using this representation, the algorithm then searches through only valid and unique coalition structures and selects the best among them using a branch-and-bound technique. We empirically show that we are able to find solutions that are optimal in 0.082% of the time taken by the state of the art dynamic programming algorithm (for 27 agents) using much less memory (O(2^ n) instead of O(3^ n) for the set of n agents). Moreover, our algorithm is the first to be able to solve the coalition structure generation problem for numbers of agents bigger than 27 in reasonable time (less than 90 minutes for 27 agents as opposed to around 2 months for the best previous solution).
Ramchurn, S. D.; Sierra, C.; Godo, L.; Jennings, N. R.
Negotiating using rewards. Journal Article
In: Artificial Intelligence Journal., vol. 171, no. 10-15, pp. 805–837, 2007.
@article{eps264225,
title = {Negotiating using rewards.},
author = {S.D. Ramchurn and C. Sierra and L. Godo and N. R. Jennings},
url = {http://eprints.soton.ac.uk/264225/},
year = {2007},
date = {2007-01-01},
journal = {Artificial Intelligence Journal.},
volume = {171},
number = {10-15},
pages = {805--837},
abstract = {Negotiation is a fundamental interaction mechanism in multi-agent systems because it allows self-interested agents to come to mutually beneficial agreements and partition resources efficiently and effectively. Now, in many situations, the agents need to negotiate with one another many times and so developing strategies that are effective over repeated interactions is an important challenge. Against this background, a growing body of work has examined the use of Persuasive Negotiation (PN), which involves negotiating using rhetorical arguments (such as threats, rewards, or appeals), in trying to convince an opponent to accept a given offer. Such mechanisms are especially suited to repeated encounters because they allow agents to influence the outcomes of future negotiations, while negotiating a deal in the present one, with the aim of producing results that are beneficial to both parties. To this end, in this paper, we develop a comprehensive PN mechanism for repeated interactions that makes use of rewards that can be asked for or given to. Our mechanism consists of two parts. First, a novel protocol that structures the interaction by capturing the commitments that agents incur when using rewards. Second, a new reward generation algorithm that constructs promises of rewards in future interactions as a means of permitting agents to reach better agreements, in a shorter time, in the present encounter. We then go on to develop a specific negotiation tactic, based on this reward generation algorithm, and show that it can achieve significantly better outcomes than existing benchmark tactics that do not use such inducements. Specifically, we show, via empirical evaluation in a Multi-Move Prisoners? dilemma setting, that our tactic can lead to a 26% improvement in the utility of deals that are made and that 21 times fewer messages need to be exchanged in order to achieve this.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Negotiation is a fundamental interaction mechanism in multi-agent systems because it allows self-interested agents to come to mutually beneficial agreements and partition resources efficiently and effectively. Now, in many situations, the agents need to negotiate with one another many times and so developing strategies that are effective over repeated interactions is an important challenge. Against this background, a growing body of work has examined the use of Persuasive Negotiation (PN), which involves negotiating using rhetorical arguments (such as threats, rewards, or appeals), in trying to convince an opponent to accept a given offer. Such mechanisms are especially suited to repeated encounters because they allow agents to influence the outcomes of future negotiations, while negotiating a deal in the present one, with the aim of producing results that are beneficial to both parties. To this end, in this paper, we develop a comprehensive PN mechanism for repeated interactions that makes use of rewards that can be asked for or given to. Our mechanism consists of two parts. First, a novel protocol that structures the interaction by capturing the commitments that agents incur when using rewards. Second, a new reward generation algorithm that constructs promises of rewards in future interactions as a means of permitting agents to reach better agreements, in a shorter time, in the present encounter. We then go on to develop a specific negotiation tactic, based on this reward generation algorithm, and show that it can achieve significantly better outcomes than existing benchmark tactics that do not use such inducements. Specifically, we show, via empirical evaluation in a Multi-Move Prisoners? dilemma setting, that our tactic can lead to a 26% improvement in the utility of deals that are made and that 21 times fewer messages need to be exchanged in order to achieve this.
Rogers, Alex; Dash, Rajdeep K.; Ramchurn, Sarvapali D.; Vytelingum, Perukrishnen; Jennings, N. R.
Coordinating Team Players within a Noisy Iterated Prisoner?s Dilemma Tournament Journal Article
In: Theoretical Computer Science, vol. 377, no. 1-3, pp. 243–259, 2007.
@article{eps263238,
title = {Coordinating Team Players within a Noisy Iterated Prisoner?s Dilemma Tournament},
author = {Alex Rogers and Rajdeep K. Dash and Sarvapali D. Ramchurn and Perukrishnen Vytelingum and N. R. Jennings},
url = {http://eprints.soton.ac.uk/263238/},
year = {2007},
date = {2007-01-01},
journal = {Theoretical Computer Science},
volume = {377},
number = {1-3},
pages = {243--259},
abstract = {In this paper, we present our investigation into the use of a team of players within a noisy Iterated Prisoner?s Dilemma (IPD) tournament. We show that the members of such a team are able to use a pre-arranged sequence of moves that they make at the start of each interaction in order to recognise one another, and that by coordinating their actions they can increase the chances that one of the team members wins the round-robin style tournament. We consider, in detail, the factors that influence the performance of this team and we show that the problem that the team members face, when they attempt to recognise one another within the noisy IPD tournament, is exactly analogous to the problem, studied in information theory, of communicating reliably over a noisy channel. Thus we demonstrate that we can use error correcting codes to implement this recognition, and by doing so, further optimise the performance of the team.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
In this paper, we present our investigation into the use of a team of players within a noisy Iterated Prisoner?s Dilemma (IPD) tournament. We show that the members of such a team are able to use a pre-arranged sequence of moves that they make at the start of each interaction in order to recognise one another, and that by coordinating their actions they can increase the chances that one of the team members wins the round-robin style tournament. We consider, in detail, the factors that influence the performance of this team and we show that the problem that the team members face, when they attempt to recognise one another within the noisy IPD tournament, is exactly analogous to the problem, studied in information theory, of communicating reliably over a noisy channel. Thus we demonstrate that we can use error correcting codes to implement this recognition, and by doing so, further optimise the performance of the team.
Rogers, Alex; Dash, Rajdeep K.; Ramchurn, Sarvapali D.; Vytelingum, Perukrishnen; Jennings, N. R.
Error-Correcting Codes for Team Coordination within a Noisy Iterated Prisoner?s Dilemma Tournament Book Section
In: Kendel, Graham; Yao, Xin; Chong, Siang Yew (Ed.): The Iterated Prisoners Dilemma Competition: Celebrating the 20th Anniversary, pp. 205–229, World Scientific, 2007.
@incollection{eps263264,
title = {Error-Correcting Codes for Team Coordination within a Noisy Iterated Prisoner?s Dilemma Tournament},
author = {Alex Rogers and Rajdeep K. Dash and Sarvapali D. Ramchurn and Perukrishnen Vytelingum and N. R. Jennings},
editor = {Graham Kendel and Xin Yao and Siang Yew Chong},
url = {http://eprints.soton.ac.uk/263264/},
year = {2007},
date = {2007-01-01},
booktitle = {The Iterated Prisoners Dilemma Competition: Celebrating the 20th Anniversary},
pages = {205--229},
publisher = {World Scientific},
keywords = {},
pubstate = {published},
tppubtype = {incollection}
}
2006
Karunatillake, N. C.; Jennings, N. R.; Rahwan, I.; Ramchurn, S. D.
Managing Social Influences through Argumentation-Based Negotiation Proceedings Article
In: Third International Workshop on Argumentation in Multi-Agent Systems (ArgMAS 2006), pp. 35–52, 2006, (Event Dates: 8th May 2006).
@inproceedings{eps262022,
title = {Managing Social Influences through Argumentation-Based Negotiation},
author = {N. C. Karunatillake and N. R. Jennings and I. Rahwan and S. D. Ramchurn},
url = {http://eprints.soton.ac.uk/262022/},
year = {2006},
date = {2006-01-01},
booktitle = {Third International Workshop on Argumentation in Multi-Agent Systems (ArgMAS 2006)},
pages = {35--52},
abstract = {Social influences play an important part in the actions that an individual agent may perform within a multi-agent society. However, the incomplete knowledge and the diverse and conflicting influences present within such societies, may stop an agent from abiding by all its social influences. This may, in turn, lead to conflicts that the agents need to identify, manage, and resolve in order for the society to behave in a coherent manner. To this end, we present an empirical study of an argumentation-based negotiation (ABN) approach that allows the agents to detect such conflicts, and then manage and resolve them through the use of argumentative dialogues. To test our theory, we map our ABN model to a multi-agent task allocation scenario. Our results show that using an argumentation approach allows agents to both efficiently and effectively manage their social influences even under high degrees of incompleteness. Finally, we show that allowing agents to argue and resolve such conflicts early in the negotiation encounter increases their efficiency in managing social influences.},
note = {Event Dates: 8th May 2006},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Social influences play an important part in the actions that an individual agent may perform within a multi-agent society. However, the incomplete knowledge and the diverse and conflicting influences present within such societies, may stop an agent from abiding by all its social influences. This may, in turn, lead to conflicts that the agents need to identify, manage, and resolve in order for the society to behave in a coherent manner. To this end, we present an empirical study of an argumentation-based negotiation (ABN) approach that allows the agents to detect such conflicts, and then manage and resolve them through the use of argumentative dialogues. To test our theory, we map our ABN model to a multi-agent task allocation scenario. Our results show that using an argumentation approach allows agents to both efficiently and effectively manage their social influences even under high degrees of incompleteness. Finally, we show that allowing agents to argue and resolve such conflicts early in the negotiation encounter increases their efficiency in managing social influences.
Ramchurn, S. D.; Sierra, C.; Godo, L.; Jennings, N. R.
Negotiating using rewards Proceedings Article
In: 5th Int. Conf. on Autonomous Agents and Multi-Agent Systems, pp. 400–407, 2006.
@inproceedings{eps262591,
title = {Negotiating using rewards},
author = {S.D. Ramchurn and C. Sierra and L. Godo and N. R. Jennings},
url = {http://eprints.soton.ac.uk/262591/},
year = {2006},
date = {2006-01-01},
booktitle = {5th Int. Conf. on Autonomous Agents and Multi-Agent Systems},
journal = {Proc. 5th Int. Conf. on Autonomous Agents and Multi-Agent Systems, Hakodate, Japan},
pages = {400--407},
abstract = {In situations where self-interested agents interact repeatedly, it is important that they are endowed with negotiation techniques that enable them to reach agreements that are profitable in the long run. To this end, we devise a novel negotiation algorithm that generates promises of rewards in future interactions, as a means of permitting agents to reach better agreements, in a shorter time, in the present encounter. Moreover, we thus develop a specific negotiation tactic based on this reward generation algorithm and show that it can achieve significantly bettter outcomes than existing benchmark tactics that do not use such inducements. Specifically, we show, via empirical evaluation, that our tactic can lead to a 26% improvement in the utility of deals that are made and that 21 times fewer messages need to be exchanged in order to achieve this under concrete settings.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
In situations where self-interested agents interact repeatedly, it is important that they are endowed with negotiation techniques that enable them to reach agreements that are profitable in the long run. To this end, we devise a novel negotiation algorithm that generates promises of rewards in future interactions, as a means of permitting agents to reach better agreements, in a shorter time, in the present encounter. Moreover, we thus develop a specific negotiation tactic based on this reward generation algorithm and show that it can achieve significantly bettter outcomes than existing benchmark tactics that do not use such inducements. Specifically, we show, via empirical evaluation, that our tactic can lead to a 26% improvement in the utility of deals that are made and that 21 times fewer messages need to be exchanged in order to achieve this under concrete settings.
2005
Ashri, R.; Ramchurn, S. D.; Sabater, J.; Luck, M.; Jennings, N. R.
Trust evaluation through relationship analysis Proceedings Article
In: 4th Int Joint Conf. on Autonomous Agents and Multi-Agent Systems, pp. 1005–1011, 2005.
@inproceedings{eps260806,
title = {Trust evaluation through relationship analysis},
author = {R. Ashri and S.D. Ramchurn and J. Sabater and M. Luck and N. R. Jennings},
url = {http://eprints.soton.ac.uk/260806/},
year = {2005},
date = {2005-01-01},
booktitle = {4th Int Joint Conf. on Autonomous Agents and Multi-Agent Systems},
journal = {Proceedings: 4th International Joint Conference on Autonomous Agents and Multi-Agent Systems},
pages = {1005--1011},
abstract = {Current mechanisms for evaluating the trustworthiness of an agent within an electronic marketplace depend either on using a history of interactions or on recommendations from other agents. In the first case, these requirements limit what an agent with no prior interaction history can do. In the second case, they transform the problem into one of trusting the recommending agent. However, these mechanisms do not consider the relationships between agents that arise through interactions (such as buying or selling) or through overarching organisational structures (such as hierarchical or flat), which can also aid in evaluating trustworthiness. In response, this paper outlines a method that enables agents to evaluate the trustworthiness of their counterparts, based solely on an analysis of such relationships. Specifically, relationships are identified using a generic technique in conjunction with a basic model for agentbased marketplaces. They are then interpreted through a trust model that enables the inference of trust valuations based on the different types of relationships. In this way, we provide a further component for a trust evaluation model that addresses some of the limitations of existing work.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Current mechanisms for evaluating the trustworthiness of an agent within an electronic marketplace depend either on using a history of interactions or on recommendations from other agents. In the first case, these requirements limit what an agent with no prior interaction history can do. In the second case, they transform the problem into one of trusting the recommending agent. However, these mechanisms do not consider the relationships between agents that arise through interactions (such as buying or selling) or through overarching organisational structures (such as hierarchical or flat), which can also aid in evaluating trustworthiness. In response, this paper outlines a method that enables agents to evaluate the trustworthiness of their counterparts, based solely on an analysis of such relationships. Specifically, relationships are identified using a generic technique in conjunction with a basic model for agentbased marketplaces. They are then interpreted through a trust model that enables the inference of trust valuations based on the different types of relationships. In this way, we provide a further component for a trust evaluation model that addresses some of the limitations of existing work.
Blankenburg, B.; Dash, R. K.; Ramchurn, S. D.; Klusch, M.; Jennings, N. R.
Trusted kernel-based coalition formation Proceedings Article
In: Proc. 4th Int Joint Conf on Autonomous Agents and Multi-Agent Systems, pp. 989–996, 2005.
@inproceedings{eps260808,
title = {Trusted kernel-based coalition formation},
author = {B. Blankenburg and R.K. Dash and S.D. Ramchurn and M. Klusch and N. R. Jennings},
url = {http://eprints.soton.ac.uk/260808/},
year = {2005},
date = {2005-01-01},
booktitle = {Proc. 4th Int Joint Conf on Autonomous Agents and Multi-Agent Systems},
journal = {Proceedings: 4th International Joint Conference on Autonomous Agents and Multi-agent Systems},
pages = {989--996},
abstract = {We define Trusted Kernel-based Coalition Formation as a novel extension to the traditional kernel-based coalition formation process which ensures agents choose the most reliable coalition partners and are guaranteed to obtain the payment they deserve. To this end, we develop an encryption-based communication protocol and a payment scheme which ensure that agents cannot manipulate the mechanism to their own benefit. Moreover, we integrate a generic trust model in the coalition formation process that permits the selection of the most reliable agents over repeated coalition games. We empirically evaluate our mechanism when iterated and show that, in the long run, it always chooses the coalition structure that has the maximum expected value and determines the payoffs that match their level of reliability.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
We define Trusted Kernel-based Coalition Formation as a novel extension to the traditional kernel-based coalition formation process which ensures agents choose the most reliable coalition partners and are guaranteed to obtain the payment they deserve. To this end, we develop an encryption-based communication protocol and a payment scheme which ensure that agents cannot manipulate the mechanism to their own benefit. Moreover, we integrate a generic trust model in the coalition formation process that permits the selection of the most reliable agents over repeated coalition games. We empirically evaluate our mechanism when iterated and show that, in the long run, it always chooses the coalition structure that has the maximum expected value and determines the payoffs that match their level of reliability.
Ramchurn, S. D.; Jennings, N. R.
Trust in agent-based software Book Section
In: Mansell, R.; Collins, B. S. (Ed.): Trust and Crime in Information Societies, pp. 165–204, Elgar Publishing, 2005.
@incollection{eps260823,
title = {Trust in agent-based software},
author = {S.D. Ramchurn and N. R. Jennings},
editor = {R. Mansell and B.S. Collins},
url = {http://eprints.soton.ac.uk/260823/},
year = {2005},
date = {2005-01-01},
booktitle = {Trust and Crime in Information Societies},
pages = {165--204},
publisher = {Elgar Publishing},
keywords = {},
pubstate = {published},
tppubtype = {incollection}
}
2004
Dash, R. K.; Ramchurn, S. D.; Jennings, N. R.
Trust-Based Mechanism Design Proceedings Article
In: 3rd Int. Conf. on Autonomous Agents and Multi-Agent Systems, pp. 748–755, 2004, (Event Dates: 19-23 July 2004).
@inproceedings{eps259352,
title = {Trust-Based Mechanism Design},
author = {R. K . Dash and S.D. Ramchurn and N. R. Jennings},
url = {http://eprints.soton.ac.uk/259352/},
year = {2004},
date = {2004-01-01},
booktitle = {3rd Int. Conf. on Autonomous Agents and Multi-Agent Systems},
pages = {748--755},
abstract = {We define trust-based mechanism design as an augmentation of traditional mechanism design in which agents take into account the degree of trust that they have in their counterparts when determining their allocations. To this end, we develop an efficient, individually rational, and incentive compatible mechanism based on trust. This mechanism is embedded in a task allocation scenario in which the trust in an agent is derived from the reported performance success of that agent by all the other agents in the system. We also empirically study the evolution of our mechanism when iterated and show that, in the long run, it always chooses the most successful and cheapest agents to fulfill an allocation and chooses better allocations than other comparable models when faced with biased reporting.},
note = {Event Dates: 19-23 July 2004},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
We define trust-based mechanism design as an augmentation of traditional mechanism design in which agents take into account the degree of trust that they have in their counterparts when determining their allocations. To this end, we develop an efficient, individually rational, and incentive compatible mechanism based on trust. This mechanism is embedded in a task allocation scenario in which the trust in an agent is derived from the reported performance success of that agent by all the other agents in the system. We also empirically study the evolution of our mechanism when iterated and show that, in the long run, it always chooses the most successful and cheapest agents to fulfill an allocation and chooses better allocations than other comparable models when faced with biased reporting.
Ramchurn, S. D.; Deitch, B.; Thompson, M. K.; de Roure, D. C.; Jennings, N. R.; Luck, M.
Minimising intrusiveness in pervasive computing environments using multi-agent negotiation Proceedings Article
In: First Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services (MobiQuitous'04), pp. 364–372, IEEE, 2004, (Event Dates: August 22 - 26, 2004).
@inproceedings{eps259566,
title = {Minimising intrusiveness in pervasive computing environments using multi-agent negotiation},
author = {S.D. Ramchurn and B. Deitch and M.K. Thompson and D. C. de Roure and N. R. Jennings and M. Luck},
url = {http://eprints.soton.ac.uk/259566/},
year = {2004},
date = {2004-01-01},
booktitle = {First Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services (MobiQuitous'04)},
pages = {364--372},
publisher = {IEEE},
abstract = {This paper highlights intrusiveness as a key issue in the field of pervasive computing environments and presents a multi-agent approach to tackling it. Specifically, we discuss how interruptions can impact on individual and group tasks and how they can be managed by taking into account user and group preferences through negotiation between software agents. The system we develop is implemented on the Jabber platform and is deployed in the context of a meeting room scenario.},
note = {Event Dates: August 22 - 26, 2004},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
This paper highlights intrusiveness as a key issue in the field of pervasive computing environments and presents a multi-agent approach to tackling it. Specifically, we discuss how interruptions can impact on individual and group tasks and how they can be managed by taking into account user and group preferences through negotiation between software agents. The system we develop is implemented on the Jabber platform and is deployed in the context of a meeting room scenario.
Ramchurn, S. D.; Huynh, T. D.; Jennings, N. R.
Trust in Multiagent Systems Journal Article
In: The Knowledge Engineering Review, vol. 19, no. 1, pp. 1–25, 2004.
@article{eps259564,
title = {Trust in Multiagent Systems},
author = {S.D. Ramchurn and T.D. Huynh and N. R. Jennings},
url = {http://eprints.soton.ac.uk/259564/},
year = {2004},
date = {2004-01-01},
journal = {The Knowledge Engineering Review},
volume = {19},
number = {1},
pages = {1--25},
abstract = {Trust is a fundamental concern in large-scale open distributed systems. It lies at the core of all interactions between the entities that have to operate in such uncertain and constantly changing environments. Given this complexity, these components, and the ensuing system, are increasingly being conceptualised, designed, and built using agent-based techniques and, to this end, this paper examines the specific role of trust in multi-agent systems. In particular, we survey the state of the art and provide an account of the main directions along which research efforts are being focused. In so doing, we critically evaluate the relative strengths and weaknesses of the main models that have been proposed and show how, fundamentally, they all seek to minimise the uncertainty in interactions. Finally, we outline the areas that require further research in order to develop a comprehensive treatment of trust in complex computational settings.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Trust is a fundamental concern in large-scale open distributed systems. It lies at the core of all interactions between the entities that have to operate in such uncertain and constantly changing environments. Given this complexity, these components, and the ensuing system, are increasingly being conceptualised, designed, and built using agent-based techniques and, to this end, this paper examines the specific role of trust in multi-agent systems. In particular, we survey the state of the art and provide an account of the main directions along which research efforts are being focused. In so doing, we critically evaluate the relative strengths and weaknesses of the main models that have been proposed and show how, fundamentally, they all seek to minimise the uncertainty in interactions. Finally, we outline the areas that require further research in order to develop a comprehensive treatment of trust in complex computational settings.
Ramchurn, Sarvapali
Multi-Agent Negotiation using Trust and Persuasion PhD Thesis
University of Southampton, 2004.
@phdthesis{eps260200,
title = {Multi-Agent Negotiation using Trust and Persuasion},
author = {Sarvapali Ramchurn},
url = {http://eprints.soton.ac.uk/260200/},
year = {2004},
date = {2004-01-01},
school = {University of Southampton},
abstract = {In this thesis, we propose a panoply of tools and techniques to manage inter-agent dependencies in open, distributed multi-agent systems that have significant degrees of uncertainty. In particular, we focus on situations in which agents are involved in repeated interactions where they need to negotiate to resolve conflicts that may arise between them. To this end, we endow agents with decision making models that exploit the notion of trust and use persuasive techniques during the negotiation process to reduce the level of uncertainty and achieve better deals in the long run. Firstly, we develop and evaluate a new trust model (called CREDIT) that allows agents to measure the degree of trust they should place in their opponents. This model reduces the uncertainty that agents have about their opponents' reliability. Thus, over repeated interactions, CREDIT enables agents to model their opponents' reliability using probabilistic techniques and a fuzzy reasoning mechanism that allows the combination of measures based on reputation (indirect interactions) and confidence (direct interactions). In so doing, CREDIT takes a wider range of behaviour-influencing factors into account than existing models, including the norms of the agents and the institution within which transactions occur. We then explore a novel application of trust models by showing how the measures developed in CREDIT ca be applied negotiations in multiple encounters. Specifically we show that agents that use CREDIT are able to avoid unreliable agents, both during the selection of interaction partners and during the negotiation process itself by using trust to adjust their negotiation stance. Also, we empirically show that agents are able to reach good deals with agents that are unreliable to some degree (rather than completely unreliable) and with those that try to strategically exploit their opponent. Secondly, having applied CREDIT to negotiations, we further extend the application of trust to reduce uncertainty about the reliability of agents in mechanism design (where the honesty of agents is elicited by the protocol). Thus, we develop $backslash$acftbmd that allows agents using a trust model (such as CREDIT) to reach efficient agreements that choose the most reliable agents in the long run. In particular, we show that our mechanism enforces truth-telling from the agents (i.e. it is incentive compatible), both about their perceived reliability of their opponent and their valuations for the goods to be traded. In proving the latter properties, our trust-based mechanism is shown to be the first reputation mechanism that implements individual rationality, incentive compatibility, and efficiency. Our trust-based mechanism is also empirically evaluated and shown to be better than other comparable models in reaching the outcome that maximises all the negotiating agents' utilities and in choosing the most reliable agents in the long run. Thirdly, having explored ways to reduce uncertainties about reliability and honesty, we use persuasive negotiation techniques to tackle issues associated with uncertainties that agents have about the preferences and the space of possible agreements. To this end, we propose a novel protocol and reasoning mechanism that agents can use to generate and evaluate persuasive elements, such as promises of future rewards, to support the offers they make during negotiation. These persuasive elements aim to make offers more attractive over multiple encounters given the absence of information about an opponent's discount factors or exact payoffs. Specifically, we empirically demonstrate that agents are able to achieve a larger number of agreements and a higher expected utility over repeated encounters when they are given the capability to give or ask for rewards. Moreover, we develop a novel strategy using this protocol and show that it outperforms existing state of the art heuristic negotiation models. Finally, the applicability of persuasive negotiation and CREDIT is exemplified through a practical implementation in a pervasive computing environment. In this context, the negotiation mechanism is implemented in an instant messaging platform (JABBER) and used to resolve conflicts between group and individual preferences that arise in a meeting room scenario. In particular, we show how persuasive negotiation and trust permit a flexible management of interruptions by allowing intrusions to happen at appropriate times during the meeting while still managing to satisfy the preferences of all parties present.},
keywords = {},
pubstate = {published},
tppubtype = {phdthesis}
}
In this thesis, we propose a panoply of tools and techniques to manage inter-agent dependencies in open, distributed multi-agent systems that have significant degrees of uncertainty. In particular, we focus on situations in which agents are involved in repeated interactions where they need to negotiate to resolve conflicts that may arise between them. To this end, we endow agents with decision making models that exploit the notion of trust and use persuasive techniques during the negotiation process to reduce the level of uncertainty and achieve better deals in the long run. Firstly, we develop and evaluate a new trust model (called CREDIT) that allows agents to measure the degree of trust they should place in their opponents. This model reduces the uncertainty that agents have about their opponents' reliability. Thus, over repeated interactions, CREDIT enables agents to model their opponents' reliability using probabilistic techniques and a fuzzy reasoning mechanism that allows the combination of measures based on reputation (indirect interactions) and confidence (direct interactions). In so doing, CREDIT takes a wider range of behaviour-influencing factors into account than existing models, including the norms of the agents and the institution within which transactions occur. We then explore a novel application of trust models by showing how the measures developed in CREDIT ca be applied negotiations in multiple encounters. Specifically we show that agents that use CREDIT are able to avoid unreliable agents, both during the selection of interaction partners and during the negotiation process itself by using trust to adjust their negotiation stance. Also, we empirically show that agents are able to reach good deals with agents that are unreliable to some degree (rather than completely unreliable) and with those that try to strategically exploit their opponent. Secondly, having applied CREDIT to negotiations, we further extend the application of trust to reduce uncertainty about the reliability of agents in mechanism design (where the honesty of agents is elicited by the protocol). Thus, we develop $backslash$acftbmd that allows agents using a trust model (such as CREDIT) to reach efficient agreements that choose the most reliable agents in the long run. In particular, we show that our mechanism enforces truth-telling from the agents (i.e. it is incentive compatible), both about their perceived reliability of their opponent and their valuations for the goods to be traded. In proving the latter properties, our trust-based mechanism is shown to be the first reputation mechanism that implements individual rationality, incentive compatibility, and efficiency. Our trust-based mechanism is also empirically evaluated and shown to be better than other comparable models in reaching the outcome that maximises all the negotiating agents' utilities and in choosing the most reliable agents in the long run. Thirdly, having explored ways to reduce uncertainties about reliability and honesty, we use persuasive negotiation techniques to tackle issues associated with uncertainties that agents have about the preferences and the space of possible agreements. To this end, we propose a novel protocol and reasoning mechanism that agents can use to generate and evaluate persuasive elements, such as promises of future rewards, to support the offers they make during negotiation. These persuasive elements aim to make offers more attractive over multiple encounters given the absence of information about an opponent's discount factors or exact payoffs. Specifically, we empirically demonstrate that agents are able to achieve a larger number of agreements and a higher expected utility over repeated encounters when they are given the capability to give or ask for rewards. Moreover, we develop a novel strategy using this protocol and show that it outperforms existing state of the art heuristic negotiation models. Finally, the applicability of persuasive negotiation and CREDIT is exemplified through a practical implementation in a pervasive computing environment. In this context, the negotiation mechanism is implemented in an instant messaging platform (JABBER) and used to resolve conflicts between group and individual preferences that arise in a meeting room scenario. In particular, we show how persuasive negotiation and trust permit a flexible management of interruptions by allowing intrusions to happen at appropriate times during the meeting while still managing to satisfy the preferences of all parties present.
Ramchurn, Sarvapali; Sierra, C.; Godo, L.; Jennings, N. R.
Devising a trust model for multi-agent interactions using confidence and reputation Journal Article
In: International Journal of Applied Artificial Intelligence, vol. 18, no. 9-10, pp. 833–852, 2004.
@article{eps260155,
title = {Devising a trust model for multi-agent interactions using confidence and reputation},
author = {Sarvapali Ramchurn and C. Sierra and L. Godo and N. R. Jennings},
url = {http://eprints.soton.ac.uk/260155/},
year = {2004},
date = {2004-01-01},
journal = {International Journal of Applied Artificial Intelligence},
volume = {18},
number = {9-10},
pages = {833--852},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
2003
Rahwan, I.; Ramchurn, Sarvapali; Jennings, N. R.; McBurney, P.; Parsons, S.; Sonenberg, L.
Argumentation-based negotiation Journal Article
In: The Knowledge Engineering Review, vol. 18, no. 4, pp. 343–375, 2003.
@article{eps258850,
title = {Argumentation-based negotiation},
author = {I. Rahwan and Sarvapali Ramchurn and N. R. Jennings and P. McBurney and S. Parsons and L. Sonenberg},
url = {http://eprints.soton.ac.uk/258850/},
year = {2003},
date = {2003-01-01},
journal = {The Knowledge Engineering Review},
volume = {18},
number = {4},
pages = {343--375},
abstract = {Negotiation is essential in settings where autonomous agents have con- flicting interests and a desire to cooperate. For this reason, mechanisms in which agents exchange potential agreements according to various rules of interaction have become very popular in recent years as evident, for example, in the auction and mechanism design community. However, a growing body of research is now emerging which points out limitations in such mechanisms and advocates the idea that agents can increase the likelihood and quality of an agreement by exchanging arguments which in- fluence each others? states. This community further argues that argument exchange is sometimes essential when various assumptions about agent rationality cannot be satisfied. To this end, in this article, we identify the main research motivations and ambitions behind work in the field. We then provide a conceptual framework through which we outline the core elements and features required by agents engaged in argumentation-based negotiation, as well as the environment that hosts these agents. For each of these elements, we survey and evaluate existing proposed techniques in the literature and highlight the major challenges that need to be addressed if argument-based negotiation research is to reach its full potential.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Negotiation is essential in settings where autonomous agents have con- flicting interests and a desire to cooperate. For this reason, mechanisms in which agents exchange potential agreements according to various rules of interaction have become very popular in recent years as evident, for example, in the auction and mechanism design community. However, a growing body of research is now emerging which points out limitations in such mechanisms and advocates the idea that agents can increase the likelihood and quality of an agreement by exchanging arguments which in- fluence each others? states. This community further argues that argument exchange is sometimes essential when various assumptions about agent rationality cannot be satisfied. To this end, in this article, we identify the main research motivations and ambitions behind work in the field. We then provide a conceptual framework through which we outline the core elements and features required by agents engaged in argumentation-based negotiation, as well as the environment that hosts these agents. For each of these elements, we survey and evaluate existing proposed techniques in the literature and highlight the major challenges that need to be addressed if argument-based negotiation research is to reach its full potential.
Ramchurn, S. D.; Jennings, N. R.; Sierra, C.
Persuasive negotiation for autonomous agents: A rhetorical approach Proceedings Article
In: IJCAI Workshop on Computational Models of Natural Argument, pp. 9–17, 2003.
@inproceedings{eps258541,
title = {Persuasive negotiation for autonomous agents: A rhetorical approach},
author = {S.D. Ramchurn and N. R. Jennings and C. Sierra},
url = {http://eprints.soton.ac.uk/258541/},
year = {2003},
date = {2003-01-01},
booktitle = {IJCAI Workshop on Computational Models of Natural Argument},
pages = {9--17},
abstract = {Persuasive negotiation occurs when autonomous agents exchange proposals that are backed up by rhetorical arguments (such as threats, rewards, or appeals). The role of such rhetorical arguments is to persuade the negotiation opponent to accept proposals more readily. To this end, this paper presents a rhetorical model of persuasion that defines the main types of rhetorical particles that are used and that provides a decision making model to enable an agent to determine what type of rhetorical argument to send in a given context and how to evaluate rhetorical arguments that are received. The model is empirically evaluated and we show that it is effective and efficient in reaching agreements.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Persuasive negotiation occurs when autonomous agents exchange proposals that are backed up by rhetorical arguments (such as threats, rewards, or appeals). The role of such rhetorical arguments is to persuade the negotiation opponent to accept proposals more readily. To this end, this paper presents a rhetorical model of persuasion that defines the main types of rhetorical particles that are used and that provides a decision making model to enable an agent to determine what type of rhetorical argument to send in a given context and how to evaluate rhetorical arguments that are received. The model is empirically evaluated and we show that it is effective and efficient in reaching agreements.
Ramchurn, Sarvapali; Sierra, C.; Godo, L.; Jennings, N. R.
A computational trust model for multi-agent interactions based on confidence and reputation Proceedings Article
In: 6th International Workshop of Deception, Fraud and Trust in Agent Societies, pp. 69–75, 2003, (Event Dates: 2003).
@inproceedings{eps258542,
title = {A computational trust model for multi-agent interactions based on confidence and reputation},
author = {Sarvapali Ramchurn and C. Sierra and L. Godo and N. R. Jennings},
url = {http://eprints.soton.ac.uk/258542/},
year = {2003},
date = {2003-01-01},
booktitle = {6th International Workshop of Deception, Fraud and Trust in Agent Societies},
pages = {69--75},
abstract = {In open environments in which autonomous agents can break contracts, computational models of trust have an important role to play in determining who to interact with and how interactions unfold. To this end, we develop such a trust model, based on confi- dence and reputation, and show how it can be concretely applied, using fuzzy sets, to guide agents in evaluating past interactions and in establishing new contracts with one another.},
note = {Event Dates: 2003},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
In open environments in which autonomous agents can break contracts, computational models of trust have an important role to play in determining who to interact with and how interactions unfold. To this end, we develop such a trust model, based on confi- dence and reputation, and show how it can be concretely applied, using fuzzy sets, to guide agents in evaluating past interactions and in establishing new contracts with one another.
2002
Panzarasa, P.; Ramchurn, S. D.; Jennings, Nick
Intrusiveness, Trust and Argumentation: Using Automated Negotiation to Inhibit the Transmission of Disruptive Information Proceedings Article
In: Proceedings of the International Conference on Computational Social and Organizational Systems, 2002.
@inproceedings{eps272014,
title = {Intrusiveness, Trust and Argumentation: Using Automated Negotiation to Inhibit the Transmission of Disruptive Information},
author = {P. Panzarasa and S. D. Ramchurn and Nick Jennings},
url = {http://eprints.soton.ac.uk/272014/},
year = {2002},
date = {2002-01-01},
booktitle = {Proceedings of the International Conference on Computational Social and Organizational Systems},
abstract = {The question of how to promote the growth and diffusion of information has been extensively addressed by a wide research community. A common assumption underpinning most studies is that the information to be transmitted is useful and of high quality. In this paper, we endorse a complementary perspective. We investigate how the growth and diffusion of high quality information can be managed and maximized by preventing, dampening and minimizing the diffusion of low quality, unwanted information. To this end, we focus on the conflict between pervasive computing environments and the joint activities undertaken in parallel local social contexts. When technologies for distributed activities (e.g. mobile technology) develop, both artifacts and services that enable people to participate in non-local contexts are likely to intrude on local situations. As a mechanism for minimizing the intrusion of the technology, we develop a computational model of argumentation-based negotiation among autonomous agents. A key component in the model is played by trust: what arguments are used and how they are evaluated depend on how trustworthy the agents judge one another. To gain an insight into the implications of the model, we conduct a number of virtual experiments. Results enable us to explore how intrusiveness is affected by trust, the negotiation network and the agents' abilities of conducting argumentation.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
The question of how to promote the growth and diffusion of information has been extensively addressed by a wide research community. A common assumption underpinning most studies is that the information to be transmitted is useful and of high quality. In this paper, we endorse a complementary perspective. We investigate how the growth and diffusion of high quality information can be managed and maximized by preventing, dampening and minimizing the diffusion of low quality, unwanted information. To this end, we focus on the conflict between pervasive computing environments and the joint activities undertaken in parallel local social contexts. When technologies for distributed activities (e.g. mobile technology) develop, both artifacts and services that enable people to participate in non-local contexts are likely to intrude on local situations. As a mechanism for minimizing the intrusion of the technology, we develop a computational model of argumentation-based negotiation among autonomous agents. A key component in the model is played by trust: what arguments are used and how they are evaluated depend on how trustworthy the agents judge one another. To gain an insight into the implications of the model, we conduct a number of virtual experiments. Results enable us to explore how intrusiveness is affected by trust, the negotiation network and the agents' abilities of conducting argumentation.
0000
Alessandro Farinelli Filippo Bistaffa, Jesús Cerquides; Ramchurn, Sarvapali D.
Algorithms for Graph-Constrained Coalition Formation in the Real World Journal Article
In: ACM Transactions on Intelligent Systems and Technology (TIST), vol. 8, no. 4, 0000.
@article{bistaffaetal2017,
title = {Algorithms for Graph-Constrained Coalition Formation in the Real World},
author = {Filippo Bistaffa, Alessandro Farinelli, Jesús Cerquides, Juan A. Rodríguez-Aguilar, and Sarvapali D. Ramchurn},
doi = {http://dx.doi.org/10.1145/3040967},
journal = {ACM Transactions on Intelligent Systems and Technology (TIST)},
volume = {8},
number = {4},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
