Project description
In the last ten years the word market (in Swedish ``marknad'')
has become one of the most frequently cited in
the media, and the phenomenon it describes has risen
to a dominating, some would say overbearing or crushing,
importance.
Yet it is an object which is very poorly understood in
fundamental terms.
The traditional viewpoint of
economic theory is that market behavior can be
understood in terms of equilibrium theory, but, as is evident
from everyday life, real markets are dynamic and
volatile, and speculation bubbles are not uncommon.
The objective of this project is to bring methods
from modern theoretical physics, scientific computing
and nonlinear dynamics to bear on the
evolution and prediction of markets.
In Stage~1, the participants are three
physicists with a background in nonlinear dynamical systems,
complex adaptive systems, and scientific computing,
and two computer scientists with backgrounds
in symbolic computing and numerical analysis.
Curricula Vitae are attached.
The project will initially be tied to the economics
community through contacts with the economics program
at the Santa Fe Institute, where M. N. is a member of
the External Faculty. This program, funded by Citicorp/
Citibank since its inception in 1988, has a number of
well-known economists as participants (e.g., Ken Arrow,
Brian Arthur, William Brock, John Geanakoplos), and has
fostered several successful collaborations between physicists,
computer scientists, and economists, e.g., on the dynamics
of double auctions. During
the first year of the project, collaborations will
also be established with Swedish economists, both in academia
and in the commercial sector.
Artificial markets are ensembles of computer strategies that
compete by buying and selling commodities. A strategy that over
time enriches itself at the expense of the competitors is deemed
successful. Some studies of this kind have involved competition
between hand-designed programs, such as in the double auction
tournament at Santa Fe Institute in 1990, where, e.g., traders, economists,
and computer scientists submitted strategies.
A more sophisticated but computationally highly expensive approach
is to automatically explore the space of trading strategies
without introducing biases, e.g., through a stochastic
process which emulates natural selection.
Large scale numerical simulations of this kind
form a natural link between the rigorous results
of mathematical economists and the study of real
data, somewhat similar to the natural interplay
between theory, numerical simulation, and experiments
found in natural science.
We intend to construct different artificial markets
with a large number of actors. Some questions to be asked are:
- The behaviour of markets with two or more commodities
are exchanged: in which situations are prices (measured
in terms of one commodity, say 'gold') stable?
In which situation do prices fluctuate periodically?
In which situations do prices fluctuate chaotically or
abruptly? Under what circumstances do intermittent
phenomena such as volatility clustering occur?
- The dependence on the price-setting mechanism:
does the type of auction, simple sealed bid, double
bid etc., influence the price dynamics?
Is there an influence of trading taking
part continuously or at fixed time intervals?
- The influence of 'speculators', agents that buy and
sell but do not in themselves produce: when are markets
stabilized by the introduction of speculators? When do
markets become more unstable by the introduction
of speculators?
- What are the effects of introducing speculators
engaged in option trading on the markets? Are there situations
where it leads to instability?
- Effects of competition between speculators of
different types: which strategies survive over time?
Development of adaptive algorithms
of speculators by survival of the fittest.
The computational implementation of these systems
consists of a large number of communicating economic
agents, which all compute their future actions depending on
the behavior on the other agents in the system.
The IBM SP-2 at PDC will be well suited for this type
of simulation.
Another situation that can be studied in this framework
is that of pricing dynamics in oligopolistic markets, such
as gasoline or air travel, where price wars are common
occurrences. This situation differs from that above in that
the actions of each participant significantly affects the market.
Using game theory, it can be modeled in terms of games similar
to a repeated $n$-person Prisoner's Dilemma, but with
continuous actions.
A computer tournament for strategies
for a 3-person game of this kind was carried out at MIT by Fader and
Hauser, but more systematic explorations of this and
more complex models of oligopolies have not yet been
carried out, in part because of the computational complexity
involved in dealing with continuous games. This work
builds naturally on previous work by one of us on the
evolutionary dynamics in strategy space for the infinitely
iterated 2-person Prisoner's Dilemma.
Prediction is arguably the final goal of science.
The ability to predict is limited by noise, lack of
knowledge of the laws of evolution and uncertainties
in the initial conditions.
It is also limited by deterministic chaos, or
inherent instablities in a system that
applify small perturbations: for practical purposes prediction
is here only possible for a finite time.
During the last twenty years, great
progress has been made
in understanding the dynamics of low-dimensional chaotic
systems.
More recently, this has also resulted in the
development of new methods for prediction, which allow
separation of the effects of deterministic chaos and noise
(and thus prediction on short time scales)
in time series which at first sight may appear stochastic.
Extending these methods to situations where noise dominates,
and to very high-dimensional dynamics, is a very active
topic of research at present.
Prediction is of great practical
interest in fields such as climatology and meteorology.
Predictability
in such high-dimensional systems, that can be described
by systems of coupled non-linear PDE's,
is not like the
simple constant time horizon that one finds
in low-dimensional chaotic
dynamics.
Lack of uniformity in the dynamics of
the degrees of freedom, and in
the couplings between them,
are essential
ingredients: one has to ask for predictability of what
quantity against what perturbation.
In addition there exists situations where the system,
say the daily temperature in a high-pressure stretch in summer,
is overall relatively well predictable, and other situations,
say the proverbial weather in April,
when the predictability time is much shorter than normal.
Artificial markets provide nontrivial data sources
on which to develop and test methods of prediction.
We intend to use
techniques from nonlinear dynamics to develop
an understanding of these markets,
as high-dimensional dynamical systems with noise, in particular
to look for
observables that characterize the degree of predictability.
In this connection, we propose to develop and implement methods for
the following approaches to data analysis:
- Develop methods to analyze very noisy data looking for weak
mean trends;
- Identify relevant observables in very high-dimensional situations;
- Look for predictability, and signs of predictability;
- Evolve technical trading rules using data from financial
markets.
A second aspect of this question is related to the introduction
of speculators using strategies that change by adaptive evolution.
If the market dynamics is in part predictable,
then an agent that can use and asses that information
is in the position to exploit transient arbitrage opportunities.
We intend to pursue collaboration with a trading firm
in the study of applications of prediction algorithms
to real financial data (this could also provide a source of
on-line data), and also to investigate applications of
evolutionary approaches to technical trading rules.
Predicting markets could also mean predicting quantities
other than prices. An improved understanding of the time
series properties of market data could for example lead
to predictions of volatility, which could improve strategies
for risk elimination.
The implementation of sophisticated non-linear time series
prediction tools in a parallel environment is also likely to have
many practical applications in situations where prediction
is somewhat less difficult than in the market case, such as
other economic forecasting tasks.
Artificial markets also have applications in computer
science. We intend to investigate the use of a market economy
for coordination of distributed problem solving in multi-agent
environments. This would be one way to achieve collaborative
behavior in a system where agents act according to their own
self-interest. In particular, this may turn out to be a
useful approach in situations where software systems are
built from reusable agents.
Similar approaches have been tried for the simpler problem
of distributing a single resource such as computer time
or network bandwidth (e.g., at Xerox PARC). The credit
assignment mechanism in John Holland's classifier systems
also works through a simplistic economic mechanism.
The market economy as a programming paradigm has been
further explored by Michael Wellman (Michigan).
We intend to emphasize interactions between adaptive
rather than hand-designed agents, where the adaptive
process is modeled through simulated evolution. The
use of evolutionary processes for program design has
been extensively explored recently following the pioneering
work by Koza, but so far little has been done in a
parallel setting.
A system for concurrent genetic programming using a
broadcasting process calculus (Prasad's TCBS) and a
modern functional language (Haskell) as a basis is
being developed at CTH by M. N. and students, and could
be viewed as a first step towards a problem solving
society of genetically adapting agents. This work will
provide useful experience for phase 2 of this project.
- Implement simulations of artificial markets
with predefined classes of agents in a parallel
environment. Study the time series properties of
the resulting market data, with special emphasis
on qualitative changes in market behavior.
- Develop parallel versions of existing algorithms
for time series prediction based on non-linear dynamical
systems theory, and apply these to characterize the time
series properties of the artificial markets in 1.
- Perform an initial exploratory study of the predictability
of real market data using the software developed under 2.
- Start development of a parallel implementation
of a market economy for regulating collective problem solving
among evolving independent agents.
- Expand the study of artificial markets to include
a larger degree of adaptability among agents, so that
even entirely new organizational structures can emerge
(such as trade with derivatives).
Consider a wide range of types of markets, both complete
simple markets and of dynamics of various kinds of auctions.
- Develop new methods for prediction based on non-linear
systems theory, in particular methods relevant to very noisy
data, and methods for identifying relevant observables in
very high-dimensional data.
- Perform an in-depth study of the predictability of
real market data, including not only market time series but
also external data. Explore applications of our prediction
algorithms to other prediction tasks of commercial relevance.
- Develop a parallel implementation of a simulation
of coevolution of pricing strategies in an oligopoly.
Study actual market data and attempt to extract strategies
from data.
- Study the application of artificial markets to computer
science, in particular collaborative problem solving among
multiple agents acting in their own self-interest. Consider
a range of application problems, in particular in distributed
control.
General motivation