Current electricity tariffs do not reflect the real costs that a customer incurs to a supplier, as units are charged at the same rate, regardless of the consumption pattern. In this paper, we propose a prediction-of-use (POU) tariff that better reflects the predictability cost of a customer. Our tariff asks customers to pre-commit to a baseline consumption, and charges them based on both their actual consumption and the deviation from the anticipated baseline. First, we study, from a cooperative game theory perspective, the cost game induced by a single such tariff, and show customers would have an incentive to minimize their risk, by joining together when buying electricity as a grand coalition. Second, we study the efficient (i.e., cost-minimizing) structure of buying groups for the more realistic setting when multiple, competing POU tariffs are available. We propose a polynomial time algorithm to compute the efficient buyer groups, and validate our approach experimentally, using a large-scale data set of domestic consumers in the U.K.

@en

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

@en

We study the problem of an advertising agent who needs to intelligently distribute her budget across a sequence of online keyword bidding auctions. We assume the closing price of each auction is governed by the same unknown distribution, and study the problem of making provably optimal bidding decisions. Learning the distribution is done under censored observations, i.e. the closing price of an auction is revealed only if the bid we place is above it. We consider three algorithms, namely ε-First, Greedy Product- Limit (GPL) and LuekerLearn, respectively, and we show that these algorithms provably achieve Hannan-consistency. In particular, we show that the regret bound of ε-First is at most O(T^2/3) with high probability. For the other two algorithms, we first prove that, by using a censored data distribution estimator proposed by Zeng [19], the empirical distribution of the closing market price converges in probability to its true distribution with a O(1/εt) rate, where t is the number of updates. Based on this result, we prove that both GPL and Lueker Learn achieve O(√T) regret bound with high probability. This in fact provides an affirmative answer to the research question raised in [1]. We also evaluate the abovementioned algorithms using real bidding data, and show that although GPL achieves the best performance on average (up to 90% of the optimal solution), its long running time may limit its suitability in practice. By contrast, LuekerLearn and ε-First proposed in this paper achieve up to 85% of the optimal, but with an exponential reduction in computational complexity (a saving up to 95%, compared to GPL).

@en

Current electricity tariffs do not reflect the real costs that a customer incurs to a supplier, as units are charged at the same rate, regardless of the consumption pattern. In this paper, we propose a prediction-of-use tariff that better reflects these costs, which asks customers to predict a baseline consumption, and charges them based both on their actual consumption, and the deviation from their prediction. We show how under this tariff no customer would have an incentive to consume in excess of their actual needs, and derive closed form expressions for their optimal prediction and expected payments. Second, using principles from cooperative game theory, we study how customers can collectively reduce their potential deviation by aggregating under a group-buying scheme. We prove that the associated cost game is concave, which means grouping reduces the total expected bill and that this payment can be fairly allocated among customers by their Shapley values. Third, considering a model where customers can join the group online, we propose marginal payment allocation schemes that incentivise them to commit early, thus preventing start-up inertia. Finally, we validate our model using real data from a set of 3000 consumers from the UK.

@en

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

The third Automated Negotiating Agents Competition (ANAC 2012) was held at the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2012, Valencia, Spain). ANAC is an international competition that aims to encourage research into bilateral, multi-issue negotiation, by providing a platform in which strategies developed independently by different research teams can be tried and compared against each other, in a real-time competition. In the 2012 edition, we received 17 entries from 9 different universities worldwide, out of which 8 were selected for the final round. This chapter aims to provide a broad description of the competition set-up (especially highlighting the changes from previous editions), the preference domains and the strategies submitted, as well as the results from both the qualifying and final rounds.

@en

