A Decentralized Mechanism for Computing Competitive Equilibria in
Deregulated Electricity Markets∗

arXiv:1603.03083v2 [math.OC] 23 Mar 2016

Erik Miehling and Demosthenis Teneketzis†
Abstract— With the increased level of distributed generation
and demand response comes the need for associated mechanisms that can perform well in the face of increasingly complex deregulated energy market structures. Using Lagrangian
duality theory, we develop a decentralized market mechanism
that ensures that, under the guidance of a market operator, selfinterested market participants:generation companies (GenCos),
distribution companies (DistCos), and transmission companies
(TransCos), reach a competitive equilibrium. We show that even
in the presence of informational asymmetries and nonlinearities (such as power losses and transmission constraints), the
resulting competitive equilibrium is Pareto efficient.
Index Terms— Power systems, Optimization, Decentralized
control, Network analysis and control, Duality theory

I. INTRODUCTION
From the introduction of the Public Utilities Regulatory
Policies Act (PURPA) in 1978 to the establishment of the
Energy Policy Act in 1992, the deregulation of electricity
markets in the United States has grown continuously, primarily under the appeal of increased technological competition
and innovation. Today, despite cases of market manipulation
(such as the California electricity crisis in 2000-2001), many
large electricity markets are, at least in some capacity,
deregulated. This transition has been centered around the
formation of specialized firms for generation, transmission,
and distribution, to name a few, with markets typically
consisting of the following companies [1] (termed market
participants): generation companies (GenCos) who produce
and sell power, transmission companies (TransCos) who own
the transmission assets and are responsible for transmitting
power across the grid, and distribution companies (DistCos)
who own the distribution networks and are tasked with
buying power from GenCos and distributing it to consumers.
The primary goal in an energy market is determining an
outcome that is not only economically optimal (that is, it is
Pareto efficient [2], [3]) but also satisfies the physical constraints of the system. Achieving this goal in a deregulated
energy market is complicated by many factors. First, market
participants possess informational asymmetries arising from
private cost information and localized system knowledge.
Additionally, there are power losses within the network,
limits on transmission lines, contingency considerations, lack
of efficient power storage capabilities, and the underlying,
fundamental rule that power flow is dictated by the laws of
physics (Kirchhoff’s laws). These physical laws result in a
*This work was supported by NSF grant CNS-1238962.
† E. Miehling and D. Teneketzis are with the Department of Electrical
Engineering and Computer Science, University of Michigan, Ann Arbor,
MI, USA, 48109. E-mail: miehling@umich.edu.

phenomenon in power systems termed loop flow, creating
externalities in the market for electricity [4].
Centralized market mechanisms are traditionally the approach used for determining the optimal, feasible outcome of
the market [5]. Under these approaches a centralized market
operator receives bids from the market participants, in the
form of cost/benefit functions and technical constraints, and
solves a large-scale centralized optimization problem to determine the market clearing outcome. This outcome consists
of a physically feasible operating point as well as a vector
of bus-specific power prices termed locational marginal
prices (LMPs). Unfortunately, centralized mechanisms suffer
from some drawbacks. First, reporting cost and technical
information raises privacy concerns for market participants.
Also, as systems grow in size, the centralized optimization
problem can become prohibitively large. This is exacerbated
by the recent surge in distributed generation and demand
side participation [6], increasing the dimensionality and
complexity of the problem further and potentially making
centralized mechanisms computationally intractable.
In hopes of avoiding these drawbacks, we introduce a decentralized market mechanism which achieves the economically optimal outcome, honoring the informational asymmetries of the problem and considering important nonlinearities
of the system (such as power losses and limits on transmission lines). The electricity market model consists of multiple
market participants, DistCos, GenCos, and TransCos, and
a single market operator. Our model allows for the consumption centers of each DistCo and the production centers
of each GenCo to be distributed across the network. For
example, a given GenCo could own generators at multiple
buses in the network (a portfolio of plants). Additionally,
our model allows for the ownership of transmission lines in
the system to be partitioned among multiple TransCos. The
market operator is responsible for obtaining a market clearing
outcome. The process of achieving this market clearing
outcome, termed a decentralized market mechanism, is based
on principles from Lagrangian duality theory, specifically
making use of the dual decomposition method [7]. The
mechanism, which we refer to as the pricing process, consists
of an iterative price response and price update procedure. All
market participants are assumed to act in a self-optimizing
manner, that is, given the current LMPs they adjust their
decision variables in order to maximize their financial surplus
subject to their own local physical and operational constraints. This allows, for instance, for DistCos to exercise
flexible demand participation for the elastic component of
their total demand and for GenCos to self-dispatch. DistCos

