Nash Equilibrium Problems In Power Markets And Product Design Analysis And Algorithms

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.

The book discusses three classes of problems: the generalized Nash equilibrium problems, the bilevel problems and the mathematical programming with equilibrium constraints (MPEC). These problems interact through their mathematical analysis as well as their applications. The primary aim of the book is to present the modern tool of variational analysis and optimization, which are used to analyze these three classes of problems. All contributing authors are respected academicians, scientists and researchers from around the globe. These contributions are based on the lectures delivered by experts at CIMPA School, held at the University of Delhi, India, from 25 November–6 December 2013, and peer-reviewed by international experts. The book contains five chapters. Chapter 1 deals with nonsmooth, nonconvex bilevel optimization problems whose feasible set is described by using the graph of the solution set mapping of a parametric optimization problem. Chapter 2 describes a constraint qualification to MPECs considered as an application of calmness concept of multifunctions and is used to derive M-stationarity conditions for MPEC. Chapter 3 discusses the first- and second-order optimality conditions derived for a special case of a bilevel optimization problem in which the constraint set of the lower level problem is described as a general compact convex set. Chapter 4 concentrates the results of the modelization and analysis of deregulated electricity markets with a focus on auctions and mechanism design. Chapter 5 focuses on optimization approaches called reflection methods for protein conformation determination within the framework of matrix completion. The last chapter (Chap. 6) deals with the single-valuedness of quasimonotone maps by using the concept of single-directionality with a special focus on the case of the normal operator of lower semi-continuous quasiconvex functions.

Local Electricity Markets introduces the fundamental characteristics, needs, and constraints shaping the design and implementation of local electricity markets. It addresses current proposed local market models and lessons from their limited practical implementation. The work discusses relevant decision and informatics tools considered important in the implementation of local electricity markets. It also includes a review on management and trading platforms, including commercially available tools. Aspects of local electricity market infrastructure are identified and discussed, including physical and software infrastructure. It discusses the current regulatory frameworks available for local electricity market development internationally. The work concludes with a discussion of barriers and opportunities for local electricity markets in the future. Delineates key components shaping the design and implementation of local electricity market structure Provides a coherent view on the enabling infrastructures and technologies that underpin local market expansion Explores the current regulatory environment for local electricity markets drawn from a global panel of contributors Exposes future paths toward widespread implementation of local electricity markets using an empirical review of barriers and opportunities Reviews relevant local electricity market case studies, pilots and demonstrators already deployed and under implementation

2019 marked the 85th anniversary of Heinrich Freiherr von Stackelberg’s habilitation thesis “Marktform und Gleichgewicht,” which formed the roots of bilevel optimization. Research on the topic has grown tremendously since its introduction in the field of mathematical optimization. Besides the substantial advances that have been made from the perspective of game theory, many sub-fields of bilevel optimization have emerged concerning optimal control, multiobjective optimization, energy and electricity markets, management science, security and many more. Each chapter of this book covers a specific aspect of bilevel optimization that has grown significantly or holds great potential to grow, and was written by top experts in the corresponding area. In other words, unlike other works on the subject, this book consists of surveys of different topics on bilevel optimization. Hence, it can serve as a point of departure for students and researchers beginning their research journey or pursuing related projects. It also provides a unique opportunity for experienced researchers in the field to learn about the progress made so far and directions that warrant further investigation. All chapters have been peer-reviewed by experts on mathematical optimization.

This highly acclaimed work, first published by Prentice Hall in 1989, is a comprehensive and theoretically sound treatment of parallel and distributed numerical methods. It focuses on algorithms that are naturally suited for massive parallelization, and it explores the fundamental convergence, rate of convergence, communication, and synchronization issues associated with such algorithms. This is an extensive book, which aside from its focus on parallel and distributed algorithms, contains a wealth of material on a broad variety of computation and optimization topics. It is an excellent supplement to several of our other books, including Convex Optimization Algorithms (Athena Scientific, 2015), Nonlinear Programming (Athena Scientific, 1999), Dynamic Programming and Optimal Control (Athena Scientific, 2012), Neuro-Dynamic Programming (Athena Scientific, 1996), and Network Optimization (Athena Scientific, 1998). The on-line edition of the book contains a 95-page solutions manual.

