WWW.ABSTRACT.XLIBX.INFO
FREE ELECTRONIC LIBRARY - Abstract, dissertation, book
 
<< HOME
CONTACTS



Pages:   || 2 | 3 | 4 | 5 |

«By HOSSEIN HAJIMIRSADEGHI Bachelor of Science in Electrical Engineering University of Tehran Tehran, Iran, 2008 Advisor: Ashkan Rahmi-Kian Associate ...»

-- [ Page 1 ] --

NASH EQUILIBRIUM SEARCH FOR NONLINEAR

GAMES USING EVOLUTIONARY ALGORITHMS

By

HOSSEIN HAJIMIRSADEGHI

Bachelor of Science in Electrical Engineering

University of Tehran

Tehran, Iran, 2008

Advisor: Ashkan Rahmi-Kian

Associate Professor, Faculty of Electrical and Computer

Engineering, University of Tehran

July, 2008

ii

TABLE OF CONTENTS

ABSTRACT

Chapter Page I. INTRODUCTION

II. METHODOLOGY

II.1. Nash Equilibrium

II.2. Coevolutionary Programming

II.2.A. Cooperative Coevolutionary Algorithm

II.2.A.a. Numerical Example

II.2.B. Competitive Coevolutionary Algorithm

II.2.B.a. Numerical Example

II.3. Iterative NE Search

II.3.A. Local Iterative NE Search

II.3.A.a. Numerical Example

II.3.B. Global Iterative NE Search

II.3.B.a. Numerical Example

II.4. Nash Equilibrium as a Minimum of a Function

II.4.A. Discrete Minimization

II.4.A.a. Numerical Example

II.4.B. Continuous Minimization

II.4.B.a. Local Profit Maximization

II.4.B.b. Global Profit Maximization

II.4.B.c. Numerical Example

III. SIMULATION RESULTS

III.1. Transmission Constrained Electricity Markets with Linear Demand Functions

III.1.A. Two-Bus Transmission Constrained Cournot Model

III.1.B. Three-Bus Transmission Constrained Cournot Model (Two Generator and Three Load)

III.1.C. Three-Bus Transmission Constrained Cournot Model

III.1.D. Four-Bus Transmission Constrained Cournot Model

iii Chapter Page III.2. Unconstrained Electricity Markets with a Total Nonlinear Demand Function

III.2.A. Cournot Model with Two Firms

III.2.B. Cournot Model with Three Firms

III.2.C. Cournot Model with Four Firms

III.2.D. Cournot Model with Six Firms

III.3. Transmission Constrained Electricity Markets with Nonlinear Demand Functions

III.3.A. Two-Bus Cournot Model

III.3.B. Three-Bus Cournot Model

III.4. Some Other Nonlinear Games

III.3.A. Uniform-Price Spot Market

III.3.A. A Simple Electricity Pool

III.3.A. A Dynamic Nonlinear Game

IV. CONCLUSION

REFERENCES

APPENDICES

Appendix A. An Introduction to Invasive Weed Optimization

Appendix B. Discrete Invasive Weed Optimization

–  –  –

Finding Nash Equilibrium (NE) for nonlinear games is a challenging work due to existence of local Nash Equilibrium traps. So, devising algorithms that are capable of escaping from trapping in local optima and finding global solutions is needed for analysis of nonlinear games. Evolutionary Algorithms as the popular stochastic global search algorithms can be exploited for this purpose. In this thesis, Nash Equilibrium search approaches for nonlinear games are studied through a number of numerical examples and practical problems.

Coevolutionary programming, evolutionary iterative Nash Equilibrium search, and minimizing objective functions with embedded Nash Equilibria, using evolutionary algorithms, are the main methods discussed in this work. Also, local optimization algorithms are employed in some of the problems for comparison.

