Pricing Under Uncertainty in Multi-Interval Real-Time Markets

1. Introduction

1.1. Motivation

In a regime of large-scale renewable resource integration, the multiperiod and uncertainty effects of renewable resources are becoming increasingly important. Flexibility, in the sense of the ability of resources to respond rapidly to real-time conditions (Schiro 2017), is becoming a valuable resource for system operators. Two important challenges that system operators face in real time are to arrive to efficient dispatch decisions but also prices that provide an incentive to flexibility providers to offer their resources voluntarily to the market. Concretely, the real-time market is operated at a time step of 5 − 15 minutes in U.S. and E.U. markets and determines the dispatch of resources such as storage, pumped hydro plants, combined cycle units, and demand response that can respond rapidly to the significant and often unpredictable variations of renewable supply. Look-ahead matters in this respect because these resources have intertemporal constraints such as ramp limits, state of charge limits, startup/shutdown costs, and so on. An increasingly important challenge in real-time market operations is to account for these intertemporal effects because ramp episodes induced by renewable resources are placing increasing stress on the system. And prices need to match the increasingly complex schedules; otherwise, system operators are facing the threat that flexibility owners may “take matters in their own hands” by self-committing or self-scheduling their resources at a time when these flexibility resources are needed most. Therefore, it is imperative that the price signal that accompanies the central dispatch decision match the profit-maximizing objectives of flexible resource owners. This challenge has placed multiperiod pricing in real-time markets at the spotlight of stakeholders and academics in recent years.

1.2. Market-Clearing Proposals in the Literature

In what follows, we revisit the existing literature on multiperiod pricing. Although this literature has been cast in the context of price consistency, our approach is rather to connect the literature to a related but different notion, that of equilibrium. An equilibrium is a pair of prices and quantities such that the market clears and the prices support the dispatch for profit-maximizing agents. We comment along the way on its relation to price consistency and other metrics that are often monitored and deemed important in market operations.

1.2.1. Single-Period Market Clearing.

For each agent $k\in K$, an abstract formulation of single-period market clearing models can be written as follows:

where x_k denotes the amount of power generation, f_k denotes the cost function, h_k denotes intertemporal constraints such as ramp constraints, with $x_k^{\#}$ being a given initial condition (the amount of power generation in the previous time step), X_k denotes constraints for each k that do not depend on time such as generation output limits, and p denotes the dual multiplier of the power balance constraint. Observe the generality of this formulation. For example, if an agent k is a network owner and y is a vector representing net demand for each node in the network, then the transmission network can be incorporated in this formulation, with x_k being the vector of the power flows of each line and X_k containing optimal power flow constraints and transmission capacity constraints. In the remainder of our paper, we assume that the functions $f_k,h_k$ are convex.

Basic convex optimization arguments establish that the solution of the fully coordinated problem provides the optimal price and quantity. The optimal price and quantity pair $(p^{*},x^{*})$ forms an equilibrium because $p^{*}$ supports $x_k^{*}$ for profit-maximizing agents. In other words, for each agent $k\in K,\hspace{0.17em}{x}_k^{*}$ is an optimal profit-maximizing solution under the price $p^{*}$. This is the approach adopted in real-time market clearing in ISO-NE, MISO, PJM, SPP (Schiro 2017), and future integrated E.U. balancing platforms (EC 2017).

1.2.2. Multi-Period Deterministic Market Clearing.

In a multiperiod deterministic setting, the notion of an equilibrium can be extended if the quantities clear for every period and if the dispatch is profit-maximizing over the full horizon. Consider an economic dispatch problem over the time interval $[t_s,t_e]$. Let us define the following optimization problem as LAD(t_s, t_e), an abbreviation of Look Ahead Dispatch Model (LAD). This term is used in Hua et al. (2019):

where the intertemporal constraints are divided into two parts in order to clearly show the treatment of initial conditions ($x_{k,t_s-1}^{\#}$). For the brevity of the paper, the initial condition is implied, and the set of constraints will be written as $h_k(x_{k,t-1},x_{k,t})\le 0,k\in K,t\in [t_s,t_e]$ in the remainder of the paper.

In practice, multiperiod deterministic models can be categorized as either static, rolling with a fixed horizon, or rolling with a moving horizon. In a one-shot, multiperiod market-clearing model, we run the dispatch and pricing model once and clear prices and quantities for the entire horizon at the beginning of the horizon. The same convex optimization arguments as in the static case guarantee that a centralized optimization problem yields the equilibrium result (Baldick 2006). The static setting is easy to study but unrealistic. The most realistic assumption is a rolling multiperiod market-clearing model with a moving horizon as in Figure 1(b), where the look-ahead length is fixed and we run the model multiple times for clearing (Mickey 2015, Hogan 2020). As time moves forward we fix the decisions for the current time step (e.g., t_s), and at the next time step we solve another optimization problem, including new information for the future demand (e.g., LAD$(t_s+1,t_e+1)$). This is the approach currently adopted in CAISO, NYISO (Schiro 2017) and under consideration in Texas (Mickey 2015). However, this setting is very difficult to study. Thus, most, if not all, previous research has focused on the case of rolling with fixed horizon (Hogan 2016, Hua et al. 2019, Guo et al. 2019, Zhao et al. 2019, Biggar and Hesamzadeh 2020, Hogan 2020, Guo et al. 2021). In this setting we still run market-clearing models multiple times, but we know when the end of the horizon is, and even from the beginning we can access to the demand information at the end of the horizon. Notice that in Figure 1(a), which corresponds to a multiperiod model with a fixed horizon, all the bars (representing the time coverage of a market-clearing model) have the same ending at t_T.

1.2.2.1. Metrics for Deterministic Multi-Period Market Clearing.

Two metrics that are often employed in practice for assessing the quality of market-clearing solutions are lost opportunity cost (LOC) and make-whole payments (MWP). Given a pair of price-quantity time series, lost opportunity cost (LOC) refers to the difference between the maximum profit that could have been ensured by an agent that is reacting freely to prices and the profit of an agent that follows the dispatch schedule of the system operator. Zero LOC is equivalent to an equilibrium. For price-quantity pairs that do not constitute an equilibrium, make-whole payments (MWP) are nonzero whenever the cost of a deployed resource exceeds the revenue that is obtained by following the dispatch instructions of the system operator.

1.2.2.2. Rolling Multi-Period with a Fixed Horizon.

For a rolling multiperiod planning with a fixed horizon, it would be tempting to argue that one should solve the dispatch problem at every time stage (as in model predictive control) and keep current-period dispatch decisions and prices as the market-clearing quantities and prices. The resulting sequence of prices and quantities actually turns out not to carry guarantees of being an equilibrium price-quantity pair. This is due to dual degeneracy (Biggar and Hesamzadeh 2020).

One way to relieve this issue is to utilize the dual multipliers from the past dispatch problems. Hogan (2016) used power balance constraints and Hua et al. (2019) used intertemporal constraints for the dual multipliers. In this work, we introduce the method of Hogan (2016) that used power balance constraints, and we generalize it in the next section to the case of uncertainty. Consider a time interval $[t_s,t_e]$. Assume that the current time step is t_c, where $t_s<t_c<t_e$, and the past decisions $x_0^{\#}=\{x_{t_s}^{\#},\dots ,x_{t_{c-1}}^{\#}\},\hspace{0.17em}{p}_0^{\#}=\{p_{t_s}^{\#},\dots ,p_{t_{c-1}}^{\#}\}$ are available. Let us define PMP$(t_s,t_c,t_e)$, an abbreviation of Price-preserving Multi-interval Pricing Model (PMP), as follows:

This pricing model (PMP) is first introduced by Hogan (2016) and formalized by Hua et al. (2019).

Hua et al. (2019) showed that, for every time step t_c, if PMP$(t_0,t_c,t_T)$ is used instead of LAD(t_c, t_T) for pricing models with rolling implementation, the resulting prices coincide with the prices from the one-shot multiperiod optimization problem LAD$(t_0,t_T)$. This is closely related to the concept of “price consistency,” defined in slide 35 of Hogan (2020) as the property, “given perfect foresight, where actual conditions equal the forecast conditions, the methodology produces the same set of prices.”

1.2.2.3. Rolling Multiperiod with a Moving Horizon.

In a more practical setting, we can no longer assume that a horizon is fixed. For a rolling multiperiod model with a moving horizon, even in the case of strongly convex market-clearing models, the application of the PMP approach can produce a price-quantity pair that does not satisfy an equilibrium for an entire horizon, that is, in the sense of perfect hindsight, and with a horizon that spans $\{1,\dots ,T\}$. This is shown in section VI-B of Hua et al. (2019). This deviation of equilibrium is different from the dual degeneracy pointed out by Biggar and Hesamzadeh (2020).

Nevertheless, empirically, PMP achieves better performance than LAD with respect to LOC and MWP in this setting. In this paper, we provide an explanation by introducing an additional characteristic of PMP. PMP not only guarantees the price consistency for a rolling multiperiod planning with a fixed horizon but also minimizes LOC for an entire horizon, including past time steps given past prices. PMP balances the past decisions and future decisions in a way that LOC is minimized, hence the better performance. This is further discussed in Section 2.3. We focus on this property of PMP and extend it to the setting under uncertainty in Section 3.3.

1.2.3. Multiperiod Market Clearing Under Uncertainty.

Our interest in this work is an extension of the analysis on multiperiod pricing in the context of uncertainty. When extending the basic setting to incorporate uncertainty, the standard definition of an equilibrium is a pair of price-quantity stochastic processes, such that the market clears at every stage for every possible sample path of uncertainty, and the dispatch instructions of agents are maximizing risked profit given the prevailing price process. Risked profit is commonly quantified using risk measures (Ralph and Smeers 2015, Philpott et al. 2016, Philpott and Ferris 2021) and is an ex ante (i.e., without the benefit of hindsight) measure of how well an agent can do given the attitude of the agent toward risk and given the underlying price process.

The computation of the underlying equilibrium relies on posing the problem in question (the look-ahead economic dispatch, in the case of our application) as a multistage stochastic program. We will concentrate our discussion of the risk-neutral setting; therefore, time consistency (Shapiro 2012) is automatically satisfied in our setting. An equilibrium can be computed in this setting as the generalization of the multiperiod deterministic case, that is, by retrieving the dispatch decisions of the stochastic program and the dual multipliers of the market-clearing constraints for every stage and every sample path. As a natural extension for LOC in the multiperiod deterministic setting, it is possible to define a metric of performance, ex ante expected LOC, that is, the difference between the maximum expected profit and the expected profit of an agent following the dispatch decision by the system operator (a formal mathematical definition is provided in the main body of the paper). A stochastic equilibrium is equivalent to this metric being equal to zero. However, this definition stumbles upon a number of implementation challenges in a practical setting. These challenges include (i) the definition of the scenarios that constitute the stochastic program that needs to be solved, (ii) an underlying assumption that all agents in the market share the same views about the distribution of uncertainty (i.e., the same set of scenarios and the same probability for all scenarios), (iii) an assumption that the system operator can correctly identify the risk attitude of the least risk-averse agent in the market, and (iv) the need to solve a large-scale stochastic program under the tight run times that are imposed by real-time operations. Consequently, this pricing method has not directly seen its way into practical implementation.

In the present work, and inspired by the spirit of the discussion in the literature on multiperiod pricing, we rather pose the question of finding a price that (i) is nonanticipative (i.e., can be computed at a given time stage given the information that is available up to that moment in time) and (ii) delivers a stochastic process of real-time prices that minimize the expected lost opportunity cost defined in an ex post sense, that is, with lost opportunity cost being defined in a hindsight fashion when all uncertainty in the market (renewable forecast errors, etc.) has been revealed. An important property of the price that is obtained is that this price minimizes ex post expected LOC not only for the optimal system dispatch but for any dispatch that satisfies the aggregate uncertain demand in the market. This is further discussed in the main body of the paper.

Our motivation for the first requirement (nonanticipativity) is that real-time market clearing is intrinsically a process that resembles model predictive control in the sense that it is executed in a rolling fashion. Concretely, we contrast this to a situation (not applied in practice) where prices are computed after the fact, that is, at the end of the horizon in question, and with the benefit of hindsight when we can observe the realized uncertainty for the full horizon.

Our motivation for the second requirement is to propose a computationally viable proxy of the ideal stochastic equilibrium benchmark, but one that can be computed in the realistic time frames of real-time market operations with minimal assumptions related to stochastic models/scenario selection. Note that both definitions of expected LOC coincide with the one in the multiperiod deterministic setting. Note also, as a consequence, that price consistency is satisfied automatically for prices that minimize ex post expected LOC in the multiperiod deterministic setting.

The paper outlines a computational procedure that can be applied for computing the prices with the requisite properties. The procedure amounts to executing a separate pricing procedure as in Hua et al. (2019) and Hogan (2016). In contrast to the case of computing a stochastic equilibrium, this minimization is essentially minimizing an expectation (as opposed to a multistage stochastic program in Philpott et al. 2016 and Philpott and Ferris 2021) that can be implemented with a straightforward algorithmic procedure. Moreover, the procedure can be applied to continuous uncertainty model without requiring scenario selection in order to restore computational tractability.

It is important to point out that the line of work pursued here is distinct from the literature on stochastic market clearing such as Bouffard et al. (2005), Pritchard et al. (2010), Morales et al. (2014), and Zavala et al. (2017). Whereas the latter is concentrated on day-ahead auctions without considerations of consistency in a rolling market clearing (since day-ahead auctions are nonoverlapping), the interest in our work is on real-time market clearing in a rolling fashion. The discussion is also distinct from that of flexible ramp products (Wang and Hobbs 2015) and their associated implementation challenges (Schiro 2017). Flexible ramp products amount to an ancillary service that is priced in addition to energy. Instead, our focus here is on the pricing of energy in real time.

2. Multiperiod Deterministic Setting

In this section, we formally define what lost opportunity cost (LOC) is in the multiperiod sense. This definition is extended to the case of uncertainty in the next section. In a simple fixed horizon setting, we show that the pair of the optimal dispatch solution and the dual price from the economic dispatch problem minimizes LOC; indeed, it makes it zero. In a more practical setting, that is, the rolling multiperiod optimization with a moving horizon, this is no longer possible. The simple look-ahead model cannot be guaranteed to achieve either a zero LOC or even a low LOC. We show that the PMP procedure proposed by Hogan (2016) relieves this issue by minimizing LOC for the horizon, including the past time steps given the prices for the past time periods.

2.1. Lost Opportunity Cost in a Deterministic Setting

First, let us define an individual profit maximization problem for each agent $k\in K$. Let $t\in \mathcal{T}=\{t_0,\dots ,t_T\}$ be a time step in the entire horizon $\mathcal{T}$. From now on, tilde is used (e.g., $\tilde{p},\tilde{x}$) to indicate that these variables represent decisions made by system operators. On the other hand, the notations without accents or superscripts (e.g., p, x) correspond to the variables that each agent uses for optimizing their individual profit maximization problem. Given price signals $\tilde{p}=\{{\tilde{p}}_t:\forall t\in \mathcal{T}\}$, the maximized profit in the time interval $[t_0,t_T]$ is defined as follows:

The lost opportunity cost (LOC) for each agent k in the period $[t_0,t_T]$ is defined as the difference between the maximized profit and the profit of an agent following the dispatch decision by the system operator (${\tilde{x}}_k)$.

By definition, LOC is a nonnegative value. The vector ${\tilde{x}}_k$ is a feasible solution for the optimization problem (4), and because it is a maximization problem the first term for (5) is greater than equal to the second term.

Another frequently used performance measure is make-whole payments (MWP), which is the amount of costs exceeding revenue for each agent k. Formally, we define it as follows:

The concepts of LOC and MWP are suggested in Schiro et al. (2016) and Hua et al. (2019). Schiro et al. (2016) refers to them as deviation incentives mostly in the context of dealing with nonconvexity. However, Hua et al. (2019) extends the usage of the metrics to the case with the convexity assumption in the rolling multiperiod optimization with a moving horizon where we can no longer guarantee to be able to have a zero LOC.

In this paper, the focus of our analysis is on LOC. Note that LOC is an upper bound of MWP if v_k is nonnegative. Even though v_k can be negative in certain cases, we can expect it to be nonnegative in most of the cases where the length of the interval $[t_0,t_T]$ is large enough. Practically, there will be no agents who would continue their business if their maximum profit is below zero. Consequently, by minimizing LOC, a low level of MWP can be obtained as a by-product. The opposite argument is not valid; the most straightforward way of guaranteeing zero MWP is clearing the market with high prices $\tilde{p}$, which would, however, result in a high LOC.

For the rest of the paper, we use the notation for the aggregation of LOC or MWP as $LO{C}^{[t_0,t_T]}(\tilde{p},\tilde{x})={\mathrm{\Sigma }}_{k\in K}LO{C}_k^{[t_0,t_T]}(\tilde{p},\widetilde{x_k})$ or $MW{P}^{[t_0,t_T]}(\tilde{p},\tilde{x})={\mathrm{\Sigma }}_{k\in K}MW{P}_k^{[t_0,t_T]}(\tilde{p},\widetilde{x_k})$.

2.2. Simple Look-Ahead Model

When the pricing horizon is fixed as $\mathcal{T}$, and if we assume that all the future demand information is available, it is possible to obtain an equilibrium price-quantity pair by solving a one-shot multiperiod optimization problem. It can be easily shown by inspection of the KKT conditions that the primal and dual optimal solutions pair for LAD$(t_0,t_T),\hspace{0.17em}(p^{*},x^{*})=\{(p_t^{*},x_t^{*}):t\in \mathcal{T}\}$ results in a zero LOC, which is equivalent to an equilibrium. In other words, the price-quantity pair $(p^{*},x^{*})$ minimizes $LO{C}^{[t_0,t_T]}(\tilde{p},\tilde{x})$.

Nonetheless, in reality, the entire horizon is not fixed. A common practical setting is one with a moving horizon. With a fixed look-ahead time length, it is natural to solve LAD at every time stage (e.g., solve LAD(t_s, t_e) at t_s, to solve LAD$(t_{s+1},t_{e+1})$ at $t_{s+1}$, etc), and to keep the current period dispatch decisions and prices. The resulting $(p_t^{*},x_t^{*})$ pair sequence is no longer an equilibrium for a longer period. One of the main issues is that the look-ahead model ignores the decisions from the previous stages as the look-ahead horizon moves forward. The existence of intertemporal constraints often results in certain agents suffering losses in certain time steps that are expected to be made up for in the next stages. When the look-ahead horizon moves forward, this loss is regarded as sunk costs by the look-ahead model. Mathematically, the solutions from the LAD(t₁, t₂) minimizing $LO{C}^{[t_1,t_2]}$ are not guaranteed to be a part of a solution minimizing $LO{C}^{[t_0,t_T]}$, when $t_0<t_1$ and $t_2<t_T.$ A simple illustrative three-stage example where the look-ahead length is two time steps is provided by Hua et al. (2019).

2.3. Binding Past Prices

Theorem 1.

A primal optimal solution $x^{*}=\{x_t^{*}:t\in [t_c,t_e]\}$ of LAD(t_c, t_e) and an optimal dual multiplier $p^{*}=\{p_t^{*}:t\in [t_c,t_e]\}$ of PMP$(t_s,t_c,t_e)$ are minimizers of $LO{C}^{[t_s,t_e]}(\tilde{p},\tilde{x}|p_0^{\#},x_0^{\#})$.

Proof.

Redistribute the terms of $LO{C}^{[t_s,t_e]}(\tilde{p},\tilde{x}|p_0^{\#},x_0^{\#})$:

$$\underset{\tilde{p},\tilde{x}}{\text{min} }LO{C}^{[t_s,t_e]}(\tilde{p},\tilde{x}|p_0^{\#},x_0^{\#})=\underset{k\in K}{\mathrm{\Sigma }}\underset{t\in [t_s,t_{c-1}]}{\mathrm{\Sigma }}{f}_{k,t}(x_{k,t}^{\#})+\underset{\tilde{x}}{ \text{min} }\underset{k\in K}{\mathrm{\Sigma }}\underset{t\in [t_c,t_e]}{\mathrm{\Sigma }}{f}_{k,t}({\tilde{x}}_{k,t})-Z,$$(7)

$$\begin{array}{l}\text{where} \text{Z}=\underset{\tilde{p}}{\text{max}}\underset{x}{\text{min}}\underset{k\in K}{\mathrm{\Sigma }}\underset{t\in [t_s,t_e]}{\mathrm{\Sigma }}{f}_{k,t}(x_{k,t})\hfill \\ +\underset{t\in [t_s,t_c-1]}{\mathrm{\Sigma }}{p}_t^{\#}(-\underset{k\in K}{\mathrm{\Sigma }}{x}_{kt}+y_t)+\underset{t\in [t_c,t_e]}{\mathrm{\Sigma }}\widetilde{p_t}(-\underset{k\in K}{\mathrm{\Sigma }}{x}_{k,t}+y_t)\hfill \\ s.t.\hspace{1em}\hspace{0.5em}{h}_k(x_{k,t-1},x_{k,t})\le 0,\hspace{1em}k\in K,t\in [t_s,t_e]\hfill \\ x_{k,t}\in X_k\hspace{1em}t\in [t_s,t_e],k\in K\hfill \end{array}$$(8)

Notice that the first term is a constant, $x^{*}$ is the minimizer of the second term, and $p^{*}$ is the maximizer of the third term (Z), because Z is the dual problem of PMP$(t_s,t_c,t_e)$. □

Corollary 1.

If $x_0^{\#},p_0^{\#}$ are a part of the primal and dual optimal solutions of LAD(t_s, t_e), then with $x^{*}$ of LAD(t_c, t_e) and $p^{*}$ of PMP,$(t_s,t_c,t_e),\hspace{0.17em}(x_0^{\#},x^{*}),(p_0^{\#},p^{*})$ become a primal and dual optimal solution of LAD(t_s, t_e).

Theorem 1 implies that the price from PMP$(t_s,t_c,t_e)$ minimizes $LO{C}^{[t_s,t_e]}$ incorporating not only future but also past time periods given the past decisions $x_0^{\#},p_0^{\#}$. Intuitively, as the look-ahead horizon moves forward, PMP takes into account past decisions and balances in a way that LOC is minimized. This new property of PMP explains the empirically better performance measured by LOC or MWP than simple look-ahead models such as LAD. What Corollary 1 guarantees is the notion of price consistency as defined in Hogan (2020).

Another point worth commenting on is that Theorem 1 suggests to separate the pricing model (PMP) from the dispatch model (LAD). In Equation (7), observe that LOC is divided into the dispatch-related term and the price-related term. In order to minimize LOC, each of the terms is minimized from the solution of different models. We focus on these properties of PMP and extend it to the setting under uncertainty.

3. Multiperiod Market Clearing Under Uncertainty

In this section, we extend the previous theory for deterministic case to the setting under uncertainty. We use a scenario tree to visualize the uncertainty as in Figure 2. A scenario tree in the setting under uncertainty is analogous to a time interval in the deterministic setting. As we define the performance metrics with respect to time intervals in the previous chapter, here, we use scenarios trees to define measures. The notation regarding scenario trees for the rest of the paper is as follows; for a scenario tree $\mathcal{G}$, let $n\in \mathcal{N}$ denote a node of the scenario tree, where $\mathcal{N}$ is the entire set of the nodes of $\mathcal{G}$. We call n₀ the root node of a scenario tree, $n-$ denotes the parent node of n, and $\sigma (n)$ denotes the probability that the scenario of node n occurs from the perspective of the root node n₀. A sample path is denoted as $\mathbb{P}$, and the set of nodes in the sample path $\mathbb{P}$ as ${\mathcal{N}}_{\mathbb{P}}$.

First, we provide the definitions of expected lost opportunity cost from two different aspects, that is, ex ante (AEL) and ex post (PEL), and we compare their characteristics. Then, we discuss two different methods for minimizing each of the definitions of expected lost opportunity cost, respectively, when a scenario tree (time horizon) is fixed. Finally, we extend one of the methods to an algorithm analogous to PMP, which can deal with the more realistic setting of a moving horizon.

3.1. Two Definitions of Expected Lost Opportunity Cost Under Uncertainty

Care must be taken when we extend the definition of lost opportunity cost to the setting under uncertainty. Depending on the perspective of the individual profit maximization problem, the expected lost opportunity cost can be defined in two different ways.

One perspective is that each agent would solve an optimization problem in order to maximize their expected profits. We assume that the future price and dispatch distribution for all the scenarios is available and that all agents share the same information. We define ex ante expected lost opportunity cost (AEL) as the difference between the maximized expected profit and the expected profit that an agent can obtain if it follows the dispatch decisions by system operators. Formally, AEL for each agent k under the scenario tree $\mathcal{G}$ is defined as follows:

where the notation for variables ($\tilde{p},{\tilde{x}}_k$) is slightly abused under scenario trees, for example, $\tilde{p}=\{\tilde{p}(n):\forall n\in \mathcal{N}\}.$

Another perspective is that each agent solves a deterministic optimization problem maximizing its profit in the ex post fashion once all the uncertainty is revealed (i.e., under a chosen sample path). We define ex post expected lost opportunity cost as the expectation of the difference between the maximized profit that an agent could have earned if it had known the uncertain information and the actual profit that the agent obtains following the dispatch decisions by system operators. Mathematically, PEL for each agent k under the scenario tree $\mathcal{G}$ is defined as follows:

The interpretation of $w_k^{\mathbb{P}}(\tilde{p})$ is the profit that the agent k can achieve with perfect foresight of path $\mathbb{P}$ given prices $\tilde{p}$. In the remainder of the paper, we define $AE{L}^{\mathcal{G}}(\tilde{p},\tilde{x})={\mathrm{\Sigma }}_{k\in K}AE{L}_k^{\mathcal{G}}(\tilde{p},{\tilde{x}}_k)$ and $PE{L}^{\mathcal{G}}(\tilde{p},\tilde{x})={\mathrm{\Sigma }}_{k\in K}PE{L}_k^{\mathcal{G}}(\tilde{p},{\tilde{x}}_k)$.

The ex ante expected lost opportunity cost (AEL) is closely related to stochastic equilibrium as zero AEL is equivalent to a stochastic equilibrium. As a special case, zero LOC is equivalent to an equilibrium in the deterministic setting. However, using AEL directly in practice seems to be unrealistic because it relies on strong assumptions and requires solving a large-scale multiperiod stochastic program (this is discussed further in Section 1.2.3.).

Example 1.

Here, we provide a simple two-stage example for the comparison between AEL and PEL in Figure 3, where there are two scenarios with equal probability. The parameters for this agent are given in the left side of the figure, and the prices and dispatch decisions from the system operator $(\tilde{p},\tilde{x})$ are also given for each possible scenario (node). Even though in order to compute the precise profit we should rescale the price or cost according to the size of a time step, for this example we present the results without rescaling to avoid fractional numbers.

For the calculation of AEL, let us start from calculating $W_k^{\mathcal{G}}(\tilde{p})$, the individual expected profit maximization problem. Because the expected gain for the second stage $(32.5-30=2.5)$ is higher than the loss at the first stage $(30-28=2)$, generating the maximum possible output at the first stage would make the best expected profit; thus $x^{*}(1)=60$. Next, at node 2, because the gain is positive $(35-30=5)$, the agent should generate the maximum possible output given $x^{*}(1)$; thus $x^{*}(2)=80$. For node 3, because the marginal cost is equal to the price, any feasible solution would produce the same result; here, let us pick $x^{*}(3)=60$. Then, we can calculate that $W_k^{\mathcal{G}}(\tilde{p})$ becomes 80, and because the actual expected profit that this agent can achieve by following $(\tilde{p},\tilde{x})$ is 70, $AE{L}_k^{\mathcal{G}}(\tilde{p},{\tilde{x}}_k)=10$.

On the other hand, for the calculation of PEL, for each sample path $\mathbb{P}$, the deterministic individual profit maximization problem for $\mathbb{P},\hspace{0.17em}{w}_k^{\mathbb{P}}(\tilde{p})$ should be obtained. In this example, there are two possible sample paths: node 1 to 2 and node 1 to 3. For the sample path that shifts from node 1 to 2, because the gain for the second stage $(35-30=5)$ is higher than the loss at the first stage $(30-28=2)$, the unit should generate the maximum possible output for both the first and the second stage; thus $x^{*}(1)=60,x^{*}(2)=80$, which makes $w_k^{(1,2)}(\tilde{p})$ equal to 280. The sample path that transitions from node 1 to 3 corresponds to the opposite. The unit should generate the minimum possible output for the first stage, and then for the second stage the marginal cost is equal to the price, so any feasible solution would be optimal. Thus, let us pick $x^{*}(1)=20,x^{*}(3)=20$, which makes $w_k^{(1,3)}(\tilde{p})$ equal to –40. Considering that the actual profit for sample path (1,2) is 220 and that for sample path (1,3) is –80, we can see that $PE{L}_k^{\mathcal{G}}(\tilde{p},{\tilde{x}}_k)=50$.

Theorem 2.

For any $\mathcal{G},AE{L}_k^{\mathcal{G}}(\tilde{p},\widetilde{x_k})\le PE{L}_k^{\mathcal{G}}(\tilde{p},\widetilde{x_k}).$

Proof.

First, we show that $W_k^{\mathcal{G}}(\tilde{p})\le {\mathbb{E}}_{\mathbb{P}}[w_k^{\mathbb{P}}(\tilde{p})]$. There is another equivalent formulation for a multiperiod stochastic program other than (10). This scenario-based formulation is introduced in Rockafellar and Wets (1991). The formulation uses separate variables $x^{\mathbb{P}}$ for each sample path $\mathbb{P}\in \mathcal{P}$. Let $Pr(\mathbb{P})$ denote the probability for a sample path $\mathbb{P}$. The formulation with our notation is as follows:

$$\begin{array}{llll}{W}_k^{\mathcal{G}}(\tilde{p})=\hfill & \underset{x,\widehat{x}}{ \text{max}}\hfill & \hfill & \underset{\mathbb{P}\in \mathcal{P}}{\mathrm{\Sigma }}Pr(\mathbb{P})\underset{n\in {\mathcal{N}}_{\mathbb{P}}}{\mathrm{\Sigma }}[\tilde{p}(n)x^{\mathbb{P}}(n)-f_k(x^{\mathbb{P}}(n))]\hfill \\ \hfill & s.t.\hfill & \hfill & h(x^{\mathbb{P}}(n-),x^{\mathbb{P}}(n))\le 0,\hspace{1em}n\in {\mathcal{N}}_{\mathbb{P}},\mathbb{P}\in \mathcal{P}\hfill \\ \hfill & \hfill & \hfill & x^{\mathbb{P}}(n)\in X(n),\hspace{1em}\hspace{1em}n\in {\mathcal{N}}_{\mathbb{P}},\mathbb{P}\in \mathcal{P}\hfill \\ \hfill & \hfill & \hfill & x^{\mathbb{P}}(n)-\widehat{x}(n)=0,\hspace{1em}\hspace{1em}n\in {\mathcal{N}}_{\mathbb{P}},\mathbb{P}\in \mathcal{P}.\hfill \end{array}$$(13)

The last set of constraints is called the set of nonanticipativity constraints. These constraints impose that variables in the same node n have the same value. Notice that if we relax these nonanticipativity constraints, formulation (13) becomes ${\mathbb{E}}_{\mathbb{P}}[w_k^{\mathbb{P}}(\tilde{p})]$; hence, $W_k^{\mathcal{G}}(\tilde{p})\le {\mathbb{E}}_{\mathbb{P}}[w_k^{\mathbb{P}}(\tilde{p})]$.

Second, we show that ${\mathrm{\Sigma }}_{n\in \mathcal{N}}\sigma (n)(\tilde{p}(n)\widetilde{x_k}(n)-f_k(\widetilde{x_k}(n))={\mathbb{E}}_{\mathbb{P}}[{\mathrm{\Sigma }}_{n\in {\mathcal{N}}_{\mathbb{P}}}(\tilde{p}(n)\widetilde{x_k}(n)-f_k(\widetilde{x_k}(n))]$. This comes from the fact that in a scenario tree, $\sigma (n)={\mathrm{\Sigma }}_{\mathbb{P}\in \mathcal{P}:n\in {\mathcal{N}}_{\mathbb{P}}}Pr(\mathbb{P}),\forall n\in \mathcal{N}$. □

As a metric of economic behavior, the ex post expected lost opportunity cost (PEL), on the other hand, has some practical advantages relative to AEL. It is easier to calculate, and it is possible to estimate PEL when the underlying uncertainty model is continuous. By Theorem 2, PEL is an upper bound of AEL. In a similar fashion as in the deterministic case, PEL is also an upper bound of the expected MWP under a mild condition (${\mathbb{E}}_{\mathbb{P}}[w_k^{\mathbb{P}}(\tilde{p})]$ is nonnegative). Note that the definition of MWP is independent from the two different perspectives of solving individual profit maximization problems mentioned above in the description of AEL and PEL; hence, the expected MWP is identical under both of the perspectives, unlike LOC. Thus, by minimizing PEL, we can regulate AEL and the expected MWP to a low level.

It is true that the economical implication of PEL diverges from conventional stochastic equilibrium theory. Even though AEL and PEL coincide (both become LOC) in the deterministic case, zero PEL is not equivalent to a stochastic equilibrium anymore, as is the case with AEL. It is even impossible to have zero PEL unless the setting is deterministic. PEL becomes zero only when an agent enjoys perfect foresight and acts optimally under this perfect foresight; that is, it applies the solution of LAD over the entire horizon. Instead, PEL can be interpreted as a metric that measures how far the decisions of system operators are compared with the optimal case under the perfect foresight assumption. When PEL is minimized in the case under uncertainty (e.g., under a scenario tree), the minimum value, which is strictly positive now, represents the inevitable LOC (calculated ex post) caused by the underlying uncertainty.

3.2. Look-Ahead Models Under Uncertainty

3.2.1. AEL Minimizing Look-Ahead Model.

Consider a stochastic economic dispatch problem under a scenario tree $\mathcal{G}$. Let us refer to the following optimization problem as SLAD$(\mathcal{G})$, an abbreviation for Stochastic Look Ahead Dispatch Model (SLAD).

Let $p^{*}(n)={\lambda }^{*}(n)/\sigma (n),\forall n\in \mathcal{N}$, where ${\lambda }^{*}(n)$ are the nodal balance optimal dual multipliers of SLAD$(\mathcal{G})$. Similar to the deterministic case in Section 1.2.2, it can be shown using KKT conditions that $(p^{*},x^{*})=\{(p^{*}(n),x^{*}(n)):n\in \mathcal{N}\}$ minimizes $AE{L}^{\mathcal{G}}(\tilde{p},\widetilde{x_k})$ to zero. This implies that $(p^{*},x^{*})$ forms the (risk neutral) stochastic equilibrium, defined as “a stochastic process of prices and a corresponding collection of actions for each agent with the property that the actions are individual expected profit maximizing solutions for each agent.” See, for example, Philpott et al. (2016) and Philpott and Ferris (2021) for further information.

3.2.2. PEL Minimizing Look-Ahead Model.

For the pricing model minimizing PEL, we use the notation for the scenario-based formulation introduced in the proof of Theorem 2 as follows:

The equivalent way of writing the first set of constraints of (15) is ${{\mathbb{E}}_{\mathbb{P}}}_{\mathbb{P}\in \mathcal{P}:n\in {\mathcal{N}}_{\mathbb{P}}}[{\mathrm{\Sigma }}_{k\in K}{x}_k^{\mathbb{P}}(n)]=\sigma (n)y(n).$ As an example, when n = n₀, the constraint can be written succinctly as ${\mathbb{E}}_{\mathbb{P}}[{\mathrm{\Sigma }}_{k\in K}{x}_k^{\mathbb{P}}(n_0)]=y(n_0).$

Theorem 3.

For a scenario tree $\mathcal{G},$ a primal optimal solution $x^{*}=\{x^{*}(n):n\in \mathcal{N}\}$ of SLAD$(\mathcal{G})$ and a dual optimal multiplier $p^{*}=\{p^{*}(n):n\in \mathcal{N}\}$ of formulation (15) under $\mathcal{G}$ are minimizers of $PE{L}^{\mathcal{G}}(\tilde{p},\tilde{x})$.

Proof.

Redistribute the terms of $PE{L}^{\mathcal{G}}(\tilde{p},\tilde{x})$:

$$\underset{\tilde{p},\tilde{x}}{\text{min} }PE{L}^{\mathcal{G}}(\tilde{p},\tilde{x})=\underset{\tilde{x}}{ \text{min} }{\mathbb{E}}_{\mathbb{P}}[\underset{n\in {\mathcal{N}}_{\mathbb{P}}}{\mathrm{\Sigma }}\underset{k\in K}{\mathrm{\Sigma }}{f}_k({\tilde{x}}_k(n))]-Z^{\mathcal{G}},$$(16)

$$\begin{array}{l} \text{where} {\text{Z}}^{\mathcal{G}}=\underset{\widetilde{\mathit{\text{p}}}}{ \text{max} }{\mathbb{E}}_{\mathbb{P}}[\underset{x}{\text{min}}\underset{n\in {\mathcal{N}}_{\mathbb{P}}}{\mathrm{\Sigma }}\underset{k\in K}{\mathrm{\Sigma }}{f}_k(x_k(n))+\tilde{p}(n)(-\underset{k\in K}{\mathrm{\Sigma }}{x}_k(n)+y(n))]\hfill \\ \hspace{1em}\hspace{1em}s.t.\hspace{1em}h(x_k(n-),x_k(n))\le 0,\hspace{1em}n\in {\mathcal{N}}_{\mathbb{P}}\hfill \\ \hspace{1em}\hspace{1em}x(n)\in X(n),\hspace{1em}n\in {\mathcal{N}}_{\mathbb{P}}.\hfill \end{array}$$(17)

Because

$$\underset{\tilde{x}}{\text{min} }{\mathbb{E}}_{\mathbb{P}}[\underset{n\in {\mathcal{N}}_{\mathbb{P}}}{\mathrm{\Sigma }}\underset{k\in K}{\mathrm{\Sigma }}{f}_k(\widetilde{x_k}(n))]=\underset{\tilde{x}}{ \text{min} }\underset{n\in \mathcal{N}}{\mathrm{\Sigma }}\sigma (n)\underset{k\in K}{\mathrm{\Sigma }}{f}_k(\widetilde{x_k}(n)),$$(18)

$x^{*}=\{x^{*}(n):n\in \mathcal{N}\}$ of SLAD$(\mathcal{G})$ minimizes the first term. From (16), $Z^{\mathcal{G}}$ can be expressed as follows:

$$\begin{array}{l}{Z}^{\mathcal{G}}=\underset{\tilde{p}}{ \text{max} }\underset{x}{ \text{min}}\underset{\mathbb{P}\in \mathcal{P}}{\mathrm{\Sigma }}Pr(\mathbb{P})\underset{n\in {\mathcal{N}}_{\mathbb{P}}}{\mathrm{\Sigma }}\underset{k\in K}{\mathrm{\Sigma }}{f}_k(x_k^{\mathbb{P}}(n))+\underset{\mathbb{P}\in \mathcal{P}}{\mathrm{\Sigma }}Pr(\mathbb{P})\tilde{p}(n)(-\underset{k\in K}{\mathrm{\Sigma }}{x}_k^{\mathbb{P}}(n)+y(n))\hfill \\ \hspace{1em}\hspace{1em}s.t.\hspace{1em}h(x_k^{\mathbb{P}}(n-),x_k^{\mathbb{P}}(n))\le 0,\hspace{1em}n\in {\mathcal{N}}_{\mathbb{P}},\mathbb{P}\in \mathcal{P}\hfill \\ {\hspace{1em}\hspace{1em}x}^{\mathbb{P}}(n)\in X(n),\hspace{1em}n\in {\mathcal{N}}_{\mathbb{P}},\mathbb{P}\in \mathcal{P}.\hfill \end{array}$$(19)

Notice that (19) is the dual problem of the formulation (15); hence, $p^{*}$ maximizes the second term ($Z^{\mathcal{G}}$). □

Theorem 3 shows that we can minimize PEL with the dispatch decision from SLAD$(\mathcal{G})$ and the price signal from formulation (15). Notice that even when the dispatch decision is not optimal, the price obtained from formulation (15) is still optimal because PEL is divided into a dispatch-related term and a price-related term (see Equation (16)). This allows us to treat dispatch and price model independently. In practice, it is not realistic to assume that we would always be able to find optimal dispatch decisions in the sense of solving SLAD. Let $x^{\#}$ be suboptimal dispatch decisions that we would encounter in practice, and then we can still guarantee that $p^{*}$ from the formulation (15) minimizes $PE{L}^{\mathcal{G}}(\tilde{p},x^{\#})$.

Notwithstanding, we note that formulation (15) is not practical for being used in real-time pricing because it requires too many variables, and the first set of constraints prevents the formulation from being separable. Here, we show a slightly modified version of (15) in order to make it more workable. The key is in the way to approach (17). Now, instead of changing (17) to (19), we re-dualize the dualized power balance constraints back to the constraints, except for the one for the root node as follows:

where we express the set of intertemporal constraints and the set of independent constraints as $X^{\mathbb{P}}$. Let $F_{\mathbb{P}}(\tilde{p}(n_0))$ be the inner optimization problem of (20). Then we can write $Z^{\mathcal{G}}$ more concisely as follows:

Notice that we can compute the gradient of $F_{\mathbb{P}}(\tilde{p}(n_0))$ by Danskin’s Theorem (Danskin 1967):

where ${\overline{x}}_k(n_0)$ is the optimal solution for the inner optimization problem of (20).

Observe that it is possible to utilize the Stochastic Gradient Descent algorithm in order to find the maximizer $p^{*}(n_0)$ for (21). This modification allows us to deal with continuous uncertainty models by incorporating the principle of stochastic approximation methods in Robbins and Monro (1951). All we need is a model that samples sample paths. Instead of knowing the whole set of scenarios for the future, if we can somehow sample future sample paths, we can apply our approach to find $p^{*}(n_0)$. Practically, we can either directly use historical data as sample paths or build an uncertainty model such as an autoregressive model in order to predict the distribution of future information. Although this does not guarantee having an exhaustive uncertainty set that represents reality perfectly, at least this approach liberates us from discretization for building a scenario tree.

This modification can be further developed by binding cleared past prices as PMP does for the deterministic setting in Section 2.3. In the next section, we introduce a PMP-style version of the PEL minimizing look-ahead model.

3.3. Binding Past Prices

Before we propose a formulation for coping with binding past prices under uncertainty, we define some additional notation. Referring to Figure 4, it is necessary to extend a scenario tree with its past path in order to link a scenario tree $\mathcal{G}$ starting from the current time step n₀ to the past. The extension is indeed a subtree of a larger scenario tree $\mathcal{H}$ whose root node is m₀. We denote the past path we have followed right before the current time step as $\mathbb{Q}$ and the node set of the path as ${\mathcal{N}}_{\mathbb{Q}}$. Naturally, we denote the extension of $\mathcal{G}$ as $\mathcal{G}\cup \mathbb{Q}$. For a future sample path, including the current time step, we use $\mathbb{P}$ as in the previous sections. To avoid ambiguity, let the node set of $\mathcal{G}$ be ${\mathcal{N}}^{\mathcal{G}}$ and that of $\mathcal{H}$ be ${\mathcal{N}}^{\mathcal{H}}$.

Let the cleared past prices be $p_0^{\#}=\{p^{\#}(m):\forall m\in {\mathcal{N}}_{\mathbb{Q}}\}$ and the past dispatch decisions be $x_0^{\#}=\{x^{\#}(m):\forall m\in {\mathcal{N}}_{\mathbb{Q}}\}$. Let us denote the following optimization problem as SPMP$(\mathcal{H},\mathcal{G})$, an abbreviation of stochastic price-preserved multi-interval pricing model (SPMP):

Theorem 4.

$(p^{*},x^{*})$ is a part of the minimizer for $PE{L}^{\mathcal{H}}(\tilde{p},\tilde{x}|p_0^{\#},x_0^{\#})$, where $x^{*}$ is an optimal solution for SLAD($\mathcal{G}$) and $p^{*}$ is an optimal dual multiplier for SPMP$(\mathcal{H},\mathcal{G})$.

Proof.

The proof is a combination of the proofs of Theorem 1 and Theorem 3. □

Corollary 2.

If $(p_0^{\#},x_0^{\#})$ is part of a minimizer for $PE{L}^{\mathcal{H}}(\tilde{p},\tilde{x})$, then $(p^{*},x^{*})$ in Theorem 4 is also part of a minimizer for $PE{L}^{\mathcal{H}}(\tilde{p},\tilde{x})$.

Theorem 4 and Corollary 2 are analogous to Theorem 1 and Corollary 1, respectively, in the deterministic case. The price from SPMP minimizes PEL, incorporating not only future but also past time periods given past decisions. It no longer treats past losses as sunk costs. However, notice the subtle difference between the two cases (deterministic/under uncertainty). In the set ${\mathcal{N}}^{\mathcal{H}}\backslash {\mathcal{N}}^{\mathcal{G}}$, there are nodes that are not in ${\mathcal{N}}_{\mathbb{Q}}.$ Because the support for $(p^{*},x^{*})$ is ${\mathcal{N}}^{\mathcal{G}}$, it is only a part of the minimizer for $PE{L}^{\mathcal{H}}(\tilde{p},\tilde{x}|p_0^{\#},x_0^{\#})$ in Theorem 4, unlike in the deterministic case where it is a minimizer for $LO{C}^{[t_s,t_e]}(\tilde{p},\tilde{x}|p_0^{\#},x_0^{\#})$ in Theorem 1. Notice that the nodes in ${\mathcal{N}}^{\mathcal{H}}\backslash ({\mathcal{N}}^{\mathcal{G}}\cup {\mathcal{N}}_{\mathbb{Q}})$ are meaningless given the current time step when the uncertainty of the past has been revealed. Mathematically speaking, when $(p_0^{\#},x_0^{\#})$ is given for ${\mathcal{N}}_{\mathbb{Q}}$, the terms related to ${\mathcal{N}}^{\mathcal{G}}\cup {\mathcal{N}}_{\mathbb{Q}}$ in $PE{L}^{\mathcal{H}}(\tilde{p},\tilde{x}|p_0^{\#},x_0^{\#})$ become completely separable from the others; hence, it can be shown that $(p^{*},x^{*})$ is a part of the minimizer for $PE{L}^{\mathcal{H}}(\tilde{p},\tilde{x}|p_0^{\#},x_0^{\#})$ without knowing the information for ${\mathcal{N}}^{\mathcal{H}}\backslash ({\mathcal{N}}^{\mathcal{G}}\cup {\mathcal{N}}_{\mathbb{Q}})$. The same argument can be applied to Corollary 2.

Now, we are in a position to propose a pricing method for rolling market clearing under uncertainty given past prices. Let us modify (23) as we have seen in the previous section (from (15) to (20) via (17)) so that we can apply the stochastic gradient descent algorithm for SPMP$(\mathcal{H},\mathcal{G})$ as follows:

where we express the intertemporal constraints set and the independent constraints set for an extended sample path $\mathbb{Q}\cup \mathbb{P}$ as $X^{\mathbb{Q}\cup \mathbb{P}}.$

Let $F_{\mathbb{Q}\cup \mathbb{P}}(\tilde{p}(n_0))$ be the inner optimization problem of (24). Then (24) can be expressed as follows:

Notice that we can compute the gradient of $F_{\mathbb{Q}\cup \mathbb{P}}(\tilde{p}(n_0))$ by Danskin’s Theorem (Danskin 1967):

where ${\overline{x}}_k(n_0)$ is the optimal solution for the inner optimization problem of (24).

Now SGD can be applied to find the maximizer $p^{*}(n_0)$ for (25). Note that (24) is very similar to (20). The main differences are twofold. First, x is defined under an extended sample path $\mathbb{Q}\cup \mathbb{P}$ instead of $\mathbb{P}$. Second, the inner optimization is equivalent to solving PMP$(t_{m_0},t_{n_0},t_e)$ instead of solving LAD$(t_{n_0},t_e)$, where $t_{m_0},t_{n_0}$ denote the time steps of the nodes m₀, n₀ respectively, and t_e the time step of the leaf nodes in the scenario tree $\mathcal{H}.$

Thanks to Corollary 2, this sequential implementation (clear only the current time step sequentially as time passes) of SPMP$(\mathcal{H},\mathcal{G})$ using (24)−(26) results in the same solution as solving (15) under $\mathcal{H}$ for clearing prices for all possible scenarios at once. This property enables us to use SPMP$(\mathcal{H},\mathcal{G})$ in a more practical setting. In the next section, we briefly formalize the SGD algorithm for (24)−(26) and analyze practical details related to initialization and step size rules.

3.4. Stochastic Gradient Descent Algorithm for SPMP

We propose the following algorithm for computing prices in a rolling market clearing under uncertainty with binding past prices.

Algorithm 1.

SGD for SPMP

Result: $p^I(n_0)$

$i\leftarrow 0$; initialize $p^0(n_0)$;

while i < I do

 Sample a sample path $\mathbb{P}$;

 Obtain ${\overline{x}}^i(n_0)$ by solving the inner optimization problem of (23);

 $\nabla F_{\mathbb{Q}\cup \mathbb{P}}^i(p^i(n_0))\leftarrow (-{\mathrm{\Sigma }}_{k\in K}{\overline{x}}_k^i(n_0)+y(n_0))$;

 $p^{i+1}(n_0)\leftarrow p^i(n_0)+{\gamma }_i\nabla F_{\mathbb{Q}\cup \mathbb{P}}^i(p^i(n_0))$;

 $i\leftarrow i+1$;

end

For initializing $p^0(n_0)$, we use the dual multiplier of PMP with future expected demand as input data. In practice, using a deterministic model with expected demand data is a commonly used way to clear market. We use it as an initial value and update it in our algorithm.

For the step sizes $\{{\gamma }_i:i\in \{0,\dots ,I\left\}\right\}$, there can be many variations. For updating step sizes, we consult mainly Bottou (2012). Note that there is another variation of SGD often referred to as averaged SGD based on Polyak and Juditsky (1992). Detailed rules are introduced in section 5.3 of Bottou (2012). Although there exist many variations for selecting the initial step size, it is common to use the ratio of the upper bounds of the norm of the argument over the norm of the gradient as a fixed learning rate or dynamic learning rate with some diminishing rules (Nemirovski et al. 2009). In our experiment, we use the maximum cost over the current net load. The argument $p(n_0)$ cannot be greater than the maximum cost, and the upper bound of the gradient is bounded by $y(n_0)$. We have experimented with variations of step size rules according to changes in parameters regarding the initial step size and the rate of diminishing step size. The reader is referred to the details in Appendix A in the e-companion.

4. Computational Results

4.1. An Illustrative Example

Let us first examine an illustrative three-stage example where two scenarios are possible for each node with equal probability as in Figure 5. We have three different units for generating power with ramp constraints as in Table 1. Each time step corresponds to five minutes. This example is an extension of example 1 in Hua et al. (2019) for the case under uncertainty. We show the results of different market clearing models in Table 2. For the stochastic model, the dispatch solution is solved by SLAD, and the two price distributions are obtained from SLAD and SPMP. For the deterministic model, the dispatch solution is obtained from LAD, and the prices are obtained from LAD and PMP. Notice that future expected demand is used for the deterministic models, and as time moves forward (with new demand information updated), truncated problems are solved in a rolling fashion, whereas for the stochastic models the result is obtained from one optimization problem.

Table 1. Unit Parameters

Table 2. Market-Clearing Solutions from Different Models

Performance metrics are compared in Tables 3 and 4 with the solutions that are presented in Table 2. We note that different dispatch solutions are used for Table 3 and Table 4, SLAD and LAD respectively; therefore, the values for SPMP are different in the two tables. In Table 3, observe that (i) for SLAD, AEL is 0 as the results of Section 3.2.1, (ii) for SPMP, AEL $\le$ PEL as foreseen by Theorem 2, also expected MWP $\le$ PEL, and (iii) most importantly, SPMP achieves smaller PEL and expected MWP than SLAD because SPMP produces prices that minimize PEL. In Table 4, we compare SPMP with deterministic pricing models (LAD and PMP). Observe that PMP achieves better performance than LAD because it accounts for binding past prices and that SPMP attains better results than PMP because it accounts for the underlying uncertainty distribution. With the optimal dispatch solutions obtained from SLAD, the results can be further reduced to the values shown in Table 3. The reason why LAD has zero MWP in this example (it happens coincidentally; it is not a property of LAD) is because the price from this model is very high compared with other models in Table 2. This example shows that we can achieve zero MWP by clearing prices at high values, but then LOC (AEL or PEL under uncertainty) increases significantly, as shown in Table 4.

Table 3. Comparison of Metrics with Dispatch Solutions from SLAD

Table 4. Comparison of Metrics with Dispatch Solutions from LAD

It is further worth noting that a stochastic equilibrium can perform poorly in terms of certain metrics. In Table 3, SLAD indeed achieves zero AEL, which is equivalent to a stochastic equilibrium; however, it exhibits rather high levels of PEL (the value that each agent would perceive when they calculate LOC in an ex post fashion) and expected MWP (simply losses). SPMP, on the other hand, by minimizing PEL directly, can regulate the level of AEL and expected MWP as by-products, but it does not constitute a stochastic equilibrium. In the next section, we present an experiment with realistic data.

4.2. Simulation with Realistic Data

In this section, we illustrate our proposal for pricing under uncertainty in a case study of the ISO New England (ISO-NE) system.

4.2.1. Case Study Description.

We consult Krishnamurthy et al. (2016) for the grid, generator, and load data based on ISO New England. The model includes eight zones with 76 generators. The original source of data is hourly. In our case study, we are interested in five-minute time resolution, because certain binding operating constraints that are driven by the random variations of renewable supply are only observable at this shorter time frame. We assume linear cost functions in our analysis, and hence, we use only the first-order cost terms from Krishnamurthy et al. (2016). The linear cost terms and the ramp rates of the generators are rescaled in order to account for the five-minute resolution of our model. Because there is no congestion due to sufficient transmission line capacity for the network in the original data, we adjusted the capacity (to 1,500 MW for each line) to induce congestion resulting in the difference in prices for different zones while making sure that there is no load-shedding because of the lack of capacity.

Minimum generation levels for the units are not specified in the original data. Instead, we assume that nuclear units have a technical minimum that is equal to 80% of their nominal output, 60% for coal-fired units, and 0% for the remaining technologies. We add pumped-hydro reservoirs to the model in order to introduce an interesting interplay between storage and renewable supply. The pumped-hydro storage data are sourced from Papavasiliou and Smeers (2017).

In order to introduce uncertainty to the model, we consider a scenario of large-scale wind power penetration. In terms of modeling wind power production, we follow the approach that is introduced by Papavasiliou and Oren (2013). Concretely, we model wind speed using a time series model, and we use a power curve in order to transform random fluctuations in wind speed to a resulting wind power stochastic process.

We use wind speed data with one-minute resolution from January 2018 to October 2019 from the Royal Meteorological Institute of Belgium (RMI). We source data with five-minute resolution, and we use a cumulative empirical distribution for transforming the data. We remove monthly seasonal effects and use an autoregressive model with a 10-order lag (AR(10) model). For our experiments, we assume a single-area wind production model. Although there are different zones for the grid data, we do not account for transmission constraints in our model. We control the amount of uncertainty in the wind power production model with a tuning parameter, WindRate. When its value is one, the level of wind penetration corresponds to average wind production equal to 17% of annual ISO-NE energy demand, and the highest possible penetration rate that we consider in our model amounts to 40% of annual ISO-NE energy demand.

4.2.2. Comparison of Metrics with Different Pricing Models.

The full horizon of our simulation consists of 312 intervals (26 hours), where an interval length is equal to five minutes. We ignore the first and last 12 intervals (one hour each) in our analysis in order to mitigate boundary effects. Two types of intertemporal constraints exist in our model: ramping constraints and the constraints that represent the dynamics of pumped hydro storage.

Because we use a continuous stochastic uncertainty model (AR model), we can no longer compute AEL. Here, the focus is on comparing deterministic pricing models (LAD and PMP) with our method (SPMP). For the deterministic models, we use expected future demand. We use the solution from the LAD model as the dispatch decision for all the models, and our goal is to compare the effect of the different pricing models. We add one more model as a benchmark named PMP_PF (PMP with perfect foresight assumption), where we provide the actual sample path for future demand. For each model, we implement a moving horizon with a look-ahead length of 12 intervals (one hour). For the models that account for binding past prices (PMP, PMP_PF and SPMP), we add the information of past prices over the 12 most recent intervals (one hour). Notice that even the benchmark model PMP_PF can have positive value of PEL, because the look-ahead length is limited (12 intervals), whereas the full horizon length for calculating LOC is much longer (288 intervals). PMP_PF has the information of the actual demand for the future; however, it does not solve one-shot optimization with a full horizon length but instead a rolling implementation, as other models do. The goal of this comparison is to quantify how much the perfect foresight assumption can change the result ceteris paribus (including the look-ahead length).

Figure 6 shows the results of PEL and the expected make-whole payments (MWP) for different models, with increasing levels of uncertainty controlled by WindRate. The bars correspond to the average result of 500 experiments, and the middle lines show the sample standard deviation of the experiments. For our method, the iteration count for the SGD algorithm I is one hundred for SPMP. First, we can observe that the binding past prices version (PMP) performs better than the simple look-ahead model (LAD). By exploiting the information of the distribution of the uncertain future, our method (SPMP) achieves significantly lower PEL and variance of the LOC than those models that use the expectation of future demand. Furthermore, SPMP achieves similar performance to the case with perfect foresight (PMP_PF). In Figure 6(b), we can observe the same pattern as Figure 6(a), but with even more noticeable differences. SPMP achieves lower expected value and variance for MWP than other models. Additionally, it also achieves a comparable result to the case with perfect foresight. The readers who are interested in the difference of prices resulting from different models are referred to Appendix B in the e-companion.

4.2.3. Computation Time.

For the computing time of our method, 500 iterations of SGD require approximately 30 seconds in the experiment on a personal computer with a 2.5-GHz dual-core CPU and 8 GB of RAM. The results and discussion about the convergence of the SGD algorithm are available in Appendix A in the e-companion.

5. Conclusion

In this paper, we introduce two different definitions of expected lost opportunity cost, and we propose and analyze a pricing method for multi-interval real-time markets that operates under uncertainty. The proposed method minimizes one type of expected lost opportunity cost (PEL). We perform experimental results that demonstrate that our pricing approach results in lower PEL and expected make-whole payments with smaller variance than alternative pricing methods that have been proposed in the recent literature. We further observe that the gap between our method and other methods that do not exploit distribution information increases as the level of uncertainty increases. This indicates that our pricing proposal is especially suitable for future renewable integration scenarios, where the role of uncertainty is expected to become increasingly important and where the accuracy of price signals will be a crucial element in preventing asset owners from “taking matters in their own hands” through self-commitment or self-dispatching. Our experimental results suggest that near-optimal prices can be obtained with a modest number of iterations of the stochastic gradient algorithm. This observation provides encouraging support to the claim that the method proposed in our paper can be implemented within operationally acceptable time frames for real-time market clearing.