A Stackelberg game-theoretic approach to optimal real-time pricing for the smart grid

Abstract

This paper proposes a Stackelberg game approach to maximize the profit of the electricity retailer (utility company) and minimize the payment bills of its customers. The electricity retailer determines the retail price through the proposed smart energy pricing scheme to optimally adjust the real-time pricing with the aim to maximize its profit. The price information is sent to the customers through a smart meter. According to the announced price, the customers can automatically manage the energy use of appliances in the households by the proposed optimal electricity consumption scheduling system with the aim to minimize their electricity bills. We model the interactions between the retailer and its electricity customers as a 1-leader, N-follower Stackelberg game. At the leader’s side, i.e., for the retailer, we adopt genetic algorithms to maximize its profit while at the followers’ side, i.e., for customers, we develop an analytical solution to the linear programming problem to minimize their bills. Simulation results show that the proposed approach is beneficial for both the customers and the retailer.

Appendices

Appendix A: Proof of existence of Stackelberg strategy

The Stackelberg game considered in this paper can be formulated as below:

There are $N+1$ players, in which one player (i.e, retailer) is the leader $L$ and N other players (i.e., customers) are the followers $F_{i} \; (i=1,2,\ldots ,N)$. The leader’s strategy is denoted as $u_{L}$ and its strategy space is $U_{L}$ whereas the strategy of follower $F_{i} \;$ is $u_{F_{i} }$ and its strategy space is $U_{F_{i} }$. The utility function for leader $L$ is $J_{L} (u_{L} ,u_{F_{1} } ,\ldots ,u_{F_{N} } )$, whereas the utility function for follower $F_{i} \;$is $J_{F_{i} } (u_{L} ,u_{F_{i} } )$, which means that the follower’s utility function is completely decided by the leader’s strategy $u_{L}$ and its own strategy $u_{F_{i} }$ and is independent to the other followers’ strategies $u_{F_{j} } \; (j=1,2,\ldots ,N,j\ne i)$. The reason for this particular form of utility functions for the followers is that each customer’s decision about electricity usages is independent from other customers’ decisions.

In this game, each player’s goal is to minimize its utility function, where each follower’s utility function is its bill function whereas the leader’s utility function is defined as minus one times its profit function (that is, the leader’s goal is to maximize the profit function). The rule of playing is: The leader (i.e., retailer) announces its strategy (i.e., prices) first, after knowing the leader’s strategy, the followers (i.e., customers) selects their best reaction to minimize their electricity bills.

The above Stackelberg game is a special case of general Stackelberg games with one leader and multiple followers, because the followers’ utility functions take the simpler form as $J_{F_{i} } (u_{L} ,u_{F_{i} } )$ rather than $J_{F_{i} } (u_{L} ,u_{F_{1} },\ldots ,u_{F_{i} } ,\ldots ,u_{F_{N} } )$. As a result, there is no need to use Nash equilibrium concept to define how the followers’ reactions to the leader’s announced strategy, but each follower just simply selects its best strategy to minimize its utility function. That is, for any announced strategy $u_{L} \in U_{L}$, the reaction from follower $F_{i} \;$ is to select its best strategy $u_{F_{i} }^{*}$ which minimizes its utility function $J_{F_{i} } (u_{L} ,u_{F_{i} } )$ with the given $u_{L} \in U_{L}$. As for each leader’s strategy, there is a reaction strategy from follower $F_{i} \;$. Therefore the follower’s reaction function can be defined as below:

$$\begin{aligned} u_{F_{i} }^{*} \!=\! R_{F_{i} } (u_{L} )= \arg \, \min _{u_{F_{i} } \in \, U_{F_{i} } } J_{F_{i} } (u_{L} ,u_{F_{i} } ) \quad i=1,2,\ldots ,N \nonumber \\ \end{aligned}$$

(27)

With the reaction functions $R_{F_{i} } (u_{L} )\; (i=1,2,\ldots ,N)$ defined as above, we can define Stackelberg strategy (equilibrium) concept below by following the standard definition.

Definition 6.1

Let $u_{L}^{S} \in U_{L}$ be a strategy which minimize the leader’s utility function as follows:

$$\begin{aligned} u_{L}^{S} =\arg \, \min _{u_{L} \in U_{L} } J_{L} [u_{L} ,R_{F_{1} } (u_{L} ),\ldots ,R_{F_{N} } (u_{L} )]\quad \end{aligned}$$