For practical simulations we apply the proposed algorithms to several nonlinear games in electricity market models with two to six players. Transmission-constrained electricity markets with linear and nonlinear demand functions and unconstrained electricity markets with a nonlinear total demand are the main case studies in this work. We adopt Invasive Weed Optimization for all the evolutionary computing purposes, and the efficiency of our proposed Coevolutionary Invasive Weed Optimization (CIWO) for finding global NE is shown in the simulations. Likewise, successful results of the proposed Discrete Invasive Weed optimization (DIWO) in NE search for games with discrete strategy spaces are provided.

–  –  –

John Nash’s formulation of noncooperative game theory was one of the great breakthroughs in the history of social science. Nash Equilibrium (NE) is a solution of a game involving two or more players in which no player has incentive to unilaterally change her action, so any change in strategies by any of the players lead that player to earn less.

In November, 1949, the proceedings of National Academy of Science received a short note from Nash which was published the next year [35]. In this assay, Nash gave general definition of equilibrium for normal-form games, and he neatly sketched an argument using the Kakutani fixed-point theorem to prove that equilibria in randomized strategies must exist for any finite normal-form game. Also, in 1951, he presented his outstanding article “Noncooperative Games” [36] in which he argued that his noncooperative equilibrium concept, together with von Neumann’s normal form gives a complete general methodology to analyze all games. Furthermore, he showed the efficiency and importance of his proposed equilibrium in a number of interesting examples, illustrating problems which have concerned game theorists ever since, including a game with one Pareto-inefficient equilibria like Prisoners’ Dilemma.





Historically, the concept of NE was developed before Nash in literature by a number of famous scientists. Antoine Augostin Cournot in his brilliant book [37], constructed a theory of oligopolistic firms that includes monopolists and perfect competitors as limiting extremes (1838). In fact, we may speak of Cournot as the founder of oligopoly theory [38].

Another prominent work was done by John von Neumann and Oskar Morgenstern who introduce the concept of mixed strategy NE for special case of zero-sum games [39].

Also, Bertrand (1883) to Felner (1949) found specific models of oligopoly which had some applied predictions [40], [41].

Since its development, NE plays an important role in game theory and has been used for modeling problems in a variety of areas like economics, biology, engineering, political science, computer science, philosophy, etc.

In this thesis we aim to find Nash Equilibrium for nonlinear games. Although rigorous mathematical frameworks have been devised to approach games with linear manipulation, however, considerable amount of attention have been dedicated in recent years for NE search in the case of nonlinear games. In this respect, the terms of evolutionary game theory [34] and Natural selection in biology and life science have been employed by economics and engineers to have more insights to the concept of Nash Equilibrium. In fact, evolutionary game theory in a computational scheme is the application of natured-inspired models of change in generations of populations to game theory.

In this study, Evolutionary Algorithms as the popular means of global search are exploited to find NE for nonlinear noncooperative games. We try to put all the common methods of NE search in evolutionary frameworks and analyze their performance through a large number of numerical simulations for finding global NE. The oligopolistic games in electricity markets are the practical problems which are studied in this work.

The remainder of thesis is arranged as follows. Chapter II explains methods and approaches for NE search in games with two or more players. A numerical example is solved with each proposed method to identify the efficiency, advantages and drawbacks of the algorithms and also to have a comparison between evolutionary and nonevolutionary frameworks.

Chapter III provides a large number of practical simulations for different models of games in electricity markets. Moreover, performance of the proposed methods in chapter II for solving complex games with fairly large number of players is investigated.

Finally, chapter IV delivers the decisive message of my work and clears the perspective for future works.

–  –  –

Many techniques have been developed for searching Nash Equilibrium (NE) in game theory problems. All the approaches are inspired by NE definition which is maximizing the payoff, given other players’ strategies. The simplest method which can be applied to two or three player games, is finding the intersection of best response curves (reaction curves) by drawing or Algebra. For graphical approach, some geometric techniques have been also proposed to come up with more than two player problems [17]. Algebra can improve the method to solve games with several players, but it can be applied to problems with simple mathematical manipulations. This algorithm is commonly used in Cournot or Bertrand models of electricity markets with linear demand functions, using the first-order condition for maximizing each player’s payoff [1], [18], [19].

