Incentivizing Reliability in Demand-Side Response

1 Introduction

A crucial aspect of operating an electric power system is that an exact balance between supply and demand must be maintained at all times. Electricity grids are facing a number of new challenges in this regard, due to both the increasing number of intermittent renewable generation resources [Su et al., 2014; Zhang et al., 2015], and the presence of more volatile types of loads, such as those from electric vehicle charging [Robu et al., 2013].

These challenges have led to an increased interest in demand-side response (DR), in which consumers (industrial, commercial, or domestic) commit to temporarily reduce or shift consumption away from periods with low generation capacity [Palensky and Dietrich, 2011]. A number of DR aggregation services exist to facilitate this process, and intermediate between distribution network operators (DNOs) and consumers. These range from those operated directly by DNOs,

Valentin Robu

Heriot Watt University V.Robu@hw.ac.uk

David C. Parkes

Harvard University parkes@eecs.harvard.edu

to commercial services. 1

We model demand response as a two-step process. First, consumers opt-in to a DR scheme, possibly sharing information about their cost to respond if asked, and their probability of being able to respond. Some, perhaps all, of these consumers are selected and asked to prepare for the possibility of demand reduction. Second, in the event that a demand reduction is required, then some, perhaps all of the selected consumers are asked to reduce demand, and may receive a payment or pay a penalty depend on whether or not they followthrough and respond.

DR aggregators are not interested only in those consumers with lowest cost, but also in consumers who are reliable, and most likely to respond if needed. Selecting reliable consumers allows a target to be met with high confidence while asking fewer consumers to prepare, leading to less economic disruption. It is natural that consumers will not always be able to respond. Consider an industrial factory for example, which uses electricity for the production line, transporting raw materials, and cooling. Its ability to respond in a DR event is highly uncertain; e.g., it may depend on the production procedure, time of day, customer requests, and weather conditions.

From a mechanism design perspective, the goal is to reliably meet a target reduction while minimizing the number of agents who are selected. There are a number of interrelated challenges: (1) incentivize consumers to opt-in to the scheme, (2) truthfully elicit information about reliability and cost, (3) select a small, reliable set of agents to ask to prepare, and (4) set up payments and penalties so that those who are selected will choose to follow-through if asked and if able to reduce demand. Simple approaches fail. For example, setting a high fixed penalty for not reducing demand when asked would ensure follow-through, but not provide incentives for opt-in.

We advance two related designs: a direct mechanism that elicits both costs and probabilities directly, and an indirect mechanism that elicits only willingness to accept a penalty in the case of non-response, from which response probabilities are inferred. The mechanisms fix a payment that will be made to agents for demand response, and select agents in decreasing order of the maximum acceptable non-response penalties until the reliability target is met. Both mechanisms have a simple dominant-strategy equilibrium, meaning truthful reporting in the direct mechanism and truthfully reporting the maximum acceptable penalty in the indirect mechanism.

1 Examples include Enernoc, Kiwi Power or Upside Energy.

In an experimental evaluation with a wide range of parameter values, we show that the mechanisms achieve close to the first best (i.e. assuming the mechanism knows agent types and can choose the most reliable ones) with regard to the number of agents who are selected and asked to prepare. We also benchmark against a spot auction, in which demand reduction is purchased from agents when needed. The spot auction has a higher total cost as well as a very large variance in payments, making the scheme risky for both the agents and the grid, as well as susceptible to collusion.

1.1 RelatedWork

To our knowledge, this is the first application of mechanism design for eliciting cost and probability information from consumers in order to achieve reliable demand response. A number of papers in the power systems literature discuss the use of DR aggregation [Zhang et al., 2015; Su et al., 2014]. Although not an approach of mechanism design, there is also some prior work on market design for demand response (e.g. [Li et al., 2015; Johari and Tsitsiklis, 2011; PJM, 2015]), proposing to allow for bids of supply or cost curves, and discussing market equilibria. Other papers [De Vries and Heijnen, 2008; Kwag and Kim, 2014] have considered reliability in DR but from a policy (non mechanism-design) perspective. There are also works that design contracts for load control, aiming at for example maximizing the system payoff while satisfying other operational constraints [Balandat et al., 2014; Haring et al., 2013; Yang et al., 2015], but again without taking a mechanism design viewpoint. Others have proposed to use scoring rules to incentivize truthful reports about expected future consumption in power grids [Rose et al., 2012; Robu et al., 2012; Akasiadis and Chalkiadakis, 2013], which do not apply to our setting because they do not set penalties correctly in order to provide incentives for follow-through if needed.

