Estimation of the Shapley Value of a Peer-to-Peer Energy Sharing Game using Coalitional Stratified Random Sampling
Liyang Han Thomas Morstyn Malcolm McCulloch



 


[footnoteinfo]This work was supported in part by the Engineering and 
Physical Sciences Research Council under Grants EP/N03466X/1 and 
EP/S000887/1, and in part by the Oxford Martin Programme on Integrating 
Renewable Energy.

First]Liyang Han 
First]Thomas Morstyn 
First]Malcolm McCulloch

[First]Department of Engineering Science, University of Oxford, UK 
(e-mail: liyang.han, thomas.morstyn, malcolm.mcculloch@eng.ox.ac.uk).

   

   

                
Various peer-to-peer energy markets have emerged in recent years in an attempt to manage distributed energy resources in a more efficient way. One of the main challenges these models face is how to create and allocate incentives to participants. Cooperative game theory offers a methodology to financially reward prosumers based on their contributions made to the local energy coalition using the Shapley value, but its high computational complexity limits the size of the game. This paper explores a stratified sampling method proposed in existing literature for Shapley value estimation, and modifies the method for a peer-to-peer cooperative game to improve its scalability. Finally, selected case studies verify the effectiveness of the proposed coalitional stratified random sampling method and demonstrate results from large games.



P2P energy sharing, cooperative game theory, Shapley value, energy management, energy storage








§ INTRODUCTION


The increasing penetration of distributed energy resources (DER) poses challenges to distribution network operation. One of the most important topics recent researches have been focusing on is how to maintain the reliability of energy supply while encouraging distributed renewable generation, which is highly variable and intermittent, see <cit.>. Curtailment is applied in some networks with high renewable generation, see <cit.>. However, it introduces inefficiency into the energy system and financially penalizes owners of renewable resources. Centralized control of DER is also proposed in various researches, but they tend to overlook the fact that prosumers, proactive-consumers with distributed energy resources that actively control their energy behaviors, are independent entities who need incentives to participate in such a centralized control scheme, see <cit.>. The idea of setting up a peer-to-peer (P2P) energy sharing scheme is gaining tremendous attention both in the industry and academia in recent years, as it is considered a key market strategy to financially encourage efficient local management of DER, see <cit.>.

A key feature of a P2P sharing scheme is its ability to use local flexibility to offset generation uncertainty. Local flexibility often takes the form of energy storage (ES), which can be modeled in a similar way as other types of flexible demand, see <cit.>. This paper makes the common assumption that the price to export energy to the energy network is lower than the price to import, see <cit.>; hence, for a single prosumer, the benefit of flexibility is easily reflected in their energy bills when they increase the local usage of their own generation by optimally scheduling their ES. In a P2P market, more joint benefit can be reaped from matching local flexibility with variable generation among all the participants. At the same time, however, it becomes a challenge to allocate the benefit to each participant in an efficient and fair way.

Game theory has been adopted in some recent research to look at how to affect prosumer behavior using financial incentives. Dynamic pricing coupled with non-cooperative game theory is one of the most popular topics, see <cit.>, but it fails to demonstrate consistent benefit for every participant, see <cit.>. Cooperative game theory is proposed as an alternative approach and is shown in <cit.> that financial rewards can be fairly allocated using the Shapley value, which is based on the contribution each prosumer makes to this joint scheme. 

A player's Shapley value in a cooperative game is a weighted average of their marginal contribution to all the possible coalitions among all players, see <cit.>. For an N-player game, there are 2^N possible coalitions, which means that the computation of Shapley value becomes intractable when increasing the number of players. The estimation of the Shapley value has been explored in some previous literature, sampling being the main methodology. An example is the cooperative scheme described in <cit.>, but the model is constructed as simple games with a binary outcome representing whether a coalition of battery-owning households can overcome a hard network constraint. This scheme overlooks the contributions made by local generation or ES units that are not big enough to switch the binary outcome. 

To improve the scalability of the P2P cooperative game proposed in <cit.>, this paper identifies a random sampling method as a way to estimate the Shapley value. The method was proposed in <cit.>, and then modified in <cit.> by adding a stratification step to the sampling, improving the accuracy of the estimation. This paper adapts this stratified sampling method by further creating coalitional strata for better performance in this specific application. The proposed sampling method enables the P2P game to scale up, and we are then able to analyze the impact of different DER adoption rates on prosumer profitability. Some interesting findings are shown in the case studies. 








§ P2P COOPERATIVE GAME


