Skip to main content
main-content

Über dieses Buch

I started to deal with genetic algorithms in 1993 when I was working on a project on learning and rational behavior in economic systems. Initially I carried out simulations in an overlapping generations model but soon got dissatisfied with the complete lack of theoretical foundation for the observed behavior. Thus, I started to work on a mathematical representation of the behavior of a simple genetic algorithm in the special setup of an interacting population of economic agents and step by step arrived at the results collected here. However, I believe that much more can and has to be done in this field. I would like to thank Gustav Feichtinger who not only supervised my doctoral thesis but always supported and encouraged me throughout the last few years. Special thanks are also due to K. Hornik, A. Mehlmann and M. Kopel who contributed largely to the work. During the preparation of the monograph I also benefited from helpful comments of A. Geyer-Schulz, G. Rote, G. Tragler and A. Rahman. Special thanks to W. A. Muller from Springer-Verlag for his support. Financial support from the Austrian Science Foundation under contract number P9112-S0Z is gratefully acknowledged.

Inhaltsverzeichnis

Frontmatter

1. Introduction

Abstract
The analysis of mathematical models describing the learning behavior of rational agents has been one of the major topics of economic research for the last few years or even decades. Many different models have been proposed and their analysis has given the researchers some insights into the phenomenon of formation of equilibria in economic systems. On the other hand, the modern development of computer technology has caused the rise of a new dynamic field of research, which deals entirely with the understanding and imitation of human behavior, namely the “artificial intelligence” research. Although there is considerable overlap between these two fields they have long developed in isolation from one another. Only recently the interest of some economists in certain techniques mainly from the AI related field of “computational intelligence” (CI) has increased and has led to the applications of these techniques to economic models.
Herbert Dawid

2. Bounded Rationality and Artificial Intelligence

Abstract
The traditional and most widely used approach for the analysis of economic systems is concentrated on equilibrium behavior. We may say that an equilibrium in the broadest sense is a situation where no agent has any incentive to deviate unilaterally from the current behavior. There are several equilibrium concepts for different classes of economic models but all these concepts rely on similar assumptions about the rationality of the economic agents. Basically two assumptions have to be made in order to state that an economic system will a priori be in equilibrium. First we have to assume that all agents are willing and able to maximize their expected utility and second that all agents have rational expectations. Rational expectations means that all agents have identical and exactly correct beliefs about how everyone will behave. Agents who fulfil both assumptions are often called completely rational.
Herbert Dawid

3. Genetic Algorithms

Abstract
In the rest of this monograph we will deal exclusively with a special technique from the field of computational intelligence research, namely genetic algorithms. Genetic algorithms were developed by Holland [60] in 1975 as a tool to find solutions of optimization problems in poorly understood large spaces. They are based on the genetic processes of biological organisms, especially on the principle of natural selection that has become famous as “survival of the fittest” since the publishing of The Origin of Species by Charles Darwin [29]. Although, this slogan seems to be slightly tautological in the natural environment, where fitness is defined as the ability to survive, it makes good sense in the world of optimization problems, where the fitness of a string is given as the value of the function to be optimized at the argument encoded by the string. GAs proved to be quite successful in finding good solutions to such complex problems as the travelling salesman problem, the knapsack problem, large scheduling problems, graph partitioning problems, but also for engineering problems like the design of bridge structures or the optimal use of power plants. The most famous application is perhaps one of the first large applications done by Goldberg. By using classifier systems based on GAs he was able to generate a control system that managed the flow in the large gas pipeline from Texas to Chicago (Goldberg [48]). In 1989 Goldberg wrote a seminal book dealing with genetic algorithms, that is up to now probably the most widely spread book in this field of research (Goldberg [50]).
Herbert Dawid

4. Genetic Algorithms with a State Dependent Fitness Function

Abstract
In the last chapter we have mainly reviewed existing literature and models, which have proven to be of great importance for the theoretical analysis of genetic algorithms. In this chapter we will deal with a new problem, which has not been dealt with up to now. The analytical models presented in chapter 3 all assume that the genetic algorithm is used to solve an optimization problem for a given non changing fitness function. However, this is not the case if we think of an economic system, like a market, where the payoff of a single market member depends crucially on the actions of the rest of the market. The same argument holds also for two agents playing a normal form game, where the payoff of a strategy depends on the opponents’ strategy. This means that two major aspects of the genetic algorithm will change when it is used to model learning in economic systems. Firstly, the fitness of a single string depends on the state of the whole population. In an optimization problem the fitness values can be written in one r-dimensional vector f, but in economic systems the fitness is given by a r-dimensional function f : S → ℝr, where f k (φ) is the fitness of string k when the whole population is in state φS 1. Secondly, we are no longer interested in the learning of optimal solutions, but we intend to learn equilibria. As the simplest concept of an economic equilibrium we say that the system is in equilibrium if the current action of every agent is optimal under the assumption, that all other agents behave according to the equilibrium. For later reference we give a formal definition of an economic equilibrium in definition 4.1.1. In what follows, we will often stress the term “economic” to distinguish it from dynamic equilibria which we will consider later on.
Herbert Dawid