On the mechanism design side, the inspiration for our approach is the work to promote capacity utilization [Ma et al., 2015]. In a sense, ours' is the inverse problemwhere we want to promote capacity reduction rather than utilization. An additional, technical aspect of the present problem is to consider the question of how to select a number of agents in order to probabilistically meet a system reliability target.

2 The Demand Side Response

In the demand side response problem, the planner is the electricity grid (or DR aggregator) and the agents are consumers of electricity interested in offering DR services. Let N = ¶1↪ 2↪ ▷ ▷ ▷ n♦ denote the set of agents. Each agent can prepare for demand response ahead at a cost of ci ≥ 0. We consider the simple setting in which each agent demands the same quantity (a single unit, w.l.o.g.). Our results easily extend to agents with heterogeneous demand sizes. If an agent prepares to reduce demand, then she is able to reduce demand with probability pi 2 (0↪ 1), at the cost of vi ≥ 0. The amount vi represents the opportunity cost for the loss of electricity. The triple ✓i = (vi↪ pi↪ ci) defines an agent's type, and is agent i's private information. Let ✓ = (✓1↪ ▷ ▷ ▷ ↪ ✓n) denote a type profile. We assume that the agents' abilities to respond are independent to each other. In our model, an agent can only respond if she first prepares. 2

Reliability Target. Denote M 2 N+ as the target capacity reduction that needs to be achieved. The designer's objective is to select a minimal set of agents to prepare for DR ahead of time such that the target reduction is met with probability at least ⌧, where ⌧ 2 (0↪ 1) is a system-wide reliability target. We make a deep market assumption, which is that there are enough agents in the economy that it is possible to meet the reliability target. This holds for most real DR markets.

Example 1. Suppose target M = 1 and probability ⌧ = 0▷9, and there are three agents with p1 = 0▷8, p2 = 0▷6, and p3 = 0▷4. If only agent 1 prepares, 1 unit of power is provided with probability 0▷8 < ⌧ thus the reliability target is not met. If both agents 1 and 2 prepare, the probability with which no one is able to respond is (1 - p1)(1 - p2) = 0▷08 < 1 - ⌧ = 0▷1, and the reliability requirement is met.

Two-Period Mechanism. We consider mechanisms that run over two time periods which use a fixed reward R > 0 and a variable penalty per agent. The timeline is as follows (see Figure 1):

Period 0:

• ÷ Agents can choose to report information to the mechanism, with knowledge of their type and the demandresponse reward R.
• ÷ The mechanism determines for each selected agent i the period-one penalty ti ≥ 0 in case of non-response.
• ÷ With the knowledge of ti and R, each selected agent decides whether to prepare for demand response.

Period 1:

• ÷ If agent i can respond (with probability pi) she decides whether or not to do so with the knowledge of ti and R.
• ÷ For selected agent i, the mechanism pays R upon response, and charges ti ≥ 0, otherwise.

Note that neither the selected agents' choice on preparation or their ability to respond are observable.

The structure of the design is well motivated, representing a small change from the current practice by DNOs and aggregators. In current practice, as in our model, selected agents do not receive a payment when asked to prepare, and the amount of payment made to an agent in the event of demand response is fixed. The new ingredients are that we elicit type information in period zero, and use this both to decide who to select, and also to set a penalty in the event of non-response.

2 In practice, advance notification is required to perform demand response at a reasonable cost [Borenstein et al., 2002].

