1

Iterative bidding in electricity markets:
rationality and robustness

arXiv:1702.06505v1 [math.OC] 21 Feb 2017

Ashish Cherukuri

Abstract—This paper studies an electricity market consisting of
an independent system operator (ISO) and a group of generators.
The goal is to solve the DC optimal power flow (DC-OPF)
problem: have the generators collectively meet the power demand
while minimizing the aggregate generation cost and respecting
line flow limits in the network. The ISO by itself cannot solve
the DC-OPF problem as generators are strategic and do not
share their cost functions. Instead, each generator submits to
the ISO a bid, consisting of the price per unit of electricity at
which it is willing to provide power. Based on the bids, the ISO
decides how much production to allocate to each generator to
minimize the total payment while meeting the load and satisfying
the line limits. We provide a provably correct, decentralized
iterative scheme, termed B ID A DJUSTMENT A LGORITHM, for
the resulting Bertrand competition game. Regarding convergence,
we show that the algorithm takes the generators bids to any
desired neighborhood of the efficient Nash equilibrium at a linear
convergence rate. As a consequence, the optimal production of the
generators converges to the optimizer of the DC-OPF problem.
Regarding robustness, we show that the algorithm is robust to
affine perturbations in the bid adjustment scheme and that there
is no incentive for any individual generator to deviate from the
algorithm by using an alternative bid update scheme. We also
establish the algorithm robustness to collusion, i.e., we show that,
as long as each bus with generation has a generator following
the strategy, there is no incentive for any group of generators to
share information with the intent of tricking the system to obtain
a higher payoff. Simulations illustrate our results.

I. I NTRODUCTION
As part of the plan to integrate distributed energy resources
(DERs) into the electricity grid, regulating authorities envision
a hierarchical architecture where, at the lower layer, different
sets of DERs coordinate their response under an aggregator
and, at the upper layer, the independent system operator (ISO)
interacts with the aggregators to solve the optimal power
flow (OPF) problem. In this scenario, aggregators function as
(virtual, large-capacity) generators, and the aggregation would
allow DERs to participate into markets in which, individually,
they do not have the capacity to do so. While the DERs
under one aggregator can cooperate among themselves, the
aggregators compete with each other in the electricity market.
In this paper, we focus on the competition aspect of this vision:
we study policies that individual generators, in conjunction
with the ISO, can implement to solve the OPF problem while
acting in a selfish and rational fashion.
Literature review: The study of competition in electricity
markets is a classical topic [3], [4]. Extensively studied models
are supply function, Bertrand (price) and Cournot (capacity)
Preliminary versions appeared in conference proceedings as [1] and [2].
Ashish Cherukuri and Jorge Cortés are with the Department of Mechanical and Aerospace Engineering, University of California, San Diego,
{acheruku,cortes}@ucsd.edu.

Jorge Cortés

bidding, see [5], [6], [7], respectively, and references therein.
These studies analyze the properties of the game that different
bidding models result into by determining the existence of the
Nash equilibrium of the game and estimating its efficiency.
Some works [8], [9], [10], [11], on the other hand, propose
iterative algorithms for the players that compute the Nash
equilibrium of the game. However, these algorithms either
require generators to have some information about other
generators (cost functions or bids) or assume that the demand
of each generator is a continuous function of the bids. Our
work does not make any such assumptions, which also rules
out the possibility of using various other Nash equilibrium
learning algorithms, such as best-response [12], fictitious
play [13], and extremum seeking [14], [15]. In a related
set of works [16], [17], decentralized generation planning is
achieved by assuming the generators to be price-takers and
designing iterative schemes based on dual-decomposition [18].
In our work, however, we consider a strategic scenario where
generators bid into the market and are hence price-setters.
The work [19] proposes an iterative auction algorithm for a
market where both generators and consumers are strategic but
does not provide convergence guarantees for the generated
bid sequences. The paper [20], closer in spirit to our work,
proposes an iterative method for the generators to find the
Nash equilibrium assuming they do not have any information
about each other. At each iteration, the generators send to the
ISO the gradient of their cost functions at a certain generation
value and the ISO then adjusts these generation values so that
social welfare is maximized. An important difference between
this setup and ours is that we do not assume truthful bidding
of gradient information by the generators.
Our electricity market game belongs to the broader class of
multi-leader-single-follower games [21], [22]. The Nash equilibria of such games can be thought of as optimizers of mathematical programs with equilibrium constraints (MPEC) [23],
that are traditionally solved in a centralized manner [24]. The
work [25] provides a distributed method to find the equilibria
of an MPEC problem but requires the follower’s (the ISO
in our case) optimization to have a unique solution for each
action of the leaders (the generators). This is in general not the
case for electricity markets. Our work broadly relates to the
recent developments in the area of “learning in games”, see
e.g., [26], [27], and references therein. Learning mechanisms
proposed in there do not apply directly to the electricity
market setting as they do not consider network constraints for
allocation of goods. Finally, our work has close connections
with the growing interest in the design of provably correct
distributed algorithms for the cooperative solution of economic
dispatch, see [28], [29], and references therein.

2

Statement of contributions: The background for the inelastic
electricity market game considered here is that the ISO seeks
to find the production levels that solve the DC optimal power
flow (DC-OPF) problem for a group of strategic generators
which do not share their cost functions. Consequently, the
ISO cannot solve the DC-OPF problem by itself. However,
each generator submits a bid to the ISO specifying the
price per unit of electricity at which the generator is willing
to provide power. Given these bids, the ISO decides how
much production to allocate to each generator so that the
cost of generation is minimized, the loads are met, and the
network flow constraints are satisfied. The resulting Bertrand
competition model defines the game among the generators,
where the actions are the bids and the payoffs are the profits.
We define the concept of the efficient Nash equilibrium, that
is, the Nash equilibrium at which the generators are willing
to produce the amount that corresponds to the optimizer of
the DC-OPF problem. Our first contribution gives two set of
conditions that ensure existence and uniqueness, respectively,
of an efficient Nash equilibrium for the inelastic electricity
market game. Our second contribution is the design of the
B ID A DJUSTMENT A LGORITHM along with its correctness
analysis. This algorithm can be understood as “learning via
repeated play”, where generators are “myopically selfish”,
changing their bid at each iteration with the aim of maximizing
their own payoff. Along the execution, the only information
available to the generators is their bid and the amount of
generation that the ISO request from them. In particular,
generators are not aware of the number of other generators,
their costs, bids, or payoffs. We show that this decentralized iterative scheme is guaranteed to take the bids of the
generators to any neighborhood of the unique efficient Nash
equilibrium provided the stepsizes are chosen appropriately.
Further, we establish that the convergence rate is linear. Our
third contribution analyzes the robustness properties of the
B ID A DJUSTMENT A LGORITHM. Specifically, we establish
that the convergence is not affected by affine disturbances,
thus showing that deviations in stepsizes by the generators
can be handled gracefully. Additionally, we show that there is
no incentive for any individual generator to deviate from the
algorithm by using an alternative bid update scheme. Finally,
we also show that, if at each generator bus there is at least
one generator running the B ID A DJUSTMENT A LGORITHM,
then there is no incentive for other generators connected to
the network to not follow the algorithm, i.e., this adjustment
scheme becomes a rational choice for all generators. These
properties provide a sound justification for why the group
generators would adopt this iterative bid adjustment scheme to
solve the DC-OPF problem. Simulations illustrate our results.
Notation: Let R, R≥0 , Z≥0 , Z≥1 be the set of real, nonnegative real, nonnegative integer, and positive integer numbers,
respectively. We use the shorthand notation [n] to denote the
set {1, . . . , n}. The 2-norm on Rn is represented by k · k. Let
Bδ (x) = {y ∈ Rn | ky − xk < δ} be the open ball centered
at x ∈ Rn with radius δ > 0. Given x, y ∈ Rn , xi is the i-th
component of x, and x ≤ y denotes xi ≤ yi for i ∈ [n]. We use
0N = (0, . . . , 0) ∈ RN . We let [u]+ = max{0, u} for u ∈ R.
A directed graph, or simply digraph, is represented by a pair
G = (V, E), where V is the vertex set and E ⊆ V × V is

the edge set. For a digraph, Nv+i = {vj ∈ V | (vi , vj ) ∈ E}
and Nv−i = {vj ∈ V | (vj , vi ) ∈ E} are the sets of out- and
in-neighbors of vi , respectively.
II. P ROBLEM STATEMENT
Consider an electrical power network with Nb ∈ Z≥1 buses.
The physical interconnection between the buses is given by
a digraph G = (V, E), where nodes correspond to buses
and edges to physical power lines. The direction for each
edge represents the convention of positive power flow. The
power flow on the line (i, j) ∈ E is zij ∈ R. Each line
(i, j) ∈ E has a limit on the power flowing through it (in
either direction), represented by z ij > 0. Assume that each
bus i ∈ [Nb ] is connected to ni ∈ Z≥0 strategic generators.
PNb
We let N = i=1
ni be the total number of generators and
assign them a unique identity in [N ]. Let the set of generators
at node i be Gi ⊂ [N ] (this set is empty if there are no
generators connected to bus i). The power demand at bus i is
denoted by yi ≥ 0 and is assumed to be fixed and known to
the Independent System Operator (ISO) that actsP
as the central
Nb
regulating authority. The total demand is y = i=1
yi . The
cost fn (xn ) of generating xn ∈ R≥0 amount of power by the
n-th generator is given by a quadratic function
fn (x) = an x2 + cn x,

(1)

where an > 0 and cn ≥ 0. Given a power
PNallocation x =
(x1 , . . . , xN ) ∈ RN
≥0 , the aggregate cost is
n=1 fn (xn ). The
dc optimal power flow problem (DC-OPF) consists of
minimize
(x,z)

subject to

N
X

fn (xn ),

(2a)

n=1

X

zij −

j∈Ni+

X

zij =

j∈Ni−

X

xn − yi , ∀i,

(2b)

n∈Gi

− z ij ≤ zij ≤ z ij , ∀(i, j),
x ≥ 0N .

(2c)
(2d)

