Transcript ppt

Computing Equilibria in
Electricity Markets
Tony Downward
Andy Philpott
Golbon Zakeri
University of Auckland
Overview (1/2)
Electricity
•
•
Electricity Network
Electricity Market
Game Theory
•
•
Concepts of Game Theory
Cournot Games
Issues
•
•
No Equilibrium
Multiple Equilibria
Overview (2/2)
Computing Equilibria
•
•
Sequential Best Response
EPEC Formulation
Example
•
•
Simplified Version of NZ Grid
Equilibrium over NZ Grid
Electricity
Electricity Network
Nodes
At each node, there can be injection and/or withdrawal of
electricity.
Lines
The nodes in the network are linked together by lines.
The lines have the following properties:
• Capacity – Maximum allowable flow
• Loss Coefficient – Affects the electricity lost
• Reactance – Affects the flow around loops
Electricity
Electricity Market (1/3)
Generators
The electricity market in New Zealand is made up of a number
of generators located at different nodes on the electricity grid.
We will assume there exist two types of generator:
• Strategic Generators – Submit quantities at price 0
• Tactical Generators – Submit linear supply curve
Demand
Initially we will assume that demand, at all nodes, is fixed and
known.
Electricity
Electricity Market (2/3)
Tactical Generator
1
1
0.8
0.8
0.6
0.6
price
price
Strategic Generator
0.4
0.4
0.2
0.2
0
0
0
0.2
0.4
0.6
quantity
0.8
1
0
0.2
0.4
0.6
0.8
1
quantity
Electricity
Electricity Market (3/3)
Dispatch Model
T
2
min
1
2
s/t
Mx  Af  Bf  d
b x
2
Lf  0
0 xq
K  f  K
 
 
 1 ,  2 
1 ,2 
x
Amount of electricity dispatched
f
d
Flows along lines
Demand at nodes
b
Slope of offer curve
M
A
Matrix mapping generation to nodes
Node-Arc incidence matrix
B
Loss Coefficients
L
q
Impedance Values
Quantities offered by generators
K
Capacities on the lines
Electricity
Game Theory
Concepts of Game Theory
Players
Each player in a game has a decision which affects the
outcome of the game.
Payoffs
Each player in a game has a payoff; this is a function of the
decisions of all players. Each player seeks to maximise their
own payoffs.
Nash Equilibria
A Nash Equilibrium is a point in the game’s decision space at
which no individual player can increase their payoff by
unilaterally changing their decision.
Game Theory
Cournot Game (1/4)
Situation
Let there be n strategic players and one tactical generator, all
situated at one node where there is a given demand d. The
tactical generator’s offer curve slope is b. The price seen by
all players is the same. This effectively reduces the game to a
Cournot model.
Residual Demand Curve
From the point of view of the competing strategic generators,
the above situation leads to a demand response curve with
intercept db and slope –b. Therefore the nodal price is given
by b(d – Q). Where Q is the sum of the strategic generators’
injections qi.
Game Theory
Cournot Game (2/4)
Best Response Correspondences
In an n player Cournot game it can be shown that:
 
 
qi  arg max qi b  d   q j  
qi
j
 
 
qi 
d  qj
j i
2
For a two player game this reduces to:
d  q2

q1 
2
d  q1

q2 
2
Game Theory
Cournot Game (3/4)
Best Response Correspondences
These previous functions are known as best response
correspondences; they are the optimal quantity a player
should offer in response to given quantities for the other
players.
Nash Equilibrium
d
q q 
3

1

