Participants in deregulated electric power markets compete for financial transmission rights (FTRs) to hedge against losses due to transmission congestion by submitting bids to the independent system operator (ISO). The ISO obtains an FTR allocation, that maximizes sales revenue while satisfying simultaneous feasibility. This FTR allocation remains in place for a length of time during which the participants compete in the energy market to maximize their total payoff from both FTR and energy markets. Energy markets (bi-lateral, day ahead, real time) continue until the the end of the current FTR period, at which time the participants can choose to modify their FTR holdings for the next FTR period. As in any noncooperative game, finding Nash equilibrium bidding strategies is of critical importance to the participants in both FTR and energy markets. In this research, a two-tier matrix game theoretic modeling approach is developed that can be used to obtain equilibrium bidding behavior of the participants in both FTR and energy markets considering the total payoff from FTR and energy. The matrix game model presents a significant deviation from the bilevel optimization approach commonly used to model FTR and energy allocation problems. A reinforcement learning (RL) algorithm is also developed which uses a simulation model and a value maximization approach to obtain the equilibrium bidding strategies in each market. The model and the RL based solution approach allow consideration of multi-dimensional bids (for both FTR and energy markets), network contingencies, varying demands, and many participants. The value iteration based RL algorithm obtains pure strategy Nash equilibrium for FTR and energy allocation. A sample network with three buses and four participants is considered for demonstrating the viability of the game theoretic model for FTR market. A PJM network example with five buses, five generators and three loads is also considered to analyze equilibrium bidding behavior in joint FTR and energy markets. Several numerical experiments on the sample networks are conducted using the approach of statistical design of experiments (DOE) to assess impacts of variations of bid and network parameters on the market outcomes like participant payoffs and equilibrium strategies.

Includes vita. / Title from PDF of title page. / Document formatted into pages; contains 111 pages. / Thesis (Ph.D.)--University of South Florida, 2003. / Includes bibliographical references. / Text (Electronic thesis) in PDF format. / ABSTRACT: A large class of sequential decision making problems under uncertainty with multiple competing decision makers/agents can be modeled as stochastic games. Stochastic games having Markov properties are called Markov games or competitive Markov decision processes. This dissertation presents an approach to solve non cooperative stochastic games, in which each decision maker makes her/his own decision independently and each has an individual payoff function. In stochastic games, the environment is nonstationary and each agent's payoff is affected by joint decisions of all agents, which results in the conflict of interest among the decision makers. In this research, the theory of Markov decision processes (MDPs) is combined with the game theory to analyze the structure of Nash equilibrium for stochastic games. In particular, the Laurent series expansion technique is used to extend the results of discounted reward stochastic games to average reward stochastic games. / ABSTRACT: As a result, auxiliary matrix games are developed that have equivalent equilibrium points and values to a class of stochastic games that are irreducible and have average reward performance metric. R-learning is a well known machine learning algorithm that deals with average reward MDPs. The R-learning algorithm is extended to develop a Nash-R reinforcement learning algorithm for obtaining the equivalent auxiliary matrices. A convergence analysis of the Nash-R algorithm is developed from the study of the asymptotic behavior of its two time scale stochastic approximation scheme, and the stability of the associated ordinary differential equations (ODEs). The Nash-R learning algorithm is tested and then benchmarked with MDP based learning methods using a well known grid game. Subsequently, a real life application of stochastic games in deregulated power market is explored. / ABSTRACT: According to the current literature, Cournot, Bertrand, and Supply Function Equilibrium (SFEs) are the three primary equilibrium models that are used to evaluate the power market designs. SFE is more realistic for pool type power markets. However, for a complicated power system, the convex assumption for optimization problems is violated in most cases, which makes the problems more difficult to solve. The SFE concept in adopted in this research, and the generators' behaviors are modeled as a stochastic game instead of one shot game. The power market is considered to have features such as multi-settlement (bilateral, day-ahead market, spot markets and transmission congestion contracts), and demand elasticity. Such a market consisting of multiple competing suppliers (generators) is modeled as a competitive Markov decision processes and is studied using the Nash-R algorithm. / System requirements: World Wide Web browser and PDF reader. / Mode of access: World Wide Web.

Planifier les actions d’un agent dans un environnement dynamique et incertain, a été largement étudié et le cadre des processus décisionnels de Markov offre les outils permettant de modéliser et de résoudre de tels problèmes. Le domaine de la théorie des jeux, a permis l’étude des interactions stratégiques entre plusieurs agents pour un jeu donné. Le cadre des jeux stochastiques, est considéré comme une généralisation du domaine des processus décisionnels de Markov et du champ de la théorie des jeux et permet de modéliser des systèmes ayant plusieurs agents et plusieurs états. Cependant, planifier dans unsystème multi-agents est considéré comme difficile, car la politique d’actions de l’agent dépend non seulement de ses choix mais aussi des politiques des autres agents. Le travail que nous présentons dans cette thèse porte sur la prise de décision distribuée dans les systèmes multi-agents. Les travaux existants dans le domaine, permettent la résolution théorique des jeux stochastiques mais imposent de fortes restrictions et font abstraction de certains problèmes cruciaux du modèle. Nous proposons un algorithme de planification décentralisée pour le modèle des jeux stochastiques, d’une part basé sur l’algorithme Value-Iteration et d’autre part basé sur la notion d’équilibre issue de la résolution des jeux matriciels. Afin d’améliorer le processus de résolution et de traiter des problèmes de taille importante, nous recherchons à faciliter la prise de décision et à limiter les possibilités d’actions à chaque étape d’interaction. L’algorithme que nous avonsproposé, a été validé sur un exemple d’interaction incluant plusieurs agents et différentes expérimentations ont été menées afin d’évaluer la qualité de la solution obtenue. / Planning agent’s actions in a dynamic and uncertain environment has been extensively studied. The framework of Markov decision process provides tools to model and solve such problems. The field of game theory has allowed the study of strategic interactions between multiple agents for a given game. The framework of stochastic games is considered as a generalization of the fields of Markov decision process and game theory. It allows to model systems with multiple agents and multiple states. However, planning in a multi-agent system is considered difficult : agent’s decisions depend not only on its actions but also on actions of the other agents. The work presented in this thesis focuses on decision making in distributed multi-agent systems. Existing works in this field allow the theoretical resolution of stochastic games but place severe restrictions and ignore some crucial problems of the model. We propose a decentralized planning algorithm for the model of stochastic games. Our proposal is based on the Value-Iteration algorithm and on the concept of Nash equilibrium. To improve the resolution process and to deal with large problems, we sought to ease decision making and limit the set of joint actions at each stage. The proposed algorithm was validated on a coordination problem including several agents and various experiments were conducted to assess the quality of the resulting solution.