This problem finds the generation profile that meets the load at
each bus (ensured by (2b)), respects the line constraints (due
to (2c)), and minimizes the total cost (given by the objective
function (2a)). In (2b) we make the convention that if Gi = ∅,
then the first term on the right-hand side is zero. We assume
that (2) is feasible. Since the individual costs are quadratic, the
optimizer of the problem, denoted (x∗ , z ∗ ), is unique [30].
The goal for the ISO is to solve (2). The ISO can interact
with the generators, whereas each generator can only communicate with the ISO and is not aware of the number of other
generators participating in the market and their respective cost
functions, or the load at its own bus. While the ISO knows
the loads and the limits on the power lines, it does not have
any information about the cost functions of the generators.
Therefore, power allocation is decided following a bidding
process, resulting into a game-theoretic formulation. Instead
of sharing their cost with the ISO, the generators bid the price
per unit of power that they are willing to provide the power
at. This price-based bidding is well known in the economics
literature as Bertrand competition [31, Chapter 12]. Specifically, generator n bids the cost per unit power bn ∈ R≥0 and,

3

when convenient, we denote the bids of all other generators
except n by b−n = (b1 , . . . , bn−1 , bn+1 , . . . , bN ). Given the
bids b = (b1 , . . . , bN ) ∈ RN
≥0 , the ISO solves the following
strategic dc optimal power flow problem (S-DC-OPF)
minimize
(x,z)

N
X

bn x n ,

(3a)

n=1

subject to

X
j∈Ni+

zij −

X

zij =

j∈Ni−

X

xn − yi , ∀i, (3b)

n∈Gi

− z ij ≤ zij ≤ z ij , ∀(i, j),
x ≥ 0N .

(3c)
(3d)

The difference between (3) and (2) is the objective function
which is linear in the former and nonlinear, convex in the
latter. The ISO solves (3) once all the bids are gathered.
Let (xopt (b), z opt (b)) be the optimizer of (3) that the ISO
selects (note that there might not be a unique optimizer)
given bids b. This determines the power requested from each
generator, given by the vector xopt (b). Knowing this process,
the objective of each generator n is to bid a quantity bn ≥ 0
that maximizes its payoff un : R2≥0 → R,
opt
opt
un (bn , xopt
n (b)) = bn xn (b) − fn (xn (b)),

(4)

opt
(b).
where xopt
n (b) is the n-th component of the optimizer x

Definition II.1. (Inelastic electricity market game): The inelastic electricity market game is defined by the following

Definition II.2. (Nash equilibrium): The (pure) Nash equilibrium of the inelastic electricity market game is the bid profile
of the group b∗ ∈ RN
≥0 for which there exists an optimizer
(xopt (b∗ ), z opt (b∗ )) of the optimization (3) that satisfies
(5)

for all n ∈ [N ], all bids bn ∈ R≥0 , and all optimizers
(xopt (bn , b∗−n ), z opt (bn , b−n )) of (3) given bids (bn , b∗−n ).
We are specifically interested in bid profiles for which the
optimizer of the DC-OPF problem is also a solution to the SDC-OPF problem. This is captured in the following definition.
Definition II.3. (Efficient bid): An efficient bid of the inelastic
electricity market is a bid b∗ ∈ RN
≥0 for which the optimizer
(x∗ , z ∗ ) of (2) is also an optimizer of (3) given bids b∗ and
for all n ∈ [N ].

III. E XISTENCE AND UNIQUENESS OF EFFICIENT NASH
EQUILIBRIUM

Here, we establish the existence of an efficient Nash equilibrium of the inelastic electricity market game described in
Section II and provide a condition for its uniqueness.
Proposition III.1. (Existence of efficient Nash equilibrium):
Assume that at each bus of the network either there is more
than one generator or there is none, i.e., either ni = 0 or
ni ≥ 2 for each i ∈ [Nb ]. Then, there exists an efficient Nash
equilibrium of the inelastic electricity market game.
Proof: For convenience, we write (2b) and (2c) as
and

J3 z ≤ z c ,

Nb ×Nb

Wherever convenient, for any n ∈ [N ], we use interchangeably the notation b and (bn , b−n ), as well as, xopt (b) and
xopt (bn , b−n ). Note that the payoff of the players is not only
defined by the bids of other players but also by the optimizer
of (3) that the ISO selects. For this reason, the definition of
the pure Nash equilibrium for the game described below is
slightly different from the standard one, see e.g. [32].

x∗n = argmaxx≥0 b∗n x − fn (x),

At the efficient Nash equilibrium, the production that the
generators are willing to provide, maximizing their profit,
coincides with the optimal generation for the DC-OPF problem (2). This property justifies the study of efficient Nash
equilibria. Note that given the efficient bid profile, there might
be many solutions to (3) because the problem is linear. Thus,
the ISO might not be able to find x∗ given the efficient
bid. However, once the ISO knows that an efficient Nash
equilibrium bid is submitted, it can ask the generators to also
submit the desirable generation levels at that bid, which would
exactly correspond to the solution of the DC-OPF problem.

J1 z − J2 x + y = 0

(i) Players: the set of generators [N ],
(ii) Action: for each player n, the bid bn ∈ R≥0 ,
(iii) Payoff: for each player n, the payoff un in (4).

∗
∗
opt ∗
un (bn , xopt
n (bn , b−n )) ≤ un (bn , xn (b )),

efficient Nash equilibrium of the inelastic electricity market
game if it is an efficient bid and is a Nash equilibrium.

(6)

The right-hand side of (6) is unique as costs are quadratic.
Definition II.4. (Efficient Nash equilibrium): A bid b∗ is an

respectively. Here, J1 ∈ {0, 1, −1}
defines the interconnection of buses in the digraph G, specifically, (i, j)-th element
of J1 is 1 if (i, j) ∈ E, is −1 if (j, i) ∈ E, and 0 otherwise. The
matrix J2 ∈ {0, 1}Nb ×N defines the connectivity of generators
to buses, that is, (i, j)-th element of J2 is 1 if and only if j-th
generator is connected to i-th bus. Lastly,
 


I|E|
z
.
J3 =
and z c =
z
−I|E|
The Lagrangian of the optimization (2) is
PN
L(x, z, ν, µ, λ) = n=1 fn (xn ) + ν > (J1 z − J2 x + y)
+ µ> (J3 z − z c ) − λ> x,
2|E|

where ν ∈ RNb , µ ∈ R≥0 , and λ ∈ RN
≥0 are Lagrange
multipliers corresponding to constraints (2b), (2c), and (2d),
respectively. Since constraints (2b)-(2c) are affine and the
feasibility set is nonempty, the refined Slater condition is
satisfied for (2) and hence, the duality gap between the primal
and the dual optimization problems is zero [30]. Under this
condition, a primal-dual optimizer (x∗ , z ∗ , ν ∗ , µ∗ , λ∗ ) satisfies
the following Karush-Kuhn-Tucker (KKT) conditions
∇f (x∗ ) − J2> ν ∗ − λ∗ = 0,
J1> ν ∗
∗

J3> µ∗
∗

−
J1 z − J2 x + y
J3 z ∗ ≤ z c , x∗
λ∗ ≥ 0, µ∗

(7a)

= 0,
= 0,
≥ 0,
≥ 0,

(7b)
(7c)
(7d)
(7e)

(x∗ )> λ∗ = 0, and (µ∗ )> (J3 z ∗ − z c ) = 0,

(7f)

4