and GenCos optimize independently, reporting their surplusmaximizing consumption and production profiles, respectively. TransCos partake in a cooperative message exchange
process to reach an operating point that induces power
flows that maximize their surpluses for transmitting power
along their respective lines. The optimizers are sent to the
market operator who is responsible for updating the LMPs
in such a way that the self-interested behavior of market
participants leads to an outcome that is physically feasible.
This outcome, when coupled with the associated set of
LMPs, forms a competitive equilibrium [2], [8], which we
show is Pareto efficient. Under relatively weak conditions
(a convex DC approximation and edge-wise positive sums
of LMPs), the market participants’ optimization problems
are convex and the pricing process converges. The pricing
process avoids the need for market participants to reveal
sensitive information, and additionally, the mechanism scales
much more effectively than its centralized counterpart.
The body of research concerning deregulated electricity
markets is vast. We focus on papers most similar to ours,
primarily including works that develop decentralized market
mechanisms (under perfect competition) using Lagrangian
duality techniques. Duality theory allows one to solve the
computationally simpler dual problem; however, this can
result in a non-zero duality gap in general. The authors
of [8], [9] construct a market model consisting of GenCos,
DistCos, and a single TransCo, considering a fully nonlinear
AC power flow model. Their decentralized mechanism, based
on a dual approach, is conjectured to converge to a zero duality gap solution under profit optimality and a convexifying
market rule (a restriction of market participants’ behavior).
Lavaei and Sojoudi [10] consider a competitive energy market setting with GenCos, DistCos, and an ISO under the AC
power flow model (using an SDP reformulation). Assuming
positive LMPs, the authors are able to show convergence to
a zero duality gap solution under the assumption of either:
a radial network, or, in the case of a mesh network, the
existence of a phase-shifter for each network cycle. In the
absence of phase-shifters, a zero duality gap can be ensured
if loads are allowed to be over-satisfied (discarding extra
power). Similar mechanisms have been applied in the context
of the unit commitment problem (e.g. [11], [12], [13]) and
demand response exchange markets (see [14] and [6]).
The contributions of this paper are twofold: 1) Modeling
generality: Our model allows for the ownership of power
system assets to be partitioned among the market participants. This allows for each DistCo and GenCo to own
multiple units that are distributed across the network (existing
literature assumes that each participant owns a single unit [8],
[9], [10]). Our model also allows for ownership of lines to
be partitioned among multiple TransCos ([8], [9] consider
a single TransCo); 2) Convergence to a zero duality gap
solution: Existing models contain nonlinearities that either
preclude convergence guarantees ([8], [9]) or require strong
sufficient conditions [10]. Our convex power flow approximation allows for power losses to be well-approximated
while (under natural conditions) ensuring convergence.

II. ENERGY MARKET MODEL
We consider a network of N buses, denoted by the set N ,
connected by transmission lines, denoted by the undirected
edge-set E. Each edge, {n, m} ∈ E, has a line limit
Knm = Kmn > 0 and an admittance Ynm = Gnm + iBnm
which consists of a conductance Gnm = Gmn > 0 and
a susceptance Bnm = Bmn > 0. We set Knm = 0 and
Ynm = 0 + i0 for {n, m} 6∈ E. Each bus has an associated
voltage angle, denoted by θn , with the vector of all angles
(termed the operating point) denoted by θ = {θn }n∈N .
In addition to the market operator (MO), the market
model in our paper contains three types of agents (market
participants): DistCos, denoted by the set D = {1, . . . , D};
GenCos, denoted by G = {1, . . . , G}; and TransCos, denoted
by T = {1, . . . , T }. Each DistCo i ∈ D owns consumption
units, consisting of elastic loads at buses NDi e ⊆ N and
inelastic loads at buses NDi s ⊆ N . The elastic
 and inelastic
load profiles of DistCo i ∈ D are ei = ein n∈N i and
De

si = sin n∈N i , respectively, where ein ∈ [ein , ēin ] is the
Ds
elastic demand and sin ≥ 0 is the (given) inelastic demand
of DistCo i’s consumption unit at bus n. Each GenCo i ∈ G
owns generation units at buses NGi ⊆ N. The real power
injection profile of GenCo i ∈ G is pi = pin n∈N i where
G

pin ∈ [pin , p̄in ] is the injection of GenCo i’s generation unit at
bus n. Lastly, each TransCo i ∈ T owns a set of transmission
lines E i with ownership of lines in the system partitioned
among TransCos, that is, E 1 ∪· · ·∪ E T = E and E i ∩E j = ∅,
i 6= j. Each edge-set E i has an associated set of buses NTi
defined as the endpoints of the edges in E i . The associated
voltage angle profile of TransCo i ∈ T is θ i = θn n∈N i .
T
A sample network can be seen in Fig. 1.
1

p22

2

4

K14

p11
p21
K12

p14
e14

K34
K45

s12

3

K23

5

e15
e25
s25

Fig. 1. A sample 5-bus network. GenCo i = 1 owns generator units at buses
NG1 = {1, 4} corresponding to an injection vector p1 = (p11 , p14 ). GenCo
i = 2 has generator units at buses NG2 = {1, 2}, p2 = (p21 , p22 ); DistCo
i = 1 has elastic loads at buses 4 and 5, e1 = (e14 , e15 ), and an inelastic load
1 = {4, 5}, N 1 = {2}; and lastly, DistCo
at bus 2, s1 = s12 , thus ND
e
Ds
2 = N 2 = {5},
i = 2 has both an elastic and inelastic load at bus ND
e
Ds
2
2
2
2
thus e = e
,
s
=
s
.
Bus
3
is
a
zero-injection
bus.
TransCo
i = 1 owns
5
5
lines E 1 = {1, 2}, {1,4}, {2, 3} thus NT1 = {1, 2, 3, 4} and TransCo
i = 2 owns lines E 2 = {3, 4}, {4, 5} so NT2 = {3, 4, 5}.

For later convenience, we also define NTi,j := NTi ∩NTj as
the set of shared buses between two TransCos’ edge-sets E i
and E j and Tn := {i ∈ T | n ∈ NTi } as the set of TransCos
that own lines that are connected to bus n.

The load and generation profiles of DistCos and GenCos
have associated utilities and costs, respectively. For an elastic
load profile ei the aggregate utility
of

