WIXLIB

YANG et al.: COMPUTING ALL NASH EQUILIBRIA OF MULTIPLAYER GAMES IN ELECTRICITY MARKETSstrategy combinationcurs is given byof Firm holding strategyunderoc. Thus, the payoffcan be calculated as. Further, the set of Nash equilibriafound with83of gamecan be(8)(6)wherewhererepresents the set of pure strategy combinations with. Then the corresponding payoff of is(7)A mixed strategy combinationis said to be a Nash equiis the best response against[25]. Therefore,librium ifis a Nash equilibrium if, andthe strategy combinationsuch thatonly if, there is no other mixed strategy. Although the set of NE is knownto be non-empty, it is a challenging task to determine the entireNE set.III. SOLUTION METHODThe complexity of the NE computation depends on whetherthe number of players is greater than two. For a two-playergame, since the NE condition can be expressed as a linear complementarity system, the Lemke-Howson algorithm is the pioneer, and still the most important, approach for finding thesample equilibrium [26]. Further, a differential-path-followingalgorithm is developed to calculate all NE [27].However, the NE problem of three or more players is morecomplicated since it is no longer a linear problem. The simplicial subdivision approach derived from the Scarf’s algorithmfor finding fixed points is employed to find the sample equilibrium in [28]. The NE problem is reformulated as a minimizationproblem of a differentiable non-negative function whose globalminima coincide with the equilibria in [29]. However, this approach, based on the Liapunov function method, will only findall NE in a probabilistic sense. The feasibility to compute allNE of the general finite game is demonstrated theoretically in[30], and a possible implementation is further discussed in [31].The work, in this paper, of analyzing all NE is inspired by themathematical work in [30] and [31].The Nash equilibrium is a one-point solution concept of agame. For generic finite n-player games in normal form witha full Lebesgue measure, Nash proves that the number of theNash equilibria is greater than or equal to one. Further, it canbe shown that the number is generally finite and odd [32], [33].The maximal number of Nash equilibria is investigated in [34].For a generic game , the set of all pure strategies is defined. Let support denote the subset of ,as , i.e.,which is subject to the property that only strategies in areplayed with positive probabilities. Based on this property, theNE condition can be reformulated using a polynomial system. Reference [30] proves that, forwith inequality constraintsall support of the game with a full Lebesgue measure, the setis a compact zero-dimensional manifold.of solutions toon supportIn addition, the set of Nash equilibriais the subset of the set of solutions to. That is, it can beguaranteed to solveby finding all isolated solutions tois the set of supports.A. ProcedureThe essence of the solution method is to enumerate all possible supports. The NE condition implies a polynomial systemof equations with inequality constraints based on a particularsupport, as we will explain later. The procedure of the proposedmethod can be summarized as follows:Step 1) Search for all feasible sets of pure strategies, whichmeet certain requirements and constraints, to construct thepossible support set ., a polynomial system of equaStep 2) For each support, in which is the settions with inequality constraints,of unknown probabilities assigned on , can be constructedbased on the NE condition.Step 3) Compute all solutions of the polynomial systemusing numerical techniques and check each solution tosee whether it satisfies the inequality constraints. The feasibleif they do exist; otherwise, the setsolutions constructis empty.areStep 4) Repeat step 2 and step 3 until all elements ofcan beinvestigated. At the end, the set of Nash equilibria.found by joining with each NE setTherefore, if the set contains all possible supports and allsolutions of the polynomial equations can be found, the proposed method can guarantee that all the NE can be found. In thefollowing subsections, the pivotal steps are introduced and analyzed in detail.B. Construction of Supports Setrepresents a set of all pureA supportstrategies with given positive probabilities, where contains allcan be inpure strategies from . Each strategyindependently, except an invalid subsetor out of the subsetin which all strategies of are out. Thus, the maximal numberof the possible supports can be calculated as(9)Note that the maximal number increases rapidly with the size ofthe game.Fortunately, the size of the support set can be reduced usinga technique based on game theory. Certain strategies may existthat will not be chosen by a rational player, regardless of whatis called strictly domitheir opponents choose. A strategyif it satisfies the followingnated by another strategycondition:(10)whererepresents the set of pure strategy combinations otherthan the pure strategies of player . These strictly dominatedstrategies can be discarded without any change in the solution