where ∇f (x∗ ) = (∇f1 (x∗1 ), ∇f2 (x∗2 ), . . . , ∇fN (x∗N ))> . In
the rest of the proof, we show that the following bid profile,
constructed from a primal-dual optimizer, is an efficient Nash
equilibrium of the inelastic electricity market game
(
∗
νi(n)
,
if min{x∗m | m ∈ Gi(n) } > 0,
∗
(8)
bn =
∇fn (0),
otherwise,
where i(n) ∈ [Nb ] denotes the bus of the network to which
generator n is connected to. Given the form (1) of the cost
functions, we deduce b∗ ≥ 0. Moreover, from the definition
of J2 , one can deduce that either all generators n ∈ Gi have
b∗n = νi or all of them have x∗n = 0. Next, to show that the
bid b∗ defined in (8) is efficient, we first establish
x∗n

=

argmaxx≥0 b∗n x

− fn (x),

(9)

for all n ∈ [N ]. For each n, consider the optimization
maxx≥0 b∗n x − fn (x). Because zero duality holds for this
optimization, a point xo ∈ R≥0 is an optimizer if and only if
it satisfies the KKT conditions
b∗n − ∇fn (xo ) − µo = 0,
µo ≥ 0, xo ≥ 0, µo xo = 0,
where µo is the dual optimizer. Since x∗n satisfies the above
conditions with µo = λ∗n , the expression (9) holds. To claim
the efficiency of b∗ , we next show that (x∗ , z ∗ ) is one of the
optimizers of (3) given bids b∗ . Note that the KKT conditions
for (3) are given by (7) with the term ∇f (x∗ ) in (7a) replaced
with b∗ . Also, one can show using the KKT conditions (7) and
the definition of b∗ that b∗ − J2> ν ∗ ≥ 0. Using these facts,
we deduce that (x∗ , z ∗ , ν ∗ , µ∗ , b∗ − J2> ν ∗ ) satisfies the KKT
conditions for (3) and hence, (x∗ , z ∗ ) is an optimizer of (3).
Our final step is to show the Nash equilibrium condition (5)
for the bid profile b∗ . Note that for each n, the payoff at the bid
profile-optimizer pair (b∗ , xopt (b∗ )) = (b∗ , x∗ ) is nonnegative.
∗
∗
Specifically, if x∗n = 0, then un (b∗n , xopt
n (b )) = 0. If xn > 0,
∗
∗
using the fact that ∇fn (x) ≤ bn for all x ∈ [0, xn ], we get
∗
∗ ∗
∗
un (b∗n , xopt
n (b )) = bn xn − fn (xn )
Z x∗n
=
∇(b∗n x − fn (x))dx
0
Z x∗n
(b∗n − ∇fn (x))dx ≥ 0.
=
0

Now pick any generator n ∈ [N ]. For bid bn 6= b∗n we have two
cases, first, bn > b∗n and second, bn ≤ b∗n . For the first case,
either (i) x∗n = 0 which implies that xopt (bn , b∗−n ) = 0 and so
∗
∗
∗
∗
un (bn , xopt
n (bn , b−n )) = un (bn , xn ) = 0; or (ii) xn > 0, so all
bids at bus i(n) are equal, implying that n increasing its bid
∗
opt
∗
yields xopt
n (bn , b−n ) = 0. That is, un (bn , xn (bn , b−n )) =
∗
∗
0 ≤ un (bn , xn ). For the second case,
∗
opt
∗
opt
∗
un (bn , xopt
n (bn , b−n )) = bn xn (bn , b−n ) − fn (xn (bn , b−n ))
∗
opt
∗
≤ b∗n xopt
n (bn , b−n ) − fn (xn (bn , b−n ))
≤ b∗n x∗n − fn (x∗n ) = un (b∗n , x∗n ),

where in the first inequality we use bn ≤ b∗n and in the second
we use (9). This shows (5), concluding the proof.
Note that the condition in Proposition III.1 of having zero or

at least two generators at each bus is reasonable. If this is not
the case, i.e., there is a bus with a single generator, and the line
capacities are such that the load at that bus can only be met by
that generator, then there is possibility of market manipulation.
The generator at the bus can set its bid arbitrarily high as
no other generator can meet that load and consequently, there
does not exist a Nash equilibrium. Next we provide a sufficient
condition that ensures uniqueness of the efficient bid.
Lemma III.2. (Uniqueness of the efficient bid): Assume that
the optimizer x∗ of (2) satisfies x∗n > 0 for all n ∈ [N ]. Then,
there exists a unique efficient bid b∗ ∈ RN
≥0 of the inelastic
electricity market game given by
b∗n = ∇fn (x∗n ) = 2an x∗n + cn ,

for all n

(10)

Proof: By definition, an efficient bid b ∈ RN
≥0 satisfies
x∗n = argmaxx≥0 bn x − fn (x)
for all n. Since x∗n > 0, first-order optimality condition of
the above optimization yields bn = ∇fn (x∗n ). This establishes (10) and hence, the uniqueness.
From Proposition III.1 and Lemma III.2, we conclude the
following result.
Corollary III.3. (Uniqueness of the efficient Nash equilibrium): Assume that at each bus of the network either there
is more than one generator or there is none. Further assume
that the optimizer x∗ of (2) satisfies x∗n > 0 for all n ∈ [N ].
Then, there exists a unique efficient Nash equilibrium of the
inelastic electricity market game given by (10) for all n.
In the rest of the paper, we assume that the sufficient
conditions in Corollary III.3 hold unless otherwise stated. Note
that the definition of the unique efficient Nash equilibrium
given in (10) is consistent with the one provided in (8). This
is so because if x∗n > 0 for all n, then ∇fñ (x∗ñ ) = νi∗ for
each bus i ∈ [Nb ] and every generator ñ ∈ Gi .
IV. T HE B ID A DJUSTMENT A LGORITHM AND ITS
CONVERGENCE PROPERTIES

In this section, we introduce a decentralized Nash equilibrium seeking algorithm, termed B ID A DJUSTMENT A LGO RITHM . We show that its executions lead the generators to
the unique efficient Nash equilibrium, and consequently, to
the optimizer of the DC-OPF problem (2).
A. B ID A DJUSTMENT A LGORITHM
We start with an informal description of the B ID A DJUSTMENT A LGORITHM . The algorithm is iterative and can be
interpreted as “learning via repeated play” of the inelastic
electricity market game by the generators. Both ISO and
generators have bounded rationality, with each generator trying
to maximize its own profit and the ISO trying to maximize the
welfare of the entities.
[Informal description]: At each iteration k, generators decide on a bid and send it to the ISO.
Once the ISO has obtained the bids, it computes an
optimizer of the S-DC-OPF problem (3), denoted
(xopt (k), z opt (k)) for convenience, and sends the

5

corresponding production level at the optimizer to
each generator. At the (k+1)-th iteration, generators
adjust their bid based on their previous bid, the
amount of produced power that maximizes their
payoff for the previous bid, and the allocation of
generation assigned by the ISO. The iterative process
starts with the generators arbitrarily selecting initial
bids that yield a positive profit.
The B ID A DJUSTMENT A LGORITHM is formally presented
in Algorithm 1.

of other players, their actions, or their payoffs. The only
information they have at each iteration is their own bid
and the generation that the ISO requests from them. This
information structure rules out the applicability of a number
of Nash equilibrium learning methods, including best-response
dynamics [12], fictitious play [13], or other gradient-based
adjustments [10], all requiring some kind of information about
other players. Methods that relax this requirement, such as
extremum seeking used in [14], [15], rely on the payoff
functions being continuous in the actions of the players, which
is not the case for the inelastic electricity market game.
•

Algorithm 1: B ID A DJUSTMENT A LGORITHM
Executed by: generators n ∈ [N ] and ISO
Data
: cost fn and stepsizes {βk }k∈Z≥1 for each
generator n, and load y for ISO
Initialize : Each generator n selects arbitrarily
bn (1) ≥ cn , sets k = 1, and jumps to step 4;
ISO sets k = 1 and waits for step 6

Remark IV.2. (Stopping criteria and justification of “myopically selfish” strategies): Algorithm 1 consists of an infinite
number of iterations. To make it implementable, later we identify stopping criteria, see Remark IV.9, based on a parameter
that the ISO selects. Since this is not known to the generators,
they cannot predict when the algorithm will terminate and,
hence, they do not have an incentive to play strategically to
maximize their payoff in the long term. Given this, they should
focus on maximizing the payoff in the next iteration, which
justifies the myopically selfish perspective adopted here.
•

1

2
3
4
5

6
7
8
9

while k > 0 do
/* For each generator n:
*/
Receive xopt
n (k − 1) from ISO
+
Set bn (k) = [bn (k−1)+βk (xopt
n (k−1) − qn (k−1))]
Set qn (k) = argmaxq≥0 bn (k)q − fn (q)
Send bn (k) to the ISO; set k = k + 1
/* For ISO:
*/
Receive bn (k) from each n ∈ [N ]
Find a solution (xopt (k), z opt (k)) to (3) given b(k)
Send xopt
n (k) to each n ∈ [N ]; set k = k + 1
end

In the B ID A DJUSTMENT A LGORITHM, the role of the ISO
is to compute an optimizer of the S-DC-OPF problem after
the bids are submitted. Generators adjust their bids at each
iteration in a “myopically selfish” and rational fashion, with
the sole aim of maximizing their payoff. Intuitively,
if n gets xopt
n (k) = 0, two things can happen: (i) n was willing to produce a positive quantity qn (k) > 0 at bid bn (k)
but the demand from the ISO is xopt
n (k) = 0. Thus, the
rational choice for n is to decrease the bid in the next
iteration and increase its chances of getting a positive
payoff; (ii) n was willing to produce nothing qn (k) = 0
at bn (k) and got xopt
n (k) = 0. At this point, reducing the
bid will not increase the payoff as it will not be willing
to produce more at a lower bid. Alternatively, increasing
the bid will not make the amount that the ISO wants the
generator to produce positive. Hence, the bid stays put.
if n gets xopt
n (k) > 0, then it would want to move the bid
in the direction that makes its payoff higher in the next
iteration, assuming that n gets a positive generation signal
from the ISO in the next round. If qn (k) < xopt
n (k), then
the demand from the ISO is more than what the generator
is willing to produce, so n increases its cost, i.e., the bid.
If qn (k) > xopt
n (k), then the demand is less than what
the generator is willing to supply so n decreases its bid.
Remark IV.1. (Information structure and other learning approaches): Generators have no knowledge of the number

B. Convergence analysis
In this section, we show that the generator bids along any
execution of the B ID A DJUSTMENT A LGORITHM converge
to a neighborhood of the unique efficient Nash equilibrium.
The size of the neighborhood is a decreasing function of the
stepsize and can be made arbitrarily small.
We first present a series of results that highlight certain
geometric properties of the bid update done in Step 3 of
Algorithm 1. These results form the basis for establishing later
the convergence guarantee. The following result states that one
could neglect the projection operator in Step 3 of Algorithm 1.
Lemma IV.3. (Generator bids are lower bounded): In Algorithm 1, let 0 < βk < 2an for all n ∈ [N ] and k ∈ Z≥1 .
Then, bn (k) ≥ cn and for all n ∈ [N ] and k ∈ Z≥1 ,
qn (k) =

bn (k) − cn
.
2an

(11)

Proof: Equation (11) follows directly from bn (k) ≥ cn ,
so we focus on proving the latter. We proceed by induction.
Note that bn (1) ≥ cn for all n ∈ [N ]. Assume that bn (k) ≥ cn
for some k ∈ Z≥1 and let us show bn (k + 1) ≥ cn . We have
+
bn (k + 1) = [bn (k) + βk (xopt
n (k) − qn (k))]
h
 b (k) − c i+
(a)
(b)
n
n
≥ [bn (k)−βk qn (k)]+ = bn (k)−βk
2an
h
βk 
cn i+
= 1−
bn (k) + βk
2an
2an

βk 
cn
(c)
= 1−
bn (k) + βk
,
2an
2an

where (a) is due to the fact that xopt
n (k) ≥ 0, (b) follows
from the definition of qn (k) given the fact that bn (k) ≥ cn ,
and (c) follows from the assumption that βk < 2an for all

6

n (which makes both terms in the expression positive). By
contradiction, assume bn (k + 1) < cn . Then,

βk 
cn
1−
bn (k) + βk
< cn ,
2an
2an
which implies that bn (k) < cn , a contradiction.
Our next result gives a different expression for the bid
update step (cf. Step 3) presenting a geometric perspective of
the direction along which the bids are moving. Specifically, we
write the k + 1-th bid as the addition of two vectors. The first
one is a convex combination of the k-th bid and the efficient
Nash equilibrium b∗ . Hence, the first vector is closer to b∗
as compared to the k-th bid. The second one depends on the
difference between what the ISO requests from the generators
and the optimizer of (2). If the second term is small enough,
then we are assured that the bids move towards b∗ .
Lemma IV.4. (Geometric characterization of the bid update):
In Algorithm 1, let 0 < βk < 2an for all n ∈ [N ] and k ∈
Z≥1 . Then, we have
b(k + 1) = bcoc (k + 1) + βk (xopt (k) − x∗ ),
for all k ∈ Z≥1 , where for each n ∈ [N ],

βk 
βk ∗
bcoc
(k
+
1)
=
1
−
bn (k) +
b .
n
2an
2an n

= βk hxopt (k) − x∗ , b∗ − b(k)i +
(a)

≥

PN

βk
∗
n=1 2an (bn

− bn (k))2 ≥

bn (k + 1) = bn (k) + βk (xopt
n (k) − qn (k))
 b (k) − c 
(a)
n
n
= bn (k) + βk (xopt
n (k)) − βk
2an


βk 
cn 
= 1−
bn (k) + βk xopt
n (k) +
2an
2an

βk 
opt
= 1−
bn (k) + βk (xn (k) − x∗n )
2an 
cn 
+ βk x∗n +
2an

βk 
βk ∗
(b)
∗
= 1−
bn (k) +
b + βk (xopt
n (k) − xn ).
2an
2an n
In the above expression, we have used (11) in the equality (a)
and (10) in the equality (b).
The next result gives a lower bound on the inner product
between the direction in which the bids move and the direction
towards the efficient Nash equilibrium.

βk
2amax kb(k)

− b∗ k2 .

For the inequality (a), we have used the fact that

hxopt (k) − x∗ , b∗ −b(k)i = hxopt (k), b∗ i − hx∗ , b∗ i

+ hx∗ , b(k)i − hxopt (k), b(k)i ≥ 0.
The last inequality follows from the fact that x∗ and xopt (k)
are the optimizers of (3) given b∗ and b(k), resp., making both
expressions on the right-hand side nonnegative.
The next result states that the distance between consecutive
bids decreases as the bids get closer to b∗ . In combination with
Lemma IV.5, one can see intuitively that the bids get closer to
b∗ and, as they get closer to it, the bid update step behaves as
if the bids are reaching an equilibrium of the update scheme.
These two facts lead to convergence.
Lemma IV.6. (Distance between consecutive bids is upper
bounded): In Algorithm 1, let 0 < βk < 2an for all n ∈ [N ]
and k ∈ Z≥1 . Let amin = minn {an }. Then, for all k ∈ Z≥1 ,
kb(k + 1) − b(k)k2 ≤

Proof: In the proof of Lemma IV.3, we have shown that
for all n and k, the term inside the projection operator [·]+ in
Step 3 of Algorithm 1 is nonnegative. Hence, the projection
can be dropped and we can write

N
X
βk ∗
(bn − bn (k))2
2a
n
n=1

βk2
kb(k) − b∗ k2 + 8βk2 y 2 .
2a2min

(13)

Proof: Consider the following
kb(k + 1) − b(k)k2
N 
2
(a) X βk
∗
(b∗n − bn (k)) + βk (xopt
(k)
−
x
)
=
n
n
2an
n=1
N
(b) X

≤

(c)

≤

2

N
β
2 X
k
∗ 2
2βk2 (xopt
(b∗n − bn (k)) +
n (k) − xn )
2an
n=1

n=1
βk2
kb(k)
2a2min

− b∗ k2 + 2βk2 kxopt (k) − x∗ k2 .

(14)

In the above expression, (a) follows from the expression of
bn (k + 1) from Lemma IV.4, (b) follows from the inequality
(x + y)2 ≤ 2(x2 + y 2 ) for x, y ∈ R, and (c) follows from the
definition of amin . Note that
kxopt (k) − x∗ k ≤

N
X

∗
xopt
n (k) − xn ≤

n=1

=

N
X

∗
xopt
n (k) + |xn |

n=1
opt
n=1 (xn (k)

PN

+ x∗n ) = 2y.

The proof concludes by using the above bound in (14).
We are ready to present the main convergence result.

Lemma IV.5. (Bids move in the direction of the efficient Nash
equilibrium): In Algorithm 1, let 0 < βk < 2an for all n ∈ [N ]
and k ∈ Z≥1 . Let amax = maxn {an }. Then, for all k ∈ Z≥1 ,
hb(k + 1) − b(k), b∗ − b(k)i ≥

βk
kb(k) − b∗ k2 .
2amax

Proof: Using Lemma IV.4, we write
hb(k + 1) − b(k), b∗ − b(k)i
= hb(k + 1) − bcoc (k + 1), b∗ − b(k)i
+ hbcoc (k + 1) − b(k), b∗ − b(k)i

(12)

Theorem IV.7. (Convergence of the B ID A DJUSTMENT A L GORITHM ): In Algorithm 1, let 0 < βk < 2an for all n ∈ [N ]
and k ∈ Z≥1 . Further, let 0 < r < kb(1) − b∗ k and for all
k ∈ Z≥1 assume
1  1
16y 2 −1
α ≤ βk ≤ B(r) :=
+ 2
,
(15)
2
2amax 2amin
r
for some α > 0. Then, the following holds
(i) there exists l ∈ Z≥1 such that kb(l) − b∗ k < r and for

7

all k ∈ [l − 1], we have kb(k) − b∗ k ≥ r with

α k/2
kb(k + 1) − b∗ k ≤ 1 −
kb(1) − b∗ k, (16)
2amax
(ii) for all k ≥ l,

B(r) 1/2
r.
kb(k) − b∗ k ≤ 1 +
2amax

(17)

Proof: Assume that kb(k) − b∗ k ≥ r for some k ∈ Z≥1 .
Then, the upper bound on the stepsizes in the inequality (15)
holds when r is replaced with kb(k) − b∗ k, that is, βk ≤
B(kb(k) − b∗ k) for all k ∈ Z≥1 . This is because r 7→ B(r) is
strictly increasing in the domain r > 0. Proceeding with this
replacement and reordering (15), we obtain
 kb(k) − b∗ k2

1
2
βk
≤
+
16y
kb(k) − b∗ k2 ,
2
2amin
2amax
or equivalently,
1
βk
kb(k) − b∗ k2 + 16βk y 2 −
kb(k) − b∗ k2
2a2min
amax
1
kb(k) − b∗ k2 .
≤−
2amax
Now consider the following inequalities

(18)

kb(k + 1) − b∗ k2 = kb(k + 1) − b(k) + b(k) − b∗ k2
= kb(k + 1) − b(k)k2 + kb(k) − b∗ k2
+ 2hb(k + 1) − b(k), b(k) − b∗ i
βk2
kb(k) − b∗ k2 + 8βk2 y 2 + kb(k) − b∗ k2
2a2min
βk
−
kb(k) − b∗ k2
(19a)
amax
(b) 
βk 
≤ 1−
kb(k) − b∗ k2 ,
(19b)
2amax
where in (a) we have used the bounds (12) and (13) from
Lemmas IV.5 and IV.6, respectively, and the inequality (b)
is implied by that in (18). Note that the inequality (18) is
conservative in the sense that the term 16βk y 2 could be replaced with 8βk y 2 and the inequality (19b) would still follow.
However, we opt for this conservativeness while defining the
map r 7→ B(r) in (15) because it results into robustness
guarantees for the algorithm as discussed in the forthcoming
∗
section. Therefore, (19b) holds
whenever

 kb(k) − b k ≥ r. By
βk
assumption, we have 0 < 1 − 2amax < 1, kb(1) − b∗ k > r,
and βk ≥ α for all k ∈ Z≥1 . Using these facts and
applying (19b) recursively, we conclude part (i).
(a)

≤

For part (ii), note that if kb(k) − b∗ k ≥ r for some k ≥ l,
then kb(k + 1) − b∗ k < kb(k) − b∗ k by (19b). Therefore, to
find an upper bound on kb(k) − b∗ k for all k ≥ l, we only
need to consider the case when kb(k) − b∗ k < r. Plugging this
bound in (19a) and neglecting the negative term, we get
kb(k + 1) − b∗ k2 ≤

βk2 r2
2a2min

+ 8βk2 y 2 + r2 .

From (15), we have
βk2 r2
βk r 2
2 2
+
16β
y
≤
.
k
2a2min
2amax

(20)

The result now follows by upper bounding the right-hand side
of (20) with the left-hand side of the above expression and
then employing the bound on the stepsizes give in (15).
Remark IV.8. (Convergence properties from Theorem IV.7):
The assertion (i) of Theorem IV.7 implies that for any choice
of r > 0, one can select stepsizes according to (15) so that
bids reach the set Br (b∗ ) in a finite number of steps and at
a linear rate. Further, once bids reach the set Br (b∗ ), we are
assured from assertion (ii) that they remain in a neighborhood
of b∗ , where the size of the neighborhood is proportional to r
(cf. (17)). In combination, the above facts mean that bids converge to any neighborhood of the efficient Nash equilibrium at
a linear rate provided the stepsizes are selected appropriately.
Note that as r becomes small, B(r) gets small and so does α.
Thus, from (16), the rate of convergence decreases as r
becomes small. This presents a trade-off between the desired
precision and the rate of convergence.
•
Remark IV.9. (Stopping criteria for the ISO): From the proof
of Theorem IV.7(i) note that, as long as kb(k) − b∗ k > r, the
distance to the efficient Nash equilibrium decreases. Therefore,
if kb(k) − b∗ k > r and k < l, then one can write
kb(k + 1) − b(k)k = kb(k + 1) − b∗ + b∗ − b(k)k
≥ kb(k) − b∗ k − kb(k + 1) − b∗ k

(a)
α 1/2
≥ kb(k) − b∗ k − 1 −
kb(k) − b∗ k
2amax


α 1/2 
= 1− 1−
kb(k) − b∗ k,
(21)
2amax
where in (a) we have used (19b) and βk ≥ α. Given this
observation, if the ISO has an estimate of α and amax , then it
can design a stopping criteria based on the distance between
consecutive bids. In fact, if the ISO decides selects  > 0 and
stops the iteration whenever kb(k + 1) − b(k)k ≤ , then it has
the guarantee that either of the following is satisfied
(i) the condition kb(k) − b∗ k > r and k < l is met and
from (21) we get


α 1/2 −1
;
(22)
kb(k) − b∗ k ≤  1 − 1 −
2amax
(ii) kb(k) − b∗ k ≤ r; or
(iii) k > l in which case from (17) we get

B(r) 1/2
kb(k) − b∗ k ≤ 1 +
r.
2amax
The ISO does not know the value of r; its value depends on the
stepsizes that the generators select. Assuming that stepsizes are
small, the ISO can adjust  depending on the desired accuracy
level to get the guarantee (22) for the k-th bid. For small , the
stopping criteria might never be met if stepsizes are too big.•
V. ROBUSTNESS OF THE B ID A DJUSTMENT A LGORITHM
Here we study the robustness properties of the B ID A DJUSTMENT A LGORITHM in a variety of scenarios. We first show
that the introduction of disturbances in the bid update mechanism does not destroy the algorithm convergence properties.
We then study robustness against either an individual agent or
colluding agents changing their strategy to get a higher payoff.

8

A. Robustness to disturbances
Here we establish the robustness properties of the B ID
A DJUSTMENT A LGORITHM in the presence of disturbances by
characterizing its input-to-state stability (ISS) properties [33].
Let d : Z≥1 → RN model the disturbance to the bid update
mechanism. Such disturbances might arise from agents using
different stepsizes than the prescribed one or other disruption
to the prescribed bid update scheme. The resulting perturbed
version of the B ID A DJUSTMENT A LGORITHM can be written
as the following discrete-time dynamical system
b(k + 1) = [b(k) + βk (xopt (k) − q(k)) + d(k)]+ , (23a)
xopt (k + 1) ∈ Solsopf (b(k + 1)),
(23b)
q(k + 1) = Soleff (b(k + 1)),
(23c)
N
N
N
where Solsopf : RN
≥0 ⇒ R≥0 and Soleff : R≥0 → R≥0 map
a bid profile to the set of optimizers of problem (3) and (6),
respectively. Note that Solsopf is a set-valued map since (3) is
a linear program. If d ≡ 0, then the dynamics (23) represents
the k-th iteration of the B ID A DJUSTMENT A LGORITHM.
The next result shows that the perturbed version of the
algorithm (23) retains the convergence properties of the unperturbed version provided the magnitude of the disturbance
satisfies an upper bound dependent on the state of the bid.

Proposition V.1. (The B ID A DJUSTMENT A LGORITHM is
robust to perturbations in the bid update): For dynamics (23),
let the hypotheses of Theorem IV.7 hold and assume that
bn (k) ≥ cn for all n ∈ [N ] and k ∈ Z≥1 . Let 0 < θ <
1
α
and assume kd(k)k ≤ θkb(k) − b∗ k for all
6 1 − 2amax
k ∈ Z≥1 . Then, the following holds
(i) there exists l ∈ Z≥1 such that kb(l) − b∗ k < r and, for
all k ∈ [l − 1], we have kb(k) − b∗ k ≥ r with
kb(k + 1) − b∗ k

k/2
α
≤ 1−
+ 2θ + 4θ2
kb(1) − b∗ k, (24)
2amax
(ii) for all k ≥ l,
1/2

B(r)
+ 2θ + 4θ2
r.
kb(k) − b∗ k ≤ 1 +
2amax

(25)

Proof: Since bn (k) ≥ cn , we obtain for dynamics (23),
n
qn (k) = bn (k)−c
, for all n ∈ [N ] and k ∈ Z≥1 . Moreover,
2an
mimicking Lemma IV.4, we rewrite the bid update (23a) as
b(k + 1) = bcoc (k + 1) + βk (xopt (k) − x∗ ) + d(k),

(26)

for all k ∈ Z≥1 . Using (26) and following the steps of
Lemma IV.5 for dynamics (23a) we get,
hb(k + 1) − b(k),b(k) − b∗ i ≤ hd(k), b(k) − b∗ i
βk
kb(k) − b∗ k2 ,
−
2amax

βk2
kb(k) − b∗ k2 + 4βk2 kxopt (k) − x∗ k2 + 4kd(k)k2
2a2min
β2
≤ 2k kb(k) − b∗ k2 + 16βk2 y 2 + 4kd(k)k2
(28)
2amin

≤

(27)

for all n ∈ [N ] and k ∈ Z≥1 . Similarly, from the reasoning
of Lemma IV.6 we obtain
kb(k + 1) − b(k)k2

2
β2
≤ 2k kb(k) − b∗ k2 + 2 kβk (xopt (k) − x∗ ) + d(k))k
2amin