P (benefit) function
DistCo i is defined as ui ei := n∈N i e uin ein , where
D
uin (ein ) is the benefit associated with elastic demand level ein .
Similarly, GenCo
 i’sPaggregate cost function (total generation
cost) is ci pi := n∈N i cin pin where cin (pin ) represents
G
the cost for producing real power pin .
A. Knowledge model
We now describe the knowledge model, that is, what
each of the power system entities knows about the system.
Each DistCo i ∈ D possesses private information regarding
their utility functions {uin }n∈NDi e and any bounds on the
elastic load level ei = {ein }n∈NDi e , ēi = {ēin }n∈NDi e .
Each GenCo i ∈ G possesses private information regarding
their cost functions {cin }n∈NGi and production bounds pi =
{pin }n∈NGi , p̄i = {p̄in }n∈NGi . Each TransCo i ∈ T knows
the connectivity of their region of the network, (NTi , E i ), as
well as the admittances of the corresponding lines, Ynm for
{n, m} ∈ E i . TransCos also possess private information of
the line limits of their transmission lines, Knm , {n, m} ∈ E i .
Each DistCo i ∈ D knows the inelastic demands at its buses,
{sin }n∈NDi , whereas the MO is assumed to know all inelastic
demand levels. Furthermore, the MO knows the location of
all DistCo and GenCo units, the network connectivity, and
the admittances of all transmission lines in the network.
B. Model Assumptions
We make five core assumptions regarding our model:
Assumption 1 (convex DC approximation): We propose a
power flow approximation which represents power flow as
a convex function of the angle difference. To begin the
derivation, recall that by the AC power flow equations [15]
the real power flowing from bus n to bus m is Pnm =
Gnm Vn2 −Gnm Vn Vm cos(θn−θm )+Bnm Vn Vm sin(θn−θm ).
We set voltage magnitudes to 1 p.u., Vn = 1 ∀n ∈ N , and
assume that voltage angle differences, θn − θm , are small
(similar to the DC approximation). Using the second-order
small angle approximations, sin(θn − θm ) ≈ θn − θm and
cos(θn −θm ) ≈ 1− 12 (θn −θm )2 , we can write the expression
for the power flow from bus n to bus m as a convex function
of the angle difference, θn −θm . The resulting approximation,
which we term the convex DC approximation, dictates that
the flow of power on line (n, m) is
1
g(θnm ) := Bnm (θn − θm ) + Gnm (θn − θm )2 . (1)
2
The above approximation maintains the asymmetry of the
power flow equations, g(θnm ) 6= −g(θmn ), and consequently
allows for power losses to be considered (unlike with the DC
power flow approximation). The real power losses along line
{n, m}, Lnm = Pnm + Pmn , are approximated by Lnm ≈
Gnm (θn − θm )2 . For notational convenience, we split Eq.
(1) into a DC component, ḡ(θnm ) := Bnm (θn − θm ), and a
(convex) loss component, g̃(θnm ) := 12 Gnm (θn − θm )2 .

Assumption 2 (slack buses): Denote the set of slack buses
by NS . We require that each TransCo has exactly one slack
bus, that is, NTi ∩ NS contains one element for all i ∈ T .
Slack buses serve solely as angle references, that is, θn = 0
for all n ∈ NS .
Assumption 3 (strong convexity): We require that all DistCo
utility functions uin are strongly concave and all GenCo cost
functions cin are strongly convex (this condition is equivalent
to strict convexity if the functions are quadratic). See [16]
for justification of the convexity assumption.
Assumption 4 (positive edge-wise sums of prices): We
require that all edge-wise sums of locational marginal prices
are positive. That is, λn + λm > 0 for all {n, m} ∈ E.1 Note
that this allows λn < 0 for some n.
Assumption 5 (price-taking behavior): We assume that the
agents (market participants) are price-taking, that is, they
assume that the price will remain unchanged if they change
their response. This assumption requires that no single agent
is large enough (apart from the MO) to influence the price;
an assumption which is reasonable in our market model as
the number of agents in the system increases.
III. MAXIMIZING SOCIAL WELFARE
We are interested in determining the set of variables,
consisting of DistCo elastic demand levels {ei }i∈D , GenCo
real power injection levels {pi }i∈G , and an operating point θ,
such that the social welfare is maximized, subject to physical
and operational constraints. It is known from microeconomic
theory that maximizing the social welfare results in a Pareto
efficient outcome [2]. The single time-period problem can be
formally stated as Problem (P) below.
X
 X i i
max i
J(x) :=
ui ei −
c p
(P)
i
x=({e }i∈D ,{p }i∈G ,θ)

i∈D

i∈G



(P.i)

p ≤ p ≤ p̄ , i ∈ G

(P.ii)

s.t. p − (e + s) = f θ
i

i

i

i

i

i

e ≤ e ≤ ē , i ∈ D


g θnm ≤ Knm , g θmn ≤ Kmn , {n, m} ∈ E

(P.iii)

θn = 0, n ∈ NS

(P.vi)

θnm ≤ θnm ≤ θ̄nm , {n, m} ∈ E
θn ∈ [−π, π], n ∈ N

(P.iv)
(P.v)
(P.vii)

The objective function of Problem (P), J(x), represents the
social welfare and is defined as the total utility to DistCos
minus the total cost to GenCos.
The constraints of problem (P) arise from both physical
laws and the operational requirements of the power system
and the agents. The first constraint (P.i), termed the power
balance equation, takes the form

p − (e + s) = f θ
(2)
P
i
where p = (p1 , p2 , . . . , pN ), with pn =
i∈G pn , is the
net generation vector and (e + s) is the net demand vector
1 Note: We are not enforcing this as a constraint in our problem, rather we
are only considering topologies where this assumption is naturally satisfied.

consisting of two components, the elastic demand vector
e = (e1 , e2 , . . . , eN ) and the (fixed) inelastic
demand vector
P
i
sP = (s1 , s2 , . . . , sN ) (with
e
=
e
=
n

 i∈D n and sn 
i
s
).
The
vector
f
θ
=
f
θ
,
f
θ
,
.
.
.
,
f
θ
1
2
N
i∈D n
denotes the power injections induced by the operating point
θ, where the injection
P at bus n is defined by the convex
function fn θ = m∈N g θnm , where g(θnm ) represents
the power flow from bus n to m defined in Eq. (1); notice that
g(θnm ) is zero if {n, m} 6∈ E. Constraint (P.i) simply states
that the injections due to physical laws, f (θ), must agree with
the net generation and demand at every bus. Constraints (P.ii)
and (P.iii) reflect the fact that GenCos/DistCos have bounds
on the amount of power they are able to produce/consume.
Transmission constraints on the amount of power flowing on
each line, constraint (P.iv), stability constraints on the voltage
angle difference, (P.v), and slack references, (P.vi), are also
imposed. The last constraint, (P.vii), is a technical condition
that ensures that the voltage angles are well-defined. We
group constraints (P.ii)-(vii) into a set denoted by X. It is
clear that X is convex since it is the intersection of halfspaces and convex inequality constraints. Lastly, we assume
that Problem (P) is feasible.
There are some fundamental difficulties in obtaining a
solution to Problem (P). First, the problem is nonconvex
due the presence of the nonlinear power balance equation.
Furthermore, by the discussion in Section II-A, no single
entity in the system has the information required to obtain
a solution to Problem (P). The remainder of the paper will
focus on obtaining a solution to Problem (P).
IV. SURPLUSES & COMPETITIVE EQUILIBRIA
The notion of a competitive equilibrium will be of central
importance in obtaining a solution to Problem (P). Before
we formally define a competitive equilibrium in the context
of our problem, we need to discuss some aspects related to
the Lagrangian dual function of Problem (P).
A partial Lagrangian of Problem (P) is formed by dualizing the power balance equation through the vector of
dual variables, λ, where each component λn represents
the locational marginal price of power at bus n. Denoting
i
i
the vector of variables
 by x = ({e }i∈D , {p }i∈G , θ), and