84IEEE TRANSACTIONS ON POWER SYSTEMS, VOL. 27, NO. 1, FEBRUARY 2012procedure [19], [21], [25]. Thus, the solution method employsthis property to determine the possible support set through thefollowing steps: first the dominated strategies are discarded; andthen, the remaining undominated strategies are enumerated toconstruct the support set according to the approach expressedin (9).C. Nash Equilibrium Condition as Polynomial System, a set of probabilities onFor supportpure strategiesis assumed to correspond. In , it is supposed that player choosesto a NEwith the probabilitya pure strategy subsetsetwhererepresents the number of purestrategies in . Since the probability of any strategy out of theis only associated with the setsupport is zero, the payoff ofin the NEof pure strategy combinationstherefore, it can be reformulated as follows:, andalgorithm has proven to be a reliable mathematical method tocompute all isolated solutions of a polynomial system [35], [36].This algorithm consists of two main stages: 1) the target systemis embedded to solve in a family of systems which are called thehomotopy system; and 2) the continuation methods are used tonumerically follow the solution paths of the homotopy systemwhose end represents the desired solutions of the target system.A classic homotopy system can be constructed as follows:(16)where and are the coefficients; is the continuation parameter;is called the start system whose solutions are calledrepresentsthe start solutions; and for notational simplicity,, which can be abbreviatedthe target equations system.toAccording to the derivative function of the homotopy systemcan be formulated asin , the solution paths(17)(11)represents a particwhereular pure strategy combination.is non-empty, withoutSince each pure strategy subsetcan be established as theloss of generality, its first strategybenchmark for notational simplicity. For any other strategy, ifwill bediscarded from the support because it is dominated by ;will be disotherwise, ifcarded. This means thatis a stable support if, and only if,. On the other hand, for any strategy, its corresponding payoff should be lessthan that of the benchmark; otherwise, it will be chosen with apositive probability.In summary, for the given support , the NE condition can beformulated as a polynomial system of equations with inequali, as follows:ties constraints,(12)whererepresents the start solutions. This shows that the solution paths can be tracked using conventional numerical techniques. The predictor-corrector method and simplicial methodare two of these fundamental methods.The construction of a suitable start system plays an importantrole in the entire framework. An upper bound for the numberof the desired isolated solutions needs to be known initially.As the theorem of Bézout says, the solutions of a polynomialsystem are counted with multiplicities, and their number is equalto the total degree of the system which is presented in detail inAppendix B., in (12), as (11) presents,For each polynomial equation,, correspondseach term,to the expected profit of player with a certain pure strategyunder a particular pure strategy combination. This, so the degreeshows that the degree of each term is, is also. On the other hand,ofit is easily seen that the degree of each polynomial in (13)polynomials andis 1. Since (12) consists of(13) consists of polynomials, the total degree of the targetispolynomial system(13)(18)(14)(15)where. Tounknown probabilitiesgether, the system withequations is solvandable. A simple example illustrating how to construct the polynomial system is presented in Appendix A.It clearly shows that the number of solution paths grows exponentially with respect to the size of the game.The start system should satisfy the conditions of having thesame number of isolated solutions as that of the target systemand all its solutions should be easily found [37]. Therefore, aclassic start system based on the total degree can be expressedasD. All Feasible Solutions of Polynomial EquationsThe set of the solutions of systemis a semi-algebraic set, which can be found by first acquiring all solutions ofthe polynomial equations and then choosing the solutions satisfying the inequalities constraints. The homotopy continuation(19)whereandare the coefficients.