A demand-response mechanism is dominant strategy incentive compatible (DSIC) if truthful reporting maximizes each agent's expected utility regardless of the reports of other agents, and conditioned on the agent making rational decisions in period one (see below). A demand-response mechanism is individually rational (IR) if each agents' expected utility for (truthful) participation is non-negative. Informally, a DSIC mechanism is "truthful" and an IR mechanism ensures that agents will choose to participate.

Rational Decisions and Expected Utilities. How should an agent i with type ✓i = (vi↪ pi↪ ci), who reports truthfully and is selected, and now faces a reward R and penalty ti, behave in the mechanism? Consider the following cases:

1. If the agent does not prepare, she is unable to respond and her utility will be -ti.
2. If the agent does prepare, and is able to respond in period one and decides to do so, her utility is R - vi - ci.
3. If the agent does prepare, but is not able to or decides not to respond in period one, her utility will be -ti - ci.

For any agent with vi > R, her utility is negative for all ti ≥ 0. As we will see later such agents will not be selected by the mechanisms for DR. Assume now that R > vi. If the agent prepares and is able to respond, then it is rational to respond because R-vi -ci > -ti -ci. If the agent decides to prepare, her expected utility is,

For (R - vi)pi - ci < 0, the expected utility, whether preparing or not, would be negative as long as the penalty ti ≥ 0, and she will not be selected by the mechanisms. Assume for now that (R - vi)pi - ci ≥ 0. Such an agent will choose to prepare (getting u(R↪ ti) rather than -ti) and also choose to respond if possible. The expected utility ui(R↪ ti) decreases linearly with slope 1-pi as the penalty ti increases. A simple example with two agents is shown in Figure 2.

Let z ≥ 0 denote the penalty that represents the unique zero crossing point of u(R↪ t), such that u(R↪ z) = 0. This is the maximum penalty that the agent is willing to pay:

Fixing vi and ci, the higher the probability pi and the more reliable the agent, the slower her expected utility ui(R↪ ti) decreases with ti, the shallower the utility curve, and the larger the crossing point, zi. For example, agent 1 in Figure 2 has a larger willingness to pay, although the expected reward she gets from the grid minus her cost (the y-intercept) is lower.

3 The Direct Mechanism

We now design a truthful, direct mechanism for demand response. The mechanism selects agents in decreasing order of willingness to pay until the reliability target is met.

Definition 1 (The Direct Mechanism with Reward R). The direct mechanismMdir(R) collects reported type profile ˆ ✓ = (ˆ ✓1↪ ▷ ▷ ▷ ↪ ˆ ✓n), and computes the willingness to pay ˆ zi according to (2). Assume w.l.o.g. that ˆ z1 ≥ ˆ z2 ≥ · · · ≥ ˆ zn (breaking ties arbtirarily). Let Xi be a Bernoulli random variable with parameter ˆ pi if ˆ zi ≥ 0 and let Xi ⌘ 0 if ˆ zi < 0.

• ÷ Selection rule (period zero): xi(ˆ ✓) = 1 for i  m and ˆ zi ≥ 0, and xi(ˆ ✓) = 0 for i > m, where the last agent selected is,
• ÷ Payment rule (evaluated in period zero, payments made in period one): make payment R to any selected agent who reduces demand. If selected, charge agent i a penalty amount ti(ˆ ✓) = ˆ zm-i for no response, where

is the agent with the smallest willingness to pay that would be selected in an economy without agent i. Demand reduction is not accepted from any unselected agent, and her payment is zero.

Note: We've focused for clarity on describing the typical case (given our assumption about a deep market) that (3) has a solution, i.e. there are enough agents participating at current reward level R. If not, the mechanism simply selects all agents and charges no penalty.

For intuition for payments, the quantity ti(ˆ ✓) = ˆ zm-i is the minimum payment that agent i needs to be willing to accept as penalty in order to be selected, and this is independent of agent i's own report.

Example 2. Suppose M = 1 needs to be reduced with probability at least ⌧ = 0▷75, and the grid pays a reward R = 6 for demand reduction. There are three agents, with types