Iterative NE search in which players repeatedly maximize their payoff by turn is another method that is applied to more complex problems. The profit maximization problem which is embedded in this method can be solved by local or global optimization algorithms. In literature, local search is more popular and have been employed in [3], [28] and [26], however in [9], a GA-based algorithm is also presented for profit maximization.

In recent years, with development of Soft Computing [23], and increasing growth of Biomimicry [24], and Bioinspired Computing in a variety of applications, there has been a considerable attention to evolutionary game theory and computational intelligence for game learning and simulation of electricity markets [3], [7]-[9], [13], [14], [22], [32], [33]. Coevolutionary programming is the most popular technique for this purpose. In [3], a novel Hybrid Coevolutionary is applied to solve constrained-transmission electricity markets, and in [8], a GA-based coevolutionary algorithm is exploited to simulate a simple electricity pool. Besides coevolutionary algorithms, learning methods in agentbased approach have also been used to study imperfect competition in electricity markets [5], [20], [21]. In fact, these days, agent-based economics is a rigorous opponent of game theory to simulate electricity markets.

Another approach for searching NE is characterization of NEs in terms of minima of a function and then minimizing this objective function. This method was firstly employed in finding mixed strategy NEs [13], [14], but recently a similar technique was introduced in [7] to identify pure NE in games with a large number of players. It seems that more in

investigations are needed to understand the efficiency of this model.

Section 1, provides a quick review for the concept of Nash Equilibrium. In section 2, Coevolutionary Programming to find NE is explained, while Iterative NE Search algorithms are described in section 3. Finally, section 4 summarizes methods of modeling Nash Equilibrium as a minimum of a function. Note that for each section a numerical example is simulated and the results are interpreted.

A general multi-player game consists of an index set = {1, 2, 3, …, N} called player’s

1. Nash Equilibrium set and an index set = {1, 2, 3, …, K} as the stages of the game, showing the allowable strategy spaces = { }, and receive a payoff of (, ), where ∈ number of moves for each player. In each stage, players take strategies from a set of

–  –  –

{ ∗, } is characterized in (2.1).

. Pure strategy Nash Equilibrium (NE) is a point where no player can obtain a higher ∗ profit by unilateral movement. The satisfying NE condition for the combined strategy ∀,∀ ∈,, ≥ (, ) ∗ ∗ ∗ (2.1) As we will use the term local NE in this dissertation, here a definition of that from [3] is

–  –  –

, ∗ ∗ ∗ ∗ (2.2)

–  –  –

2. Coevolutionary Programming In [10], coevlolutioanry algorithm (CEA) is defined as “an evolutionary algorithm that employs a subjective internal measure for fitness assessment.” The term subjective internal measure means that fitness for the individuals are measured based on their interaction with each other and this fitness value influences their evolution in some way.

This is a general definition for coevolutionary algorithm which most the coevolutionary computation researchers agree, however there are controversy on some topics like what precisely is the nature of interaction? Should the interacting individual be in different populations? Do they have to treat concurrently? [10] The answer to these questions is beyond the scope of this survey, but in this thesis, we focus on multi-population models in which the fitness for individuals is measured by their interaction with individuals in other populations. In the following two parts we define Cooperative and Competitive Coevolutionary Algorithms and present coevolutionary frameworks to find Nash Equilibrium for game theory problems.

A. Cooperative Coevolutionary Algorithm In Cooperative CEA, each population represents a piece of a larger problem and the populations evolve their own pieces in interaction with each other to solve the larger problem. A general cooperative coevolutionary framework for is explained in Algorithm 1.

–  –  –

1. For population, all populations

1.1. Initialize population

2. For population, all populations

2.1. Evaluate population with collaborators

