SIAM News Blog
SIAM News
Print

Mathematics of Electricity Markets Under Uncertainty

By Andy Philpott

The last twenty years have witnessed a transformation in the development of market mechanisms for supplying electric power. Applied mathematics continues to make major contributions in both understanding and implementing these market mechanisms. This article presents a personal perspective on the role of applied mathematics in this area, as well as a selected set of contributions and promising directions.

Studying market mechanisms for electricity is simplified by its being a single commodity, but complicated by features that make standard economic models difficult to apply. To begin, electricity is not easily storable, and the flow of power over a transmission network must satisfy certain laws of physics. The optimal power flow problem of meeting active and reactive power requirements at least cost is formulated with complex variables and is highly nonlinear. Scheduling power dispatch of large generation units must also satisfy unit-commitment constraints that involve costs and delays for starting turbines or ramping them up or down. All these features lead engineers toward system optimization problems of some complexity that, in their most general form, are not convex. Nevertheless, powerful optimization techniques (e.g., mixed integer programming for capacity expansion and unit commitment [8], or semi-definite programming relaxations for optimal power flow [10]) have been developed to attack these problems.

Electricity market mechanisms attempt to replace such system optimizations by individual optimizations. The goal of the market designer is to recover the system optimal solution, but to do so by providing incentives rather than control. The incentives are intended to produce an optimal supply of power in the short run (from the cheapest plants), as well as to provide sufficient profits to cover the long-run costs of generation, including the construction of new generating plants when and where needed. Ideally, incentives would give a system optimal solution in both the short and the long run, but this is not typically possible. If the underlying short-run system optimization problem is not convex, for example, some approximation is needed to make it so and thus allow its decomposition into agent problems.

Even when the system optimization problem is convex, if generators can act as price setters in these markets, the exercise of their market power often leads to Nash equilibrium solutions that incur losses of overall welfare. In other words, acting in their own self-interest, generators seek to withhold generation so as to increase prices above competitive levels; this leads to an equilibrium at which no generators are willing  to unilaterally alter their generation levels. Although the result is increased profits for generators, the losses to consumers often exceed this gain. Many papers in the applied mathematics literature deal with this phenomenon not only in electricity, but also in telecommunications, road traffic, supply chains, and other applications.

Most practical questions about market power in electricity markets are asked ex ante. Market designers prefer to model a market mechanism before testing it in the real world, when real money is at stake. Different mechanisms produce different overall efficiencies, but also different transfers of wealth between agents. 

It has been known for some years that imperfectly competitive generation and distribution of electricity in constrained transmission networks are difficult to model ex ante. In a classic paper, Borenstein, Bushnell, and Stoft [3] showed that for a simple two-node example with a constrained transmission line, there is no pure-strategy Nash equilibrium for two identical generators located at each node. When the line capacity is small, each generator has an incentive to reduce its output less than the competitor. Each generator’s node imports power and constrains the line to yield monopoly profits. Because both agents have this incentive, no symmetric Nash equilibrium exists unless they adopt mixed strategies. In certain cases uncertain demand serves to smooth out the discontinuities that lead to failure in the Borenstein example, and it is possible to obtain pure-strategy Nash equilibria in supply-function equilibrium [9], but these results seem to be difficult to scale to real transmission networks.

A different pathology might occur when a pair of agents are at the same location but share a transmission line to consumers. If the line has a capacity constraint, the problem becomes one of generalized Nash equilibrium<>  [6]––that is, an equilibrium problem in which the feasible set of actions (as well as the payoff) of an agent depends on the other agents’ strategies. An equilibrium might no longer be unique in this setting, as for some range of \(\lambda\), an action by one agent that uses a proportion \(\lambda\) of the line capacity can be matched by a best response by the other that uses the proportion \((1 – \lambda)\), defining a continuum of equilibria. Much progress has been made in understanding the mathematics of problems of this type, led by Jong-Shi Pang [12] and Francisco Facchinei [5].

Several approaches can be taken to guarantee unique pure-strategy Nash equilibria in problems with transmission networks. One is to ignore the transmission network and treat all agents as being at a single location. Such models, well studied in the literature, lead to useful insights about the features of different market mechanisms but suffer from some lack of realism. Another approach is to include a transmission network in the model, but impose conditions on the rationality of the agents that restrict them in anticipating congestion; an example can be found in [20]. A weakness in this approach is that it is hard to justify a method for choosing the limitation on rationality, and different choices can yield very different equilibrium outcomes.

A third possibility, and our focus henceforth, is to assume that agents are perfectly competitive. At first sight, this might appear to be a backward step. Because perfect competition is an ideal that won’t occur in practice, models that assume it are unlikely to give good predictions when agents behave strategically––unless the system implemented computes marginal prices from a model that computes a socially optimal plan, and then requires agents to trade at these prices. This approach, called market socialism by economists, is essentially the electricity spot market design used in a number of regions with abundant hydro energy (such as Brazil and Chile).