for all k ∈ Z≥1 for dynamics (23a). Employing (27) and (28),
assuming kb(k) − b∗ k ≥ r, and writing the set of inequalities (19) with α ≤ βk , we deduce the following

α 
kb(k + 1) − b∗ k2 ≤ 1 −
kb(k) − b∗ k2 + 4kd(k)k2
2amax
+ 2hd(k), b(k) − b∗ i.
(29)
Finally, using kd(k)k ≤ θkb(k) − b∗ k we get


α
kb(k+1)−b∗ k2 ≤ 1−
+2θ+4θ2 kb(k)−b∗ k2 . (30)
2amax
Iteratively, we obtain (24). The bound (25) can be computed
in a similar way as done in the proof of Theorem IV.7.
Similar to the convergence guarantees of Theorem IV.7, the
above result establishes that the perturbed version of the algorithm (23) converges to a neighborhood of the efficient Nash
equilibrium provided the stepsizes and the disturbance satisfy
appropriate bounds, and that the size of this neighborhood is
tunable as a function of these.
The next result complements Proposition V.1 by giving an
alternative representation of robustness of (23). It establishes
two properties: first, when the disturbance is bounded (not
necessarily satisfying the bound of Proposition V.1), the bids
remain bounded; second, if the disturbance goes to zero, then
the bids satisfy the bound (17) asymptotically. Notice that
both these results do not follow directly from Proposition V.1,
justifying the need for a formal proof.
Proposition V.2. (Bounded disturbance implies bounded bids
for B ID A DJUSTMENT A LGORITHM): For dynamics (23), let
the hypotheses of Theorem IV.7 hold and assume that bn (k) ≥
cn for all n ∈ [N ] and
kd(k)k ≤ dmax for all
 k∈
 Z≥1 . Let