YANG et al.: COMPUTING ALL NASH EQUILIBRIA OF MULTIPLAYER GAMES IN ELECTRICITY MARKETS85TABLE IIISITUATION OF ALL MARKET EQUILIBRIA UNDER LIMIT 30 MWFig. 1. Sample test system (Source: [19, Fig. 1]).TABLE ICOST COEFFICIENTS OF THE FIRMSA. Uniform Discretization Interval as 100 MWTABLE IIBENEFIT COEFFICIENTS OF THE CONSUMERSThe complete framework of the homotopy continuationalgorithm has been constructed based on (16)–(19). Multiplepublicly available software packages exist that are dedicatedto solving the polynomial system by homotopy continuation.In this work, PHCpack [38] is employed as the platform asit is a stable and integrated workbench offering various toolsand options. Reference [39] surveys publicly available software packages to solve the system problems raised by the NEcomputation; and the comparative performance reports usingGambit, Singular, and PHCpack conclude that the PHCpackoutperforms the other software packages in terms of computational stability and capacity.IV. CASE STUDYThe multi-machine sample system from [19] is used to verifythe performance of the proposed method. The system depictedin Fig. 1 consists of three firms and three consumers. The relatedcoefficients are presented in Tables I and II, respectively. Thetransmission lines are assumed to be lossless and have equalexists on thereactance. Additionally, a transmission limitline connecting bus and bus .In [19], the initial range of the generation bids is reasonablyestimated. The set of pure strategies is then constructed for eachfirm by uniformly discretizing the range. Further, according toseveral heuristics, the market is analyzed with a gradually finerdiscretization. Inspired by the work in [19], the solution methodis employed in accordance with the previously mentioned procedure in Section III. Especially, the same initial range as thatof [19] is set to [600, 1500] MW. The different discretizationlevels, as well as different transmission limits, are investigated,respectively, in the following subsections.Under this uniform discretization interval, the size of the purestrategy set is 10 10 10. In the following subsection, themarket cases under the different transmission limits are analyzed, respectively.: Without1) Without Transmission Constraintsconsidering transmission constraints, since the payoff functionsof firms are concave, many dominated strategies are discardedin the construction of the possible support set. The computation. Underresults in the sole pure strategy NEthe market equilibrium, the payoffs are 26 157/h, 22 835/h,and , respectively. The results areand 21 007/h forconsistent with those solved by the approach in [19].MW: Assume2) With Transmission Constraintsthat a transmission limit of 40 MW is exerted on the line betweenand in this case. After discarding the dominated strategies,the number of remaining undominated strategies is 5 for eachelements.firm, and therefore the support set consist ofAfter enumerating each element in the pool, the proposed method shows the existence of only one mixedstrategy NEwith the probabilities offorfor, and the pure strategyis chosen by. Given these strategies, the correspondingexpected payoffs are 26 748/h, 27 990/h, and 19 414/h for, and, respectively. If the results are compared withthat reported in [19], the sample NE found in [19] is exactly thesole NE in this case. The whole computational time on a PCcomputer of Pentium R 3.00 GHz with 1 GB of RAM memoryis 57 min and 38 s.In [19], this case is regarded as a sample case considering thetransmission constraints. Certainly, it is meaningful to investigate the market equilibria under different transmission limits, asshown next.MW: In this3) With Transmission Constraintscase, a tight transmission constraint, 30 MW, is imposed on thesystem. The size of the reduced pure strategy set is 5 4 5after discarding the dominated strategies. According to thecomputational results, we can see that there are, in total, threemarket equilibria. All the equilibria are shown in Table IIIwhere “prob.” represents the corresponding set of probabilities.To analyze these equilibria in detail, we investigate the expected payoff with regard to the strategy, given the equilibriumstrategies of the opponents.