Other regions with lots of hydro energy, like New Zealand and the Nordpool countries, have deregulated electricity pools. A reason to study perfectly competitive markets in these settings is to provide some ex post benchmark for the performance of a real market. Market data, even if not made public, should be available to the regulator. If observed prices are significantly above perfectly competitive benchmarks, a regulator has some evidence to support investigations of possible market manipulation. Social planning optimization models and the system marginal prices they yield (as Lagrange multipliers) are obvious candidates for competitive benchmarks.

Use of optimization models to benchmark electricity market performance needs an important caveat: The socially optimal outcomes delivered in theory by market socialism do not always coincide with a perfectly competitive equilibrium. If enough market instruments and agents are risk-neutral, then an equilibrium under perfect competition will correspond to a socially optimal solution. Having enough market instruments is a market-completeness assumption. A well-known example of market incompleteness was identified in Brazil when different agents owned generating stations at different points on the same river. As shown by Lino et al. [11], such situations can lead to a loss of welfare in competitive equilibrium unless the market is completed with contracts that enable the agents to trade in the water they use for generating electricity.

A more subtle form of incompleteness can result from risk aversion. In this case, agents might accept the same probability distribution for uncertain events, but have different attitudes to risk. (We do not consider here the real possibility that their probability distributions might differ, which leads to a different model.) Each agent’s attitude to risk gives a higher weight to bad outcomes in a way that has been formalized by the theory of coherent risk measures (see [1, 17, 19]). Here, the risk-adjusted cost of a random cost \(Z\) can be expressed as

\[\begin{equation}
\rho(Z)=\sup_{\mu \in \mathcal{D}} \mathbb{E}_{\mu}[Z],
\end{equation}\]

that is, the worst-case expectation of the costs when taken with respect to some probability measure that lies in a convex set \(\mathcal{D}\). For the simplest setting, \(\mathcal{D}\) can be taken to be polyhedral, as illustrated in Figure 1.

 

Figure 1. Given random cost outcomes \(Z(\omega_{1}) < Z (\omega_{2}) < Z(\omega_3)\) with equal probability, the coherent risk measure \(\rho(Z) = ¾ \mathbb{E} [Z ] + ¼\) max \(Z\) has risk set \(\mathcal{D} = \mathrm{conv} {(½, ¼, ¼), (¼, ½, ¼), (¼, ¼, ½)}\), as depicted by the shaded triangle, yielding \(\rho(Z) = max_{\mu \in \mathcal{D}} \mathbb{E}_\mu [Z ] = ¼ Z(\omega_1) + ¼ Z (\omega_2)+ ½ Z(\omega_3)\).

 

When all agents maximize their risk-adjusted profits, the competitive equilibrium obtained is often different from an optimal social plan. To see why, it is helpful to imagine what risk measure a social planner would use to account for the different preferences of all the different agents. When a hydro producer dislikes low reservoir inflows that yield low revenues, and a thermal producer dislikes high hydro reservoir inflows that yield low energy prices, any coherent risk measure used by the social planner will fail to cover both as worst cases.

To get closer to an optimal social plan, someone has to make tradeoffs. The word is well chosen, as the tradeoffs can be shown to come from specific contracts traded between the players. In the example of the hydro reservoir, the hydro agent arranges a contingent claim (a two-way option) with the thermal plant that pays the hydro player an amount from the thermal plant when reservoir inflows are low and a (possibly) different amount in reverse when reservoir inflows are high. The actual amounts paid are based on the probability distribution of inflows, and reduce the risk of both parties. Such a contract was recently arranged in New Zealand between a thermal and a hydro generator (see [2]).

In the last few years a very elegant theory of market equilibrium and coherent risk measures has emerged ([7, 16]). The key result, established by Danny Ralph and Yves Smeers [16], states that if each agent \(i\) has a coherent risk measure with risk set \(\mathcal{D}_i\), and \(\cap_{i}\mathcal{D}_i\) is polyhedral or has nonempty relative interior, and the market for trading risk is complete, then a risk-averse social planning solution with risk set \(\cap_{i}\mathcal{D}_i\) corresponds to a competitive equilibrium in which all agents optimally trade their risk. In this equilibrium, all agents and the social planner view the random future through the same lens, placing higher weight on exactly the same scenarios. The risk trading, that is, alters the players’ payoffs so that all agree on the worst-case future scenarios.

This correspondence with a socially optimal solution enables regulators and market designers to go some way toward establishing good market mechanisms under perfect competition. The theorem indicates that sufficient traded instruments are needed if a social optimum is to be achieved. Numerical experiments with different mixtures of contracts show that some existing instruments are better than others, and can get most of the way to a socially optimal solution. These models are being used to understand how capital investment decisions are affected by risk in competitive markets [4], and how prices in markets with hydroelectricity increase as water shortages approach [15].