1
α
k ∈ Z≥1 and let θ ∈ 0, 6 1 − 2amax . Then, the following
holds for all k ∈ Z≥1 ,

k/2
α
kb(k) − b∗ k ≤ 1 −
+ 2θ + 4θ2
kb(1) − b∗ k
2amax
+ G(r, θ, dmax ),
(31)
where G(r, θ, dmax ) := max{G1 (r, dmax ), G2 (θ, dmax )} and
1/2
 B(r)r2
G1 (r, dmax ) :=
+ (2dmax + r)2
,
2amax


1
G2 (θ, dmax ) := 2 +
dmax .
θ
As a consequence, as k → ∞, if kd(k)k → 0, then
n

B(r) 1/2 o
max kb(k) − b∗ k, 1 +
r → 0.
(32)
2amax
Proof: We first show that if for some k ∈ Z≥1 , kb(k) −
b∗ k ≤ G(r, θ, dmax ), then kb(l) − b∗ k ≤ G(r, θ, dmax ) for all
l ≥ k. To this end, as a first case, assume that r ≤ kb(k) −
b∗ k ≤ G(r, θ, dmax ). Then, following the steps of the proof of
Proposition V.1, we arrive at (29). If kd(k)k ≤ θkb(k) − b∗ k,
then we get the inequality (30) which implies that kb(k + 1) −
b∗ k ≤ kb(k) − b∗ k ≤ G(r, θ, dmax ). On the other hand, if

9

kd(k)k > θkb(k) − b∗ k, then using this bound in (29), we get

α  kd(k)k2
kb(k + 1) − b∗ k2 < 1 −
+ 4kd(k)k2
2amax
θ2
kd(k)k2
+2
θ
1

4
< 2 + + 4 kd(k)k2 .
θ
θ
Thus, using kd(k)k ≤ dmax , we get kb(k + 1) − b∗ k <
G2 (θ, dmax ) ≤ G(r, θ, dmax ). As a second case, assume
kb(k) − b∗ k < r. Note that r < G(r, θ, dmax ), and so
kb(k)−b∗ k < G(r, θ, dmax ). For this case, using kb(k)−b∗ k <
r and inequalities (27) and (28), we get as in (19a) that
kb(k + 1) − b∗ k2 ≤

βk2 r2
+ 16βk2 y 2 + 4kd(k)k2 + r2
2a2min
+ 2rkd(k)k.

Now applying bounds kd(k)k ≤ dmax and βk ≤ B(r), we
obtain kb(k + 1) − b∗ k ≤ G1 (r, dmax ). Hence, we arrive at the
conclusion that if kb(k) − b∗ k ≤ G(r, θ, dmax ), then kb(l) −
b∗ k ≤ G(r, θ, dmax ) for all l ≥ k.
Consider now the case when for some k ∈ Z≥1 , kb(k) −
b∗ k > G(r, θ, dmax ). By definition of G(r, θ, dmax ), this implies that kb(k) − b∗ k > r and kb(k) − b∗ k > d(k)
θ . Therefore,
from the proof of Proposition V.1, we arrive at (30). Finally,
combining the reasoning of the two cases when kb(k) − b∗ k is
greater than or less than equal to G(r, θ, dmax ), we obtain the
inequality (31). The limit (32) follows from that fact that as
k → ∞, the first term of (31) converges to zero and as dmax

1/2
B(r)
tends to zero, G(r, θ, dmax ) tends to 1 + 2a
r.
max
One can observe from (31) that the limiting behavior of
the bids depend on the magnitude of r and dmax : if r is
designed to be small enough and if dmax is small enough,
or this bound becomes small as the algorithm iterates, then
the bids do converge to a small neighborhood of b∗ .
As an aside, in the theory of ISS for discrete-time dynamical
systems [33], one typically would conclude Proposition V.2
from Proposition V.1. However, the traditional ISS results
require asymptotic convergence of the unperturbed dynamics,
(i.e., dynamics (23) with d ≡ 0) to a point. This is not the
case here and hence, we provide a formal proof.
Remark V.3. ( B ID A DJUSTMENT A LGORITHM is robust to
variation in stepsizes): In practice, given that generators are
competing and do not share information with each other, it is
conceivable that they do not agree on a common stepsize.
Propositions V.1 and V.2 provide a way to quantify the
performance of the algorithm when the stepsizes are different.
Specifically, let βk , k ∈ Z≥1 , denote a common set of stepsizes
for all generators that satisfies the hypotheses of Theorem IV.7
and hence, guarantees the convergence properties outlined
therein. Assume that each generator selects a different stepsize
at each iteration, denoted as βk,n , k ∈ Z≥1 , for generator n.
Then, the bid iteration in Step 3 of the B ID A DJUSTMENT
A LGORITHM can be written as (23) where now
dn (k) = (βk,n − βk )(xopt
n (k) − qn (k))
for all n ∈ [N ] and k ∈ Z≥1 . Now if the variation in stepsizes,