2
Game Theory
Cournot Game (4/4)
Best Response Correspondences
1
0.9
Nash Equilibrium
0.8
0.7
q2
0.6
Player 1
Player 2
0.5
0.4
0.3
0.2
0.1
0
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
q1
Game Theory
Issues
No Equilibrium (1/2)
Borenstein, Bushnell and Stoft. 2000. Competitive Effects of Transmission Capacity.
q1
q2
|f|≤K
Q1
Q2
d
d
Profit, q2 = 0.75
Profit, q2 = 0.5
0.3
0.25
0.25
0.2
Profit
Profit
0.2
0.15
0.15
0.1
0.1
0.05
0.05
0
0
0
0.2
0.4
0.6
q1
0.8
1
1.2
0
0.2
0.4
0.6
0.8
1
1.2
q1
Issues
No Equilibrium (2/2)
No Intersection of Best Response Curves
1
0.8
0.6
q2
Player 1
Player 2
0.4
0.2
0
0
0.2
0.4
0.6
0.8
1
q1
Issues
Multiple Discrete Equilibria
Two Nash Equilibria
1.6
1.4
1.2
q2
1
Player 1
Player 2
0.8
0.6
Two Equilibria
0.4
0.2
0
0
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
q1
Issues
Continuum of Equilibria
Continuum of Equilibria
1
q1
0.8
Q
|f|≤K
0.6
q2
Player 1
Player 2
0.4
q2
d
0.2
0
Continuum of Equilibria
0
0.2
0.6
0.4
0.8
1
q1
Issues
Computing
Equilibria
Sequential Best Response (1/2)
Cournot, A. 1838. Recherchés sur les principes mathematiques de la theorie des richesses.
Best Response
We need to be able to calculate the global optimal injection
quantity. To do this we can perform a bisection search.
Residual Demand Curve
Revenue as Function of Offer
1.2
0.25
1
0.2
Revenue
Price
0.8
0.6
0.15
0.1
0.4
0.2
0.05
0
0
0
0.2
0.4
0.6
0.8
Offer
1
1.2
1.4
0
0.2
0.4
0.6
0.8
1
1.2
1.4
Offer
Computing Equilibria
Sequential Best Response (2/2)
Sequential Best Response
SBR Algorithm
1
1.
Set starting
quantities for all
players.
0.8
0.6
3.
For each player,
choose optimal
quantity assuming
all other players
are fixed.
If not converged
go to step 2.
Player 1
Player 2
SBR
q2
2.
0.4
0.2
0
0
0.2
0.4
0.6
0.8
1
q1
Computing Equilibria
EPEC Formulation (1/2)
Dispatch Problem
Player’s Revenue Maximisation
bT x 2
min
1
2
s/t
Mx  Af  Bf 2  d
Lf  0
0 xq
K  f  K
 
 
 1 ,  2 
1 ,2 
Formulate KKT System
max  xi   i
s/t
Optimal Dispatch
0  qi  qimax
Solve all players’ revenue
maximisation KKTs simultaneously;
a Nash equilibrium will be a feasible
solution to these equations.
Formulate KKT System
Computing Equilibria
EPEC Formulation (2/2)
Non-Concave
The issue with the EPEC formulation is that the revenue
maximisation problems are not concave. This means that
there will exist solutions to the EPEC system which are only
local, not global equilibria.
Candidate Equilibria
The non-concavity stems from capacity constraints, which
give rise to orthogonality constraints in the KKT. Solving this
problem for a specific regime yields a candidate equilibrium.
Checking Equilibria
Once a candidate equilibrium is found, it still needs to be
verified.
Computing Equilibria
Example
PERM Grid
This is a cut-down version of the
New Zealand electricity network.
It has 18 nodes and 25 lines.
The actual New Zealand network
has 244 nodes and over 400
lines.
Example
Equilibria over NZ Grid (1/2)
Price at Benmore
d
70
q1
60
Q1
Price /$
50
40
30
20
q2
10
0
0
200
400
600
800
Benmore's Offer /MW
d
Q2
Example
Equilibria over NZ Grid (2/2)
Example
Thank You
Any Questions?
Electricity Market
Dispatch Example
If q1 + q2 ≤ 1, then the tactical
generator is dispatched for,
qt = 1 – q1 – q2
Combined Offers
1
0.75
Price
• 1 node with demand equal to 1
• 1 tactical generator with offer
curve, p = qt
• 2 strategic generators, which
offer q1 and q2
0.5
0.25
0
0
0.25
0.5
0.75
1
1.25
1.5
Quantity
The tactical generator sets the
price, p = qt
Electricity
Sequential Best Response
Bi-Section Search
It can be shown that price at node i is non-increasing with injection
at node i. This allows bounds to placed upon revenue to speed up
search process.
Iteration
Iteration 12
3
7
4
1.2
1.2
11
pp
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
0.2
00
0
00
0
0.2
0.2
0.2
0.4
0.4
0.4
0.6
0.6
0.6
0.8
0.8
0.8
11
1
1.2
1.2
1.2
1.4
1.4
1.4
qq
q
Computing Equilibria
Multi-nodal Best Response
• So far we have considered a player to be a generator situated
at a single node.
• Some New Zealand generators have plants situated at
multiple nodes around the grid; these plants may receive
different prices.
• The challenge is therefore to maximise their combined profit,
when changing the offer at one node impacts other nodes’
prices.
• An extension of the bi-section method can be used.
Future Work
Supply Function Equilibria
• Until now we have assumed demand to be fixed, however a
more realistic situation is demand being a random variable.
• This means an offer at price 0 is no longer the best response
in expectation. As there now exist multiple residual demand
curves, which each have an associated probability.
• If we confine our decision space to piecewise linear offer
curves, we can parameterise the curve by the end of each
piece (p,q). It is then possible to perform a multi-dimensional
bisection method to find a best response.
Future Work
Supply Function Best Response
Supply Function Best Response
250
200
150
p
1 Piece
2 Pieces
3 Pieces
100
50
0
0
20
40
60
80
100
120
140
160
q
Future Work