3. t:=0

4. do

4.1. For population, all populations 4.1.1. Evolutionary Process to make the next generation 4.1.2. Evaluate next generation with collaborators

4.2. t:= t+1

5. Repeat 4 until terminating criteria is met For evaluating part, each individual is combined with its collaborators from other populations to form a complete solution and the objective function is evaluated.

Terminating criteria can be satisfied by falling short of the acceptable tolerance for changes in strategies or exceeding the maximum number of iterations. In evolutionary process, any evolutionary algorithm (EA) can be exploited, like Genetic Algorithm (GA), Particle Swarm Optimization (PSO), Mimetic Algorithm (MA), Simulated Annealing (SA). We employ Invasive Weed Optimization (IWO), a novel EA proposed by Mehrabian and Lucas [2], for all the evolutionary computation purposes throughout this dissertation (See Appendix A).



Pages:   || 2 | 3 | 4 | 5 |


Similar works:

«SEABROOK CITY COUNCIL NOTICE OF REGULAR CITY COUNCIL MEETING TUESDAY, JANUARY 8, 2013 7:00 PM NOTICE IS HEREBY GIVEN THAT THE SEABROOK CITY COUNCIL WILL MEET ON TUESDAY JANUARY 8, 2013 AT 7:00 PM IN THE SEABROOK CITY HALL COUNCIL CHAMBERS, 1700 FIRST STREET, SEABROOK, TEXAS 77586, TO DISCUSS, CONSIDER, AND IF APPROPRIATE, TAKE ACTION WITH RESPECT TO THE ITEMS LISTED BELOW. THIS FACILITY IS WHEELCHAIR ACCESSIBLE AND ACCESSIBLE PARKING SPACES ARE AVAILABLE. REQUESTS FOR OTHER ACCOMMODATIONS OR...»

«Янко Слава (Библиотека Fort/Da) || http://yanko.lib.ru || slavaaa@yandex.ru || Icq# 75088656 1Сканирование и форматирование: Янко Слава (Библиотека Fort/Da) || http://yanko.lib.ru || slavaaa@yandex.ru || yanko_slava@yahoo.com || Icq# 75088656 || Библиотека: http://yanko.lib.ru/gum.html || Номера страниц внизу update 22.03.06 История развития высших психических...»

«ULTIMATE SAMPLER-WORKSTATION OPERATION MANUAL for Independence 2.0, Independence Basic 2.0, Independence Player 2.0 & Independence Free 2.0 The information in this document is subject to change without notice and does not represent a commitment on the part of yellow tools GbR. The software described by this document is subject to a License Agreement and may not be copied to other media. No part of this publication may be copied, reproduced or otherwise transmitted or recorded, for any purpose,...»

«Massachusetts Department of Elementary & Secondary Education, Office for the Education of Homeless Children and Youth: http://www.doe.mass.edu/mv CHELSEA PUBLIC SCHOOLS National Center for Homeless Education: http://www.center.serve.org/nche MCKINNEY-VENTO HOMELESS EDUCATION ASSISTANCE ACT National Association for the Education of Homeless A guide for parents, guardians, and caregivers Children and Youth: http://www.naehcy.org The goal of the McKinney-Vento Homeless Education Assistance Act is...»

«OECD/G20 Projekt Gewinnverkürzung und Gewinnverlagerung Erläuterung Abschlussberichte 2015 OECD/G20 Projekt Gewinnverkürzung und Gewinnverlagerung Erläuterung Bitte zitieren Sie diese Publikation wie folgt: OECD (2015), Erläuterung, OECD/G20 Projekt Gewinnverkürzung und Gewinnverlagerung, OECD. www.oecd.org/tax/beps-explanatory-statement-2015.pdf Originaltitel: Explanatory Statement, OECD/G20 Base Erosion and Profit Shifting Project. Übersetzung durch den Deutschen Übersetzungsdienst...»