86IEEE TRANSACTIONS ON POWER SYSTEMS, VOL. 27, NO. 1, FEBRUARY 2012Fig. 5. Variation of the form of the NE set with respect to the limit.Fig. 2. Expected payoffs of each firm under the NE .Fig. 6. Evolution of payoffs of each firm in the equilibrium.Fig. 3. Expected payoffs of each firm under the NE Fig. 4. Expected payoffs of each firm under the NE .As in Fig. 2,andcorrespond to the highest profit of 25 454/h for, and therefore both strategies are the best response against the strategies chosen by its opponents. The exis 37 618/h, which is the highestpected payoff of strategy. Both and provide the best profit of 18 303/h forfor. Thus, the results of, including the support and probandareabilities, satisfy the NE condition. Similarly,the verified market equilibria, based on Figs. 3 and 4. The entirecomputational process takes 9 min and 38 s, in this case.Comparing these results under different transmission limits,it is shown that the market equilibria are sensitive to changes oftransmission limits. Thus, it is interesting to further analyze theimpact of transmission constraints on the market equilibria.4) Form of the Nash Equilibrium Set: The number of NE, andthe status of whether it is a pure or mixed strategy equilibriumfor each NE, is defined as the form of the NE set here. Theinfluence of transmission constraints on the form of the NE setis analyzed in Fig. 5, in which the abscissa represents differentvalues of the transmission limit. The corresponding expectedpayoff of each firm under the equilibrium is shown in Fig. 6,where for the case with multiple NE, the results of the pureMW and 90 MW) and(strategy NE (MW) are depicted.From Figs. 5 and 6, we have the following observations: When the limit is greater than 100 MW, there is only one. Thus, the expectedpure strategy NE that is equal topayoff of each firm remains unchanged. When the limit declines to 90 MW, the NE set has three eland two mixedements including one pure strategy NEstrategy NE. When the limit decreases from 80 MW to 40 MW, a uniquemixed strategy NE exists under each limit. When the limit is 30 MW and 20 MW, respectively, themarket has multiple NE for each case. Also, a different purestrategy NE exists at 20 MW. When the limit is 10 MW and 5 MW, a pure strategy NEexists in each case and the equilibrium of each case differs.From Fig. 6, we can roughly see that the expected payoff ofis fluctuating smoothly during the entire process without agradually increases withmajor step change. The profit ofdethe decline of the limit; on the other hand, the profit ofcreases with respect to a tighter transmission limit. These resultsdemonstrate that the market powers of firms are affected by thetransmission constraints.

YANG et al.: COMPUTING ALL NASH EQUILIBRIA OF MULTIPLAYER GAMES IN ELECTRICITY MARKETSFig. 7. Payoffs of multiple equilibria under the particular limits.5) Multiple Equilibria and Equilibrium Selection: The existence of multiple Nash equilibria is a challenging problem frequently encountered in game theory. The Harsanyi-Selten solution theory is the first general contribution in the equilibriumselection [21]. Based on a combination of payoff dominanceand risk dominance, the theory selects the more attractive equilibrium by the comparison between various pairs of equilibria.An NE is considered payoff dominant if it is Pareto superiorto all other NE. Conversely, the concept of risk dominance is aformalization of the probabilistic considerations to identify theleast risky equilibrium. When a choice is to be made among theequilibria, all players would agree on the payoff dominant equilibrium since it offers at least as much payoff as each player’sbest alternative.The payoffs of multiple Nash equilibria under particulartransmission limits are shown in Fig. 7, where the abscissarepresents the different NEs. Note that the variation trend ofis approximately similar to that ofunder all listed limits, butis opposite to that of . Therefore, none of these NE is Paretosuperior. That is, under these transmission limits, there is nopayoff dominant NE. In this case, it is not easy to select thesolution equilibrium. For the cases without a globally dominantequilibrium, a framework is proposed by Harsanyi and Selten[21] to decide the relative importance of the various dominancerelations and choose the one unique equilibrium as the actualsolution. This approach primarily relies on the following operations: determination of the strategic distance, check for payoffdominance, and comparing the stability radii of all solutioncandidates [21]. Since the entire operation processes are quitecomplicated, the analyses based on equilibrium selection arebeyond the scope of this study, but they could be an interestingtopic to be investigated in the future.B. Finer DiscretizationWithin a fixed range, the number of pure strategies increasesas the discretization becomes finer. Moreover, the number of undominated strategies increases, which causes the computationalprocess to become more complicated.: At first, the interval1) Without Constraint50 MW of the uniform discretization is used to constructeach pure strategy set, and then the process of discarding87dominated strategies reduces the effective size of the purestrategy set from 19 19 19 to 3 3 3. Next, the sole NEMW for, and, respectively, isattained. Based on the heuristic technique introduced in [19,Section III.C], the range can be reduced to [1050, 1150] MW, [1000, 1100] MW for, and [950, 1050] MW forfor. In addition, the interval is set to 10 MW, and then the effective size is reduced to 2 2 2 after the discarding process.Based on the computational results,

IEEE TRANSACTIONS ON POWER SYSTEMS, VOL. 27, NO. 1, FEBRUARY 2012 81 Computing All Nash Equilibria of Multiplayer Games in Electricity Markets by Solving Polynomial Equations Yan Yang, Student Member, IEEE, Yao Zhang, Fangxing Li, Senior Member, IEEE, and Haoyong Chen, Senior Member, IEEE