Search

This paper investigates repeated security games with unknown (to the defender) game payoffs and attacker behaviors. As existing work assumes prior knowledge about either the game payoffs or the attacker's behaviors, they are not suitable for tackling our problem. Given this, we propose the first efficient defender strategy, based on an adversarial online learning framework, that can provably achieve good performance guarantees without any prior knowledge. In particular, we prove that our algorithm can achieve low performance loss against the best fixed strategy on hindsight (i.e., having full knowledge of the attacker's moves). In addition, we prove that our algorithm can achieve an efficient competitive ratio against the optimal adaptive defender strategy. We also show that for zero-sum security games, our algorithm achieves efficient results in approximating a number of solution concepts, such as algorithmic equilibria and the minimax value. Finally, our extensive numerical results demonstrate that, without having any prior information, our algorithm still achieves good performance, compared to state-of-the-art algorithms from the literature on security games, such as SUQR, which require significant amount of prior knowledge.\ud \ud

1 IntroductionUKMAS has now been running for six years, in 1996 and 1997 under the heading of FoMAS (Foundations of Multi-Agent Systems) both organised by Michael Luck at Warwick University and then subsequently in its current incarnation, UKMAS, first by Michael Fisher at Manchester Metropolitan University then by Chris Preist at Hewlett Packard Laboratories, Bristol and finally by Mark d'Inverno at St Catherine's College, Oxford in 2000. After the success of the workshop last year at St Catherine's in providing an excellent opportunity for academics and industrialists to come together to discuss current work and directions in the multi-agent systems field, it was decided by the steering committee to use St Catherine's once again as the venue for UKMAS 2001. The workshop was sponsored by the Engineering and Physical Sciences Research Council and by AgentLink, the European Commission's IST-funded Network of Excellence for Agent-Based Computing.

Self-organising multi-agent systems provide a suitable paradigm for developing autonomic computing systems that manage themselves. Towards this goal, we demonstrate a robust, decentralised approach for structural adaptation in explicitly modelled problem solving agent organisations. Based on self-organisation principles, our method enables the autonomous agents to modify their structural relations to achieve a better allocation of tasks in a simulated task-solving environment. Specifically, the agents reason about when and how to adapt using only their history of interactions as guidance. We empirically show that, in a wide range of closed, open, static and dynamic scenarios, the performance of organisations using our method is close (70-90%) to that of an idealised centralised allocation method and is considerably better (10-60%) than the current state of the art decentralised approaches.

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 £1.5B).