• Agent 1: v1 = 1, p1 = 0▷9, c1 = 1
• Agent 2: v2 = 1, p2 = 0▷7, c2 = 1
• Agent 3: v3 = 1, p3 = 0▷6, c3 = 1

For truthful reports, the zero-crossings are z1 = 35↪ z2 = 8▷3 and z3 = 5. We first allocate to agent 1. Since P [X1 ≥ M] = p1 > ⌧, agent 1 is the only agent that is selected.

In the economy without agent 1, we would first allocate to agent 2. Since P [X2 ≥M] = p2 < ⌧, allocating to only agent 2 is not enough to satisfy the reliability requirement. Thus we also allocate to agent 3 and we can check P [X2 +X3 ≥ M] > ⌧ . Therefore, m-1 = 3, and agent 1's penalty is t1(✓) = zm-1 = 5 if she does not respond.

The rational decision of agent 1 is to prepare and respond if possible, and her expected utility is u1(R↪ t1) = 3 > 0. It's easy to see that for all report ˆ ✓1 of agent 1 s.t. ˆ z1 ≥ z3, agent 1 would be selected and face the same payments since agent 2 herself cannot meet the reliability target. Making reports s.t. ˆ z1 < z3, agent 1 would not be selected thus gets utility zero. Truthful reporting is therefore a dominant strategy. ⇤

For each agent, the two possible alternatives under the direct mechanism are that she is selected or not. Now we show that the mechanism satisfies agent-independence and agent maximizing, thus is DSIC [Nisan, 2007]. Agentindependence requires that each agent faces prices for each alternative that are independent of their own report, and agent maximizing means that the mechanism selects the alternative that maximizes her utility under such prices.

Theorem 1. The direct mechanism is DSIC, IR and always meets the reliability target for a sufficiently large R.

Proof. First, note that for a selected agent the penalty ti = zm-i and reward R are independent of ˆ ✓i. Also, there is no payment to or from unselected agents thus payments satisfy agent-independence.

Fix an agent i. If xi(ˆ ✓) = 1, we know i  m and P hPi-1 i0=1 Xi0 ≥ M i < ⌧ . This implies that m-i ≥ i+1, and thus ti = zm-i  zi. Agent i's expected utility for preparing ui(R↪ ti) ≥ ui(R↪ zi) = 0, i.e. selecting agent i is agentmaximizing for her, comparing with not selecting which results in utility zero. If agent i is not selected, then i > m (as computed in (3)) or zi < 0. If zi < 0, ui(Ri↪ ti) < 0 for all ti ≥ 0 thus if selected agent i gets negative utility. If i > m, m-i = m and ti = zm-i ≥ zi thus expected utility from preparing ui(R↪ ti)  0. Not selecting her is agentmaximizing, which gives her utility zero.

Combining the two cases we see that the mechanism is DSIC. From the above argument, we also see that the expected utility for all agents are non-negative thus IR follows.

With R high enough, zi ≥ 0 for all agents i thus (3) can be met due to the deep market assumption. It follows from rational decisions in period one that all selected agents will choose to prepare and then reduce demand when possible, and that the mechanismwill achieve its reliability target.

The mechanism does not necessarily select the most reliable agents, since the zero-crossings zi's are not always aligned with the pi's, and we cannot allocate in decreasing order of the reported pi's while retaining incentive alignment.

3.1 Reliability Evaluation

The total quantity of demand reduction by a set S of selected agents, X = Pi2S Xi, is a Poisson-binomial distributed random variable [Chen and Liu, 1997]. The CDF of X is

where F` is the set of all subsets of S that are of cardinality `, and Ac = S ∩ A. A naive way of evaluating the CDF requires computing the sum of an exponential number of terms. However, exact polynomial time algorithms based on recursive methods [Radke Jr and Evanoff, 1994] or Fourier Transform [Fern´andez and Williams, 2010] exist, and return the CDF of a summation of a thousand random variables within seconds. Hence, we adopt the Fourier Transform approach in the experiments reported here. 3

4 The Indirect Mechanism