(28)

and $u_{F_{i} }^{S} =R_{F_{i} } (u_{L}^{S} ) (i=1,2,\ldots ,N)$. Then $\big (u_{L}^{S} ,\, u_{F_{1} }^{S} ,\ldots , u_{F_{N} }^{S} \big )$ is called Stackelberg strategy.

In the case when $N=1$, the above definition gives the standard definition of Stackelberg strategy for a two-person (i.e., one leader and one follower) Stackelberg game. In this case, the index in $F_{1} \;$will be omitted and denotes as $F$. For two-person Stackelberg game, the following theorem about the existence of Stackelberg strategies was given and proved in Simaan and Cruz (1973).

Lemma 6.1

For a two-person Stackelberg game, if $U_{L}$ and $U_{F}$ are compact sets, $U_{L} \subset R^{n_{L} }$ and $U_{F} \subset R^{n_{F}}\!,$ and if $J_{L} (u_{L} ,u_{F} )$  and $J_{F} (u_{L},u_{F} )$  are real-valued continuous functions on $U_{L} \times U_{F}$, then a Stackelberg strategy exists.

Now using the above Lemma, the following theorem can be proved.

Theorem 6.1

For the considered one leader and $N$-follower Stackelberg game, if $U_{L}$ and $U_{F_{i} } \; (i=1,2,\ldots ,N)$ are compact sets, $U_{L} \subset R^{n_{L} }$ and $U_{F_{i} } \subset R^{n_{F_{i} } } \; (i=1,2,\ldots ,N)$, and if $J_{L} (u_{L} ,u_{F_{1} } ,\ldots ,u_{F_{N} } )$ and $J_{F_{i} } (u_{L} ,u_{F_{i} }) (i=1,2,\ldots ,N)$ are real-valued continuous functions on $U_{L} \times U_{F_{1} } \times \cdots \times U_{F_{N} }$, then a Stackelberg strategy exists.

Proof

Firstly consider the following two-person Stackelberg game: The leader’s strategy is $u_{L} \in U_{L}$ and the follower’s strategy is $\stackrel{\rightharpoonup }{u}_{F} \,=(u_{F_{1} } ,\ldots ,u_{F_{N} } ) \in \; \stackrel{\rightharpoonup }{U}_{F} \,= U_{F_{1} } \times \cdots \times U_{F_{N} }$. Further the leader’s utility function is $J_{L} (u_{L} ,\, \stackrel{\rightharpoonup }{u}_{F} )$ and the follower’s utility function is

$$\begin{aligned} J_{F} (u_{L} ,\stackrel{\rightharpoonup }{u}_{F} )=\sum _{i=1}^{N}J_{F_{i} } (u_{L} ,u_{F_{i} } ) \end{aligned}$$

Under the given condition of Theorem 6.1, it is implied immediately that $U_{L}$ and $\stackrel{\rightharpoonup }{U}_{F}$ are compact sets, $U_{L} \subset R^{n_{L} }$ and $\stackrel{\rightharpoonup }{U}_{F} \subset R^{\sum _{i=1}^{N} n_{F_{i} } }$, and $J_{L} (u_{L} ,\stackrel{\rightharpoonup }{u}_{F} )$and $J_{F} (u_{L} ,\stackrel{\rightharpoonup }{u}_{F} )$are real-valued continuous functions on $U_{L} \times \stackrel{\rightharpoonup }{U}_{F}$. Then from Lemma 6.1, we have that a Stackelberg strategy $\big (u_{L}^{S} ,\, \stackrel{\rightharpoonup }{u}_{F}^{S} \big ) =\big (u_{L}^{S} ,\, u_{F_{1} }^{S} ,\ldots ,u_{F_{N} }^{S} \big )$ exists. Based on the definition of Stackelberg strategy, it is known

$$\begin{aligned} u_{L}^{S} =\arg \, \min _{u_{L} \in U_{L} } J_{L} [u_{L} ,\stackrel{\rightharpoonup }{R}_{F} (u_{L} )] \end{aligned}$$

(29)

with $\stackrel{\rightharpoonup }{R}_{F} (u_{L}^{} )=\big [\stackrel{\rightharpoonup }{R}_{F_{1} } (u_{L}^{} ),..,\stackrel{\rightharpoonup }{R}_{F_{N} } (u_{L}^{} )\big ]$ being the follower’s reaction function and