i.e., the quantity βk,n − βk , is bounded above by a particular
function of the distance of the bid-state to the efficient Nash
equilibrium, then the linear convergence and the ultimate
bound is guaranteed following Proposition V.1. On the other
hand, if the variation in stepsizes do not depend on the state but
are bounded then, then the bids still converge asymptotically to
a neighborhood of the efficient Nash equilibrium, as concluded
in Proposition V.2. Note that the assumption of bn (k) ≥ cn
for all n and k holds whenever the stepsizes are positive for
all agents at all times (cf. Lemma IV.3).
•
B. Robustness to deviation in bid update
We illustrate here another aspect of robustness of the B ID
A DJUSTMENT A LGORITHM by establishing that, if all generators follow the bid update scheme, then there is no incentive
for any generator to deviate from it. We next formalize these
notions. Assume that all generators, except ñ ∈ [N ], follow
the B ID A DJUSTMENT A LGORITHM, and that ñ follows an
arbitrary strategy to update its bids. Then, one can write the
B ID A DJUSTMENT A LGORITHM under this deviation as
+
b−ñ (k + 1) = [b−ñ (k) + βk (xopt
−ñ (k) − q−ñ (k))] ,


(k)
k
bñ (k + 1) = Hñ {bñ (t), xopt
ñ (t), qñ (t)}t=1 ,
opt

x

(k + 1) ∈ Solsopf (b(k + 1)),
q(k + 1) ∈ Soleff (b(k + 1)),

(33a)
(33b)
(33c)
(33d)

(k)

∞
where the maps {Hñ : R3k
≥0 → R≥0 }k=1 represent the update
scheme of ñ at iterations 1, 2, . . . Recall that the subscript −ñ
denotes the vector without the component corresponding to the
generator ñ. Note that (33b) implies that at each iteration k,
the generator ñ only knows the bids it made and the quantities
the ISO demanded from it up until iteration k.
We next introduce the notion of “incentive to deviate” from
the B ID A DJUSTMENT A LGORITHM for the generator ñ. A
natural way to quantify incentives for a generator is in terms
of the payoff (4): a generator has an incentive to deviate if
this would bring in a higher payoff, when the ISO stops the
iteration, than not deviating. This is formalized below.

Definition V.4. (Incentive to deviate from B ID A DJUSTMENT
A LGORITHM): Let r > 0 and assume that the stepsizes for any
execution of (33) satisfy the hypotheses of Theorem IV.7. Then,
the generator ñ ∈ [N ] has an incentive to deviate from the
B ID A DJUSTMENT A LGORITHM if there exists an execution
of (33) and l ∈ Z≥1 such that
max
uñ (bñ (k), xopt
ñ (k)) > uñ ,

(34)

for all k ≥ l, where
n

B(r) 
∗
umax
:= max uñ (bñ ,xopt
r
ñ
ñ (b)) kb − b k ≤ 1 +
2a
omax
and xopt (b) ∈ Solsopf (b) . (35)
In the above definition, recall the short-hand notation
xopt (k) for xopt (b(k)). Equation (34) implies that the generator ñ has an incentive to deviate if, after a finite number
of iterations, it is guaranteed a higher payoff than what it
might eventually get if it follows the B ID A DJUSTMENT

10

A LGORITHM. This captures the fact that the generator does
not know when the ISO might stop the bid and hence it would
deviate only when it is guaranteed to get a higher payoff after
a finite number of steps. The next result shows that there is no
incentive to deviate from the B ID A DJUSTMENT A LGORITHM.
Proposition V.5. (Robustness to deviation from B ID A DJUSTMENT A LGORITHM ): For dynamics (33), let the hypotheses
of Theorem IV.7 hold and assume that bn (k) ≥ cn for all
n ∈ [N ] and k ∈ Z≥1 . Also, assume that the ISO selects
a vertex solution xopt (k) ∈ Solsopf (b(k)) at each iteration
k ∈ Z≥1 . Then, no generator has an incentive to deviate from
the B ID A DJUSTMENT A LGORITHM.
Proof: We reason by contradiction. Assume that a generator ñ has an incentive to deviate from the B ID A DJUSTMENT
A LGORITHM. That is, there exists an execution of (33) and
l ∈ Z≥1 such that (34) holds for all k ≥ l. By definition,
umax
> b∗ñ x∗ñ − fñ (x∗ñ ).
ñ

(36)

Now consider the map
R≥0 3 b 7→ gñ (b) := max{bq − fñ (q) | q ≥ 0}.
From (6), we get gñ (b∗ñ ) = b∗ñ x∗ñ − fñ (x∗ñ ). Further, using (1),
one can show that this map is continuous, strictly increasing
in the domain b ≥ cñ , and gñ (b) → ∞ as b → ∞. These facts
along with (36) imply that there exists a unique bmax
> b∗ñ
ñ
max
max
max
such that gñ (bñ ) = uñ , gñ (b) > uñ for all b > bmax
ñ ,
and gñ (b) < umax
for all cñ ≤ b < bmax
ñ
ñ . Then, (34) reads as
max
uñ (bñ (k), xopt
ñ (k)) > gñ (bñ ),

(37)

for all k ≥ l. From the above expression, we deduce that
bñ (k) ≥ bmax
for all k ≥ l. Indeed otherwise, there exists
ñ
k̃ ≥ l such that bñ (k̃) < bmax
ñ . This further implies that
opt
opt
uñ (bñ (k̃), xopt
ñ (k̃)) = bñ (k̃)xñ (k̃) − fñ (xñ (k̃))

≤ gñ (bñ (k̃)) < gñ (bmax
ñ ),
contradicting (37). In the above expression, the first inequality
follows from the definition of gñ and the second follows from
the fact that gñ is strictly increasing.
The above reasoning has helped us establish that bñ (k) ≥
bmax
> b∗ñ for all k ≥ l. Note that xopt
ñ
ñ (k) > 0 for all
k ≥ l because otherwise uñ (bñ (k), xopt
ñ (k)) = 0 and (37)
gets violated. By assumption, there exists at least one more
generator connected to the bus i(ñ) to which ñ is connected
to. For now assume that there is only one other generator
n̄ ∈ [N ] connected to i(ñ). Since for all k ≥ l, xopt (k) is a
solution of (3), from the fact that xopt
ñ (k) > 0, we deduce
bn̄ (k) ≥ bñ (k) ≥ bmax
ñ ,
for all k ≥ l. Now let
qn̄max := inf
argmax{bq − fn̄ (q) | q ≥ 0}.
max
b≥bñ

Note that qn̄max > 0 because of the facts: (i) b∗n̄ = b∗ñ <
∗
∗
bmax
ñ ; (ii) argmax{bn̄ q − fn̄ (q) | q ≥ 0} = xn̄ > 0; and (iii)
b 7→ argmax{bq − fn̄ (q) | q ≥ 0} is nondecreasing. Since
bn̄ (k) ≥ bmax
for all k ≥ l, we obtain qn̄ (k) ≥ qn̄max for
ñ
all k ≥ l (see Step 4 of the B ID A DJUSTMENT A LGORITHM

for the definition of qn̄ (k)). Thus, if bn̄ (k) > bñ (k) for some
opt
(k) is an optimizer
k ≥ l, then xopt
n̄ (k) = 0 (because x
of (3) given bids b(k)) and bn̄ (k) > bmax
ñ . As a consequence,
bn̄ (k + 1) = bn̄ (k) − βk qn̄ (k) ≤ bn̄ (k) − αqn̄max .

(38)

Therefore, if bn̄ (k) > bñ (k) for some k ≥ l, then from (38)
we deduce that there exists a finite k̃ > k such that, either
bn̄ (k̃) < bñ (k̃) or bn̄ (k̃) = bñ (k̃). In the former case,
opt
uñ (bñ (k̃), xopt
ñ (k̃)) = 0 as xñ (k̃) = 0. This contradicts (34).
In the latter case, two further cases can arise. In the first one,
opt
we get xopt
ñ (k̃) = 0 implying uñ (bñ (k̃), xñ (k̃)) = 0 and
contradicting (34). In the second one, we obtain xopt
n̄ (k) =
0, implying bn̄ (k + 1) < bñ (k + 1). This further yields
uñ (bñ (k̃ + 1), xopt
ñ (k̃ + 1)) = 0, thereby, contradicting (34).
Finally, if there are other generators connected to i(ñ) that
follow the B ID A DJUSTMENT A LGORITHM, then one can
carry out the same reasoning as done above and show that
we contradict (34). This completes the proof.
Remark V.6. (Generalization of Proposition V.5): It is interesting to observe that in the proof of Proposition V.5, we
have not used at any point that the generators connected
at buses other than the one that ñ is connected follow the
B ID A DJUSTMENT A LGORITHM. In fact, independently of
how such generators update their bids, the B ID A DJUSTMENT
A LGORITHM ensures that ñ does not have any incentive to
deviate. This is a useful property which we use later when
studying robustness to collusion.
•
Remark V.7. (Other notions of “incentive to deviate”): In
Definition V.4, one can impose the condition of higher payoff (34) to hold for all executions of (33). If this condition
holds, then the generator has an even stronger incentive to
deviate from the B ID A DJUSTMENT A LGORITHM. However,
by Proposition V.5, we are ensured that there does not exist
such strong incentive to deviate. This is because the result
shows that there does not exist any execution of (33) for
which (34) holds. If, on the other hand, we replace the
condition (34) in Definition V.4 with the requirement that there
exists an execution of (33) along which
max
lim sup uñ (bñ (k), xopt
ñ (k)) > uñ

(39)

k→∞

holds. This inequality means that there exists an execution
of (33) in which the generator ñ gets a higher payoff than
umax
infinitely often. Since the ISO can stop the iterations
ñ
at any time, the generator is not guaranteed a higher payoff,
but the possibility is still there. We conjecture that the B ID
A DJUSTMENT A LGORITHM is not robust to this notion of
weak incentive to deviate. However, the obfuscation of the
stopping criteria by the ISO makes such a weak incentive not
enough for a rational generator to deviate.
•
C. Robustness to collusion
Here we study the robustness of the B ID A DJUSTMENT
A LGORITHM against collusion. Collusion refers to the action
of a set of generators to share among themselves information
about their bids and generation demands by the ISO, with the
goal of getting a higher profit, possibly by deviating from the
bid update scheme. The following makes this notion formal.

11