defining h(x) := f θ − p + e + s, the Lagrangian is

L x, λ := J(x) − λ> h(x)
X
 X



=
ui ei − ci pi − λ> f θ − p + e + s
i∈D

=

i∈G

X X
i∈D n∈N i e

 X X i i
uin ein −
cn pn
i∈G n∈NGi

D

!
−

X
n∈N

λn

fn (θ) −

X
i∈G

pin

+

X

ein

=

i∈D



i∈D


X

+

sin


X 
X



uin ein − λn ein −
λn sin 
i
n∈ND
e

i
n∈ND
s


+

X
i∈G


X
X 


λn fn (θ). (3)
λn pin − cin pin  −
n∈N

n∈NGi

Due to the structure of the Lagrangian, Eq. (3), the evaluation

the dual function, defined as φ(λ) = maxx∈X L x, λ ,
is greatly simplified via separable optimizations.


φ(λ) = max L x, λ
x∈X
 X

X
X
 i i

i
i
u
e
−
λ
e
−
λ
s
=
max
n
n
n n
n
n
i
i
i∈D

+

e ∈E

X
i∈G

i
n∈ND
e

p ∈P


+ max
θ∈Θ

i
n∈ND
s

 X



i
i
i
λn pn − cn pn
max
i
i
−

n∈NGi

X


λn fn (θ)

(4)

n∈N

where the constraint sets are Ei = {ei |ei ≤ ei ≤ ēi }, Pi =
{pi |pi ≤ pi ≤ p̄i }, and Θ = {(θ 1 , . . . , θ T ) ∈ Θ1 × · · · ×
ΘT : θni = θnj , n ∈ NTi,j , i, j ∈ T } with each TransCo’s
feasible set defined as



Θi := θ i g θnm ≤ Knm , g θmn ≤ Kmn , {n, m} ∈ E i ;
θnm ≤ θnm ≤ θ̄nm , {n, m} ∈ E i ;

θn = 0, n ∈ NTi ∩ NS ; θn ∈ [−π, π], n ∈ NTi .
For later reference, the dual problem of Problem (P) is simply
min φ(λ).

(D)

λ

A. Agent Surplus Functions
The arguments of the maximizations in Eq. (4) represent
surplus functions of the agents. This follows from the fact
that the dual variables, λ, of the power balance equation
represent locational marginal prices. The surplus for DistCo
i ∈ D for a given demand profile (ei , si ) at price λ is equal
to the utility obtained from ei minus the cost of total demand
(sum of elastic and inelastic demand), defined as
X 
X


i
ΨD
(ei , λ) :=
uin ein − λn ein −
λn sin .
i
n∈ND
e

i
n∈ND
s

The surplus of each GenCo i ∈ G is equal to the payment it
receives for producing power minus the generation cost,
X 

ΨGi (pi , λ) :=
λn pin − cin pin .
n∈NGi

TransCos receive a surplus for facilitating power flow across
the network. Congestion and losses in transmission lines
creates different valuations for power across the network
(represented by LMPs) and results in a discrepancy between
the payments received from DistCos and the payments made
to GenCos. This creates a surplus (possibly negative) for
transmitting power from GenCos to DistCos, termed the
merchandizing surplus. Under the convex DC approximation
(assumption 1), the total merchandizing surplus (argument of
the last maximization term in Eq. (4)) can be shown to be
X
X
ΨT (θ, λ) = −
λn fn (θ) = −
λn g(θnm )
n∈N

~
(n,m)∈E

=


1 X
(λm − λn )ḡ(θnm ) − (λn + λm )g̃(θnm ) (5)
2
~
(n,m)∈E

where E~ is the directed edge-set and is defined as the set that
contains the pair (n, m) and (m, n) for
 every edge {n,
 m} ∈
E. The quantity λm − λn ḡ θnm − λn + λm g̃ θnm
is the merchandizing surplus for enabling flow between
buses n and m at the price
vector λ. Notice that the first

term, λm − λn ḡ θnm , is the familiar expression for the
merchandizing surplus under the DC approximation [17].
The second term, − λn + λm g̃ θnm , arises from the fact
that we are considering losses in our model (see assump. 1).
Since the ownership of transmission lines is partitioned
among TransCos we can separate the total merchandizing
surplus into each TransCo’s merchandizing surplus as
1 X
(λm − λn )ḡ(θnm )
ΨTi (θ i , λ) =
2
i
~
(n,m)∈E

− (λn + λm )g̃(θnm ) . (6)
We show that, via a message exchange process described in
Section V-A.3, TransCos communicate to obtain the angle
profile which maximizes ΨT (θ, λ) over θ ∈ Θ at price λ.
B. Competitive Equilibria in Energy Markets

parallel to obtain the optimal profiles for the current price
λt , denoted by {ei (λt )}i∈D and {pi (λt )}i∈G , respectively.
TransCos partake in a message exchange process (due to coupling of merchandizing surplus functions) in order to obtain
the operating point which maximizes the total merchandizing
surplus at the current price, denoted by θ(λt ). The MO uses
these maximizers to update the price in such a way as to
enforce feasibility (condition (i) of Def. 1). A block diagram
outlining the method can be seen in Fig. 2.
DistCos