In this paper, we introduce DCOPs with uncertainty (U-DCOPs), a novel generalisation of the canonical DCOP framework where the outcomes of local functions are represented by random variables, and the global objective is to maximise the expectation of an arbitrary utility function (that represents the agents' risk-profile) applied over the sum of these local functions. We then develop U-GDL, a novel decentralised algorithm derived from Generalised Distributive Law (GDL) that optimally solves U-DCOPs. A key property of U-GDL that we show is necessary for optimality is that it keeps track of multiple non-dominated alternatives, and only discards those that are dominated (i.e. local partial solutions that can never turn into an expected global maximum regardless of the realisation of the random variables). As a direct consequence, we show that applying a standard DCOP algorithm to U-DCOP can result in arbitrarily poor solutions. We empirically evaluate U-GDL to determine its computational overhead and bandwidth requirements compared to a standard DCOP algorithm.

We describe the winning strategy of the inaugural Lemonade Stand Game (LSG) Tournament. The LSG is a repeated symmetric 3–player constant–sum finite horizon game, in which a player chooses a location for their lemonade stand on an island with the aim of being as far as possible from its opponents. To receive a high utility in this game, our strategy, EA2 , attempts to find a suitable partner with which to coordinate and exploit the third player. To do this, we classify the behaviour of our opponents using the history of joint interactions in order to identify the best player to coordinate with and how this coordination should be established. This approach is designed to be adaptive to various types of opponents such that coordination is almost always achieved, which yields consistently high utilities to our agent, as evidenced by the Tournament results and our subsequent experimental analysis. Our strategy models behaviours of its opponents, rather than situations of the game (e.g. game theoretic equilibrium or off equilibrium paths), which makes EA2 easy to generalize to many other games.

Planning how to interact against bounded memory and unbounded memory learning opponents needs different treatment. Thus far, however, work in this area has shown how to design plans against bounded memory learning opponents, but no work has dealt with the unbounded memory case. This paper tackles this gap. In particular, we frame this as a planning problem using the framework of repeated matrix games, where the planner's objective is to compute the best exploiting sequence of actions against a learning opponent. The particular class of opponent we study uses a fictitious play process to update her beliefs, but the analysis generalizes to many forms of Bayesian learning agents. Our analysis is inspired by Banerjee and Peng's AIM framework, which works for planning and learning against bounded memory opponents (e.g an adaptive player). Building on this, we show how an unbounded memory opponent (specifically a fictitious player) can also be modelled as a finite MDP and present a new efficient algorithm that can find a way to exploit the opponent by computing in polynomial time a sequence of play that can obtain a higher average reward than those obtained by playing a game theoretic (Nash or correlated) equilibrium.

In this paper we extend the control methodology based on Extended Markov Tracking (EMT) by providing the control algorithm with capabilities to calibrate and even partially reconstruct the environment’s model. This enables us to resolve the problem of performance deterioration due to model incoherence, a negative problem in all model based control methods. The new algorithm, Ensemble Actions EMT (EA-EMT), utilises the initial environment model as a library of state transition functions and applies a variation of prediction with experts to assemble and calibrate a revised model. By so doing, this is the first control algorithm that enables on-line adaptation within the Dynamics Based Control (DBC) framework. In our experiments, we performed a range of tests with increasing model incoherence induced by three types of exogenous environment perturbations: catastrophic, periodic and deviating. The results show that EA-EMT resolved model incoherence and significantly outperformed the best currently available DBC solution by up to $95$$%$.

This paper reports on a novel decentralised technique for planning agent schedules in dynamic task allocation problems. Specifically, we use a Markov game formulation of these problems for tasks with varying hard deadlines and processing requirements. We then introduce a new technique for approximating this game using a series of static potential games, before detailing a decentralised solution method for the approximating games that uses the Distributed Stochastic Algorithm. Finally, we discuss an implementation of our approach to a task allocation problem in the RoboCup Rescue disaster management simulator. Our results show that our technique performs comparably to a centralised task scheduler (within 6% on average), and also, unlike its centralised counterpart, it is robust to restrictions on the agents' communication and observation range.

In this paper we address the problem of decentralised coordination for agents that must make coordinated decisions over continuously valued control parameters (as is required in many real world applications). In particular, we tackle the social welfare maximisation problem, and derive a novelcontinuous version of the max-sum algorithm. In order to do so, we represent the utility functionof the agents by multivariate piecewise linear functions, which in turn are encoded as simplexes.We then derive analytical solutions for the fundamental operations required to implement the max-sum algorithm (specifically, addition and marginal maximisation of general n-ary piecewise linearfunctions). We empirically evaluate our approach on a simulated network of wireless, energy constrained sensors that must coordinate their sense/sleep cycles in order to maximise the system-wide probability of event detection. We compare the conventional discrete max-sum algorithm with our novel continuous version, and show that the continuous approach obtains more accurate solutions (up to a 10% increase) with a lower communication overhead (up to half of the total message size).

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

The efficient allocation of the limited energy resources of a wireless sensor network in a way that maximises the information value of the data collected is a significant research challenge. Within this context, this paper concentrates on adaptive sampling as a means of focusing a sensor’s energy consumption on obtaining the most important data. Specifically, we develop a principled information metric based upon Fisher information and Gaussian process regression that allows the information content of a sensor’s observations to be expressed. We then use this metric to derive three novel decentralised control algorithms for information-based adaptive sampling which represent a trade-off in computational cost and optimality. These algorithms are evaluated in the context of a deployed sensor network in the domain of flood monitoring. The most computationally efficient of the three is shown to increase the value of information gathered by approximately 83%, 27%, and 8% per day compared to benchmarks that sample in a naive non-adaptive manner, in a uniform non-adaptive manner, and using a state-of-the-art adaptive sampling heuristic (USAC) correspondingly. Moreover, our algorithm collects information whose total value is approximately 75% of the optimal solution (which requires an exponential, and thus impractical, amount of time to compute).

In this paper we describe the IAMwildCAT agent, designed for the TAC Market Design game which is part of the International Trading Agent Competition. The objective of an agent in this competition is to effectively manage and operate a market that attracts traders to compete for resources in it. This market, in turn, competes against markets operated by other competition entrants and the aim is to maximise the market and profit share of the agent, as well as its transaction success rate. To do this, the agent needs to continually monitor and adapt, in response to the competing marketplaces, the rules it uses to accept offers, clear the market, price the transactions and charge the traders. Given this context, this paper details IAMwildCAT’s strategic behaviour and describes the wide techniques we developed to operationalise this. Finally, we empirically analyse our agent in different environments, including the 2007 competition where it ranked first.