Definition V.8. (Collusion between generators): A group of
generators J ⊂ [N ] form a collusion if at each iteration
k ∈ Z≥1 of the algorithm, each generator n ∈ J ,
(i) has the information
Ik := {(br (t), xopt
r (t)) | r ∈ J , t ∈ [k]}, and
(ii) determines its next bid bn (k + 1) based on the information Ik , not necessarily following the update scheme
(Step 3) of the B ID A DJUSTMENT A LGORITHM.
An iteration of the B ID A DJUSTMENT A LGORITHM under
a collusion between a group of generators J ⊂ [N ] is given
by the following dynamics
+
bn (k + 1) = [bn (k) + βk (xopt
n (k) − qn (k))] , ∀n 6∈ J ,
(40a)


(k)
k
(40b)
bn (k + 1) = Hn Ik , {qn (t)}t=1 , ∀n ∈ J

xopt (k + 1) ∈ Solsopf (b(k + 1)),
q(k + 1) = Soleff (b(k + 1)),
(k)

(40c)
(40d)

(2|J |+1)k

→ R≥0 }n∈J ,k=1,2,... reprewhere maps {Hn : R≥0
sent the update scheme of generators in collusion. Notice that
for each generator n, the quantity qn (k), for all k ∈ Z≥1 , is
part of its private information, irrespective of the fact that n
belongs to J or not. Next, we define what it means for the
group of generators J to have an incentive to collude.
Definition V.9. (Incentive to collude): Let r > 0 and assume that the stepsizes for any execution of (40) satisfy the
hypotheses of Theorem IV.7. Then, the group of generators
J has an incentive to collude under the B ID A DJUSTMENT
A LGORITHM if there exists an execution of (40), a generator
ñ ∈ J , and l ∈ Z≥1 such that
max
uñ (bñ (k), xopt
ñ (k)) > uñ ,

(41)

for all k ≥ l, where umax
is defined in (35).
ñ
This notion essentially says that there is an incentive to
collude for the generators in J if there exists at least one
execution of (40) along which at least one generator in J
gets a higher payoff after finite number of steps. The next
result shows that no group of generators has an incentive to
collude provided there is at least one generator at each bus with
generation that follows the B ID A DJUSTMENT A LGORITHM.
Proposition V.10. (Robustness to collusion under the B ID
A DJUSTMENT A LGORITHM): For dynamics (40), let the hypotheses of Theorem IV.7 hold and assume that bn (k) ≥ cn for
all n ∈ [N ] and k ∈ Z≥1 . Assume that the ISO selects a vertex
solution xopt (k) ∈ Solsopf (b(k)) at each iteration k ∈ Z≥1 .
Assume that at each bus that has generators connected to
it, there exists at least one generator that follows the update
scheme of the B ID A DJUSTMENT A LGORITHM. Denote these
generators by K ⊂ [N ]. Then, there is no incentive to collude
for any group of generators contained in [N ] \ K.
Proof: Let J ⊂ [N ]\K be a group of generators that form
a collusion. Assume first Scenario 1 where each generator in
J is connected to a different bus. By hypotheses, there exists
at least one other generator following the B ID A DJUSTMENT

A LGORITHM at the bus where a generator in J is connected
to. Thus, mimicking the proof of Proposition V.5 (cf. Remark V.6), at each bus, no generator has an incentive to deviate
from the B ID A DJUSTMENT A LGORITHM. By Definition V.4,
this implies that there does not exist any execution of (40) for
which (41) holds for any generator in J . Hence, for Scenario
1, generators in J do not have an incentive to collude.
Next, consider Scenario 2, where at least a bus, say i ∈ [Nb ],
has more than one generator from J , that is, Ji := Gi ∩ J
has cardinality larger than or equal to 2. Let n̄ ∈ Gi be the
generator at i that follows B ID A DJUSTMENT A LGORITHM.
For the sake of contradiction, assume the existence of a
generator ñ ∈ Ji for which (41) holds for some execution
of (40). Since the ISO selects a vertex solution at each iteration
k ∈ Z≥1 , we deduce that for all k ≥ l, all other generators in
Ji get zero production signal from the ISO, i.e., xopt
n (k) = 0
for all n ∈ Ji \ {ñ} and k ≥ l. Therefore, for the purpose of
analysis, one can neglect the generators in Ji \{ñ} and assume
that only ñ and n̄ are connected to i. Again, mimicking the
proof of Proposition V.5, we deduce that ñ does not have an
incentive to deviate and so (41) does not hold, a contradiction.
Since i is arbitrary, we conclude that for Scenario 2, generators
in J do not have an incentive to collude either.
An alternative definition of an incentive to collude could
be where every generator in the collusion gets a higher payoff
after a finite number of steps. Proposition V.10 however shows
that, under the assumed hypotheses, such a scenario does
not occur as there is not even a single generator that gets
a higher payoff after a finite number of iterations. Note that
the assumptions of the above result is tight in the sense that if
all generators at a bus collude, then based on the load and the
line limits, generators at that bus can increase their bid to an
arbitrarily high value, thus creating an incentive to collude.
Remark V.11. (Limitations on robustness under generator
bounds): The robustness of the B ID A DJUSTMENT A LGO RITHM against deviation and collusion relies heavily on the
fact that we have not considered upper bounds on the generation capacities. In the presence of such bounds, the generators
might be able to push the bids and their individual utilities
to a higher value based on the load at the respective bus and
the capacity constraints on the lines connected to the bus. To
avoid such behavior of market manipulation, either one can
modify network capacities or investigate alternative allocation
mechanisms that disincentivizes such behavior.
•
VI. S IMULATIONS
We illustrate the convergence and robustness properties of
the B ID A DJUSTMENT A LGORITHM using a modified IEEE
9-bus test case [34]. The traditional IEEE 9-bus system has 3
generators, at buses v1 , v2 , and v3 and three loads at buses
v5 , v7 , and v9 . In our modified test case, we have added one
generator each at buses v1 , v2 and v3 . The interconnection
topology is given in Figure 1. The line flow limit between
any two buses (vi , vj ) is 2.5 except for three lines, (v5 , v6 ),
(v3 , v6 ), and (v6 , v7 ), for which the limits are 1.5, 3.0, and
1.5, respectively. The loads are y5 = 2, y7 = 3, and y9 = 1,
where yi denotes the load at bus vi . The cost function for each

12

4
v2

15

10

5

8

v3

10

3

6

6
v8

v7

v6

0.4

4

0.3

5

v9

Loads

v5

0

Generators

v4

0.2
0.1

2

0

0

36

72

108

144

180

0

0

36

72

150

160

108

170

180

144

180

(b) Distance kb(k) − b∗ k

(a) Bids b(k)
Buses

1

15

10

v1

8

2

10
6
0.4

Fig. 1. Network layout of the modified IEEE 9-bus test case.

4

0.3

5

ai x2i

generator i is fi (xi ) =
+ ci xi , where the coefficients for
all the generators are given by the vectors
a = (0.1100, 0.0950, 0.0850, 0.1000, 0.1225, 0.0750),
c = (3.5, 3.8, 1.2, 0.8, 1.0, 1.3).
(42)
For the given costs and loads, the generation profile at the
optimizer of the DC-OPF problem (2) is
x∗ = (1.4268, 0.0732, 0.2703, 2.2297, 1.8987, 1.1013),
and the unique efficient Nash equilibrium is
b∗ = (3.8139, 3.8139, 1.2459, 1.2459, 1.4652, 1.4652). (43)
Figure 2 depicts the evolution of the bids and their distance to
the efficient Nash equilibrium along an execution of the B ID
A DJUSTMENT A LGORITHM. The initial bids b(1) are selected
satisfying bn (1) ≥ cn for all the generators n ∈ [6]. The
stepsizes are constant, βk = 0.01 for all k, and satisfy βk <
2an . As predicted by Theorem IV.7, Figure 2 shows that the
bids converge towards the efficient Nash equilibrium b∗ at a
linear rate and, after a finite number of steps, remain in a
neighborhood of b∗ . If one selects r = 1.35, then B(r) =
0.0101 and condition (15) holds for the stepsizes. Computing
the right hand side of (17) using these values, we conclude
that bids eventually remain in the neighborhood centered at
b∗ with radius 1.3775. Figure 2(b) validates this claim and, in
fact, shows that the bound is conservative since bids actually
remain in a neighborhood of radius 0.05.
15

10

8
10
6
0.04

4
5

0.02

2

0

0

0

36

72

108

(a) Bids b(k)

144

180

0

0

36

72

150

108

160

170

180

144

180

(b) Distance kb(k) − b∗ k

Fig. 2. Execution of the B ID A DJUSTMENT A LGORITHM for the modified
IEEE 9-bus test case in Figure 1. The cost function for each generator i is
fi (xi ) = ai x2i + ci xi , with coefficients given in (42). The load is y5 = 2,
y7 = 3, and y9 = 1. The efficient Nash equilibrium b∗ is given in (43).
Plots (a) and (b) show, respectively, the evolution of the bids and their
distance to b∗ . The stepsizes are βk = 0.01 for all k and the initial bids are
b(1) = (7.6096, 9.9313, 7.6087, 8.4827, 6.6175, 7.5254). Bids converge to
and then remain in a neighborhood of the efficient Nash equilibrium.

0.2
0.1

2

0

0

0

36

72

108

(c) Bids b(k)

144

180

0

0

36

72

150

108

160

170

180

144

180

(d) Distance kb(k) − b∗ k

Fig. 3. Execution of the B ID A DJUSTMENT A LGORITHM under different
stepsize selection for the example of Figure 2. All data is the same except
for the stepsizes. In plots (a) and (b), each generator at each iteration randomly selects the stepsize from the set [0.001, 0.1] with uniform probability
distribution. We observe that the bids still converge to a neighborhood of
the efficient Nash equilibrium, but the size of the neighborhood is bigger
than that achieved in Figure 2. In plots (c) and (d), the interval of stepsize
selection decays with time to a single point 0.01. The bids now converge
to the efficient Nash equilibrium with greater accuracy. These observations
validate the robustness guarantees of Proposition V.2.

We next illustrate the robustness properties of the B ID
A DJUSTMENT A LGORITHM against disturbances (cf. Section V-A). Figure 3 considers the same setup as above but
now with generators choosing a different stepsize at each
iteration. These differences in stepsizes can be interpreted
as a disturbance to the B ID A DJUSTMENT A LGORITHM, as
discussed in Remark V.3. In Figure 3(a)-(b), the interval
from which stepsizes are selected is constant, whereas in
Figure 3(c)-(d) the size of this interval decays with time. In
both cases, the bids converge to a neighborhood of b∗ (in the
latter case of decaying interval, the bids converge to a smaller
neighborhood), as established in Proposition V.2. Observe that
the convergence rate in Figure 3(a)-(b) is higher than in Figure 2(a)-(b). This is because stepsizes are allowed to be large in
the former. However, this higher convergence rate comes with
the pitfall of loss in accuracy, cf. Remark IV.8. Hence, to retain
both properties, stepsizes should be large initially and decay
as iterations proceed. This is seen in Figure 3(c)-(d), where
stepsizes decay over time (in expectation), yielding both high
convergence rate and accuracy. Finally, Figure 4 demonstrates
the robustness against collusion of the B ID A DJUSTMENT
A LGORITHM (cf. Section V-C), where generators 1, 3, and 5
form a collusion. These generators may select their bids in any
fashion they want: for this example, we assume a particular
strategy of bid selection, explained in Figure 4. The plot shows
that the utility of the colluding generators eventually becomes
lower than umax
(defined in (35)). Hence, there is no incentive
n
for collusion, as ensured by Proposition V.10.
VII. C ONCLUSIONS
We have formulated an inelastic electricity market game
capturing the strategic interaction between generators in a

13

20
unit 1
unit 3
unit 5

13
0.5
0

6

-0.5
-1
160

-1

0

(a)

40

80

180

120

un (bn (k), xopt
n (k))

−

200

160

200

un (b∗n , x∗n )

Fig. 4. Execution of the B ID A DJUSTMENT A LGORITHM for the example
considered in Figure 2 with generators 1, 3, and 5 forming a collusion. The
initial condition is the same and the stepsize is 0.01 at each iteration for
generators 2, 4, and 6. For each n ∈ {1, 3, 5}, at each iteration k, bn (k) =
0.99 ∗ bn+1 (k) if this value is bigger than or equal to b∗n . Otherwise, bn (k)
is selected randomly from the interval [b∗n , b∗n + 1], with uniform probability
distribution. With this choice of bid, the colluding generators aim to get a
positive production signal and at the same time bid high enough so as to
obtain a high utility. The plot shows the evolution of the difference between
the utility obtained at each iteration, un (bn (k), xopt
n (k)), and the utility at the
∗
optimal bid and generation, un (b∗n , xopt
n (b )) for each n ∈ {1, 3, 5}. This
value becomes negative for all generators after a finite number of iterations.
Since umax
> un (b∗n , x∗n ), the example shows that (41) does not hold.
n

bid-based energy dispatch setting. For this game, we have
established the existence and uniqueness of the efficient Nash
equilibria. We have also designed the B ID A DJUSTMENT
A LGORITHM, which is an iterative strategy amenable to decentralized implementation that provably converges to a neighborhood of the efficient Nash equilibrium at a linear rate. We have
characterized the robustness properties of the algorithm against
disturbances, deviation in bid updates, and collusions among
generators. Future work will analyze the dynamic behavior
of the market under other bidding schemes, such as Cournot
bidding, supply function bidding, and price-capacity bidding.
We would also like to examine the convergence of other
learning schemes such as regret minimization in the context of
electricity markets. Finally, we wish to incorporate stochastic
load demands and changing sets of generators in our setup.
R EFERENCES
[1] A. Cherukuri and J. Cortés, “Decentralized Nash equilibrium learning
by strategic generators for economic dispatch,” in American Control
Conference, Boston, MA, Jul. 2016, pp. 1082–1087.
[2] A. Cherukuri and J. Cortés, “Decentralized Nash equilibrium seeking by
strategic generators for DC optimal power flow,” in Annual Conference
on Information Systems and Sciences, Baltimore, MD, Mar. 2017, to
appear.
[3] S. Stoft, Power system economics: designing markets for electricity.
Piscataway, NJ: IEEE Press, 2002.
[4] F. Kirschen and G. Strbac, Fundamentals of power system economics.
Sussex, England: John Wiley & Sons, 2004.
[5] R. Johari and J. N. Tsitsiklis, “Parameterized supply function bidding:
Equilibrium and efficiency,” Operations Research, vol. 59, no. 5, pp.
1079–1089, 2011.
[6] W. Tang and R. Jain, “Game-theoretic analysis of the nodal pricing
mechanism for electricity markets,” in IEEE Conf. on Decision and
Control, Florence, Italy, Dec. 2013, pp. 562–567.
[7] D. Cai, S. Bose, and A. Wierman, “On the role of a market maker in
networked Cournot competition,” 2016, preprint available at http://boses.
ece.illinois.edu.
[8] T. Li and M. Shahidehpour, “Strategic bidding of transmissionconstrained GENCO’s with incomplete information,” IEEE Transactions
on Power Systems, vol. 20, no. 1, pp. 437–447, 2005.
[9] X. Hu and D. Ralph, “Using EPECs to model bilevel games in restructured electricity markets with locational prices,” Operations Research,
vol. 55, no. 5, pp. 809–827, 2007.
[10] G. I. Bischi, C. Chiarella, M. Kopel, and F. Szidarovszky, Nonlinear
oligopolies: stability and bifurcations. New York: Springer, 2010.

[11] U. Nadav and G. Piliouras, “No regret learning in oligopolies: Cournot
vs Bertrand,” in Algorithmic Game Theory, ser. Lecture Notes in
Computer Science, S. Kontogiannis, E. Koutsoupias, and P. G. Spirakis,
Eds. New York: Springer, 2010, vol. 6386, pp. 300–311.
[12] E. N. Barron, R. Goebel, and R. R. Jensen, “Best response dynamics for
continuous games,” Proceeding of the American Mathematical Society,
vol. 138, no. 3, pp. 1069–1083, 2010.
[13] D. Fudenberg and D. K. Levine, The Theory of Learning in Games.
Cambridge, MA: MIT Press, 1998.
[14] P. Frihauf, M. Krstić, and T. Başar, “Nash equilibrium seeking in noncooperative games,” IEEE Transactions on Automatic Control, vol. 57,
no. 5, pp. 1192–1207, 2012.
[15] M. S. Stankovic, K. H. Johansson, and D. M. Stipanovic, “Distributed
seeking of Nash equilibria with applications to mobile sensor networks,”
IEEE Transactions on Automatic Control, vol. 57, no. 4, pp. 904–919,
2012.
[16] J. Warrington, P. Goulart, S. Mariéthoz, and M. Morari, “A market
mechanism for solving multi-period optimal power flow exactly on ac
networks with mixed participants,” in American Control Conference,
Montréal, Canada, Jun. 2012, pp. 3101–3107.
[17] D. J. Shiltz, M. Cvetković, and A. M. Annaswamy, “An integrated
dynamic market mechanism for real-time markets and frequency regulation,” IEEE Transactions on Sustainable Energy, vol. 7, no. 2, pp.
875–885, 2016.
[18] D. P. Palomar and M. Chiang, “Alternative distributed algorithms
for network utility maximization: Framework and applications,” IEEE
Transactions on Automatic Control, vol. 52, no. 12, pp. 2254–2269,
2007.
[19] M. N. Faqiry and S. Das, “Double-sided energy auction in microgrid:
equilibrium under price anticipation,” IEEE Access, vol. 4, pp. 3794–
3805, 2016.
[20] S. Pu and A. Garcia, “Iterative mechanisms for electricity markets,”
2016, available at https://arxiv.org/abs/1608.08987.
[21] S. Leyffer and T. Munson, “Solving multi-leader-common-follower
games,” Optimization Methods and Software, vol. 25, no. 4, pp. 601–
623, 2010.
[22] J.-S. Pang and M. Fukushima, “Quasi-variational inequalities, generalized nash equilbria, and multi-leader-follower games,” Computational
Management Science, vol. 2, no. 1, pp. 21–56, 2005.
[23] Z.-Q. Luo, J.-S. Pang, and D. Ralph, Mathematical programs with
equilibrium constraints. Cambridge, UK: Cambridge University Press,
1996.
[24] M. C. Ferris, S. P. Dirkse, and A. Meeraus, “Mathematical programs
with equilibrium constraints: automatic reformulation and solution via
constrained optimization,” in Frontiers in Applied General Equilibrium
Modeling. Cambridge, UK: Cambridge University Press, 2005, pp.
67–94.
[25] D. Zhang and G.-H. Lin, “Bilevel direct search method for leaderfollower problems and application in health insurance,” Computers &
Operations Research, vol. 41, pp. 359–373, 2014.
[26] S. Hart and A. Mas-Colell, “Markets, correlation, and regret-matching,”
Games and Economic Behavior, vol. 93, pp. 42–58, 2015.
[27] T. Lykouris, V. Syrgkanis, and Éva Tardos, “Learning and efficiency in
games with dynamic population,” in Annual ACM-SIAM Symposium on
Discrete Algorithms, Arlington, VA, 2016, pp. 120–129.
[28] A. Cherukuri and J. Cortés, “Initialization-free distributed coordination
for economic dispatch under varying loads and generator commitment,”
Automatica, vol. 74, pp. 183–193, 2016.
[29] S. T. Cady, A. D. Domı́nguez-Garcı́a, and C. N. Hadjicostis, “A
distributed generation control architecture for islanded AC microgrids,”
IEEE Transactions on Control Systems Technology, vol. 23, no. 5, pp.
1717–1735, 2015.
[30] S. Boyd and L. Vandenberghe, Convex Optimization.
Cambridge
University Press, 2004.
[31] A. Mas-Colell, M. Whinston, and J. Green, Microeconomic Theory.
Oxford, UK: Oxford University Press, 1995.
[32] D. Fudenberg and J. Tirole, Game Theory. Cambridge, MA: MIT Press,
1991.
[33] Z.-P. Jiang and Y. Wang, “Input-to-state stability for discrete-time
nonlinear systems,” Automatica, vol. 37, no. 6, pp. 857–869, 2001.
[34] R. D. Zimmerman, C. E. Murillo-Sánchez, and R. J. Thomas, “Matpower: Steady-state operations, planning and analysis tools for power
systems research education,” IEEE Transactions on Power Systems,
vol. 26, no. 1, pp. 12–19, 2011.