We study the problem of designing efficient auctions where bidders have interdependent values; i.e., values that depend on the signals of other agents. We consider a contingent bid model in which agents can explicitly condition the value of their bids on the bids submitted by others. In particular, we adopt a linear contingent bidding model for single minded combinatorial auctions (CAs), in which submitted bids are linear combinations of bids received from others. We extend the existing state of the art, by identifying constraints on the interesting bundles and contingency weights reported by the agents which allow the efficient second priced, fixed point bids auction to be implemented in single minded CAs. Moreover, for domains in which the required single crossing condition fails (which characterizes when efficient, IC auctions are possible), we design a two-stage mechanism in which a subset of agents ("experts" ) are allocated first, using their reports to allocate the remaining items to the other agents.@en

We develop an online mechanism for the allocation of an expiring resource to a dynamic agent population. Each agent has a non-increasing marginal valuation function for the resource, and an upper limit on the number of units that can be allocated in any period. We propose two versions on a truthful allocation mechanism. Each modifies the decisions of a greedy online assignment algorithm by sometimes cancelling an allocation of resources. One version makes this modification immediately upon an allocation decision while a second waits until the point at which an agent departs the market. Adopting a prior-free framework, we show that the second approach has better worst-case allocative efficiency and is more scalable. On the other hand, the first approach (with immediate cancellation) may be easier in practice because it does not need to reclaim units previously allocated. We consider an application to recharging plug-in hybrid electric vehicles (PHEVs). Using data from a real-world trial of PHEVs in the UK, we demonstrate higher system performance than a fixed price system, performance comparable with a standard, but non-truthful scheduling heuristic, and the ability to support 50% more vehicles at the same fuel cost than a simple randomized policy.

@en

Following previous work on payment redistribution in static mechanisms, we develop the theory of redistribution in online mechanisms (e.g., [2, 10, 8]). In static mechanisms, redistribution is important as it increases social welfare in scenarios with no residual claimant. Many online scenarios also do not have a natural residual claimant, and redistribution there is equally important. In this work, we adopt a fundamental online mechanism design model where a single expiring item is allocated in each of T periods. Agents with unit demand are present in the market between their arrival and departure periods, which are private information along with the value an agent attributes to the item. For this model, we derive a number of properties characterizing redistribution in online mechanisms (including revenue monotonicity properties, and quantifying the effect an agent can have on the total revenue). We then design two redistribution functions. The first one generalizes the static redistribution proposed by Cavallo [2] making redistribution after the departure of the last agent. For this redistribution function we provide theoretical worst-case guarantees. The second function is truly "online" making redistribution to each agent on her departure. The performance of both functions is evaluated using numerical simulations.@en

With the growing popularity of electric vehicles (EVs), the number of public charging stations is increasing rapidly, allowing drivers to charge their cars while parked away from home or en-route to their destination. However, as a full charge can take a significant amount of time, drivers may face queues and uncertainty over availability of charging facilities at different stations and times. In this paper, we address this problem by proposing a novel, two-sided market for advance reservations, in which agents, representing EV owners, report their preferences for time slots and charging locations, while charging stations report their availability and costs. In our model, both parties are rational, profit-maximising entities, and buyers enter the market dynamically over time. Given this, we apply techniques from online mechanism design to develop a pricing mechanism which is truthful on the buyer side (i.e., drivers have no incentive to misreport their preferences or to delay their reservations). For the seller side, we adapt three well-known pricing mechanisms and compare them both theoretically and empirically. Using realistic simulations, we demonstrate that two of our proposed mechanisms consistently achieve a high efficiency (90-95% of optimal), while offering a trade-off between stability and budget balance. Surprisingly, the third mechanism, a common payment mechanism that is truthful in simpler settings, achieves a significantly lower efficiency and runs a high deficit.

@en

We describe the strategy used by our agent, IAMhaggler2011, which finished in third place in the 2011 Automated Negotiating Agent Competition. A key feature of this agent is the way in which it models the likely negotiation behaviour of its opponent. Specifically, it first uses a Gaussian process regression technique to estimate the future concession of its negotiation opponent. Its concession is then set as a best response to this prediction.

@en