The direct mechanism asks for the full type of each agent and computes the willingness to pay using the reported costs and reliability. For simplicity, and also to better protect the private cost information of participants, we introduce an indirect mechanism, which elicits a single bid from each agent, estimates the pi's of each agent from the bid, and then evaluates the reliability target using the estimated pi's.

We can compute a bound on reliability pi from the willingness to pay. We know from (2) that

where the inequality holds since ci↪ vi ≥ 0. Note that with fixed R, the expression zi◁(zi +R) is monotone in zi. Let bi be agent i's bid, and b = (b1↪ ▷ ▷ ▷ ↪ bn) denote a bid profile.

Definition 2 (The Indirect Mechanism with Reward R).

1. Reports: The indirect mechanism Mind(R) collects a single bid bi from each agent, representing the maximum willingness to accept a penalty in the case of non-response. Assume w.l.o.g. that b1 ≥ · · · ≥ bn (breaking ties arbitrarily).
2. Inference: Let ˜ pi = bi◁(bi +R) and ˜Xi be a Bernoulli random variable with parameter ˜ pi .
3. Outcome: The indirect mechanism determines selection and payments as in the direct mechanism, simply replacing Xi with ˜Xi and zi with bi.

Theorem 2. It is a dominant strategy for each agent to bid b⇤i = zi under the indirect mechanism. The indirect mechanism is IR and meets the reliability target for R large enough.

Proof. Consider an agent with zero-crossing zi. If she bids bi = zi and does not get selected, we know that m-i = m as computed in (3) and i > m. Bidding lower than bm-i would not change her utility. Bidding higher than bm-i means that agent i would be selected and get charged bm-i > zi, thus get negative utility in expectation.

If an agent bids bi = zi and gets selected, we know m-i > i must hold and ti(b)  zi, thus agent i gets non-negative utility in expectation. Bidding weakly above bm-i would not change her utility. Bidding below bm-i , the agent i would not get selected thus would get utility zero.

Combining the above two cases, we know that it's a dominant strategy to bid b⇤i = zi. Therefore under the DSE,

3 The Chernoff bound [Chernoff, 1952] and other large deviation bounds can also be used to approximate this expression, and would select slightly more agents than necessary but provide an easy way of evaluating reliability while retaining truthfulness.

˜ pi = b⇤i ◁(b⇤i + R) = zi◁(zi + R) is a lower bound on the reliability pi of each agent. With similar argument as in the direct mechanism we know that selected agents always prepare and choose to respond when possible, thus the reliability requirement is always met with large enough R.

Example 2. (continued) Continuing the earlier example, in the indirect mechanism, agents bid their willingness to pay, b⇤1 = 35↪ b⇤2 = 8▷3 and b⇤3 = 5, and the estimated probabilities are ˜ p1 = 0▷85↪ ˜ p2 = 0▷58, and ˜ p3 = 0▷45. With M = 1 and ⌧ = 0▷75, it suffices to select only agent 1 since she will respond with probability at least ˜ p1 = 0▷85. We can check that in the economy without agent 1, both agents 2 and 3 need to be selected, thus the penalty agent 1 would be charged in case of non-response is b3 = 5. In this case, the outcome is the same as the outcome of the direct mechanism.

Suppose instead that ⌧ = 0▷9. Now, from the estimated reliability, agent 1 does not appear to be sufficient to meet the target in the indirect mechanism, even though she is actually able to meet the reliability target. In this case, the two mechanisms would have different outcomes. ⇤

Observe that the gap pi - ˜ pi is small while vi and ci are small, since the (conservative) inference approach approximates them by adopting zero. Also, the gap is small when pi is large, since with large pi the zero-crossing zi is high thus vi and ci are less significant. Since we select agents in decreasing order of zi, we are selecting the set of agents for which the bounds are relatively tight.

5 AComparison with a Spot Auction