5. Genetic Learning in Evolutionary Games

Abstract
After having derived some theoretical insights into the long run behavior of genetic algorithms in SDF systems, we will present in this chapter several simulations of the learning behavior of GAs in evolutionary games 1. The theory of evolutionary games was first developed for biological models, but has attracted more and more attention of economists in the last few years. It deals with situations where individuals get some payoff from their interaction with other members of the same population. In general, it is assumed that all individuals have the same set of strategies at their disposal, and that the payoff they receive depends only on the own strategy and the opponent’s strategy. For two-player games the payoffs can be written down in a payoff matrix and we call a game given by the set of strategies and the payoff matrix as a normal form game. We say that a game is an evolutionary game if the payoff of an individual is independent from the fact whether he is the first or the second player in the game. Thus, for every evolutionary game the payoff matrix of the second player is the transpose of the payoff matrix of the first player. In some cases it is assumed that each individual meets only one opponent in each period, where the matching is done randomly. Another possible setup is that every individual will play all other individuals in each period. We assume that the second setup holds, which implies that each individual plays against a virtual player who plays a mixed strategy corresponding to the population distribution.
Herbert Dawid

6. Simulations with Genetic Algorithms in Economic Systems

Abstract
In chapter 5 we presented some simulations of genetic learning in evolutionary games. As it is, evolutionary games are however always a stylized model of an economic system, since no explicit structure of the model is given, but only the payoffs of the different actions in different circumstances. In chapter 3 we argued that economic systems are SDF systems because all the single individuals together determine the state of the economy, which again determines the payoffs of the different actions of the individuals. If we consider evolutionary games we always assume that the payoff of any action is the average of the payoffs which would be attained against all the different individuals (or more accurately against a uniform population acting like this individual) in the population. In other words, if we consider genetic learning in evolutionary games the fitness function is always a linear function of the state of the population. Obviously there are however many economic models where no such linear relationship exists and these differ in the basic structure from evolutionary games.
Herbert Dawid

7. Stability and Encoding

Abstract
The main purpose of these notes is to demonstrate that genetic learning is a plausible model of interaction between economic agents and to study the long term properties of this learning process. Thus we have carried out a dynamical analysis which should answer the key questions for any economic learning rule and have demonstrated the results with examples of economic models. Keeping in mind our behavioral interpretation of the considered process the obtained insights provide information about adaptive learning per se. Besides these economic implications the results of chapter 4 may also be very useful for the appropriate shaping of the algorithm and for the correct interpretation of the results. In this chapter we concentrate on this aspect of genetic learning because we think that our mathematical analysis may be of great help for anyone who actually implements a simulation of an economic system with a GA. In particular we will provide a method which facilitates the learning of economic equilibria in a model. This may be of great importance if we consider simulations in models where the equilibria are not known a priori. In such models a GA may be a useful tool to determine equilibria. Therefore a technique which facilitates the reaching of equilibria is of great importance.
Herbert Dawid

8. Conclusions

Abstract
These notes are intended to contribute to the growing field of research dealing with the use of AI and CI techniques in economics. We have shortly summarized some of the most important contributions of the recent years and have afterwards concentrated on a thorough analysis of a special CI technique, namely genetic algorithms. We have argued that GAs, due to their decentralized structure which very naturally resembles to a group of economic agents and their interactions, are especially well-suited to simulate the behavior of an economic system. Further we have shown how to interpret the single operators contained in a genetic algorithm in an economic sense, but have also pointed out the problems we have with the economic interpretation of certain aspects of the algorithm. The fact that in economic setups the fitness of a single string depends on the current state of the whole population has led us to the conclusion that the analytical models which describe the behavior of a genetic algorithm used to solve an optimization problem can not be applied in an economic system. Perhaps the main results are several propositions describing the limit behavior of a genetic algorithm in systems where the fitness function is state dependent. These theoretical results, but of course also the learning ability of a GA as such, have been illustrated afterwards with several examples from the field of game theory and economics. The simulations showed that our mathematical theory enables us not only to understand but also to predict the behavior of GAs in economic systems. Ilowever these examples made also clear that a local analysis like the one done in chapter 4 will in many cases not be able to explain the complete behavior of the system. In several cases we had to give heuristic explanations for a certain kind of behavior instead of a rigorous mathematical analysis. We have to face the fact that the current insight to high-dimensional non-linear difference equations does not enable us to describe the global behavior of such a system. Nevertheless, we are confident that the application of special theories like the graph theoretical approach taken here in proposition 4.2.1 or the theory of nonlinear dynamical systems will permit further mathematical insights into the behavior of GAs in SDF systems.
Herbert Dawid

Backmatter

Weitere Informationen