In 1996, the Federal Electricity Regulatory Committee (FERC) issued orders 888 and 889 that resulted in the unbundling of electric generation, transmission, and distribution assets (Joskow, 2005). Now, in just over half of the US, no one entity controls all aspects of the market, and administrative bodies called Independent System Operators (ISOs) operate the energy market as a neutral third party by taking supply side offers from generators and demand side bids from consumers. An additional responsibility of ISOs is to plan for transmission expansion. But since they are not responsible for generation planning, ISOs have to take generators' and consumers' response to network additions and transmission prices into account when evaluating potential grid reinforcements (Munoz et al., 2012). On the other hand, in regions where utilities remain vertically integrated, transmission planning is undertaken by the generation companies.
Transmission planning is inherently complex. Several factors contribute to this complexity, including:
1. Transmission upgrades are costly. A poor planning process might result in over-investment ("stranded" assets whose costs exceed their benefits) or under-investment (which can result in inefficient operations). Examples of inefficient outcomes include extensive wind curtailment, as in Texas in the 2000s (Gu et al., 2011) or presently in China (Lam et al., 2016), and solar curtailment, as in India now (Manley, 2016), as well as inefficient siting of generators.
2. Power flows are governed by Kirchhoff's laws.
3. Economic spillovers, in which one region's grid and dispatch decisions affect other regions' costs and benefits.
Notwithstanding these difficulties, US regional transmission planning entities (see Fig. 1) each have planning processes for transmission investment in their control regions. Examples of such processes are MISO (2014) and ER-COT (2014). But these processes usually focus on the benefits of investments to the planner's own region without considering (a) the reactions of generator investment to these investments (i.e., no transmission-generation investment co-optimization), or (b) the effect of the proposed lines on dispatch and transmission investment in other regions (which in turn may affect the planner's own region). In fact, FERC order 1000 (FERC, 2016) recognizes the latter problem by explicitly obligating public utility transmission providers to set-up processes that can identify "possible transmission solutions that may be located in neighboring transmission planning regions". The adoption of this order by FERC is an acknowledgment of the need to consider spillover benefits and costs in other regions, including their quantification and use as a basis for cost allocation. Some interregional transmission planning initiatives such as WECC (2013) and EIPC (2010) naively ignore boundaries between ISOs, focusing on identifying lines that "benefit" the entire system without recognizing that it may be difficult to finance and permit lines that benefit multiple regions. For instance, WECC (2013) and EIPC (2010) develop transmission plans for the western and eastern interconnections respectively using simple production costing and implicitly assuming a single planner.
Many researchers have also proposed solving a single optimization problem to identify transmission reinforcements that would enhance the system's "total economic surplus" or "social welfare" (Gu et al., 2012;Özdemir et al., 2016;Munoz et al., 2012). This is generally done by solving a single cost minimization Mixed Integer Program (MIP) that minimizes the cost of generator investments, transmission investments, and generator dispatch. Such a cost-based model is used because under certain assumptions, it can be shown that the investments resulting from cost minimization are same as the investments from multiple profit-maximizing players' problems. Some of these assumptions are:
1. The players all behave competitively, i.e., they act as if they maximize their individual profit subject to fixed prices.
2. They all hold the same beliefs about future load growth, fuel prices, and environmental policies.
3. They all take decisions simultaneously.
4. There is a single market operator who is also the grid planner.
5. There is no significant spillover of benefits or costs to neighboring regions.
This equivalence can mathematically be proven by showing that the Karush-Kuhn-Tucker (KKT) conditions of the single problem and the individual players' KKT conditions are the same. More details can be found in Özdemir et al. (2016).
But using such a model for a large region encompassing multiple transmission planning entities might not accurately identify lines that will end up getting built, given regional planners' imperfect cooperation and focus on benefits within their regions. Evidence for the divergence of local and market-wide benefits is provided by some promising instances of interregional cooperation and information exchange in transmission planning. For example, MISO and SPP had to re-evaluate proposed interregional lines upon observing that the estimates of some lines' benefits differed significantly when evaluated by regional models versus an interregional model (O'Malley, 2015). Therefore, there is a need for modeling frameworks that explicitly take into account this inconsistency between one subregion's incentives and the overall benefits to all the subregions. In fact, FERC commissioner at the time, Philip Moeller, has been quoted as saying, "There are so many benefits to interregional transmission, but they're so hard to identify and to figure out how to get them built...but it's where there's a lot of inefficiencies." (Rivera-Linares, 2015).
Models that identify transmission lines that are economically attractive even when subregional planners do not cooperate with each other can provide a baseline against which the benefits each subregional planner (and other players within that subregion) may gain by cooperating with other subregional planners can be evaluated. At the same time, such models can be used to identify different side-payment arrangements among planners that could result in benefits for all regions (a strict Pareto improvement).
The objective of this study is then three-fold:
1. Build a general model that accurately captures the incentives faced by subregions within a large region with the goal of identifying transmission lines that get built across all subregions when there is no cooperation between them.
2. Quantify the surplus gained or lost by the individual players (generators, consumers, transmission planner) in all subregions when they cooperate with each other in interregional transmission planning, relative to the extreme of no cooperation in planning. The sum of these individual surplus gains and losses is the total value of interregional cooperation.
3. Show how these individual surplus gains and losses can be used to identify side-payment agreements that incentivize all stakeholders (here, the groups of generators, consumers, and transmission planners) to participate in the cooperation process by guaranteeing that they do not lose money due to the cooperation and in fact may gain from such an exercise. This is possible because quantification of the exact surplus gained or lost by each player gives a clear understanding of who benefits and who does not from interregional cooperation and by how much.
A classic paper in multi-player transmission expansion is Gately (1974) which models different State Electricity Boards in India playing a cooperative game (with side payments amongst the states), where the objective of each state is to maximize its gain by choosing either to act on its own or join a coalition. The drawbacks of this study are that the gains of the coalitions and players are known beforehand and are not considered endogenous to the problem. Furthermore, each state is modeled as controlling both the generation and transmission within its boundaries. While this was (and still is) true in India, much of the US is now deregulated, with generators separated from transmission operators. Another example is Contreras & Wu (1999), which also looks at coalition formation -when being in a coalition means sharing the costs of building transmission lines connecting the coalition's member regions. Unlike the models we propose, that study does not take generators' response to transmission investments into account, and the only transmission decisions made by the model concern lines connecting different regions, and not lines within a region. Jin & Ryan (2014) is one of several papers that address centralized transmission planning subject to reactions of a deregulated generation market. Although this paper models market equilibria problems among generators, it still treats transmission planning as centralized with one transmission planner.
Papers that tackle the problem of multiple transmission planners include Buijs & Belmans (2012), Buijs et al. (2012), Huppmann & Egerer (2015), Tohidi &Hesamzadeh (2014), andTohidi et al. (2017). We discuss each of these in turn. In Buijs & Belmans (2012), three transmission planning paradigms are evaluated -a supranational transmission planner who anticipates the reaction of the entire region, a Pareto-optimal transmission planner who is similar to the supranational planner except for an additional constraint that all zones within the region maintain at least their initial total surplus, and a zonal-planner who is again similar to the supranational planner except that transmission lines across all regions are identified that benefit a single region. The latter approach does not aim to find an equilibrium among different zones. Rather, it is one zone's problem with the objective of identifying transmission lines across all regions that are beneficial to itself. In Buijs et al. (2012), the authors propose a bi-level approach for transmission expansion. In this paper, transmission investment decisions are treated as continuous variables with a phantom bus acting as a mid-way point between two regions (in a two-region case) with both regions building transmission capacity connecting their regions to the phantom bus. In a simple three-zone, three-line example, each zone controls the decision of building transmission capacity on a single line. Each zone's reaction curves are mapped that show how investment by other regions affects that zone's transmission investment. Huppmann & Egerer (2015) propose a three-stage equilibrium model to identify transmission investments that result from a game among different planners. They assume that there is a supra-player at a level above the planners whose objective is to choose seam-line investments (transmission lines crossing regional borders) that maximize the welfare of the interregional system and who correctly anticipates how the planner will react by expanding the capacities of their regional non-seam lines. In our study, we present a more general framework in which every potential line addition is the responsibility of just one of the noncooperative planners with no supra-player. The framework can be easily extended to depict multiple cost-sharing arrangements. We also consider generators' reactions (building plants) to the transmission investments made by the regional planners. Furthermore, Huppmann & Egerer (2015)'s assumptions might lead to two regions building and sharing the costs of a line which neither of them would want to build in the absence of the supra-player. This cannot happen in our model. Finally, while Huppmann & Egerer (2015) unrealistically treat transmission investment decisions as continuous variables, we model them as discrete i.e., it is not possible to build fractions of a line.
In the next of these multi-player papers, Tohidi & Hesamzadeh (2014), each regional transmission planner is assumed to minimize resource cost (the sum of transmission investment and generation costs within the region). This fails to consider the crucial role of import payments and export revenues, and effects on regional power prices. This can lead, e.g., to a situation in which a potentially exporting region would never consider expanding transmission, because exports increase generation costs (even if off-setting revenues are far larger). That paper also disregards the reaction of generator investment to grid reinforcements. Transmission investment is a lengthy process that takes typically 7-10 years and its estimated benefits can be much larger if effects on generator siting and mix are considered (Krishnan et al., 2016). After all, limited transmission capacity is a key driver for locally-sited generation. For example, in California, Local Capacity Requirement (LCR) zones are regions within the state that are deemed to be transmission-constrained and are evaluated annually for local-generation need (CAISO, 2018). Indeed, in addition to showing that generation investment acts as an alternative to transmission lines, we show below a case in which cooperative network planning incents generators to invest in more efficient forms of generation.
In the final paper we discuss, Tohidi et al. (2017) also ignores cross-border trade revenues, and similar to Huppmann & Egerer (2015), penalties are imposed on deviations from a central planner approach. In the US, while FERC Order 1000 (FERC, 2016) encourages transmission planners to cooperate with each other, there is nothing that compels regional transmission plans to maximize benefits to the whole system. Moreover, that study also makes the assumption that inter-regional ties are never congested. This assumes away the most interesting part of the problem, as it is inter-regional congestion that motivates transmission expansion.
In addition to the specific shortcomings already pointed out, the general limitation of these studies is that most of them do not explicitly address the fundamental conflict between a subregion's incentives and those of the wider region as mentioned in Section 1.1. The studies that do, such as Buijs & Belmans (2012), Huppmann & Egerer (2015), and Tohidi et al. (2017), use some form of supra-player or penalties to push the subregions' transmission investments 200 towards those that benefit the entire region. This represents some degree of cooperation or coordination between the subregions which still fails to identify lines that would be built in the absence of any degree of cooperation. Identi-fying lines that an individual region would be motivated to add even without cooperation with other regions is crucial to characterizing one extreme of the cooperation spectrum, with the other extreme characterized by a full-cooperation model (such as the one in Özdemir et al. (2016) and Section 6). Characterizing these extremes allows quantification of the value of any degree of cooperation on this spectrum as well as identification of the exact impact of that cooperation on individual surpluses. This in turn, could incentivize stakeholders (generators, consumers, and transmission planners) to participate in the interregional planning effort, as side-payment agreements can now be identified that guarantee that no player is made worse-off by cooperating.
We address the shortcomings of previous work by creating a general model that represents the independence of planners in different regions by modeling multiple players in the market (ISOs, generators, and consumers) while also recognizing that individual regional planners have their own planning processes that focus primarily on benefits for their own region. We model this interaction as a Nash noncooperative game with no supra-player guiding the players' decisions. The paper is organized as follows. After introducing notation in section 2, in section 3, we develop the mathematical structure of a single regional planner's optimization problem where the goal of the ISO is to maximize the surplus of its region. That surplus is defined as the combined surplus of the generators and consumers in the region and the planner's own surplus. Here, for simplicity, we generalize the concept of a regional planner to that of an ISO where the ISO controls investment in transmission lines in its control region and its surplus arises from its operation of the spot markets. These problems are structured as Mathematical Programs with Equilibrium Constraints (MPECs). In section 4, we expand this model to the case where there are multiple regional planners who simultaneously (but separately and noncooperatively) make their individual investment decisions, each anticipating the spot market's reaction to their decisions. This problem has the structure of an Equilibrium Program with Equilibrium Constraints (EPEC).
Then in section 7, in a case-study using a 17-bus system based on the CAISO network, we show how this multi-planner EPEC can be solved. Consistent with the Nash noncooperative game framework, this is done presuming that each region assumes that other regions do not change their strategies (the transmission lines they build). We then consider whether the transmission plans from this noncooperative planning process differ from plans based upon a single-central planner. We also ask what the value is, if any, of regional planners cooperating with each other when considering transmission investments.
2.1. Sets:
Phase angle in bus b and hour h p b,h
Price at bus b in hour h [$/MWh]
We start by modeling a single regional planner's (ISO's) problem as a cooptimization in which the ISO makes transmission investments anticipating how generators and consumers (in all the regions) respond to those investments. Generators respond to transmission investments by building generation capacity they see as profitable and operating their units economically. Consumers respond by buying energy. While demand is assumed to be inelastic here up to a ceiling price corresponding to the Value Of Lost Load (VOLL), more general formulations can have elastic demand.
The ISO's objective is to maximize the economic surplus of all players within its region. We define this to be the sum of consumers', generators', and the ISO's own economic surpluses. Consumer surplus can be thought of as the monetary gain by consumers from buying power at prices less than the maximum they would have willingly paid. This is the integral of the consumers' demand function from 0 to the quantity (q) purchased, minus the expenditures associated with purchasing q. Here, as load is considered to be inelastic with load curtailment penalized at the VOLL, it can be interpreted as the money saved from avoiding loss of load. Producer surplus can similarly be viewed as generators' net monetary gain from selling power at prices higher than what they would have willingly produced at, minus expenditures on new generation capacity investments. This is the difference between what the producers get paid for selling quantity q to consumers and the sum of the integral of their supply curve from 0 to q and expenditures on generator investments. The ISO only controls line investments within its control-region and on seams (subject to the adjoining ISO's action on that line, see section 3.2 for more details). Its surplus is the net monetary gain from acting as a price-taking spatial arbitrager and trans- The structure of the problem lends itself naturally to a hierarchical model where the regional planner (ISO) is in the upper level making decisions knowing that its objective function (the regional surplus) is affected by outcomes of the generation investment and spot market equilibrium model in the lower level. So, the problem facing each ISO has the structure shown in Fig. 2. The subscript i in ISO i indicates this is a single region's optimization problem.
These bi-level hierarchical problems are also called MPECs since the portion of the ISO's constraints corresponding to market operations is itself an equilibrium problem (Luo et al., 1996). Bi-level problems have been used to depict the structure of leader (here, the ISO) and followers (here, generators and consumers in the entire market) since at least 1934, when the economist von Stackelberg published his book Market Structure and Equilibrium (Von Stackelberg, 2010). Therein, he described the hierarchical problems that came to be known as Stackelberg games, which are sequential games in which the leader moves first knowing how followers would react. The followers then react naively, taking prices as exogenous not realizing that their actions affect market outcomes.
In the U.S. power sector, the need for such hierarchical equilibrium models has increased since the market was unbundled (Gabriel et al., 2012). Now there are multiple players in the market, each trying to make the best decisions possible for themselves while in some cases anticipating other players' reactions. The structure of MPECs fits naturally to many of these problems. For instance, Hobbs et al. (2000) uses MPECs to analyze market power in oligopolistic power markets and Bakirtzis et al. (2007) uses them to model optimal bidding strategies by generators in the day-ahead energy market. Kazempour et al. (2011) models and solves an MPEC where in the upper level, a strategic generator makes investment and operation decisions anticipating how the market clears in response to her decisions. Similarly, Wogrin et al. (2011) also models a strategic generator looking to invest, but the generator now faces uncertainty regarding rival generators' actions. When transmission operators are explicitly modeled in multi-level models, they are generally represented as a single entity controlling all regions (Pozo et al., 2013) or as the spot market operator in the lower level (Ralph & Smeers, 2006).
We now present our lower and upper level formulations for the single-ISO case in sections 3.1 and 3.2 respectively, followed by a discussion of the MPEC solution strategy in section 3.3.
The lower-level problem is a manifestation of the ISO's belief that in the future (once it commits to investing in the lines it plans to invest in and communicates that to the lower level), the generation market operates based on certain assumptions. These assumptions were listed above (section 1) and they allow the lower-level player problems (Generators' and Consumers') to be combined into a single cost-minimization linear program ( Özdemir et al., 2016). This is the case if demand is considered to be inelastic. But if demand is elastic, it is a nonlinear program (NLP), with the special case of linear sloped demand yielding a quadratic program (QP) (De Jonghe et al., 2012). The lower-level equilibrium problem is as follows (dual variables are shown to the right of constraints):
The lower level is a DCOPF approximation (Li & Bo, 2007) of the transmissionconstrained market equilibrium problem with generation investment and this is based on the assumptions listed in section 1 and in Özdemir et al. (2016).
The lower-level objective is to minimize the cost of operating existing and new generation, investing in new generation, and from lost load over the planning horizon.
For simplicity, we assume that both generation and transmission investments are decided today, i.e., as soon as the new transmission plans are announced, generators react and decide their investments accordingly. We further assume that their construction time is the same and they come online after T I years. We then assume the system is operated for T O years after the investments come online (Fig. 3). The model can be easily changed to reflect alternative assumptions on construction and operation times without loss of generality. While we do not presently include generator disinvestment (retirements), the model is general enough to incorporate this (Chen & Wang, 2016).
Constraint (2) ensures that demand is met at every bus in every hour, or that a loss in load occurs and is penalized. Constraints (3) and (4) restrict flows on existing and new lines to be within their thermal limits. Constraints ( 5) and (6) ensure that line flows on all lines obey Kirchhoff's Voltage Law (KVL). Constraints ( 7) -( 9) impose upper bounds on generation output, investment and load curtailment. For simplicity, active power losses on lines are neglected, although other Stackelberg models include them (Chen et al., 2006).
The dual variable of the power balance constraint at each bus b, p b,h , is its Locational Marginal Price (LMP) in hour h. The asterisks on transmission investment variables z * l in constraints ( 4) and ( 6) indicate that they are viewed by the lower-level problem as fixed at the values decided by the upper level. Note that since load can be curtailed, the lower-level problem is feasible for any feasible solution, ẑl , of the upper level problem.
The above optimization problem [(1) -( 9)] defines the reaction of generators and the energy market given transmission investment z * l from the upper level. The leader's (regional ISO's) objective ( 10) is to maximize the total surplus within its region i, subject to this reaction. The upper level problem is given in equations ( 10) -( 17).
The equilibrium problem [( 1)
The surplus of a region is the total surplus of the region's producers, consumers, and the ISO. In the objective (10), the regional generators' surplus is the profit they make by selling their marginal-costed production at their respective bus LMPs, net of their generator investment cost. Consumer surplus is the benefit from load served (not curtailed) minus expenditures. If demand is assumed to be perfectly inelastic, consumer surplus is infinite. However, we assume that demand can be curtailed at a penalty equal to VOLL in that region. Hence, the consumer surplus portion of the upper level's objective function is written as
. This can be interpreted as money saved from prevention of lost load.
Meanwhile, the ISO's own surplus is from congestion rents minus the cost of their transmission investments. Congestion rent is the money collected by the owners of the rights to a transmission line (in this study, the ISO). Typically, this amount is equal to the flow on the line times the energy price differential across the line (Stoft, 2006). The interpretation here is that the ISO collects congestion rents and passes them on to consumers in its region.
From the perspective of an ISO, there are two categories of transmission lines that it can earn congestion rents from -existing lines and new lines. We assume the ISO gets all the rents from existing lines lying entirely within its region, i.e., connecting buses within the region. Rents from existing seam lines (connecting buses in different regions) are shared with the neighboring ISO according to some pre-defined sharing agreement that is specified using H i l . Note that i H i l = 1, i.e., the sum of the allocations of rents from a seam line has to be equal to the congestion rent generated from that line. Each ISO can both build its own internal new lines or choose to go it alone and build new seam lines. Rents from new lines, whether internal or seams, are allocated to the ISO that builds them.
Equation ( 11) constrains line investment variables to binary variables while (12) defines as binary the variable that specifies each player i's decision about a seam line: whether to unilaterally build the line on its own or not. Although (13) ensures that only one player can build a seam line, the model is general enough to include multiple lines along the same path, giving all regions the opportunity to build lines along a path (Ho et al., 2016). ( 14) sets the value of z l for a seam line depending on if any of the regions build it or not. ( 15) and ( 16) ensure that f N,i l,h takes on the value of f N l,h depending on which player decides to build the seam line l. The ISO's strategic planning model is constrained by the lower-level solution given by ( 17).
The presence of other upper-level players' decision variables a j l in player i's set of MPEC constraints makes this problem a Generalized Nash Equilibrium Problem (Harker, 1991;Han et al., 2012). This is because each players' admissible strategy set depends on other players' strategies.
We acknowledge that there could be other ways of modeling investments on seam lines and additional related phenomena such as how other regions react to a seam line investment decision by one region (beyond constructing their own lines and generators). For example, because a seam line traverses multiple regions, one of the regions might deny construction or right-of-way permits to a line, thereby exercising its "veto" power over the investment decision. While exploring this particular question is beyond the scope of this paper and is a topic for future research, we do note that the model is general enough to include this. We choose the current approach as it avoids the need to assume any particular (and possibly arbitrary and complex) cooperation or coordination requirements among the regional players for new lines. The only coordination assumed is for rent-sharing for existing lines (defined by H i l -and even these can be set to zero for one of the players, for instance if there is no precedent of them coordinating). The present model makes a clear link between investment and congestion rents without making complex assumptions about sharing line costs and rents: the entity that builds the line gets the rents.
Bi-level MPECs such as the one described in ( 10) -( 17) are optimization problems that are constrained by equilibrium problems. Here, the lower-level problem [equations (1) -( 9)] is a LP and hence could be replaced by its KKT conditions. Equivalently, it can also be replaced by the combined set of its primal constraints, dual constraints, and strong duality condition (Bot ¸et al., 2005). We do this for the single-ISO MPEC by writing out the lower-level problem's dual constraints and strong duality condition. These, when combined with the primal constraints [(2) -( 9)], can then be inserted into the constraint set of the upper level problem which can then be solved as a single optimization problem. Lower level's dual constraints.
Additionally, in equations ( 24) -( 25), dual variables λ N - l,h , λ N + l,h are constrained to be zero when there is no investment in the corresponding transmission line.
Here, M is a large scalar. Everything is now tied together by adding the following non-linear strong duality condition which equates the lower-level problem's primal and dual objective values at the optimal solution.
The resulting problem is a Mixed Integer Quadratically Constrained Quadratic Program, which is more difficult to solve to global optimality than LPs or MILPs due to the presence of bilinear terms in (26). We simplify the solution process by linearizing as many non-linear terms as possible in the model.
We replace constraint (4) in the lower-level constraints with two equivalent constraints. These are:
Two new dual variables γ - l,h , γ + l,h now enter the associated dual constraint ( 23) which now becomes:
To describe the relationship between z l and γ - l,h , γ + l,h , we add two constraints:
This results in the exactly linearized strong duality condition (32).
b,k
Summarizing, the single-ISO MPEC's constraints are all linear now and the problem is summarized below: Minimize (10) s.t. ( 11) -( 16) (Leader's own constraints) (2) -(3), ( 5) -( 9), ( 27), (28) (Lower primal constraints) (18) -( 22), ( 24), ( 25), ( 29) -(31) (Lower dual constraints) (32) (Strong duality)
However, we still have non-linearities in the single-ISO MPEC's objective function (10) in the form of bilinear terms. In the appendix (Appendix, 2019), we show why this objective function cannot be exactly linearized. These bilinear terms make the problem a non-convex MINLP, and problems of this type are in general more difficult to solve than comparitively sized LPs and MILPs (Belotti, 2012). While state-of-the-art solvers such as CPLEX and Gurobi can solve LPs and MILPs efficiently, their ability to solve non-convex MINLPs is limited (D'Ambrosio & Lodi, 2013).
The next step is to expand this single-ISO framework to the multi-ISO case by combining all individual ISO's MPECs into a single framework (see Fig. 4). In effect, we are trying to find an equilibrium for the situation where each regional ISO is trying to make transmission investments that maximize its own regional surplus. Problems with this structure, with multiple leaders (ISOs) and a single follower (the market), are classified as Equilibrium Programs with Equilibrium Constraints (EPECs). Denoting region i's total regional surplus as calculated in equation ( 10) as RS i , the Nash Equilibrium for the multi-ISO EPEC is defined as the set of transmission investments, z * l for which (33) holds true.
EPECs have been used to model many energy market applications. For example, Hobbs et al. (2000) solves a series of MPECs with each MPEC depicting a generator's bidding problem in an oligopolistic market while anticipating rival generators' reactions. Pozo & Contreras (2011) generalizes this by optimizing generators' bids while also considering demand stochasticity, making this a stochastic EPEC. Other examples are Ralph & Smeers (2006) and Hobbs et al. (2000) which model generators with the knowledge that their output affects transmission prices (the price of moving power from one bus to another).
EPECs can be solved in a variety of ways, the most popular method being diagonalization (Pineau & Murto, 2003), which is what we use in this study. Diagonalization is based on the Gauss-Siedel method (Weisstein, 2002), which is used to find solutions of simultaneous equations. The MPEC of one leader is solved at a time, assuming that the strategies of the other leaders are fixed. The leaders' strategies are updated at each iteration to the most recently computed values. This is done iteratively until there is no change in the leaders' strategies from one iteration to the next. For an overview of this and other methods used to solve EPECs, see Gabriel et al. (2012).
MPECs in general are non-convex. So, the corresponding EPEC (when using diagonalization) might not converge. For example, while Hobbs et al. (2000) reports that their diagonalizations converged for every test case they used, Jin & Ryan (2014) admits that their diagonalization did not converge for certain instances. Non-convergence does not necessarily imply that a purestrategy equilibrium does not exist. It could be that even though one or more equilibria exist, the algorithm fails to converge to one of them.
If the EPEC converges, there is no guarantee that the equilibrium found is unique or the best possible equilibrium for all players involved (i.e., Pareto superior to all other equilibria). In the general case, each MPEC's constraint set defines a non-convex feasible region. So, not all MPEC local optima are necessarily globally optimal. Hence, nothing in general can be said about the existence or uniqueness of EPEC solutions (Gabriel et al., 2012). In fact, Ehrenmann (2004) points out that non-unique solutions are common.
One or more Nash equilibria might be found using diagonalization. For example, in an EPEC with two leaders, depending on who is assumed to make the first move, two different Nash equilibria might be found. Alternatively, both Nash equilibria might be the same. In fact, in the test case of this study (section 7), with two leaders, we find the same Nash equilibria irrespective of who the diagonalization starts with. As mentioned above, it is also possible that no equilibrium exists, or there are more than two equilibria.
Looking beyond diagonalization, techniques to identify all equilibria of an EPEC is currently an active area of research. An avenue with which more recent studies reported positive experience is the direct-solution method. In this method, an auxiliary optimization problem with an arbitrary objective function is solved with the optimality conditions of all MPECs within the EPEC forming the constraints. Changing the objective function multiple times and re-solving the problem might lead to alternative stationary points. All such stationary points can be evaluated to pick the "most optimal" EPEC solution. This method was originally proposed by Hu & Ralph (2007) in the context of bi-level games with locational electricity prices, and clarified and formalized in Ruiz et al. (2012).
Nevertheless, there is still no guarantee that a) all stationary points would be found by this procedure. This is especially true because complementarity constraints of MPECs are non-regular in general, making this auxiliary optimization problem difficult to solve to optimality. There is also no guarantee that b) the "most optimal" EPEC solution would be the one that is picked by the players. The EPEC solution that the players would choose (in the absence of a supra-player, which is the case in this study) would depend on their individual starting points. As can be seen from the above references, the construction, solving, and evaluation of equilibria found from such an auxiliary problem (if equilibria exist and are found) is in general very challenging. This is especially true given the fact that there is no exact linear approximation of the MPECs ISO 1 ISO i ISO n constituting the EPEC of this paper (as shown in the Appendix).
We acknowledge the complexity in finding all equilibria for a given EPEC. For the non-cooperative transmission planning EPEC formulated in section 4, prima facie, there is no evidence that other methods from the literature for obtaining equilibria (such as the one described above) will deliver further insights into the nature of cooperation in transmission planning when compared to diagonalization. Keeping this in mind and given the scope of this paper, we use diagonalization to solve the non-cooperative EPEC in this study's test case (section 7) while taking precautions to ensure that the equilibria we find are stable and close to optimal. First, we use multiple starting points while solving each MPEC iteration of the diagonalization (see section 7.2.5). For a given iteration, we pick the best solution from the set of stationary points that result from using multiple starting points for that iteration and consider that to be the player's best response. This solution is then held fixed while similarly solving for the next player's best response. In the limiting case, as the number of starting points become large, the set of MPEC solutions will encompass all possible responses of the player to other player's investments, making the best solution the player's optimal response. Second, we confirm that in this case study, irrespective of which player is assumed to make the first move in the diagonalization, the final set of transmission lines that are built is the same.
The noncooperative ISO planning problem solution in section 4 is compared to a benchmark cooperative solution which is the least-cost co-optimized trans-mission\generation solution. Here, all the regional planners are assumed to fully cooperate with each other in the planning process. When there is a single lower-level energy market in which all players are competitive, the cooperative transmission planning model takes the form of a single cost minimization model.
The equivalence between such a cost minimization model and a model where all players and their actions are modeled explicitly can be established by showing that their KKT conditions are the same ( Özdemir et al., 2016). This is in line with centralized transmission planning models such as Munoz et al. (2014) and van der Weijde & Hobbs (2012).
The objective function is to minimize the total cost of the transmission and generation investments and the assumed operations for T O years from year T I onward:
The constraint set is formed by concatenating the constraint sets of each of the regional transmission planner, i.e., the constraint set defining the market equilibrium and the generators' response to the transmission planners' investments. These include equations ( 1) -( 9) and ( 11).
In effect, this is an Integrated Planning Model, except the interpretation here is that regional transmission planners fully cooperate with each other, generators are reacting competitively by making their investments simultaneously, and these reactions are correctly anticipated by the "proactive" transmission planner (Sauma & Oren, 2006).
In this section, we (a) illustrate how our model can be applied to a small test case, defined in section 7.1, (b) show how the transmission and generation investment results from a noncooperative model can be very different from a cooperative (cost-minimization) model (section 7.2.1), and (c) calculate the economic value each individual player in the system gains (or loses) if transmission planners from the different ISOs cooperate (Table 3 in section 7.2.1). The last point directly addresses the notion that there will be "winners" and "losers" when the planning paradigm changes. We then define and calculate the net monetary Value Of Cooperation (VOC) (section 7.2.2) and show how this framework can be used to evaluate proposed side-payment agreements between control regions that could leave everyone better off (section 7.2.3). Section 7.2.5 addresses the computational performance of the solution algorithms.
To test our model, we used the CAISO 17-bus data set (Munoz et al., 2012;Appendix, 2019). We selected a subset of 12 hours from the dataset to represent yearly operations. The subset of hours was chosen to match the yearly averages, standard deviations, and geographical correlation of load and wind. Specifically, we used hour sampling techniques from van der Weijde & Hobbs (2012) to minimize the total squared error of the above metrics between the samples 600 and yearly data. We use a discount rate of 5% per year and we assume that transmission investments take 10 years to be built and come online since the time of the decision. Lastly, we assume the Value Of Lost Load (VOLL) is $1000/MWh.
We consider the simplest case where there are two regional planners and they have a common follower (the energy market). We divide the region into two regions, roughly along the North-South axis. This arbitrary geographical division is for illustrative purposes and not meant to reflect or represent any real planning agency in the State of California or elsewhere. We then solve the two-region EPEC using Gauss-Seidel diagonalization (Gabriel et al., 2012) where we solve each planner's MPEC assuming it is a Nash player. Note that henceforth, we use the term "Regional Planner" instead of "ISO".
From Table 1, we see the following changes under cooperative planning relative to noncooperative planning. Regarding internal regional lines (top twothirds of the table), one extra line is built in both regions (lines 21 and 22 respectively) while one line (line 7) is dropped from Region 2's noncooperative plan. For seam lines, Regions 1 and 2 choose to build three and one lines respectively in the noncooperative framework. In contrast, only two of these lines are built in the cooperative framework (see Figure 5).
At the same time, we see that generators respond to these changes in transmission investments. From Table 2, we see that generators in Region 1 increase their overall investment by 1.5 GW while generators in Region 2 decrease theirs by 1.9 GW. Furthermore, the mix changes. With cooperative transmission plans, more combined cycle (CCGT) units are built as opposed to combustion turbines (CT) in Region 1. No load curtailment occurs in either solution.
Even though Region 1's generators invest more with cooperation, their profit decreases compared to the noncooperative framework (Table 3). This is partly Region ∆ (Cooperative -Non Cooperative)(GW) 1 CT: -2.2, CCGT: 3.7 2 CCGT: -1.9 due to increased competition from cheaper generation in Region 2 which the cooperative solution's additional transmission capacity now makes more accessible to Region 1's consumers. Overall, Tables 1 and2 indicate that, in at least this case, a cooperative framework surprisingly invests in fewer transmission lines and lower total generation capacity than the noncooperative framework.
It is interesting to note the nature of some of this new transmission under the cooperative framework. We see that there is one line in both regions (indicated by * in Table 1) that is internal to each region (not a seam line) and is only built under the cooperative framework. These internal lines have interregional benefits and are only built if the regional transmission planners cooperate with each other. Investments in seams lines are also affected by the framework that is used. Overall, three lines -two seam and one internal -are dropped while two additional internal lines are built under the cooperative framework when compared to the noncooperative framework. This is contrary to what might have been expected, so it should not be assumed that the primary effect of cooperation is only upon the economics of lines connecting regions; here, internal lines were equally affected.
We calculate the Value Of Cooperation (VOC), which is the benefit each (group of) player (consumers, producers, and the ISO itself) gains as a result of the two transmission planning entities cooperating with each other in the planning process. The concept of VOC is related to cooperative game theory's notion of the 'characteristic function' which calculates the total payoff for a set of players. This idea first appeared in Neumann and Morgenstern's seminal 1944 book on Game theory (Von Neumann & Morgenstern, 2007). More recently, this concept appeared in a variety of studies, including transmission planning (Gately, 1974), water-resource sharing (Whittington et al., 2005), and in analyzing competitive advantage in farmers' markets (Lindgreen et al., 2008).
In this study, VOC is the difference between a player's surplus in the cooper- ative setting and the noncooperative setting. Hence, a player's VOC, if positive, indicates that cooperation in transmission planning benefits the player while a negative VOC indicates a loss. While we cannot say anything in general about the nature of these individual surplus' changes, the total interregional surplus can only increase with cooperative planning, i.e., the total interregional VOC will always be non-negative. This is due to the fact that under our assumptions, by definition, the cooperative model maximizes total surplus. Table 4 indeed indicates that the interregional VOC is positive. Note that these are annualized surplus values over a period of T O years' worth of market operations, in this case 30 years. As expected, with cooperative transmission planning, the overall investment and operational cost to the system decreases and the total interregional surplus increases. Region 1's consumers benefit most from cooperation because the region's average hourly energy price falls by $ 0.67/MWh with cooperative planning (Table 3). This is due to increased access to cheaper generation from Region 2, where as expected, we see an increase in the average hourly energy prices (by $ 5.66/MWh). Commensurate with this, Region 2's producers' profits increase and Region 1's producers' profits decrease, as shown in Table 4. Each ISO's VOC depends on assumptions about who builds the new seam lines in the cooperative case. Here, we take the two bookend scenarios where Region 1 or Region 2 entirely pays for the new seam lines (and gets the resulting congestion rents). For example, if Region 1 pays for all new seam lines in the cooperative case, the ISOs' annual VOCs are -$241.7 Million and -$2 Million respectively.
Overall, both regions benefit from cooperation in transmission planning. Region 1's VOC is in the range of $52.65 -$172.10 Million annually while Region 2's VOC is $41.10 -$160.55 Million annually. The total interregional VOC is $213.20 million annually which is 95% of the total (noncooperative) transmission investment cost. That is, the net benefits of cooperation are of the same magnitude as total transmission investment, and must therefore be viewed as significant.
We tested the diagonalization process with the second player instead of the first player making the first move. We then found that while the overall set of lines that end up getting built in the noncooperative framework is the same as presented in Table 1, the builders of seam lines seems to depend on who made the first move. This change affects the regional distribution of surpluses, thus affecting individual regional Values Of Cooperation. However, it does not affect the total interregional Value of Cooperation, as the overall set of lines is the same irrespective of who made the first move. No solutions were found with different physical investments, although this could happen for other problems or parameter settings. It would be interesting to see if the aforementioned first-movers' advantage still remains when other regions are allowed to "veto" a region's seam line investment decision, as mentioned in Section 3.2. Exploring this question is the subject of future research.
This framework can be used to evaluate different side-payment agreements (Leng & Parlar, 2009) between the regions and also among players within a region. For example, in this case study, we see from Table 4 that while Region 2's net surplus increases with cooperation, producers in that region gain the most due to increased prices and lower generation investment while consumer surplus in that region decreases. Therefore, Region 2's consumers would only cooperate in the transmission planning process if they are compensated for their losses and this compensation has to be at least an annualized amount of $ 20.98 M.
For illustrative purposes, one practical way of transferring these side-payments is in the form of a regulator-facilitated agreement between Region 2's producers and consumers to keep energy rates at the same average value as before cooperation. In this way, consumers are not exposed to the higher energy rates and get to maintain their status quo while producers are still better off than before by $60.08 -$20.98 = $39.10 Million annually. Another possibility is for producers to be taxed and the proceeds used to subsidize energy conservation programs that benefit consumers, as is done for instance in the Regional Greenhouse Gas Initiative (Holt et al., 2007). These are examples of an intra-regional side-payment. For more ways in which side-payments can be calculated and transferred, the interested reader is referred to Wang & Parlar (1994), Jackson & Wilkie (2005), and Leng & Zhu (2009).
The main condition that is necessary for the stability of the coalition and existence of a core in a N-region game without externalities is superadditivity (equation ( 35)). That is, the value of a union of disjoint coalitions is at least equal to the sum of separate values of the coalitions (Shapley, 1971;Pulido & Sánchez-Soriano, 2009;Lozano et al., 2013). In this case, we treat the 'region' as an entity for the purposes of coalition-forming with the underlying assumption that generators and consumers in a region can prevent their ISO from cooperating with another region.
For a 2-region case, equation ( 35) always holds true. This is because a 2-region game automatically reduces to a game without externalities and the total value of cooperation is always non-negative. This can also be understood intuitively in terms of incentives for market players to cooperate and support the mostefficient solution. First, players with a positive VOC will always want to be in the coalition. This is because these players are gaining from the cooperative framework and they have nothing to gain from anything other than the coalition (in a 2-region case, this is also the grand coalition), i.e., they have no incentive to block the coalition. For example, consider the case of Region 2's generators -their VOC is $64.08 Million annually if the regions cooperate in the transmission planning process. These generators only have two choicesagree to the cooperation and gain $64.08 Million annually or leave the agreement (the coalition) and get zero (as the cooperative process can go ahead only if all players affected are on board). Given that Region 2's generators face these two choices, they will always prefer the coalition. The same reasoning applies to other players with a positive VOC. Second, the only players that gain from the coalition not forming are the players that currently have a negative VOC. Ab-sent side-payment agreements, these players are better off outside the coalition than within it. The interpretation is that they have a positive payoff by preventing future losses that they would incur if they remain in the coalition. The players with a positive payoff can compensate players (through side-payments) with a negative VOC thereby disincentivizing them from blocking the coalition (Guajardo et al., 2016). Such a side-payment agreement always exists in a 2region case since the total interregional VOC is always non-negative. Hence, in a 2-region case the core always exists.
As mentioned above, in a 2-region case, any side-payment agreement that compensates all losing players for at least their losses is stable and is in the core. This can be shown as follows. Consider the lower end case where all losing players are compensated exactly up to their losses making their VOC zero while keeping all the previously gaining players' VOC positive. This is possible as long as there is a strictly non-negative net benefit to the coalition, which we showed is always the case in section 7.2.2. The previously-losing players are then indifferent to the coalition forming or not and the gaining players would not want to form a sub-coalition because there is nothing to be gained from anything other than the coalition.
For problems with more than two regions, the VOC for an individual region depends on the actions of all other regions. For example, in a 3-region case, a region's payoffs are different if the other two regions choose to form a coalition or not. In such games with externalities, superadditivity is no longer sufficient for the efficiency of the grand coalition (Abe, 2016). In such cases, convexity is the sufficient condition (Hafalir, 2007). Here, convexity means the incentive for a region to join a larger coalition must increase with the size of the coalition (Chander & Tulkens, 2006;Bilbao et al., 1999). Exploring this condition for the model in this paper is the subject of future research.
All models were run on a Windows 7 PC with 8 GB of RAM and Intel Core i7-860 processor. The cooperative models are MILPs and these were solved using CPLEX 12.6 in AIMMS (Bisschop & Entriken, 1993).
For very small test-cases, CPLEX (V 12.3 and above) can be used to solve the noncooperative MPECs which are non-convex MIQPs (Bliek1ú et al., 2014). For larger cases, CPLEX's progress is extremely slow and we used a Multi-start Outer-Approximation algorithm in AIMMS (Hunting, 2012) which is based on the outer-approximation algorithm proposed by Quesada & Grossmann (1992) to solve the individual planner MPEC. For each MPEC, we ran the algorithm twice, first with 20 iterations and next with 10 iterations to help find good initial feasible solutions as suggested in Hunting (2012). For the multi-start algorithm, we ran the algorithm with 10 initial random starting points and chose the best solution from amongst them. In each iteration of the EPEC diagonalization, this solution was fixed for one planner and the other transmission planner's MPEC was solved in a similar manner until the convergence criterion was met. The EPEC converged in three iterations and the solution times are shown in Table 5. It should be noted that we allocated transmission lines and buses to each region by trying to distribute load equally among buses. As a result, the more densely populated Region 2 is allocated almost twice the number of buses and transmission lines as Region 1. Region 2's MPEC is consequently larger in size and hence takes longer to solve.
We have developed the optimization problems facing regional transmission planners while explicitly recognizing the absence of cooperation in planning across political boundaries. We showed how the multi-planner problem can be formulated as an EPEC and solved using an Outer-Approximation algorithm. For this case-study, the EPEC converged. Convergence is not guaranteed and even if it occurs, multiple equilibria might exist, as mentioned in sections 4 and 5.
We demonstrated the applicability of our model by running a 17-bus test case. In this, we showed that the transmission plans can be very different with regional cooperation than without. Further, generation investments can change in reaction to these transmission investment changes. With this cooperation, consumers in some regions gain access to cheaper generation from other regions, lowering their average energy price. Build-out of seam lines is different and there are two lines that are internal to the regions (not seam lines) that have interregional benefits, but are built only when regional transmission planners cooperate with each other.
We also calculated the Value Of Cooperation (VOC) for each player involved, defined as the increase in their surplus when transmission planners from different regions cooperate with each other. We showed that both regions benefit from cooperative transmission planning and in this test-case, the region-wide benefit is of the same order of magnitude as the transmission investment cost. Thus, the models' calculation of VOC can pave the way for interregional cooperation by identifying grid reinforcements that benefit the entire system, as well as side-payments that may incent individual players to cooperate. Although it is natural to have "winners" and "losers" while moving from a noncooperative to a cooperative planning paradigm, individual player's Values Of Cooperation can be used to identify side-payment agreements so that every player is made better off and incentivize them to cooperate in the transmission planning process.
Future research will address the scaling of the multi-ISO EPEC to larger test systems, recasting the lower-level problem as a multi-player follower representing regional generator investments and operation, exploring the conditions for the existence of a core in a game with more than two regions. Another interesting avenue for future research would be including generator retirements as part of the generators' strategy set. Indeed, in response to increased competition from a neighboring region's generators (that results in lowered energy prices, which is the case with region 1's generators in this case study), a region might choose to retire some of its generation and this would shed more light on the interplay between generation and transmission investment.