D {ei ( t )}i2D
GenCos

MO
Price
Update

G {pi ( t )}i2G

t

t+1

t

TransCos

t+1

T

✓(

t

)

t

x( )

We can now define the concept of a competitive equilibrium in the context of our energy market model. The
definition builds upon the one found in [8].
Definition 1 (Competitive Equilibrium): A
competitive
equilibrium is defined as the tuple ({êi }i∈D , {p̂i }i∈G , θ̂, λ̂)
such that
(i)

fn (θ̂) − p̂n + ên + sn < ε for all n ∈ N , ε > 0

i
(ei , λ̂) s.t. ei ∈ Ei , ∀ i ∈ D
(ii) êi (λ̂) maximizes ΨD

p̂i (λ̂) maximizes ΨGi (pi , λ̂) s.t. pi ∈ Pi , ∀ i ∈ G

θ̂ i (λ̂) maximizes ΨTi (θ i , λ̂) s.t. θ i ∈ Θi , ∀ i ∈ T
The above definition states that a competitive equilibrium
must not only satisfy the power balance equation (condition
(i)) but also result in maximum surplus for all DistCos,
GenCos, and TransCos (condition (ii)).
V. SOLUTION METHODOLOGY
Throughout the remainder of the paper we describe a
procedure in which the MO and agents interact in order
to obtain a globally optimal solution x∗ to the nonconvex
primal problem (P). The procedure is based on the dual
decomposition method; an iterative method that first involves
the evaluation of the dual function for a given set of
dual variables (prices), followed by an update of the dual
variables.
In the context of the electricity market model in this
paper, the evaluation of the dual function is performed in
a distributed fashion by the agents. In fact, maximization of
surpluses by the agents corresponds exactly to the evaluation
of the dual function. DistCos and GenCos maximize in

Fig. 2. The pricing process: Given the current price vector λt , DistCo’s
and GenCo’s update the respective components of the consumption profiles
{ei (λt )}i∈D and generation profile {pi (λt )}i∈G , in parallel. TransCo’s
participate in a message exchange process to reach an angle profile agreement θ(λt ). The MO then updates the price to λt+1 using the responses
x(λt ) = ({ei (λt )}i∈D , {pi (λt )}i∈G , θ(λt )) (outlined in Section V-B).

A. Price Response - Dual Function Evaluation
The first step of the iterative process involves evaluation
of the dual function for a given current price vector λt . This
is achieved via the following agent surplus maximizations.
1) DistCo Optimizations: Each DistCo, i ∈ D, wishes to
specify the elastic demand level ei in order to maximize its
surplus from buying power (both elastic and inelastic) at the
current price λt . Each DistCo i ∈ D solves
i
ei (λt ) = argmax ΨD
(ei , λt )
ei ∈Ei

(PDi )

By assumption 3, each uin is strictly concave and therefore
the maximizer ei (λt ) of Problem (PDi ) is unique for each i.
2) GenCo Optimizations: Each GenCo, i ∈ G, wishes
to specify the injection levels pi in order to maximize its
surplus from selling power at λt . Each GenCo i ∈ G solves
pi (λt ) = argmax ΨGi (pi , λt )
pi ∈Pi

(PGi )

Again, by assumption 3, the maximizer pi (λt ) of Problem
(PGi ) is unique for each i ∈ G.

3) TransCo Optimizations: Each TransCo, i ∈ T , aims
to specify their voltage angle profile θ i ∈ Θi such that the
induced flows maximize their merchandizing surplus at the
current price, ΨTi (θ i , λt ). Doing so is complicated by the
fact that there exist buses that are shared between one or
more TransCos, that is, NTi,j 6= ∅ for neighboring i, j ∈ T .
The presence of these shared buses creates coupling between
the merchandizing surplus functions of distinct TransCos.
As a result, all neighboring TransCos must negotiate the
angle value of their shared buses. Arriving at a systemwide agreement for the shared buses, with each TransCo
maximizing their own merchandizing surplus, results in a
maximization of the total merchandizing surplus (achieving
the value of the last term in Eq. (4)). The angle profile
agreement is achieved via a message exchange process that is
based on the ADMM algorithm [18] in which neighboring
TransCos iteratively exchange the voltage angle values of
their shared buses.
To make use of the ADMM algorithm, it is necessary to
write the problem of maximizing the total merchandizing
surplus, maxθ∈Θ ΨT (θ, λ), as the equivalent problem
X
t
max
Ψ
(θ,
λ
)
=
ΨTi (θ i , λt )
(PT )
T
i
{θ }i∈T ,z

subject to

i∈T

i

i

θ ∈ Θ ,i ∈ T

θ i − zi = 0, i ∈ T
where z ∈ RN is the global variable representing the systemwide angle profile θ and zi = {zn }n∈NTi is the relevant
component of z corresponding to TransCo i’s angle profile.
We associate a set of dual variables, yi = {yn }n∈NTi , with
each of the consensus constraints θ i − zi = 0, i ∈ T . The
consensus constraints enforce the angle profiles of TransCos
to agree. Defining primal and dual residual norms [18] as

r(k) := θ 1,(k) − z1,(k) , . . . , θ T,(k) − zT,(k)
(7)

(k)
1,(k)
1,(k−1)
T,(k)
T,(k−1)
s := −ρ z
−z
,...,z
−z
(8)
the TransCo message exchange process is given by Alg. 1.
Algorithm 1: TransCo Message Exchange Process
Initialize k = 0, yi,(0) = 0 for all i ∈ T , z(0) = 0, ρ > 0;
while ¬(||r(k) ||2 < εprimal and ||s(k) ||2 < εdual ) do
for i ∈ T do (parallel optimization and broadcast)
TransCo i solves:

θ i,(k+1) (λt ) = argmax ΨTi (θ i , λt )
2

i,(k+1)

n

Lemma 1 and the convergence result of the ADMM in [18]
(p.17) lead to the following corollary.
Corollary 1: Alg. 1 generates iterates {z(k) } that converge to the unique solution θ(λt ) of maxθ∈Θ ΨT (θ, λt ).
All of the maximizers for the current price λt are then
broadcast to the MO, as in Fig. 2, and the price is updated.
B. Price Update
The MO receives all of the maximizers from the agents,
x(λt ) = ({ei (λt )}i∈D , {pi (λt )}i∈G , θ(λt )), for the current
price λt and uses them to compute an updated price λt+1 .
The price is updated in such a way as to iteratively enforce
the power balance equation (see cond. (i) of Def. 1). Before
defining the price update, we state the following result.
Lemma 2: The Hessian of the Lagrangian is negative
definite, that is, ∇2xx L(x, λ) ≺ 0 for all x.
Proof: See appendix B.
As a consequence of the strong concavity of the Lagrangian,
the dual function, Eq. (4), is unique and its derivative exists.
The gradient of the dual function is (see Thm. 6.3.3 of [19])
∇λ φ(λ) = h(x(λ))>

(9)

where h(x) was defined at the beginning of Section IV. As
a result, solving the power balance equation is equivalent to
finding where the gradient of the dual function vanishes. The
price update follows a gradient descent method
λt+1 = λt − αt ∇λ φ(λt ) = λt − αt h(x(λt ))



= λt − αt f θ(λt ) − p(λt ) + e(λt ) + s

(10)

with step-size αt , net generationPprofile p(λt ) =
(p1 (λt ), . . . , pN (λt )), with pn (λt ) = i∈G pin (λt ), and net
elastic demand
e(λt ) = (e1 (λt ), . . . , eN (λt )), with

P profile
t
i
t
t
en (λ ) =
i∈D en (λ ). The injection term f θ(λ ) is
computed from the angle profile θ(λt ) (from Sec. V-A.3).

A. Convergence Properties of the Pricing Process


Broadcast {θn
}n∈N i,j to neighboring j ∈ T ;
T
for i ∈ T do (parallel average and dual variable update)
1 X j,(k+1)
(k+1)
Average: zn
=
θn
, ∀n ∈ NTi
|Tn | j∈T
Update: yi,(k+1) = yi,(k) + ρ(θ i,(k+1) − zi,(k+1) )
Update residuals: set r(k+1) , s(k+1) via Eq.’s (7), (8);
Update counter: k ← k + 1;

Lemma 1: The merchandizing surplus function ΨTi (θ i , λ)
is strongly concave in θ i for all i ∈ T .
Proof: See appendix A.

VI. ANALYSIS

θ i ∈Θi

>
ρ
− yi,(k) (θ i − zi,(k) )−
θ i − zi,(k)
2

By assumption 2, each TransCo i has a slack bus in its
set of buses NTi , and the following lemma holds.

We begin by showing that the dual function is Lipschitz
continuous (this follows from the fact that a function with a
bounded derivative is Lipschitz). By Eq. (9), the gradient of
>
the dual function satisfies
 ∇λ φ(λ) = h(x(λ)) . Noting that
kh(x(λ))k
 = kf θ(λ) − p(λ) + e(λ) + sk and the fact that
f θ(λ) , p(λ), and e(λ) are all bounded, there exists some
M < ∞ such that k∇λ φ(λ)k = kh(x(λ))k ≤ M . Thus the
dual function is Lipschitz continuous.
The dual function φ(λ) is a convex function of λ. It can
be shown through standard arguments that, for a sufficiently

small step-size, gradient descent applied to a convex function
generates iterates satisfying
Pt
kλ0 − λ∗ k2 + s=0 αs2 k∇φ(λs )k2
φ(λt ) − φ∗ ≤
Pt
2 s=0 αs
where φ∗ denotes a minimum of φ. In order
P∞ to 2ensure
convergence,
one
must
choose
α
such
that
t
s=0 αs < ∞
P∞
s
and
α
=
∞.
Noting
that
k∇φ(λ
)k
≤
M for all
s=0 s
s, we have φ(λt ) → φ∗ . Selecting a step-size of the form
αt = β/t, β > 0, ensures that the pricing process converges
to a minimizer λ∗ of the dual function φ(λ), solving the
dual problem (D).2 Since the dual problem is unconstrained,
∇φ(λ)|λ=λ∗ = 0, and, again by Eq. (9), h(x(λ∗ )) = 0.
B. Duality Gap
In this section, we demonstrate that the converged dual
solution λ∗ results in a zero duality gap with Problem (P).
Theorem 1: The pricing process described in Section V
generates a competitive eq. (x∗ , λ∗ ), where x∗ = x(λ∗ ) is
a globally optimal solution to Problem (P).
Proof: Consider Problem (Q), defined as
max {G(ω) : r(ω) = (r1 (ω), . . . , rM (ω)) = 0}.

ω∈Ω⊆RW

(Q)

Also, consider the following definition.
Definition 2 (Global ω-max, ν-min saddle point [20]):
A point (ω̂, ν̂) is a global ω-max, ν-min saddle point for
the Lagrangian M(ω, ν) = G(ω) − ν > r(ω) if and only if
M(ω, ν̂) ≤ M(ω̂, ν̂) ≤ M(ω̂, ν) ∀ ω ∈ Ω, ν ∈ RM .
The proof proceeds in two steps: (i) We prove a general result
demonstrating that if (ω̂, ν̂) is a global ω-max, ν-min saddle
point for the Lagrangian M then ω̂ is the global optimum
for the problem (Q) (similar to the proof found in [20]); (ii)
We show that the pricing process generates a global x-max,
λ-min saddle point for the Lagrangian L of Problem (P).
Part (i): Assuming that (ω̂, ν̂) is a global ω-max, ν-min
saddle point, we have M(ω̂, ν̂) ≤ M(ω̂, ν) for all ν. Thus
G(ω̂) −