In an N-player cooperative game, the grand coalition 𝒩 is defined as the group of all N players. Any subset of the grand coalition 𝒯: 𝒯⊆𝒩 is called a coalition. The basic framework of the P2P cooperative game proposed in <cit.> involves mainly three steps. Step 1 is to cooperatively manage DER within all coalitions, which requires optimally scheduling the ES units to minimize the coalitional energy cost, see Subsection <ref>. Step 2 is to quantify the value of forming each coalition, see Subsection <ref>. Step 3 is to divide the total energy cost savings from forming the grand coalition to all the players based on certain criteria, see Subsection <ref>.



 §.§ Coalitional Energy Management
 

We index each prosumer by i and the grand coalition by i ∈𝒩 := {1,2,...,N}. If we consider K timesteps (t = 1, 2,..., K) with a time interval of Δ t, the total energy cost of a coalition 𝒯 can be written as

    F_𝒯(𝐛) = ∑_t=1^K∑_i ∈𝒯{r^im_t  [p_it + b_it]^+ + r^ex_t [p_it + b_it]^- }

where subscripts i and t are indices for the player and the timestep respectively. The known inputs are r^im_t, r^ex_t, and p_it, which are electricity import price (/kWh), electricity export price (/kWh), and net energy consumption (positive) or generation (negative) (kWh) without ES. The variables are 𝐛∈ℝ^N × K := b_it, ∀ i ∈ [1,N], ∀ t ∈ [1,K]: ES charge (positive) or discharge (negative) energy (kWh). We also define operation [z]^+(-) = max (min) {z,0}.

With the assumption r^im_t > r^ex_t, ∀ t, we can schedule all the ES units' operation within coalition 𝒯 to minimize the coalitional energy cost G(𝒯), which is defined as

    G(𝒯) =     min_𝐛F_𝒯(𝐛)
    
    s.t.      b_i≤ b_it≤b_i,   ∀ i ∈𝒯, ∀ t ∈ [1, K] 
        0 ≤ e_i SoC^0_i + ∑_t=1^k ([b_it]^+η_i^in + [b_it]^- / η_i^out)  ≤ e_i
                             ∀ i ∈𝒯, ∀ k ∈ [1, K] 
       ∑_t=1^K ([b_it]^+η_i^in + [b_it]^- / η_i^out) = 0,   ∀ i ∈𝒯

where (<ref>), (<ref>), and (<ref>) represent the ES power constraint, energy constraint, and cycle constraint respectively. We consider each prosumer i's ES system has an energy capacity (𝑘𝑊ℎ) of e_i≥ 0, a charge limit (𝑘𝑊ℎ) of b_i≥ 0 and a discharge limit (𝑘𝑊ℎ) of b_i≥ 0 over the time span of Δ t, a charge efficiency of η_i^in∈ (0, 1) and a discharge efficiency of η_i^out∈ (0, 1), and an initial state of charge of SoC^0_i ∈ [0, 1]. For a prosumer who does not own an ES system, we set their energy capacity and charge/discharge limits all as zeros. 



Fig. <ref> demonstrates the effect of cooperative ES operation in a 16-prosumer scenario. As shown in (d), the cooperative ES operation tends to flatten the load as it tries to match the consumption and generation within the coalition to minimize the coalition energy cost.



 §.§ Value of Coalitions
 

The purpose of using cooperative game theory is to establish a framework to quantify the benefit of cooperation, and then to allocate the benefit to the participants efficiently. The coalitional energy cost provides a great metric to evaluate a coalition's performance. Here, we define the value of a coalition  𝒯 as the energy cost savings obtained by forming the coalition. This is given by the difference between the sum of the energy costs incurred by each prosumer in 𝒯 when they schedule the ES systems individually, and the minimum coalitional energy cost of 𝒯 when the prosumers schedule their ES systems collectively:

    v(𝒯) = ∑_i ∈𝒯G({i}) - G(𝒯)


By this definition, the value of the grand coalition becomes the total energy cost savings of a P2P cooperative game, which denotes the total amount of payoffs we can award to all the participants.



 §.§ Prosumer Payoffs and Shapley Value
 

The second step in a cooperative game framework is the allocation of payoffs. We use vector 𝐱∈ℝ^N as the payoff allocation whose entry x_i represents the payment to prosumer i ∈𝒩. One important payoff allocation is called the Shapley value denoted as ϕ_i, ∀ i ∈𝒩, see <cit.>, representing each player's weighted average marginal contribution to all possible coalitions within the game:

    ϕ_i = ∑_𝒯⊂𝒩, i ∉𝒯(𝒯)! (N - 𝒯 - 1)!/N! [v(𝒯∪ i) - v(𝒯)]