Nash equilibrium is the central solution concept in Game Theory. Since Nash's original paper in 1951, it has found countless applications in modeling strategic behavior of traders in markets, (human) drivers and (electronic) routers in congested networks, nations in nuclear disarmament negotiations, and more. A decade ago, the relevance of this solution concept was called into question by computer scientists~\cite{DGP, CDT}, who proved (under appropriate complexity assumptions) that {\em computing} a Nash equilibrium is an intractable problem. And if centralized, specially designed algorithms cannot find Nash equilibria, why should we expect distributed, selfish agents to converge to one? The remaining hope was that at least approximate Nash equilibria can be efficiently computed. Understanding whether there is an efficient algorithm for {\em approximate Nash equilibrium} has been the central open problem in this field for the past decade. In this thesis, we provide strong evidence that even finding an approximate Nash equilibrium is intractable. We prove several intractability theorems for different settings (two-player games and many-player games) and models (computational complexity, query complexity, and communication complexity). In particular, our main result is that under a plausible and natural complexity assumption (``Exponential Time Hypothesis for \PPAD''), there is no polynomial-time algorithm for finding an approximate Nash equilibrium in two-player games. The problem of approximate Nash equilibrium in a two-player game poses a unique technical challenge: it is a member of the class \PPAD, which captures the complexity of several fundamental total problems, i.e. problems that always have a solution; and it also admits a quasipolynomial ($\approx n^{\log n}$) time algorithm. Either property alone is believed to place this problem far below \NP-hard problems in the complexity hierarchy; having both simultaneously places it just above \P, at what can be called the frontier of intractability. Indeed, the tools we develop in this thesis to advance on this frontier are useful for proving hardness of approximation of several other important problems whose complexity lies between \P~and \NP: \begin{description} \item [Brouwer's fixed point] Given a continuous function $f$ mapping a compact convex set to itself, Brouwer's fixed point theorem guarantees that $f$ has a fixed point, i.e. $x$ such that $f(x) = x$. Our intractability result holds for the relaxed problem of finding an approximate fixed point, i.e. $x$ such that $f(x) \approx x$. \item [Market equilibrium] Market equilibrium is a vector of prices and allocations where the supply meets the demand for each good. %We consider the Arrow-Debreu model where agents are both sellers and buyers of goods. Our intractability result holds for the relaxed problem of finding an approximate market equilibrium, where the supply of each good approximately meets the demand. \item [CourseMatch (A-CEEI)] Approximate Competitive Equilibrium from Equal Income (A-CEEI) is the economic principle underlying CourseMatch, a system for fair allocation of classes to students (currently in use at Wharton, University of Pennsylvania). \item [Densest $k$-subgraph] Our intractability result holds for the following relaxation of the $k$-Clique problem: given a graph containing a $k$-clique, the algorithm has to find a subgraph over $k$ vertices that is ``almost a clique'', i.e. most of the edges are present. \item [Community detection] We consider a well-studied model of communities in social networks, where each member of the community is friends with a large fraction of the community, and each non-member is only friends with a small fraction of the community. \item [VC dimension and Littlestone dimension] The Vapnik-Chervonenkis (VC) dimension is a fundamental measure in learning theory that captures the complexity of a binary concept class. Similarly, the Littlestone dimension is a measure of complexity of online learning. \item [Signaling in zero-sum games] We consider a fundamental problem in signaling, where an informed signaler reveals private information about the payoffs in a two-player zero-sum game, with the goal of helping one of the players.

Computer science and economics have engaged in a lively interaction over the past fifteen years, resulting in the new field of algorithmic game theory. Many problems that are central to modern computer science, ranging from resource allocation in large networks to online advertising, involve interactions between multiple self-interested parties. Economics and game theory offer a host of useful models and definitions to reason about such problems. The flow of ideas also travels in the other direction, and concepts from computer science are increasingly important in economics. This book grew out of the author's Stanford University course on algorithmic game theory, and aims to give students and other newcomers a quick and accessible introduction to many of the most important concepts in the field. The book also includes case studies on online advertising, wireless spectrum auctions, kidney exchange, and network management.

Explains the economics of electricity at each step of the supply chain: production, transportation and distribution, and retail.

'Algorithms to Live By' looks at the simple, precise algorithms that computers use to solve the complex 'human' problems that we face, and discovers what they can tell us about the nature and origin of the mind.

The latest practical applications of electricity market equilibrium models in analyzing electricity markets Electricity market deregulation is driving the power energy production from a monopolistic structure into a competitive market environment. The development of electricity markets has necessitated the need to analyze market behavior and power. Restructured Electric Power Systems reviews the latest developments in electricity market equilibrium models and discusses the application of such models in the practical analysis and assessment of electricity markets. Drawing upon the extensive involvement in the research and industrial development of the leading experts in the subject area, the book starts by explaining the current developments of electrical power systems towards smart grids and then relates the operation and control technologies to the aspects in electricity markets. It explores: The problems of electricity market behavior and market power Mathematical programs with equilibrium constraints (MPEC) and equilibrium problems with equilibrium constraints (EPEC) Tools and techniques for solving the electricity market equilibrium problems Various electricity market equilibrium models State-of-the-art techniques for computing the electricity market equilibrium problems The application of electricity market equilibrium models in assessing the economic benefits of transmission expansions for market environments, forward and spot markets, short-term power system security, and analysis of reactive power impact Also featured are computational resources to allow readers to develop algorithms on their own, as well as future research directions in modeling and computational techniques in electricity market analysis. Restructured Electric Power Systems is an invaluable reference for electrical engineers and power system economists from power utilities and for professors, postgraduate students, and undergraduate students in electrical power engineering, as well as those responsible for the design, engineering, research, and development of competitive electricity markets and electricity market policy.