Nash equilibrium problems in power markets and product design: Analysis and algorithms

Kannan, Aswin

Permalink

https://hdl.handle.net/2142/15973 Copy

Description

Title

Nash equilibrium problems in power markets and product design: Analysis and algorithms

Author(s)

Kannan, Aswin

Issue Date

2010-05-18T18:53:08Z

Director of Research (if dissertation) or Advisor (if thesis)

• Shanbhag, Vinayak V.
• Kim, Harrison H.M.

Department of Study

Industrial & Enterprise Sys Eng

Discipline

Industrial Engineering

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

• competition
• Game
• Cournot
• Bertrand
• power markets
• product deisgn
• algorithms
• analysis

Abstract

The focus of this research is on the analysis and computation of equilibria in noncooperative Cournot and Bertrand games. The application of focus for Cournot competition is power markets while that for Bertrand competition is product design. We consider Cournot-based models for strategic behavior in power markets while Bertrandbased models are employed for analyzing the behavior of price-based competition in product design. This thesis is partitioned into three parts. Of these, the rst two parts focus on power market applications while the third part focuses on product design. Motivated by the risk of capacity shortfall faced by market participants with uncertain generation assets, the rst part considers a game where agents are assumed to be risk-averse optimizers, using a conditional value-at-risk (CVaR) measure. The resulting game-theoretic problem is a two-period risk-based stochastic Nash game with shared strategy sets. In general, this stochastic game has nonsmooth objectives and standard existence and uniqueness results cannot be leveraged for this class of games, given the lack of compactness of strategy sets and the absence of strong monotonicity in the gradient map of the objectives. However, when the risk-measure is independent of competitive interactions, a subset of equilibria to the risk-averse game are shown to be characterized by a solvable monotone single-valued variational inequality. If the risk-measures are generalized to allow for strategic interactions, then the characterization is through a multi-valued variational inequality. Both this object and its single-valued counterpart, arising from the smoothed game, are shown to admit solutions. The equilibrium conditions of the game grow linearly in size with the the sample-space, network size and the number of participating rms. Consequently, direct schemes are inadvisable for most practical problems and instead, we present a distributed regularized primaldual and dual projection scheme where both primal and dual iterates are computed separately. Rate of convergence estimates are provided and error bounds are developed for inexact extensions of the dual scheme. Unlike projection schemes for deterministic problems, here the projection step requires the solution of a possibly massive stochastic program. By utilizing cutting plane methods, we ensure that the complexity of the projection scheme scales slowly with the size of the sample-space. Insights regarding market design and operation are obtained after testing the model on a 53-node electricity network. The second part extends this model by considering the grid operator to be a pro t maximizer. However the effect of risk is neglected in this model. The resulting problem is a quasi variational inequality. An analysis of the equivalent complementarity problem (CP) allows us to claim that the game does admit an equilibrium. By observing that the CP is monotone, we are in a position to employ a class of iterative regularization techniques namely the iterative Tikhonov and the iterative proximal algorithms. The algorithms are seen to scale well with the size of the problem. The model is employed for examining strategic behavior on a twelve node network and several economic insights are drawn. The third part of this thesis deals with Bertrand competition in a product design regime. With due consideration to the attribute dimension in addition to price competition, more specifically for design and consumer service industries, a game theoretic model is formulated. The logit model, in lieu of some of its tractable properties, is deployed to capture consumer preferences and thereby the demand. Subsequently the variational formulations corresponding to the game are analyzed for existence of solutions. The lack of convexity of objectives, analytical intractability of the variational formulations corresponding to the game state some drawbacks of the logit model. Several projection and interior point schemes are deployed for solving these classes of problems. Numerical results for smaller instances of these games are illustrated by means of a painkiller example. Suggestions on alternate revenue maximization models are presented.

Graduation Semester

2010-5

Permalink

http://hdl.handle.net/2142/15973

Copyright and License Information

Copyright 2010 Aswin Kannan

Owning Collections