As plug-in electric vehicles become more widespread, their charging needs to be coordinated, in order to ensure that capacity constraints are not exceeded. This is becoming particularly critical as new fast-charging technologies are being developed that place additional burden on local transformers. To address this problem, we propose a novel online mechanism in which agents representing vehicle owners are incentivised to be truthful not only about their marginal valuations for electricity units, but also about their arrival, departure and maximum charging speeds. The work extends the state of the art in several ways. We develop an online, model-free mechanism that handles multi-unit demand per period, thus accommodating vehicles with heterogeneous and flexible charging speeds; we provide competitive worst-case bounds for our mechanism; finally, we simulate the proposed online mechanism using data from a real-world trial of electric vehicles in the UK, showing that using fast charging leads to significant cost savings.@en

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

We describe the strategy used by our agent, IAMhaggler, which finished in third place in the 2010 Automated Negotiating Agent Competition. It uses a concession strategy to determine the utility level at which to make offers. This concession strategy uses a principled approach which considers the offers made by the opponent. It then uses a Pareto-search algorithm combined with Bayesian learning in order to generate a multi-issue offer with a specific utility as given by its concession strategy.@en

In this paper we present a novel option pricing mechanism for reducing the exposure problem encountered by bidders with complementary valuations when participating in sequential, second-price auction markets. Existing option pricing models have two main drawbacks: they either apply a fixed exercise price, which may deter bidders with low valuations, thereby decreasing allocative efficiency, or options are offered for free, in which case bidders are less likely to exercise them, thereby reducing seller revenues. Our novel mechanism with flexibly priced options addresses these problems by calculating the exercise price as well as the option price based on the bids in an auction. For this novel setting we derive the optimal strategies for a bidding agent with complementary preferences. Furthermore, to compare our approach to existing ones, we derive, for the first time, the bidding strategies for a fixed price mechanism, in which exercise prices for options are fixed by the seller. Finally, we use these strategies to empirically evaluate the proposed option mechanism and compare it to existing ones, both in terms of the seller revenue and the social welfare. We show that our new mechanism achieves higher market efficiency, while still ensuring higher revenues for the seller than direct sale auctions (without options).

@en

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

We propose a new scheme for efficient demand side management for the Smart Grid. Specifically, we envisage and promote the formation of cooperatives of medium-large consumers and equip them (via our proposed mechanisms) with the capability of regularly participating in the existing electricity markets by providing electricity demand reduction services to the Grid. Based on mechanism design principles, we develop a model for such cooperatives by designing methods for estimating suitable reduction amounts, placing bids in the market and redistributing the obtained revenue amongst the member agents. Our mechanism is such that the member agents have no incentive to show artificial reductions with the aim of increasing their revenues.@en

We propose a novel strategy to enable autonomous agents to negotiate concurrently with multiple, unknown opponents in realtime, over complex multi-issue domains. We formalise our strategy as an optimisation problem, in which decisions are based on probabilistic information about the opponents' strategies acquired during negotiation. In doing so, we develop the first principled approach that enables the coordination of multiple, concurrent negotiation threads for practical negotiation settings. Furthermore, we validate our strategy using the agents and domains developed for the International Automated Negotiating Agents Competition (ANAC), and we benchmark our strategy against the state-of-the-art. We find that our approach significantly outperforms existing approaches, and this difference improves even further as the number of available negotiation opponents and the complexity of the negotiation domain increases.@en

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

In multi-issue automated negotiation against unknown opponents, a key part of effective negotiation is the choice of concession strategy. In this paper, we develop a principled concession strategy, based on Gaussian processes predicting the opponent's future behaviour. We then use this to set the agent's concession rate dynamically during a single negotiation session. We analyse the performance of our strategy and show that it outperforms the state-of-the-art negotiating agents from the 2010 Automated Negotiating Agents Competition, in both a tournament setting and in self-play, across a variety of negotiation domains.@en