Many mathematical challenges remain. Hydrothermal scheduling problems with many reservoirs are high-dimensional stochastic control problems. Approximate solutions can be obtained with variations of the stochastic dual dynamic programming (SDDP) algorithm [13], in both risk-neutral and risk-averse settings [14, 18]. This method constructs an outer approximation of the Bellman function of dynamic programming through Monte-Carlo sampling of the random variables and cutting planes. A version of the Ralph–Smeers theorem is also available for multistage problems when formulated in scenario trees. Regulators can use this method to postulate a system dynamic risk measure that enables them to benchmark actual market prices against those obtained with a competitive equilibrium and complete markets for risk.

The main challenge with such an approach arises in the computation. As mentioned above, computing approximate solutions to multistage social planning problems uses a dynamic programming approach that approximates the Bellman functions with cutting planes. This approach relies on the random processes having stagewise-independent noise terms, a serious restriction. For most problems with no more than about ten reservoirs, the approximate Bellman functions converge to a policy that, when simulated, is provably close to optimal (with high probability). The subgradients of the Bellman function, however, show poorer convergence behavior. This matters, as these marginal water values are estimates of equilibrium energy prices.

Finally, the numerical solution of multistage competitive equilibrium in the incomplete case remains a challenge that mathematicians are actively pursuing. The goal is to compute a competitive equilibrium at large scale, which makes decomposition essential. Policy makers and regulators are in desperate need of such computational tools, which will enable them to oversee market behavior in the hope of making it more competitive and therefore more efficient.

References
[1] P. Artzner, F. Delbaen, J.-M. Eber, and D. Heath, Coherent measures of risk, Math. Finance, 9 (1999), 203-228.
[2] K. Barker, Meridian signs new hedge contract with Genesis, NZ Energy News, July 8, 2014.
[3] S. Borenstein, J. Bushnell, and S. Stoft, The competitive effects of transmission capacity in a deregulated electricity industry, RAND J. Econom., 31:2 (2000), 294-325.
[4] A. Ehrenmann and Y. Smeers, Generation capacity expansion in a risky environment: A stochastic equilibrium analysis, Oper. Res., 59:6 (2011), 1332-1346.
[5] F. Facchinei and C. Kanzow,  Generalized Nash equilibrium problems, Ann. Oper. Res., 175:1 (2010), 177-211.
[6] P.T. Harker, Generalized Nash games and quasi-variational inequalities, Eur. J. Oper. Res., 54:1 (1991), 81-94.
[7] D. Heath and H. Ku, Pareto equilibria with coherent measures of risk, Math. Finance, 14:2 (2004), 163-172.
[8] B.F. Hobbs, The next generation of electric power unit commitment models, International Series in Operations Research & Management Science, Vol. 36, Springer, New York, 2001.
[9] P. Holmberg and A.B. Philpott, Supply function equilibria in transportation networks, Tech. Rep., Electric Power Optimization Centre, 2013; www.epoc.org.nz.
[10] J. Lavaei and S.H. Low, Zero duality gap in optimal power flow problem, IEEE Trans. Power Systems, 27:1 (2012), 92-107.
[11] P. Lino, L.A.N. Barroso, M.V.F. Pereira, R. Kelman, and M.H.C. Fampa, Bid-based dispatch of hydrothermal systems in competitive markets, Ann. Oper. Res., 120:1 (2003), 81-97.
[12] J.-S. Pang and M. Fukushima, Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games, Comput. Manag. Sci., 2:1 (2005), 21-56.
[13] M.V.F. Pereira and L.M.V.G. Pinto, Multi-stage stochastic optimization applied to energy planning, Math. Program., 52 (1991), 359-375.
[14] A.B. Philpott, V.L. de Matos, and E.C. Finardi, On solving multistage stochastic programs with coherent risk measures, Oper. Res., 2013.
[15] A.B. Philpott, M.C. Ferris, and R.J.-B. Wets, Equilibrium, uncertainty and risk in hydrothermal electricity systems, Tech. Rep., Electric Power Optimization Centre, 2014; www.epoc.org.nz.
[16] D. Ralph and Y. Smeers, Pricing risk under risk measures: An introduction to stochastic-endogenous equilibria, 2011; http://ssrn.com/abstract=1903897.
[17] R.T. Rockafellar and S. Uryasev, Optimization of conditional value at risk, J. Risk, 2 (2000), 21-41.
[18] A. Shapiro, Analysis of stochastic dual dynamic programming method, Eur. J. Oper. Res., 209 (2011), 63-72.
[19] A. Shapiro, D. Dentcheva, and A. RuszczyƄski, Lectures on Stochastic Programming, SIAM, Philadelphia, 2009.
[20] J. Yao, I. Adler, and S.S. Oren, Modeling and computing two-settlement oligopolistic equilibrium in a congested electricity network, Oper. Res., 56:1 (2008), 34-47.


Andy Philpott is a professor of engineering science at the University of Auckland, New Zealand.

blog comments powered by Disqus