$$\begin{aligned} \stackrel{\rightharpoonup }{u}_{F}^{S}&=\left( u_{F_{1} }^{S} ,\ldots ,u_{F_{N} }^{S} \right) =\stackrel{\rightharpoonup }{R}_{F} (u_{L}^{S} )\nonumber \\&=\left[ \stackrel{\rightharpoonup }{R}_{F_{1} } (u_{L}^{S} ),\ldots , \stackrel{\rightharpoonup }{R}_{F_{N} } (u_{L}^{S} )\right] \end{aligned}$$

(30)

Based on the definition of the reaction function given in 27, it is known that

$$\begin{aligned}&\stackrel{\rightharpoonup }{R}_{F} (u_{L}^{} )=\left[ \stackrel{\rightharpoonup }{R}_{F_{1} } (u_{L}^{} ),..,\stackrel{\rightharpoonup }{R}_{F_{N} } (u_{L}^{} )\right] \nonumber \\&\qquad = \arg \, \min \limits _{\stackrel{\rightharpoonup }{u}_{F}^{} \subset \stackrel{\rightharpoonup }{U}_{F} } \, J_{F} (u_{L}^{} ,\stackrel{\rightharpoonup }{u}_{F}^{} )\nonumber \\&\qquad = \arg \, \min \limits _{(u_{F_{1} } ,\ldots ,u_{F_{N} } )\subset U_{F_{1} } \times \ldots \times U_{F_{N} } } \, \sum _{i=1}^{N} J_{F_{i} } (u_{L}^{} ,u_{F_{i} }^{} )\nonumber \\&\qquad = \sum \limits _{i=1}^{N} \arg \, \min \nolimits _{u_{F_{i} } \subset U_{F_{i} } } \, J_{F_{i} } (u_{L}^{} ,u_{F_{i} }^{} ) \end{aligned}$$

(31)

Noting that $R_{F_{i} } (u_L )=\arg \, \min _{u_{F_{i} } \subset U_{F_{i} } } \, J_{F_{i} } (u_{L}^{} ,u_{F_{i} }^{} ) (i=1,2,\ldots ,N)$, the above equality implies $R_{F_{i} } (u_L ) =\stackrel{\rightharpoonup }{R}_{F_{i} } (u_L ) \; (i=1,2,\ldots ,N)$ and thus $\stackrel{\rightharpoonup }{R}_{F} (u_{L}^{} )= \big [\stackrel{\rightharpoonup }{R}_{F_{1} } (u_{L}^{} ),..,\stackrel{\rightharpoonup }{R}_{F_{N} } (u_{L}^{} )\big ]=\big [R_{F_{1} } (u_{L}^{} ),..,R_{F_{N} } (u_{L}^{} )\big ]$

Substituting the above equality into (29) and (30), we have

$$\begin{aligned}&u_{L}^{S} =\arg \, \min _{u_{L} \in U_{L} } J_{L} [u_{L} ,\stackrel{\rightharpoonup }{R}_{F} (u_{L} )] \nonumber \\&\quad \quad = \arg \, \min _{u_{L} \in U_{L} } J_{L} [u_{L} ,R_{F_{1} } (u_{L} ),\ldots ,R_{F_{N} } (u_{L} )]\end{aligned}$$

(32)

$$\begin{aligned}&\left( u_{F_{1} }^{S} ,\ldots ,u_{F_{N} }^{S} \right) =\left[ \stackrel{\rightharpoonup }{R}_{F_{1} } (u_{L}^{S} ),\ldots ,\stackrel{\rightharpoonup }{R}_{F_{N} } (u_{L}^{S} )\right] \nonumber \\&\quad \quad \quad \quad \quad \quad \quad \quad \quad = \left[ R_{F_{1} } (u_{L}^{S} ),\ldots ,R_{F_{N} } (u_{L}^{S} )\right] \end{aligned}$$

(33)

Based on Definition 6.1, the above implies that

$\big (u_{L}^{S} ,\, \stackrel{\rightharpoonup }{u}_{F}^{S} \big ) =\big (u_{L}^{S} ,\, u_{F_{1} }^{S} ,\ldots ,u_{F_{N} }^{S} \big )$ is a Stackelberg strategy and this ends the proof of the existence. $\square$