M
X

m=1

ν̂m rm (ω̂) ≤ G(ω̂) −

M
X

νm rm (ω̂).

(11)

m=1

Let there exist an index m0 such that rm0 (ω̂) > 0, then we
can choose νm0  0 such that Eq. (11) is violated. Similarly,
let there exist an index m00 such that rm00 (ω̂) < 0, we can
violate Eq. (11) by choosing νm00  0. Thus rm (ω̂) = 0 for
all m and therefore ω̂ is feasible for Problem (Q).
Since (ω̂, ν̂) is a global ω-max, ν-min saddle point, we
also have
for all ω ∈ Ω. Thus
PMM(ω, ν̂) ≤ M(ω̂, ν̂) P
M
G(ω)− m=1 ν̂m rm (ω) ≤ G(ω̂)− m=1 ν̂m rm (ω̂). Since
r(ω) = 0 for every feasible ω, we have that G(ω) ≤ G(ω̂)
everywhere on {ω|r(ω) = 0, ω ∈ Ω} and thus ω̂ is optimal
for Problem (Q).
Part (ii): Let x∗ = x(λ∗ ) = argmaxx∈X L(x, λ∗ ), where
λ∗ is the converged price vector obtained from the pricing
2 Prices must satisfy assumption 4 at each iteration t in order to ensure
the TransCo subproblems are convex. This can simply be achieved through
choice of a sufficiently positive λ0 .

process (Eq. 10). The profile x∗ is returned from the agents
when provided with the price λ∗ (via the optimizations
in Section V-A). By assumption 3 and Corollary 1, x∗ is
unique. Notice that (x∗ , λ∗ ) is a competitive equilibrium
by Def. 1. Also, due to the concavity of L (Lemma 2),
φ(λ∗ ) = L(x∗ , λ∗ ) ≥ L(x, λ∗ ) for all x ∈ X. We know that
∇φ(λ)|λ=λ∗ = 0 and thus, by Eq. (9), h(x(λ∗ )) = h(x∗ ) =
0. Consequently, L(x∗ , λ∗ ) = J(x∗ ) − (λ∗ )> h(x∗ ) =
J(x∗ ) = J(x∗ ) − λ> h(x∗ ) = L(x∗ , λ) for all λ. In
summary L(x, λ∗ ) ≤ L(x∗ , λ∗ ) = L(x∗ , λ) for all x ∈
X, λ and thus (x∗ , λ∗ ) is a global x-max, λ-min saddle
point for the Lagrangian L(x, λ).
From parts (i) and (ii), we conclude that the pricing
process generates the pair (x∗ , λ∗ ) where x∗ is a globally
optimal solution to Problem (P).
In summary, the pricing process generates the competitive
equilibrium (x∗ , λ∗ ) which results in a globally optimal
solution x∗ to the (nonconvex) social welfare maximization
problem (P). Consequently, x∗ is a Pareto efficient outcome.
VII. NUMERICAL EXAMPLE
We demonstrate the performance of the pricing process
on a modified version of the IEEE 14 bus test system.
The ownership of generators in the modified system is split
among three GenCos with p1 = (p11 , p12 ), p2 = (p23 , p26 ), and
p3 = (p38 ). The network also consists of seven DistCos with
e1 = (e12 , e13 ), e2 = (e23 , e24 ), e3 = (e35 ), e4 = (e46 , e411 , e412 ),
e5 = (e59 , e510 ), e6 = (e612 , e613 ), e7 = (e714 ) and inelastic
demands (in MW) s12 = 15, s35 = 10, s412 = 15, s510 = 10,
s614 = 15. The 
ownership of lines is split among two
TransCos, E 1 = {1,2},{1,5},{2,3},{2,4},{2,5},{3,4},{4,

5},{4,7},{5,6} , E 2 = {4,9},{6,11},{6,12},{6,13},{7,8},
{7,9},{9,10},{9,14},{10,11},{12,13},{13,14} with slack
bus NS = {6}. Parameters for the TransCo message
exchange process (Alg. 1) are ρ = 0.21, εprimal = 5×10-5 ,
εdual = 5×10-6 . Fig. 3 demonstrates the convergence of the
process.
It is evident from Fig. 3(b) that the pricing process
generates a solution where the power balance equation is
satisfied (condition (i) of Def. 1). At the corresponding
prices, agents report their surplus-maximizing responses, satisfying condition (ii) of Def. 1. By Theorem 1, the resulting
competitive equilibrium is Pareto efficient.
VIII. CONCLUSIONS & FUTURE WORK
We have developed an electricity market model and an
associated decentralized market mechanism that, under natural assumptions, ensures convergence to a Pareto efficient
market (competitive) equilibrium. The market model includes
multiple DistCos, GenCos, and (cooperative) TransCos all
of which are assumed to be surplus-maximizing given the
current set of LMPs. A market operator updates LMPs via a
gradient method in order to achieve an operating point that
satisfies the power balance equations and consequently clears
the market.

t=1

Voltage angles

2

t=2

t=3

t=4

t = 14

t = 24

1

0

-1

(corresponding to GenCo units), respectively. By assumption
3, we have U, C ≺ 0. Similar to the proof of Lemma 1,
matrix M can be shown to be an irreducibly diagonally
dominant matrix with a negative diagonal and thus, again by
Prop. 2.2.20 of [22], M ≺ 0. Since ∇2xx L is block-diagonal
with each block negative definite, we conclude ∇2xx L ≺ 0.
R EFERENCES

-2
1

123 1

245 1

271 1

103

1 101

1

98

Algorithm 1 cycle iterations, k
(a)

Bus power mismatch

40
30
20
10
0
-10
-20
-30
-40

1

2

3

4

5

6

7

8

9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Pricing process iterations, t
(b)

Fig. 3. Convergence of pricing process: (a) TransCos reach an angle
agreement for each price vector λt via Alg. 1 (each negotiation cycle
corresponds to a price vector); (b) The power mismatch at each bus n,
hn (x(λt )) = fn (θ(λt )) − pn (λt ) + en (λt ) + sn , converges to zero.