«Genfer Initiative | „Kontexte – eine Chronik“ von Dr. Reiner Bernstein „Kontexte – eine Chronik“ April 2007 Stand: 15.06.07 30. April: Die von der Regierung eingesetzte fünfköpfige Untersuchungskommission unter Vorsitz des ehemaligen Richters am Obersten Gericht von Eliyahu Winograd übergibt die Ergebnisse ihrer Nachforschungen zum Krieg in Libanon 2006 unter dem Titel „Kommission zur Untersuchung des Ereignisfeldzugs im Libanon 2006“ und legt in einer ausführlichen...»

«Change Your Brain, Change Your Life The Breakthrough Program for Conquering Anxiety, Depression, Obsessiveness, Anger, and Impulsiveness Daniel G Amen Three Rivers Press New York Looking Into Anxiety and Fear: The Basal Ganglia Functions of the Basal Ganglia System integrates feeling and movement shifts and smoothes fine motor behavior suppresses unwanted motor behaviors sets the body's idle speed or anxiety level enhances motivation mediates pleasure/ecstasy. The basal ganglia are a set of...»

«Prioritäten des Europäischen Forschungsraums: Sachstand in den Organisationen, die Forschung fördern und betreiben Der Europäische Forschungsraum (EFR) wurde im Jahr 2000 ins Leben gerufen, und Organisationen wie Ihre machen diesen Tag für Tag zur Realität. Allerdings sind noch viele weitere Fortschritte notwendig. Deshalb enthält die Mitteilung der Kommission über Eine verstärkte Partnerschaft im Europäischen Forschungsraum im Zeichen von Exzellenz und Wachstum...»

«Abstracts of Papers Presented in Washington, D.C. Abstracts of Papers Presented at MathFest 2015 Washington, D.C. August 5 – 8, 2015 Published and Distributed by The Mathematical Association of America Contents Invited Addresses 1 Earle Raymond Hedrick Lecture Series.......................................... 1 Hendrick Lecture 1 Wednesday, August 5, 9:30 AM 10:20 AM, Salon 2/3.......................... 1 Hendrick Lecture 2...»

«Journal of Interactive Online Learning Volume 12, Number 1, Spring 2013 www.ncolr.org/jiol ISSN: 1541-4914   A Comparative Study of an Online and a Face-to-Face Chemistry Course Ozcan Gulacar, Texas State University—San Marcos Fehmi Damkaci, State University of New York at Oswego Charles R. Bowman, Texas State University—San Marcos Abstract While online and face-to-face (F2F) courses have been compared in numerous studies, there has been a lack of focus on online chemistry courses. This...»

«Электронное научное издание Альманах Пространство и Время. Т. 2. Вып. 1 • 2013 Electronic Scientific Edition Almanac Space and Time Elektronische wissenschaftliche Auflage Almabtrieb ‘Raum und Zeit‘ Теории, концепции, парадигмы Theories, Conceptions, Paradigms / Theorien, Konzeptionen, Paradigmen УДК 001:165.5 Батурин В.К. Познавательные традиции как инвариант...»

«Stadt Quickborn Kreis Pinneberg Vorhabenbezogener Bebauungsplan Nr. 94 für das Gebiet nördlich der Heinrich-Hertz-Straße und östlich des Himmelmoorweges Begründung Auftraggeberin PLUS BAU Projektentwicklungsgesellschaft mbH & Co. KG Skandinavienallee 3 25479 Ellerau Bearbeiterin Dipl.-Ing. Wiebke Becker, Stadtplanerin Dipl.-Geogr. K. Hachmann-Fichtner, Landschaftsplanung Bokel, den 05.03.2012 Stadt Quickborn Vorhabenbezogener B-Plan Nr. 94 – Stand März 2012 Inhalt...»





 
<<  HOME   |    CONTACTS
2016 www.abstract.xlibx.info - Free e-library - Abstract, dissertation, book

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.