For a simple comparison, we adopt a spot auction, where we run an M + 1st-price auction with a reserve price r, i.e. the reserve sets an upper bound on the reward payment. This auction is run in period one in the event that DR is required, and without pre-selection in period zero of which agents should invest effort and prepare. Rather, agents need to reason about possible payments from the auction in period one in order to decide whether to prepare in period zero.

For simplicity, we will study a complete information Nash equilibrium of the period-zero preparation decisions under the spot auction mechanism (i.e., assuming bidders know each others' values.)

Definition 3 (Spot Auction with Reserve r). The Spot Auction Spot(r) collects a single bid bi from each agent at period one, and chooses the M lowest bidders to reduce their consumption, making payment to each agent equal to the minimum of the M + 1st lowest bid and the reserve price r. Denote b = (b1↪ ▷ ▷ ▷ ↪ bn) as a bid profile and assume w.l.o.g. that b1  · · ·  bn (breaking ties arbitrarily.)

• ÷ Payment rule: pay allocated agents min(r↪ bM+1). No payment to or from unallocated agents.
• ÷ Allocation rule: xi(b) = 1, if i M and bi  r.

The period one strategic problem for an agent in the spot auction is straightforward. An agent who has prepared, and is now able to respond at a cost of vi has a dominant strategy to bid b⇤i = vi. What is challenging for an agent is to decide whether or not to invest effort and prepare in period zero.

5.1 Period-Zero Preparation Decision

For simplicity, assume that every agent has the same cost of preparation ci = c, and the same probability of being able to respond pi = p. As earlier in the paper, we assume np ≫ M, so that if all agents prepare the capacity requirement will be met with high probability.

Assume w.l.o.g. v1  · · ·  vn so that the agents with lower index find it less costly to reduce demand, and denote ⇡i as the probability that agent i prepares for demand response. Let Xi be a Bernoulli random variable with probability pi (=p) and let X(m) = Pmi=1 Xi.

Proposition 1 (Pure Strategy Nash Equilibrium in preparation). Under the spot auction with capacity M and reserve price r, there is a pure Nash equilibrium where each agent i prepares according to:

The threshold mr is the largest index mr =maxm2N m s.t.

If there is no such agent, then mr = 0 and ⇡⇤ i = 0, 8i.

We give the intuition for this result. First, observe that if an agent prepares and is able to respond, the highest amount that she can get paid is bounded by r. When mr = 0, we have (r - v1)p - c < 0, which implies that even the lowestcost agent always loses in expectation by preparing and thus ⇡⇤ i = 0 is the unique equilibrium.

Assume now that mr > 0. We can check that the left hand side of (7) is the expected utility of agent m assuming agents i  m all prepare with probability 1 and agents i > m all prepare with probability 0. Therefore agent mr gets non-negative utility under (6), and we can check agents i < m get non-negative utility from preparation, and that for an agent i > m, deviate from ⇡⇤ i and prepare would result in an expected utility smaller than zero.

5.2 Reserve r and Reliability Target

Under the same setup as in Section 5.1, in order to meet the reliability target ⌧, we need to make sure that a minimum number of agents m⇤ such that P ⇥X(m⇤ ) ≥M ⇤ ≥ ⌧ are preparing in equilibrium. We know from (7) that this requires (r - vm⇤) · p · P ⇥X(m⇤-1) M -1⇤ - c ≥ 0 which can be rewritten as a lower bound on the reserve price r ≥ vm⇤ + c◁ (p · P ⇥X(m⇤-1) M -1⇤). When M is large, P ⇥X(m⇤-1)  M - 1⇤ and P ⇥X(m⇤ )  M ⇤ are close thus the reserve price needs to be r ⇡ vm⇤ + c◁ (p(1 - ⌧)). As ⌧ becomes close to 1, the minimum reserve required to meet the reliability target is a lot larger than both c and vi.

Remark: The only way that the spot auction can meet the reliability target is to set a huge reserve price, which is paid with a very small probability close to 1 - ⌧. Although an equilibrium strategy exists, participation in the spot auction is essentially a lottery for both the agent and mechanism designer. Most of the time the capacity is met and the M + 1st bid is paid, but once in 1◁(1-⌧ ) events the mechanism makes a very large payment due to the huge reserve price. Hence, agents must be willing to gamble by preparing for DR. Moreover, the potential high payoff (much higher than in the direct mechanism) makes the spot auction susceptible to collusion.

6 Simulation Results

We show in this section via simulation that the direct and indirect mechanisms have good performance, comparing with the best possible outcome (in a world without private information) as well as the spot auction.

Direct, Indirect Mechanisms v.s. First Best We compare the number of agents selected by the direct and indirect mechanisms with what we call the "first best," which assumes that the mechanism knows the types of agents and can select agents in decreasing order of pi's (this would not be truthful). Let the total number of agents be n = 500 and the types be iid from the distributions: vi ⇠ U[0↪ 2], ci ⇠ U[0↪ 2], pi ⇠ U[0↪ 1]. We first assume that the grid pays reward R = 10, and would like to achieve a capacity of M = 100.

With ⌧ varying from 0▷9 to 0▷999, the average number of selected agents over 1000 economies are as shown in Figure 3(a). The horizontal axis -log10(1 - ⌧) translates ⌧ = 0▷9 to 1 and ⌧ = 0▷999 to 3. We can see that under both the direct and indirect mechanisms, more agents are selected when ⌧ increases. Both mechanisms are doing well comparing with the first best, and the indirect mechanism selects roughly 10 more agents due to the estimation of pi's.

Fixing ⌧ = 0▷98, the effect of varying reward R is as shown in Figure 3(b). The numbers of selected agents decrease in both mechanisms as R increases, since with higher R, the willingness to pay zi's are more aligned with the reliability pi so the mechanisms are effectively selecting agents that are more reliable. For the indirect mechanism, increasing R also improves the inference on pi and we see an additional significant drop in the number of selected agents.

As the reward R increases, both the reward and the penalty increase, however the increase in total paid rewards outweigh the additional penalty collected. The effect is that the total (expected) cost increases as the reward R increases (figure not included due to space limit). The cost under the indirect mechanism is typically 5% to 10% (depending on R) larger since more agents are selected.

Direct Mechanism v.s. Spot Auction. Consider a fixed economy with n = 1000 agents, each of whom has the same pi = 0▷8 and ci = 2. Assume that vi = i◁100, so that the agents with lower index find it less costly to reduce demand. For comparison between the direct mechanism and the spot auction, we set the reward R and reserve r (in the direct and spot, respectively) to be the minimum values such that a minimum number of agents (denoted m⇤ ) prepares thus M = 100 units are guaranteed with probability ⌧ . For the direct mechanism, R needs to be large enough such that m⇤ agents have non-negative zero crossings, and for the spot auction r needs to incentivize m⇤ agents to prepare in equilibrium.

The mean and standard deviation (std) of the total costs (reward payments minus collected penalties for the direct mechanism) computed over 1 million economies are shown in Figure 4. The total cost under the direct mechanism is lower than that of spot auction, moreover, the std of the total costs under the spot auction is extremely high.

This is because under the spot auction, the total cost are low most of the times (when the M+1th bid is paid), however, with probability close to 1 - ⌧ the huge reserve price is paid, and this results in a huge variance in the total payments. Given the high variability of the payment (and the high payoff from colluding), we conclude a spot auction is less practical than the two-period mechanisms.

7 Conclusions

We studied the problem of incentivizing truthfulness when selecting from a number of unrealiable providers in demand response. We introduce two new, dominant-strategy equilibrium mechanisms. The mechanisms are almost first-best in their ability to select a small number of reliable agents, and achieve lower payments and lower variance in payments than the spot auction. In future work, we plan to understand whether it is possible to meet the reduction target with high probability without reducing beyond the target and while retaining dominant-strategy equilibrium. Another interesting direction is to consider agents for whom the probability of responding is a function of the effort invested in preparation.

Acknowledgments

Parkes is supported by the SEAS TomKat fund, Li by NSF CAREER 1553407, and Robu by EPSRC EP/P001173/1: Centre for Energy Systems Integration.