APPENDIX
A. Proof of Lemma 1
i
λ), P
see Eq. (6), with
Let v = θ i . The Hessian of
 ΨT (v,
2
i
respect to v is ∇vv ΨT v, λ = − 12 ∇2vv
~i (λn +
(n,m)∈E

λm )g̃(vnm ) , where the first order terms do not enter into
the expression. Define ι = NTi as the (ordered) set of bus
indices of TransCo i and define
 X
−
(λιj + λιl )Gιj ιl if j = k



{j,l}∈E i
Ajk =
−(λιj + λιk )Gιj ιk
if {j, k} ∈ E i



0
if {j, k} 6∈ E i

for each j, k = 1, . . . , |ι| = |NTi |. By assumption 2, there
exists an index s ∈ ι that corresponds to a slack bus. The
Hessian ∇2 ΨTi is defined as matrix A with the sth row
and column removed. Consequently, ∇2 ΨTi belongs to the
class of irreducibly diagonally dominant matrices, known to
be non-singular (see Theorem 6.2.27 of [21]). To see this,
note that the Hessian is diagonally dominant for all rows.
Additionally, it is strictly diagonally dominant in rows that
correspond to buses that are immediately connected to a slack
bus. By assumption 4, the diagonal elements of the Hessian
are negative and by Prop. 2.2.20 of [22], ∇2 ΨTi ≺ 0.
B. Proof of Lemma 2
The Hessian of the Lagrangian, denoted P
by ∇2xx L, is a
i
square,
block-diagonal
matrix
of
dimension
i∈D |ND e | +
P
i
|N
|
+
|N
\
N
|.
It
consists
of
three
blocks,
U,
C,
S
G
i∈G
and M, where U and C are diagonal matrices consisting of
elements (uin )00 (corresponding to DistCo units) and −(cin )00

[1] R. D. Christie and A. Bose, “Load frequency control issues in
power system operations after deregulation,” IEEE Trans. Power Syst.,
vol. 11, no. 3, pp. 1191–1200, 1996.
[2] A. Mas-Colell, M. Whinston, and J. Green, Microeconomic Theory.
Oxford University Press, 1995.
[3] D. Kirschen and G. Strbac, Fundamentals of Power System Economics.
John Wiley & Sons, 2004.
[4] H. P. Chao and S. Peck, “A market mechanism for electric power
transmission,” J. Regul. Econ., vol. 10, pp. 25–59, 1996.
[5] S. Stoft, Power System Economics: Designing Markets for Electricity,
ser. IEEE Press. Wiley, 2002.
[6] D. Papadaskalopoulos and G. Strbac, “Decentralized participation of
flexible demand in electricity markets - Part I: Market mechanism,”
IEEE Trans. Power Syst., vol. 28, no. 4, pp. 3658–3666, 2013.
[7] D. P. Bertsekas, Nonlinear programming. Athena scientific, 1999.
[8] A. Motto, F. Galiana, A. Conejo, and M. Huneault, “On Walrasian
equilibrium for pool-based electricity markets,” IEEE Trans. Power
Syst., vol. 17, no. 3, pp. 774–781, 2002.
[9] F. D. Galiana, A. L. Motto, A. J. Conejo, and M. Huneault, “Decentralized nodal-price self-dispatch and unit commitment,” in The
Next Generation of Electric Power Unit Commitment Models, ser.
International Series in Operations Research and Management Science,
B. F. Hobbs, M. H. Rothkopf, R. P. O’Neill, and H. P. Chao, Eds.
Springer US, 2002, vol. 36, pp. 271–292.
[10] J. Lavaei and S. Sojoudi, “Competitive equilibria in electricity markets
with nonlinearities,” in ACC, 2012, pp. 3081–3088.
[11] F. Zhuang and F. D. Galiana, “Towards a more rigorous and practical
unit commitment by Lagrangian relaxation,” IEEE Trans. Power Syst.,
vol. 3, no. 2, pp. 763–773, 1988.
[12] J. F. Bard, “Short-term scheduling of thermal-electric generators using
Lagrangian relaxation,” Oper. Res., vol. 36, no. 5, pp. 756–766, 1988.
[13] W. Ongsakul and N. Petcharaks, “Unit commitment by enhanced
adaptive Lagrangian relaxation,” IEEE Trans. Power Syst., vol. 19,
no. 1, pp. 620–628, 2004.
[14] D. T. Nguyen, M. Negnevitsky, and M. De Groot, “Walrasian market
clearing for demand response exchange,” IEEE Trans. Power Syst.,
vol. 27, no. 1, pp. 535–544, 2012.
[15] O. Elgerd, Electric Energy Systems Theory: An Introduction.
McGraw-Hill, 1973.
[16] B. Stott, O. Alsac, and A. Monticelli, “Security analysis and optimization,” Proc. IEEE, vol. 75, no. 12, pp. 1623–1644, 1987.
[17] F. Wu, P. Varaiya, P. Spiller, and S. Oren, “Folk theorems on
transmission access: Proofs and counterexamples,” J. Regul. Econ.,
vol. 10, no. 1, pp. 5–23, 1996.
[18] S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, “Distributed
optimization and statistical learning via the alternating direction
method of multipliers,” Foundations and Trends R in Machine Learning, vol. 3, no. 1, pp. 1–122, 2011.
[19] M. S. Bazaraa, H. D. Sherali, and C. M. Shetty, Nonlinear programming: theory and algorithms. John Wiley & Sons, 2013.
[20] P. B. Morgan, An Explanation of Constrained Optimization for
Economists. University of Toronto Press, 2015.
[21] R. Horn and C. Johnson, Matrix analysis. Cambridge University
Press, 1985.
[22] R. Cottle, J. Pang, and R. Stone, The Linear Complementarity Problem, ser. Classics in Applied Mathematics. SIAM, Philadelphia, PA,
1992.