For Stackelberg game considered in this paper, it can be verified as below that the condition of Theorem 6.1 holds:

• 1. For each customer’s billing minimization problem, the constraint set is bounded in a finite dimension real space due to constraints shown as Eqs. (5) and (7). Further all other constraints are equality or less than and equal inequalities. This implies that the constraint set is closed. As each bounded and closed set in a finite dimension real space is compact, this ensures the compact condition holds for each follower.

• 2. For the retailer’s profit maximization problem, the constraint set is bounded in a finite dimension real space due to that each price is bounded by the min and max price bounds. Further all other constraints are equality or less than and equal inequalities. This implies that the constraint set is closed. For the same reason as before, this ensures the compact condition holds for the leader.

• 3. The condition that the utility functions are continuous is obvious as the utility functions for customers’ billing minimisation are bilinear function whereas the utility functions for the retailer’s profit maximization is a quadratic function.

As the conditions of Theorem 6.1 holds, it implies immediately the existence of Stackelberg strategy.

Appendix B: Details of design of our considered genetic algorithms

1.1 B.1 Population representation

We choose the binary-coded representation in this paper as it is the most nature choice and applies to our considered problem.

In Eq. (13), we assume that for each $h \in \{1,2,\ldots 24\}$, we have $p^{min} \le p^h \le p^{max}$. For example, we set $8.00$ cents $\le p^h \le 14.00$ cents. As we know that the length of the binary bits is related to the value and precisions of the variables, we assume the precision requirement $d$ for each variable is two places after decimal, i.e., $d=10^{-2}$ and the length of binary bits is $l_h$. To map the real variable $p^h$ into a corresponding binary form (Bashir and Neville 2013), we have

$$\begin{aligned} 2^{l_h-1} \le (p^{max}-p^{min}) \times \frac{1}{d} \le 2^{l_h} \end{aligned}$$

(34)

Thus, for the problem, we have:

$$\begin{aligned} 2^{l_h-1} \le 600 \le 2^{l_h} \end{aligned}$$

and

$$\begin{aligned} 2^9\le 600 \le 2^{10} \end{aligned}$$

Hence, the required bit length for each variable is $l_h = 10$.

Notice that for our problem to be well encoded so as to handle the required precision of 2-decimal places, the use of 10-bits in the binary representation is crucial.

However, since the interval of [8.00 14.00] only requires a maximum of 600 numbers, employing the 10-bits representation unavoidably results in, for a significant portion of the samples, having to map two consecutive genotype samples into a common phenotype value (some sort of redundant representation leading to utilising just more than half of the available space).

While this might slow down the evolutionary process, it does not render the overall evolutionary process any faulty.

1.2 B.2 Tournament selection and Elitism

Binary deterministic tournament selection is adopted in our paper. In this selection, two individuals are chosen at random and the better of the two individuals is selected into the mating pool. The process of tournament selection is described in Algorithm 3 (Blickle and Thiele 1996).

To make sure that the best individuals always survive to the next generation, we adopt elitism in the selection process. In elitism, the best chromosome is copied to the next generation without taking the crossover and mutation. Since the elitism stores the best chromosome obtained till the current generation, it guarantees the reproduction of best chromosome during the evolutionary search procedure. As a consequence, it increases the convergence of the optimization process as well as the robustness of the algorithm.

A typical genetic algorithm with elitism can be described as follows:

Step 1: Generate an initial population $P$ randomly;

Step 2: Evaluate population $P$ and find the best chromosome $C_{best}$ of it;

Step 3: Perform Selection, Crossover and Mutation operations on the population $P$ to get a new population;

Step 4: Find the best chromosome $C_{best}^{'}$ and worst chromosome $C_{worst}^{'}$ of the new Population. If $C_{best}^{'} < C_{best}$, let $C_{worst}^{'} = C_{best}$. Otherwise, no replacement takes place.

Step 5: Go to step 2.

1.3 B.3 Uniform crossover

Algorithm 4 (Syswerda 1989) describes how the uniform crossover works. Usually, we set the probability of swapping to 0.5.

1.4 B.4 Mutation

Bit flip, which simply inverts the value of the chosen gene, is adopted in this paper. This kind of mutation can only be used for binary genes.