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

Demand-side response (DR.) is emerging as a crucial technology to assure stability of modern power grids. The uncertainty about the cost agents face for reducing consumption imposes challenges in achieving reliable, coordinated response. In recent work, Ma et al. [13] introduce DR as a mechanism design problem and solve it for a setting where an agent has a binary preparation decision and where, contingent on preparation, the probability an agent will be able to reduce demand and the cost to do so are fixed. We generalize this model to allow uncertainty in agents' costs of responding, and also multiple levels of effort agents can exert in preparing. For both cases, the design of contingent payments now affects the probability of response. We design a new, truthful and reliable mechanism that uses a "reward- bidding" approach rather than the "penalty-bidding" approach It has good performance when compared to natural benchmarks. The mechanism also extends to handle multiple units of demand response from each agent.@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

We study the problem of incentivizing reliable demand-response in modern electricity grids. Each agent is uncertain about her future ability to reduce demand and unreliable. Agents who choose to participate in a demand-response scheme may be paid when they respond and penalized otherwise. The goal is to reliably achieve a demand reduction target while selecting a minimal set of agents from those willing to participate. We design incentivealigned, direct and indirect mechanisms. The direct mechanism elicits both response probabilities and costs, while the indirect mechanism elicits willingness to accept a penalty in the case of non-response. We benchmark against a spot auction, in which demand reduction is purchased from agents when needed. Both the direct and indirect mechanisms achieve the reliability target in a dominant-strategy equilibrium, select a small number of agents to prepare, and do so at low cost and with much lower variance in payments than the spot auction.@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

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