The Shapley value also satisfies the following axioms:


  * (Efficiency) ∑_i ∈𝒩ϕ_i = v(𝒩). This requires the entirety of the value created by the grand coalition to be allocated to the players. 

  * (Individual Rationality) ϕ_i ≥ v({i}), ∀ i ∈𝒩. This ensures that no player is penalized for cooperating.  

  * (Symmetry) If v(𝒯∪{i}) = v(𝒯∪{j}), ∀𝒯⊆𝒩, 𝒯∩{i,j} = ∅, then ϕ_i = ϕ_j.  This means that two players should be assigned the same Shapley value if they have the same marginal contributions to all the coalitions. 

  * (Dummy Axiom) If v(𝒯) = v(𝒯∪{i}), ∀𝒯⊆𝒩, 𝒯∩{i} = ∅, then ϕ_i = 0. Therefore, a player's Shapley value should be zero if they add zero marginal value to any of the coalitions. 

  * (Additivity) If v and u are characteristic functions, then ϕ_i(v+u) = ϕ_i(v) + ϕ_i(u), ∀ i ∈𝒩. This indicates that the Shapley value of two games played at the same time should be the sum of the two games' Shapley values when played separately. 


Axiom (<ref>) guarantees that all the profits allocated to the prosumers add up to the total energy cost savings from the grand coalition. In our P2P cooperative game, v({i}) = 0, ∀ i ∈𝒩, so Axiom (<ref>) requires ϕ_i ≥ 0, ∀ i ∈𝒩. Axiom (<ref>) and (<ref>) ensure the `fairness' of the payoff allocation. Axiom (<ref>) is not actively used in this paper as the P2P cooperative game is the only game discussed here.

The Shapley value offers a way to incentivize prosumers to participate in this cooperative scheme, improving the local energy supply reliability while encouraging the efficient use of distributed renewable generation. However, the scalability of the proposed model is very limited because the Shapley value's computational time increases exponentially with the size of the grand coalition. The following section looks into a sampling method to estimate the Shapley value to reduce the model's computational complexity. 



§ ESTIMATION OF SHAPLEY VALUE


The scalability of the P2P cooperative game model is mainly limited by the sheer number of cost minimization problems that are required to be solved. This number is equal to the number of possible coalitions, 2^N, where N is the number of participating prosumers. Since the Shapley value is the weighted average of a player's marginal contributions, sampling is identified as a promising estimation technique to be applied in our P2P cooperative game. 






































 §.§ Stratified Random Sampling


The conventional definition is expressed in (<ref>). <cit.> provided an alternative definition of the Shapley value expressed in terms of all possible orders of the players, which was then adopted by <cit.> to develop a random sampling method to estimate the Shapley value. In this approach, π(𝒩) is defined as the set of all possible permutations with player set 𝒩, and O: 𝒩→𝒩 as a permutation that assigns player O(k) to position k. For a given O ∈π(𝒩), the set of predecessors of the player i is denoted as Pre^i(O), where if i = O(k), Pre^i(O) = {O(1), O(2), ..., O(k-1)}. Player i's marginal contribution is δ(O)_i = v(Pre^i(O) ∪ i) - v(Pre^i(O)). The alternative definition of Shapley value can be written as

    ϕ_i = ∑_O ∈π(𝒩)1/N!δ(O)_i, i ∈𝒩


Since π(𝒩) = N! and δ(O)_i are equally weighted for all O ∈π(𝒩) in (<ref>), the Shapley value can be estimated using the unweighted expectation of δ(O)_i given a set of randomly sampled permutations M:

    ϕ_i = ∑_O ∈ M1/Mδ(O)_i, i ∈𝒩


The alternative definition of the Shapley value is just a special case where M=π(𝒩).

Using (<ref>), the Shapley value can be estimated from randomly sampling player permutations, see <cit.>. To improve the estimation accuracy, <cit.> proposed a stratified random sampling approach to divide the population of all player permutations into subpopulations that have the same size of predecessors for each player. This stratified random sampling method follows the following steps.


  * A stratum, or a stratified set of player permutations is defined as P_il := {O ∈π(𝒩) | O(l) = i, ∀ i, l ∈ [1, N] }. Therefore, P_il contains every permutation O ∈π(𝒩), in which player i is in position l. Player i's mean marginal contribution of each stratum is

    ϕ_il = 1/P_il∑_O ∈ P_ilδ(O)_i, ∀ i,l ∈ [1, N]


  * A random permutation sample M_il of size M_il is obtained with replacement from each stratum P_il.

  * Adapted from (<ref>), player i's mean marginal contribution of the samples from each stratum is

    ϕ_il = 1/M_il∑_O ∈ M_ilδ(O)_i, ∀ i,l ∈ [1, N]

The estimated Shapley value can then be calculated as ϕ^st_i = ∑_l=1^N 1/Nϕ_il, ∀ i ∈ [1, N].



We notice that in (<ref>), δ(O)_i are equally weighted for all O ∈ M_il. Because each player set (coalition) Pre^i(O) appears (l-1)!(N-l)! times for a given l, they have the same probability of being sampled from P_il into M_il. We define the coalitional stratum as the set of coalitions Q_il := {𝒯⊆𝒩| i ∉𝒯, 𝒯 = l-1, ∀ i,l ∈ [1,N]}, and Δ(𝒯)_i = v(𝒯∪ i) - v(𝒯). We then obtain a random sample H_il with replacement from Q_il, and because the order of players does not matter in a coalition, H_il can be considered a combination sample. (<ref>) can be rewritten as

    ϕ_il = 1/H_il∑_𝒯∈ H_ilΔ(𝒯)_i, ∀ i,l ∈ [1, N]




 §.§ Modified Sampling with Optimal Sample Allocation


In order to implement the stratified random sampling method, a procedure to determine the sample size of each stratum needs to be established. <cit.> identified the true variance as a metric to allocate the samples among strata to minimize the estimation error, and proposed a two-stage Shapley value estimation algorithm with optimal sample allocation. In the first stage, 50% of the samples are evenly distributed to each stratum to obtain an initial estimated Shapley value and each stratum's sample variance. In the second stage, the remaining 50% of the samples are optimally allocated to each stratum in proportion to their sample variances calculated in the first stage. The final estimated Shapley value is then calculated using the sampling results from both stages.









We then recognize that Q_il = (N-1)!/(l-1)!(N-l)!, which means that evenly dividing the samples in the first stage could result in a sample size larger than the size of some coalitional strata: H_il > Q_il, especially when l is close to 1 or N. Applying random sampling to obtain ϕ_il in these coalitional strata would take even more time and produce less accurate results than directly calculating ϕ_il:

    ϕ_il = 1/Q_il∑_𝒯∈ Q_ilΔ(𝒯)_i, ∀ i,l ∈ [1, N]

Using (<ref>) and (<ref>), we modify the two-stage stratified random sampling method with optimal sample allocation to estimate the Shapley value. This modified method is detailed in Algorithm <ref>.



In Stage 1, in the case where the evenly distributed sample size is bigger than the stratum size, we compute the stratum's precise mean marginal contribution ϕ_il, and add the saved samples to Stage 2. This way, we can improve the accuracy of the estimation both by using the precise stratum marginal contribution, and by increasing the number of samples for optimal allocation. 



§ CASE STUDIES


In the following two case studies, we implement the proposed sampling method to estimate the Shapley value of our P2P cooperative game. In the first case study, we select a range of prosumer numbers so we can compare the computational time of the estimated Shapley value and the actual Shapley value, and evaluate the accuracy of the estimation. In the second case study, we scale up the size of the game to evaluate the payoffs to the prosumers based on their DER types. 

Some of the model inputs are as follows: the domestic load data was measured in the Customer-Led Network Revolution trials[http://www.networkrevolution.co.uk/resources/project-library]. the model time frame is 24 hours starting from the midnight of a sunny summer day in July. The PV systems are 4kW with fixed 20 degree tilt, simulated in PVWatts[http://pvwatts.nrel.gov/pvwatts.php] using the London Gatwick solar data. The ES model has an energy capacity of 7 kWh, a maximum charge power of 3.5 kW, a maximum discharge power of 3.2 kW, both charge and discharge efficiencies of 95%, an initial state of charge of 50%, and a state of charge range of 20-95%. The energy import price follows a UK Economy 7 residential rate structure: 0.072/kWh for midnight–7am, and 0.1681/kWh for 7am–midnight[https://www.gov.uk/government/statistical-data-sets/annual-domestic-energy-price-statistics], and the energy export price is the UK feed-in tariff[https://www.gov.uk/feed-in-tariffs/overview] fixed at 0.0485/kWh.



 §.§ Validation of Sampling-Based Shapley Estimation


In this case study, we fix the the PV and ES adoption rates both at 50%, and both ownerships are randomly assigned independently of each other. In other words, each prosumer can have a PV system, or an ES system, or both, or neither. We apply a range of prosumer numbers to compare the computation time between the full Shapley value calculation and the Shapley value estimation with the proposed sampling method. 

Compared against each other are three models: 1) full Shapley value calculation, 2) Shapley value estimation using the proposed sampling method with 10^3 samples per player, and 3) Shapley value estimation using the proposed sampling method with 10^2 samples per player. 

Table <ref> shows the computation time[Running on Apple iMac with a processor of 2.8 GHz Intel Core i5 and a memory module of 16 GB 1867 MHz DDR3] of the three models. We only show computation times that are under 10 hours as we consider any time above 10 hours to be impractical for this application. As predicted, the full Shapley value calculation is shown to be intractable. When the number of players exceeds 16, the sampling method significantly reduces the computation time, and with the same number of players the computation time is largely in proportion to the number of samples specified.





We then compare the model results for the 16-player game, the largest game that can be computed for a full model within a reasonable time. From Fig. <ref> we can see that the Shapley value estimation accuracy with 10^3 samples per player is very high, whereas the estimation with 10^2 is slightly less accurate. This confirms that there is a trade-off between the computation time and the accuracy of the model when choosing the number of samples. 



In order to understand this trade-off better when the number of prosumer is further increased. We select a game of 30 prosumers and compare the estimated Shapley values with the two different sample sizes, and the results are plotted in Fig. <ref>. Even though the computation time for the 10^3 samples/player model is about 10 times the 10^2 samples/player model, see Table <ref>, the estimated Shapley values from the two models are very similar regardless of the type of resources owned by a prosumer. This gives us confidence in using a relatively low number of samples (≥ 10^2 samples/player) to estimate the Shapley value of larger P2P cooperative games.



 §.§ Sampling-Based Shapley Value for Large Games




For a P2P cooperative game with 50 prosumers, we use 250 samples/player to ensure each coalitional stratus is sufficiently represented in the samples while keeping the computation within an acceptable time. First, we keep the number of PV and ES systems the same and vary their adoption rates together. Fig. <ref> compares the estimated Shapley values by players' DER ownership type, where each marker represents a prosumer's estimated Shapley value. There are a few interesting observations. First, except for a few outliers, prosumers with the same DER ownership type are rewarded similar Shapley values regardless of the overall DER adoption rate. Second, as the DER adoption rates change, there is a significant shift in the Shapley values; when the DER adoption rates are low, PV owners are awarded significantly higher Shapley values likely because they provide cheaper energy to the coalitions, while when the DER adoption rates are high, pure consumers and ES owners are awarded higher Shapley values likely because they absorb more local generation. Third, as the DER adoption rates increase, the average Shapley values by DER ownership type tends to converge despite the wider spread among the pure consumers and prosumers with only ES systems. 



With the same 50 prosumers, we then pick out four typical prosumers with different DER ownership types, and run the P2P cooperative model under four different scenarios: 1) PV adoption rate is fixed at 30%, and ES adoption rate varies from 10% to 50%, 2) PV adoption rate is fixed at 50%, and ES adoption rate varies from 10% to 50%, 3) ES adoption is rate fixed at 30%, and PV adoption rate varies from 10% to 50%, and 4) PV and ES are with the same adoption rate that varies from 10% to 50%. Fig. <ref> illustrates how the Shapley value changes with different DER adoption rates. Based on the DER ownership type, the trend at which the Shapley value changes with the varying DER adoption rates can be very different. For example, a consumer that does not own any PV or ES tends to be awarded more when the adoption rates for the PV and ES increase together, whereas a prosumer that owns both PV and ES display the opposite trend. It is interesting to note that when the PV adoption rate is fixed, whether at 30% or 50%, varying the ES adoption rate has very little influence on the Shapley value regardless of the prosumer type. In contrast, whether the ES adoption rate is fixed at 30% or follows the PV adoption rate, varying the PV adoption rate has a significant impact on the Shapley value of all prosumer types.

It is worth noting that the main purpose of the case studies is to validate the scalability of the proposed sampling method applied in the P2P cooperative game. The specific results shown are dependent on the assumptions made about the PV, ES system specifications, and the energy prices. Further sensitivity analyses need to be conducted to generalize the results to other markets. 



§ CONCLUSION


To improve the scalability of the P2P cooperative game <cit.>, this paper modifies a stratified random sampling method <cit.> to estimate the Shapley value. The maximum size of the game that can be computed in a reasonable time (<10 hours) is thus increased from less than 20 players to 50 players. Through case studies, the estimation errors are shown to be very small. The proposed model is then run on a P2P cooperative game of 50 players to demonstrate some interesting patterns and trends in the Shapley value for different prosumer DER ownership types and with varying DER adoption rates. Some future work includes sensitivity analyses on the PV and ES system inputs and electricity prices, and improving the sampling method to be able to further scale up the size of the P2P cooperative game.




















             
                                                     
                                                   

































                                                                         
