%---------------------------------------------------------
% General formatting directives

\def\mail{meyer dmeyer@chonji.ucsd.edu}\def\prange{0 0}
\documentclass{article}	% Tell LaTeX the document type
\usepackage{amsmath}	% Macros for fancy math if needed
\usepackage{graphicx}	% Macro for graphics if needed
\input ICCSsty.tex	% Load style  for ICCS

%---------------------------------------------------------
% Give data to appear in the title section

\title{Towards the global:  complexity, topology and chaos in 
       modelling, simulation and computation}

\author{David A. Meyer%
\thanks{This paper reports on part of a collaborative project with 
        Thad Brown, Gary Doolen, Brosl Hasslacher, Ronnie Mainieri 
        and Mark Tilden.  I also thank Mike Freedman, Melanie Quong, 
        Leslie Smith and Peter Teichner for discussions on various 
        aspects of this work, and Bruce Boghosian for inviting me to 
        speak in the modelling and simulation session at the ICCS.  
        I gratefully acknowledge support from the John Deere 
        Foundation and from DISA.}
 \affil{Center for Social Computation, Institute for Physical 
        Sciences, and}\par
 \affil{Project in Geometry and Physics, Department of 
        Mathematics,}\par
 \affil{University of California/San Diego, La Jolla, CA 92093-0112}}

\date{14 October 1997}

\abstract{
Topological effects produce chaos in multiagent simulation and 
distributed computation.  We explain this result by developing three 
themes concerning complex systems in the natural and social sciences:  
({\it i\/})  Pragmatically, a system is complex when it is represented 
{\em efficiently\/} by different models at different scales.  
({\it ii\/})  Nontrivial topology, identifiable as we scale towards 
the global, {\em induces\/} complexity in this sense.  ({\it iii\/})  
Complex systems with nontrivial topology are typically chaotic.}

% Here is the document

%---------------------------------------------------------
% macros for this particular paper; no need to put in your paper,
% but put here any macros you define

\font\bbb=msbm10                                                
\def\C{\hbox{\bbb C}}
\def\N{\hbox{\bbb N}}
\def\R{\hbox{\bbb R}}
\def\Z{\hbox{\bbb Z}}

\def\AAM{{\sl Advances in Appl.\ Math.}}
\def\ACMCS{{\sl ACM Comput.\ Surveys}}
\def\AcM{{\sl Acta Math.}}
\def\AI{{\sl Artif.\ Intell.}}
\def\AJPS{{\sl Amer.\ J. Pol.\ Sci.}}
\def\AM{{\sl Advances in Math.}}
\def\AnM{{\sl Ann.\ Math.}}
\def\AMM{{\sl Amer.\ Math.\ Monthly}}
\def\ANASP{{\sl Ann.\ Scuola Norm.\ Sup.\ Pisa}}
\def\ARFM{{\sl Ann.\ Rev.\ Fluid Mech.}}
\def\ANYAS{{\sl Ann.\ NY Acad.\ Sci.}}
\def\AP{{\sl Ann.\ Phys.}}
\def\APS{{\sl Acta Physica Slovaca}}
\def\BAMS{{\sl Bull.\ Amer.\ Math.\ Soc.}}
\def\BLMS{{\sl Bull.\ Lond.\ Math.\ Soc.}}
\def\BS{{\sl Behav.\ Sci.}}
\def\BSTJ{{\sl Bell System Tech.\ J.}}
\def\CACM{{\sl Commun.\ ACM}}
\def\CE{{\sl Comput.\ Econom.}}
\def\CDE{{\sl Contrib.\ Diff.\ Eq.}}
\def\CMP{{\sl Commun.\ Math.\ Phys.}}
\def\CPAM{{\sl Commun.\ Pure Appl.\ Math.}}
\def\CQG{{\sl Class.\ Quantum Grav.}}
\def\CS{{\sl Complex Systems}}
\def\DM{{\sl Discrete Math.}}
\def\E{{\sl Econometrica}}
\def\EA{{\it \'Economie Appliqu\'ee}} 
\def\ESQ{{\sl Econom.\ Studies Quart.}}
\def\FP{{\sl Found.\ Phys.}}
\def\GRG{{\sl Gen.\ Relativ.\ Grav.}}
\def\IEEETSMCB{{\sl IEEE Trans.\ Systems Man Cybernet.\ B}}
\def\IER{{\sl Int.\ Econom.\ Rev.}}
\def\IJMPB{{\sl Int.\ J. Mod.\ Phys.\ B}}
\def\IJTP{{\sl Int.\ J. Theor.\ Phys.}}
\def\IPL{{\sl Info.\ Processing Lett.}}
\def\IM{{\sl Invent.\ math.}}
\def\JACM{{\sl J. ACM}}
\def\JAP{{\sl J. Appl.\ Phys.}}
\def\JCP{{\sl J. Comput.\ Phys.}}
\def\JCR{{\sl J. Conflict Resolution}}
\def\JCSS{{\sl J. Comp.\ Syst.\ Sci.}}
\def\JET{{\sl J. Econom.\ Theory}}
\def\JFM{{\sl J. Fluid Mech.}}
\def\JFMO{{\sl J. Fine Mech.\ Optics}}
\def\JLMS{{\sl Proc.\ Lond.\ Math.\ Soc.}}
\def\JME{{\sl J. Math.\ Econom.}}
\def\JMO{{\sl J. Mod.\ Optics}}
\def\JMP{{\sl J. Math.\ Phys.}}
\def\JMPA{{\sl J. Math.\ Pures Appl.}}
\def\JPA{{\sl J. Phys.\ A}}
\def\JPC{{\sl J. Phys.\ C}}
\def\JPE{{\sl J. Pol.\ Econom.}}
\def\JPSJ{{\sl J. Phys.\ Soc.\ Japan}}
\def\JRAM{{\sl J. Reine Angew.\ Math.}}
\def\JSP{{\sl J. Stat.\ Phys.}}
\def\LAS{{\sl Los Alamos Science}}
\def\MA{{\sl Math.\ Ann.}}
\def\MARS{{\sl M\'emoires de l'Acad\'emie Royale des Sciences}}
\def\MMP{{\sl Monat.\ Math.\ Phys.}}
\def\MST{{\sl Math.\ Systems Theory}}
\def\Na{{\sl Nature}}
\def\NP{{\sl Nucl.\ Phys.}}
\def\NPB{{\sl Nucl.\ Phys.\ B}}
\def\O{{\sl Order}}
\def\PAMS{{\sl Proc.\ Amer.\ Math.\ Soc.}}
\def\PCPS{{\sl Proc.\ Camb.\ Phil.\ Soc.}}
\def\PA{{\sl Physica A}}
\def\PD{{\sl Physica D}}
\def\PJM{{\sl Pacific J. Math.}}
\def\PLA{{\sl Phys.\ Lett.\ A}}
\def\PLB{{\sl Phys.\ Lett.\ B}}
\def\PNAW{{\sl Proc.\ Nederl.\ Akad.\ Wetensch.}}
\def\PPMSJ{{\sl Proc.\ Phys.\ Math.\ Soc.\ Japan}}
\def\PRp{{\sl Phys.\ Rep.}}
\def\PR{{\sl Phys.\ Rev.}}
\def\PRA{{\sl Phys.\ Rev.\ A}}
\def\PRB{{\sl Phys.\ Rev.\ B}}
\def\PRD{{\sl Phys.\ Rev.\ D}}
\def\PRE{{\sl Phys.\ Rev.\ E}}
\def\PRL{{\sl Phys.\ Rev.\ Lett.}}
\def\PRSE{{\sl Proc.\ Roy.\ Soc.\ Edinburgh}}
\def\PRSLA{{\sl Proc.\ Roy.\ Soc.\ Lond.\ A}}
\def\PSAM{{\sl Proc.\ Symp.\ Appl.\ Math.}}
\def\PTP{{\sl Prog.\ Theor.\ Phys.}}
\def\PTRSLA{{\sl Phil.\ Trans.\ Roy.\ Soc.\ Lond.\ A}}
\def\RAS{{\sl Robotics and Autonomous Systems}}
\def\RES{{\sl Rev.\ Econom.\ Stud.}}
\def\RMP{{\sl Rev.\ Mod.\ Phys.}}
\def\Sc{{\sl Science}}
\def\SCW{{\sl Soc.\ Choice Welf.}}
\def\SIAMJNA{{\sl SIAM J. Numer.\ Anal.}}
\def\SPAWPM{{\sl Sitzungsber.\ Preuss.\ Akad.\ Wiss., Phys.-Math.}}
\def\SPJETP{{\sl Sov.\ Phys.\ JETP}}
\def\SRO{{\sl Sociological Research Online}}
\def\TAMS{{\sl Trans.\ Amer.\ Math.\ Soc.}}
\def\TIEICEJE{{\sl Trans.\ IEICE Japan E}}
\def\TMP{{\sl Theor.\ and Math.\ Phys.}}
\def\YMJ{{\sl Yokohama Math.\ J.}}
\def\ZP{{\sl Z. Physik}}
\def\ZPB{{\sl Z. Phys.\ B}}
\def\ZPC{{\sl Z. Phys.\ C}}


\def\dajm{\hbox{D. A. Meyer}}
\def\luca{\hbox{L. Bombelli}}
\def\rds{\hbox{R. D. Sorkin}}
\def\ljdr{\hbox{\luca, J. Lee, \dajm\ and \rds}}
\def\brosl{\hbox{B. Hasslacher}}
\def\bd{\hbox{\brosl\ and \dajm}}

\def\albrecht{\hbox{A. Albrecht}}
\def\baxter{\hbox{R. J. Baxter}}
\def\deutsch{\hbox{D. Deutsch}}
\def\feynman{\hbox{R. P. Feynman}}
\def\gz{\hbox{G. Gr\"ossing and A. Zeilinger}}
\def\hpdp{\hbox{J. Hardy, Y. Pomeau and O. de Pazzis}}
\def\hdpp{\hbox{J. Hardy, O. de Pazzis and Y. Pomeau}}
\def\mckelvey{\hbox{R. D. McKelvey}}
\def\teich{\hbox{W. G. Teich}}
\def\zurek{\hbox{W. H. Zurek}}

\def\hfb{\hfil\break}

\def\ie{{\it i.e.}}
\def\eg{{\it e.g.}}
\def\etc{{\it etc.}}
\def\etal{{\it et al.}}

%---------------------------------------------------------
\begin{document}
\maketitle

\section{Introduction}\sectlabel{intro}

%--------|---------|---------|---------|---------|---------|---------|
Although the concerns of modelling and simulation can be quite 
different \cite{Segel}, both support a pragmatic definition of 
complexity:  {\em A system is complex if it is represented efficiently 
by different models at different scales.}  This idea is commonplace, 
reflected in the way we organize our understanding of the world around 
us into physics, chemistry, biology, psychology, economics and 
political science at (roughly) increasing size scales.  The goal of 
this paper is to explain a recently demonstrated difficulty with 
multiagent simulations of complex systems at the social science end of 
this spectrum \cite{rMB} by placing it in the context of (possibly 
more familiar) models and simulations of complex systems at the 
natural science end.

%--------|---------|---------|---------|---------|---------|---------|
We begin by showing that this definition of complexity is more than 
subjective.  In \sect{two} we consider the hierarchical algorithm of 
Barnes and Hut for simulation of gravitationally interacting particles 
\cite{rBH}.  Their multiscale algorithm is more efficient, in a very 
precise sense, than na{\"\i}ve direct simulation.  Large scale states
are described by total mass and average position of particles, so the
model is similar at different scales.  We describe this situation as
{\em simplicity}.  For more complicated systems, as we increase in 
scale towards the global, we may identify states with nontrivial 
topology.  The presence of such states can lead to a different and 
more efficient model at the larger scale; {\em topology induces 
complexity}.  

%--------|---------|---------|---------|---------|---------|---------|
The purest example of this phenomenon might be topological geons in 
quantum gravity \cite{Sorkin}:  prime components of the spacelike 
3-manifold comprise localized nontrivial topology and can be modelled 
as particles.  The intellectual heritage of this model includes Lord 
Kelvin's theory of atoms as knotted vortex lines \cite{Kelvin}.  That 
theory was mistaken, of course, but it was motivated by Helmholtz's 
mathematical analysis of hydrodynamical vortices \cite{Helmholtz}.  
Vortices alone {\em are\/} topologically nontrivial states, in terms 
of which the equations for fluid mechanics can be recast and which are 
utilized in very practical vortex simulations of fluid flow 
\cite{Leonard}.  We explain this in \sect{three}, remarking on the 
efficiencies gained by use of a hierarchical algorithm.  While 
demonstrations of improved simulation efficiency are not available for 
all the systems we consider, these two examples reenforce the belief, 
based on the conceptual adequacy of different models at different 
scales, that the systems are indeed complex.

%--------|---------|---------|---------|---------|---------|---------|
Multiagent systems are discrete, in contrast to PDE models for fluid
mechanics.  To develop our theme of topology induced complexity for 
application in the former, we must explain how it can occur in 
non-continuum systems.  In \sect{four} we consider the homogeneous 
sector of a multispecies reaction-diffusion model in 
chemistry/population biology.  This model, analyzed by Ruijgrok and 
Ruijgrok \cite{Ruijgrok}, illustrates our first two themes:  
(discrete) topology induces complexity in the sense of a different 
efficient model at the global scale.

%--------|---------|---------|---------|---------|---------|---------|
The same nontrivial discrete topology---a cycle---is ubiquitous in 
formal models of economics and political science:  In \sect{five} and 
\sect{six} we describe two fundamental results---Sonnenschein, Debreu, 
and Mantel's excess demand theorems \cite{rSMD} and Arrow's voting 
theorem \cite{Arrow}---which guarantee the existence of cycles in 
market and voting models, respectively.  We also expand our third 
theme:  systems with topologically induced complexity are typically 
chaotic.  In particular, we explain the precise mathematical sense in 
which aggregation by voting makes multiagent simulations chaotic 
\cite{rMB}.

%--------|---------|---------|---------|---------|---------|---------|
But the aggregation processes which scale multiagent simulations 
towards the global are usually market mechanisms or voting rules; 
thus such systems are typically complex, and, according to the results 
described in \sect{six}, chaotic.  In the final section we discuss the 
consequences of this phenomenon and mechanisms which might be 
implemented to control it.

\section{Hierarchical efficiency}\sectlabel{two}

%--------|---------|---------|---------|---------|---------|---------|
Simulation of interesting natural or social systems compels careful 
attention to the efficiency of the algorithms used.  Algorithms which 
are exponential in the size of the system are essentially useless, and 
even for polynomial algorithms, decreasing the leading exponent 
reduces runtime by orders of magnitude.  The simulations of concern 
here typically consist of a large number $N$ of fundamental objects 
interacting according to rules which model the dynamics of the system 
under investigation.  Algorithmic efficiency is thus determined by 
runtime as a function of $N$.

%--------|---------|---------|---------|---------|---------|---------|
Consider the problem of simulating the (Newtonian) gravitational 
dynamics of $N$ particles.  Each particle exerts a force on every 
other particle and is subject to the sum of the forces exerted on it 
by all the other particles.  The most straightforward algorithm would 
compute the $N(N-1)/2$ pairwise forces, sum the forces on each 
particle, and then evolve each particle accordingly, at each timestep.
This algorithm involves no approximations beyond the finite precision
computer representation of real numbers; it provides an accurate 
$O(N^2)$ description of the dynamics.

%--------|---------|---------|---------|---------|---------|---------|
Barnes and Hut showed, however, that by aggregating the particles into
a hierarchy of clusters of increasing sizes, the average run time can 
be reduced to $O(N\log N)$ {\em with bounded error\/} \cite{rBH}.  
Their algorithm works by dividing up the volume of space containing 
the particles into a tree of cubical cells:  Starting with a cube 
large enough to contain all the particles, at each timestep consider 
the particles in some (arbitrary) sequence.  While the particle lies 
in the same cube as any previous particle, subdivide that cube into 
eight cubes of half the linear size.  Now assign to each non-empty 
cube a `cluster-particle' with the total mass of the particles in that 
cell, and locate the cluster-particle at the center of mass of those 
particles.  On average, constructing the tree of cells and
cluster-particles requires $O(N\log N)$ steps.

%--------|---------|---------|---------|---------|---------|---------|
The force on a given particle is now computed recursively by working
down the tree:  If a cluster-particle lies in a cube of size $l$, is 
distance $d$ from the particle, and $l/d < \theta$ (a constant), 
compute the force it would exert; if not move down to the next smaller
cluster-particles in the tree and repeat.  This algorithm approximates 
the force on a particle, with bounded error (depending on $\theta$), 
in an average of $O(\log N)$ steps.  The average runtime per timestep 
is thus $O(N\log N)$ for the whole algorithm.

%--------|---------|---------|---------|---------|---------|---------|
In this description `average' refers to possible particle 
configurations with respect to a uniform probability distribution on
the cube.  When the particles are literally clustered, as in the 
simulation Barnes and Hut present of two interacting clusters, 
additional efficiencies obtain.  Even in this case, however, the
larger scale representation is essentially similar to the smaller 
scale one; the system is simple.  

\section{Topology induces complexity}\sectlabel{three}

%--------|---------|---------|---------|---------|---------|---------|
Fluid flow provides our first example of a system with different 
representations at different scales.  Disregarding the fact that real 
fluids are composed of molecules, which are composed of atoms, 
$\ldots$, and should, by virtue of that multiscale description alone, 
be complex systems, let us take the system to be defined by the
Navier-Stokes equations:
%
\begin{align*}
\partial_t v +  v\cdot\nabla v
 &=
-\nabla p + \nu\nabla^2 v                                           \\
\nabla\cdot v &= 0,
\end{align*}
%
together with appropriate boundary conditions.  Here $v$ is the 
velocity field of the (incompressible) fluid, $p$ is the pressure, and 
$\nu$ is the viscosity.  Immense effort has, of course, gone into
simulating the Navier-Stokes equations \cite{rBP}, whose solutions 
range from laminar to turbulent flow.

%--------|---------|---------|---------|---------|---------|---------|
The configuration variable in this system, the velocity field, can be 
topologically nontrivial:  there may be, for example, {\em vortices}, 
\ie, closed loops in the flow.  Their presence is measured by the 
{\em vorticity\/} $\omega := \nabla\wedge v$ \cite{Helmholtz}, in 
terms of which the first equation above can be rewritten as
$$
\partial_t\omega = \nabla\wedge(v\wedge\omega) + \nu\nabla^2\omega,
$$
eliminating the pressure.  The inverse of the Poisson equation 
defining vorticity is the Biot-Savart law; it gives $v$ as a function 
of $\omega$ and allows the system to be reformulated entirely in terms 
of the vorticity.  This is a different, although entirely equivalent, 
model for fluid flow.

%--------|---------|---------|---------|---------|---------|---------|
When the flow is restricted to two dimensions the vorticity has only a
single (orthogonal) component so the configuration variable for the
model is a (pseudo-)scalar field.  As such it can be approximated by
a superposition of delta functions, or more physically, by a 
collection of point vortices with circulations $c_i$:
$$
\omega(r,t) \approx \sum_{i=1}^N c_i \delta\bigl(r - r_i(t)\bigr).
$$
Even before the advent of digital computers Rosenhead simulated fluid 
flow using this approximation \cite{Rosenhead}:  For inviscid flow, 
the velocity of each vortex is the value of the velocity field at its 
present location; this is given in terms of the vorticity field by the
Biot-Savart law.  Notice that a straightforward algorithm for this 
computation would be $O(N^2)$.  Just as in the simulation of 
gravitating particles considered in \sect{two}, the vortex positions 
can then be integrated forward in time.

%--------|---------|---------|---------|---------|---------|---------|
There are several problems with this procedure:  While it is correct 
for inviscid flow, the singularities in the vorticity field make the 
errors in time integration difficult to control when the point 
vortices pass too close to one another.  (We anticipate the results of
\sect{six} by remarking that such systems with only a few vortices 
have been shown to be chaotic \cite{Aref}.)  This problem can be 
resolved to some extent by implementing a `cloud-in-cell' technique 
\cite{Christiansen} which also improves the runtime for solving the 
Poisson equation to $O(N) + O(M\log M)$, where $M$ is the size of an 
approximating spatial mesh.  Alternatively, and at the same time 
modifying the model so as to be able to simulate viscous flow, the 
point vortices can be replaced with `vortex blobs' in which the 
vorticity has a fixed but nonsingular distribution \cite{Chorin}.  
Hald has shown that the error can be controlled in simulations of 
inviscid flow with such models \cite{Hald}.

%--------|---------|---------|---------|---------|---------|---------|
These simulations demonstrate that two dimensional hydrodynamics is
therefore a complex system according to our operational definition:  
Not only are there efficient algorithms at different size scales, as 
presaged by our discussion of gravitating particles, but the system is 
modelled differently at each scale---by a velocity field, by a 
collection of vortices, and by a distribution of vorticity on a mesh.  
Topology will play this role---inducing new models at more global 
scales---for the rest of the discussion.

\section{Finite topology}\sectlabel{four}

%--------|---------|---------|---------|---------|---------|---------|
Vortices in fluids contain cycles---closed continuous flow lines.  But 
continuity of this sort is not necessary for nontrivial topology.  
Moving away from physics to a model for a system in chemistry or 
population biology, consider three species (types of particles) with 
interactions%
%
\footnote{Delightfully, Sinervo and Lively have observed populations
of lizards competing according to very similar rules \cite{rSL}.}
%
$$
A + B  \to 2A, \qquad B + C  \to 2B, \qquad C + A  \to 2C.
$$
We notice immediately that there is a kind of cyclicity inherent in 
this set of reactions.  Ruijgrok and Ruijgrok have analyzed a system
of such particles which are simultaneously interacting according to
$$
A + 2B \to 3B, \qquad B + 2C \to 3C, \qquad C + 2A \to 3A,
$$
with relative rate $\alpha$ \cite{Ruijgrok}.

%--------|---------|---------|---------|---------|---------|---------|
Since each of the reactions conserves particle number we can normalize
to population densities $A+B+C = 1$.  Since $A$, $B$ and $C$ are all
positive, the configurations of the system can be represented by 
points in the interior of an equilateral triangle with side 
$2/\sqrt{3}$:  for any point inside this triangle the sum of the 
altitudes $A$, $B$ and $C$ to the three sides is 1.  The evolution of
the system is a flow on the triangle, described by the system of three
ODEs obtained from 
$$
\dot A = A(B-C) + \alpha A(AC-B^2)
$$
by cyclic permutations of $(ABC)$.

%--------|---------|---------|---------|---------|---------|---------|
Notice that the center of the triangle $A=B=C=1/3$ is an equilibrium
point.  When $\alpha = 0$, the product $P := ABC$ is left invariant by
the flow:  all the solutions are periodic orbits along the closed
curves $P = {\rm const}$.  In general, 
$$
\frac{1}{P(t)}\frac{{\rm d}P(t)}{{\rm d}t} 
 = -\frac{9}{4}\alpha r^2(t),
$$
where $r(t)$ is the distance from the center of the triangle.  Thus
for $\alpha < 0$, the center $(1/3,1/3,1/3)$ is a stable equilibrium,
while for $\alpha > 0$ it is unstable; the $\alpha = 0$ model is not
structurally stable.

%--------|---------|---------|---------|---------|---------|---------|
Although we have not introduced the formalism for finite topological 
spaces, this analysis motivates identification of the cyclicity of the 
two sets of reactions as topological nontriviality; certainly this
cyclicity can induce cycles in the evolution of the system.  Moreover,
in the sense that the system can be represented globally as a cycling
`ecology', or one at a stable or unstable equilibrium, rather than 
only in terms of individual, interacting particles, it is complex.

\section{Economics and politics}\sectlabel{five}

%--------|---------|---------|---------|---------|---------|---------|
Thinking of the preceding system as a model in population biology 
leads us towards social science models of multiple interacting agents.  
By now we should expect cycles to occur in these systems---and they 
do, in very similar ways.  We begin by considering an example, due to 
Scarf \cite{Scarf}, which indicates difficulties with the general 
equilibrium model in economics \cite{Walras}.

%--------|---------|---------|---------|---------|---------|---------|
In this model there are multiple agents with initial endowments 
$w_i \in \R^k_{\ge0}$, where the components of $w_i$ represent amounts
of $k$ goods.  The prices of these goods are represented by another 
vector $p \in \R^k_{\ge0}$, so the initial wealth of agent $i$ is
$p\cdot w_i$.  By exchanging goods according to prices $p$, agent $i$
can afford any commodity bundle $x \in \R^k_{\ge0}$, provided 
$p\cdot x \le p\cdot w_i$.

%--------|---------|---------|---------|---------|---------|---------|
The agents also have preferences among the different goods, modelled
by {\em utility functions\/} $u_i : \R^k_{\ge0} \longrightarrow \R$; 
$u_i(y) \ge u_i(x)$ means that agent $i$ prefers commodity bundle $y$ 
to bundle $x$.  We assume that for each agent $i$, 
$\{y \in \R^k_{\ge0} \mid u_i(y) \ge u_i(x)\}$ is a strictly convex
set and that $\nabla u_i \in \R^k_{>0}$.  At given prices $p$, agent
$i$ maximizes utility with a commodity bundle $x_i(p)$ satisfying
$\lambda p = \nabla u_i\bigl(x_i(p)\bigr)$, for some $\lambda > 0$;
this bundle is the agent's {\em demand}.  Notice that any rescaling of
$p$ can be absorbed into $\lambda$; we follow tradition and rescale so
that $p\cdot p = k$, although we could equally well rescale $p$ so 
that $p\cdot (1,\ldots,1) = 1$; in either case we refer to the 
{\em price simplex\/} of possible price vectors.  The {\em excess 
demand\/} of agent $i$ at prices $p$ is $x_i(p) - w_i$; the 
{\em aggregate excess demand\/} 
$v(p) := \sum_i\bigl(x_i(p) - w_i\bigr)$ is a continuous vector field
on the price simplex.

%--------|---------|---------|---------|---------|---------|---------|
The aggregate excess demand defines a flow on the price simplex 
according to $\dot p = v(p)$.  That there is always an equilibrium 
point $v(p) = 0$ for such a flow is a consequence of Brouwer's fixed
point theorem \cite{Brouwer}; this is the {\em topological\/} content 
\cite{Uzawa} of the Arrow-Debreu approach to the existence of 
competitive equilibria \cite{rAD}.  Scarf demonstrated, however, that 
such equilibria can be globally unstable \cite{Scarf}:  Consider the 
utility function in a $k = 3$ good economy defined by 
$u_1(x) = \min (x_1,x_2)$.  Suppose this is the utility function for 
agent 1 and that there are two more agents with utility functions 
obtained from $u_1$ by cyclic permutations of $(x_1,x_2,x_3)$.  Let 
the initial endowments of the three agents be $(1,0,0)$ and its cyclic 
permutations, respectively.  Then the first component of the aggregate 
excess demand is 
$$
v_1(p) = \frac{-p_2}{p_1+p_2} + \frac{p_3}{p_3+p_1};
$$
the other two components are obtained by cyclic permutation of
$(p_1,p_2,p_3)$.

%--------|---------|---------|---------|---------|---------|---------|
The center point $p_1 = p_2 = p_3 = 1$ is an equilibrium point and, 
just as in the $\alpha = 0$ case of the example discussed in the
preceding section, the product $p_1p_2p_3$ is left invariant by the 
flow.  Thus the system has no stable equilibrium.  While the utility 
functions used in this example are convex, but not strictly convex, 
and the initial endowments are at an extreme, Scarf showed that there
is a family of such models (just as there was in \sect{four}) which 
have strictly convex utility functions and inital endowments nonzero 
in each good, but which are also globally unstable \cite{Scarf}.

\medskip
%--------|---------|---------|---------|---------|---------|---------|
In this economic model the discrete cycle of utility functions leads
to {\em continuous\/} cyclic orbits just as the discrete cycle of 
reaction equations did in Ruijgrok and Ruijgrok's model.  But suppose
there are only a finite number of states for the system.  This is the
situation in political science models where each agent's utility
function is replaced with a {\em preference order\/} among a finite 
set of alternatives:  a relation, denoted $\ge$, which is 
{\em complete\/} (for all pairs of alternatives $a \ge b$ or 
$b \ge a$) and {\em transitive\/} (if $a \ge b$ and $b \ge c$ then 
$a \ge c$) \cite{Arrow}.  When $a \ge b$ and $b \ge a$, the agent with 
this preference order is {\em indifferent\/} between $a$ and $b$; when 
only $a \ge b$, say, the agent {\em strictly\/} prefers $a$ and we
write $a > b$.

%--------|---------|---------|---------|---------|---------|---------|
The analogue of the aggregate excess demand is a map $f$ from 
preference {\em profiles\/} (lists of the agents' preference orders) 
$p$ to directed graphs $f_p$.  A directed edge $a \leftarrow b$ in 
$f_p$ indicates that for profile $p$ the map $f$ chooses alternative 
$a$ over alternative $b$.  We call $f$ a {\em voting rule\/} if for 
all profiles $p$, $f_p$ is {\em complete\/} (for all pairs of 
alternatives $a \leftarrow b$ or $b \leftarrow a$) and Pareto (if
$a \ge b$ in each preference order in $p$ then $a \leftarrow b$ in
$f_p$).

%--------|---------|---------|---------|---------|---------|---------|
More than 200 years ago Condorcet recognized that there are potential
problems with voting rules, namely that aggregation might produce
cycles rather than a definitive outcome \cite{Condorcet}.  For 
example, suppose that there are three alternatives $\{a,b,c\}$ and 
three agents rank them in the orders $a > b > c$, $b > c > a$, and 
$c > a > b$.  Given a choice between $b$ and $a$, a 2:1 majority 
prefers $a$; if they are offered the opportunity to switch from $a$ to 
$c$, again a majority will vote to do so; finally a majority also 
prefers $b$ to $c$, completing a cycle.  This cycle exists in the 
directed graph $f_p$ corresponding to the majority voting rule; it is 
the discrete analogue of the continuous cyclic orbits we have seen in 
the two preceding systems.

\section{Complexity and chaos}\sectlabel{six}

%--------|---------|---------|---------|---------|---------|---------|
These social science models, therefore, have features in common with 
the natural science models we considered in \sect{two}, \sect{three} 
and \sect{four}.  At the more global scale defined by the aggregation 
mechanisms, the set of agents may be replaced by a cyclic (sub)market 
and a cyclic decision process, respectively.  Of course, if the 
utility functions of the economic agents are such that the aggregate 
excess demand is representable as the excess demand for a single agent 
then the market has a unique stable equilibrium.  Similarly, given a 
voting rule, the preferences of the agents may cohere to the extent 
that there is a definitive outcome; even more simply, the voting rule 
might be {\em dictatorial}, \ie, dependent only on the preferences of 
a single, specified agent.  In all of these cases the model at the 
global scale is similar to the individual agent model; the topology is 
trivial and the systems are simple.

%--------|---------|---------|---------|---------|---------|---------|
We emphasize, however, that complexity is inherent in social 
aggregation:  The theorems of Sonnenschein, Mantel, and Debreu show 
that for two or more goods and at least as many agents, the 
aggregate excess demand can be {\em any\/} continuous vector field on 
the price simplex \cite{rSMD}.  In particular, the flow need not have 
a stable equilibrium:  As we have seen already in two dimensions, even
though the Poincar\'e-Bendixson theorem precludes more complicated 
behaviour \cite{rPB}, the limit set may include cycles.  If there is 
any time dependence from external effects, and in higher dimensional
markets, the Kupka-Smale theorem \cite{rKS} implies that 
{\em chaotic\/} dynamics is structurally stable; systems with a unique 
or stable equilibrium point are far from generic.

%--------|---------|---------|---------|---------|---------|---------|
For completely discrete voting models, Arrow's theorem imples that for 
more than two agents, under a reasonable condition%
%
\footnote{This is the {\em independence of irrelevant alternatives}, 
namely that the relation between $a$ and $b$ in $f_p$ depend only on 
the relations of $a$ and $b$ in the preference orders in $p$.}
%
on voting rules, any which are not dictatorial must contain cycles
\cite{Arrow}.  We recently showed that in the latter situation, not 
only is the system complex, but it is also chaotic in the mathematical 
sense \cite{rMB}:  The {\em topological entropy\/} \cite{rSPAKM}, 
defined to be
$$
\lim_{n\to\infty} 
 \frac{1}{n}\log(\hbox{number of $n$-periodic orbits in $f_p$})
$$
is positive exactly when there is a cycle in $f_p$; beyond identifying
the existence of chaos, it quantifies `how chaotic' the system is.  
Averaged over the space of voter preferences, the topological entropy 
measures the complexity of a voting rule, and averaged over voting 
rules, it measures the (lack of) coherence among voter preferences 
\cite{rMB}.

\section{Consequences}\sectlabel{seven}

%--------|---------|---------|---------|---------|---------|---------|
Aggregation rules define the way models of social systems scale 
towards the global.  The larger scale model may be similar to the 
smaller scale one, as is the case for a dictatorial voting rule, for 
example.  In equivalently simple physical models, rescaling simply 
renormalizes the state variables and their interactions, but 
introduces no new ones.  Complexity emerges when nontrivial topology 
exists at the more global scale.  This is a cycle in each of our 
examples, and it induces qualitatively different models in both 
natural and social systems.

%--------|---------|---------|---------|---------|---------|---------|
The attendant chaos has profound consequences for simulations of these
systems:  Fine grained prediction is impossible---only certain 
statistical properties of the evolution are robust.  This fact is
appreciated heuristically in some of the economics and sociology 
literature \cite{rSB}, but seems to receive less emphasis in 
discussions of specific multiagent simulation platforms 
\cite{rMBLAEA}.  It will, nevertheless, determine to which problems 
such programs can be applied successfully.

%--------|---------|---------|---------|---------|---------|---------|
Systems of multiple software agents, interacting to effect some 
(un)intentional distributed computation, are subject to exactly the
same analysis.  Whether their interactions are decision theoretic 
\cite{rZRER} or market oriented \cite{rWCW}, designers and users must 
be aware of the possibilities for complexity and chaos.  Even when the 
artificial agents are physical---autonomous robots 
\cite{rHT}---attempts at designing coordinated action \cite{rBWM} 
should be informed by these same considerations.

%--------|---------|---------|---------|---------|---------|---------|
Particularly in the context of deploying interacting software or 
hardware agents for some specific task, but also in the context of
modelling or simulating multiagent social systems, success may depend
on controlling the degree of chaos in the resulting complex system.
As we noted at the end of the last section, the topological entropy,
for example, measures how chaotic a system is and allows us to 
identify the sources of complexity, but this alone is insufficient for 
control.  There are several possibilities:  We have primarily 
considered immutable agents; there are also models with adaptive 
agents \cite{rHM} which one might hope to have better generic 
behaviour.  The population biology example of \sect{four}, however, 
models a particular kind of adaptation, so chaos is probably no less 
generic in complex adaptive systems.  Agents with `higher' rationality 
have also been modelled \cite{rGDT}; these are agents which make 
internal models for the behaviour of the other agents with which they 
interact.  This approach, while possibly more realistic for modelling 
human agents, seems to flirt with self-reference and undecidability 
\cite{Godel}, and must, at best, constrain the depth of the internal 
models to achieve acceptable computational efficiency \cite{rVD}.  
Most generally, it seems that models for complex social systems should 
include some form of `back reaction' from the more global aggregation 
scale to the local individual agent scale.  Such a back reaction might 
affect the agents' preferences or the way they interact, but must be 
carefully implemented to model interesting complex systems which 
balance precariously between simplicity and extreme chaos.

{\small
\begin{thebibliography}{99} % Use 99 if you have more than 9 entries
\sectlabel{references}
\let\bib\bibitem

\bib{Segel}
{\sc Segel}, Lee A., 
``The theoretician grapples with complex systems'',
SFI working paper 93-05-032 (1993).

\bib{rMB}
{\sc Meyer}, David A., and Thad A. {\sc Brown},
``Statistical mechanics of voting''.
CSC/IPS/UCSD/UM preprint (1997).

\bib{rBH}
{\sc Barnes}, Josh, and Piet {\sc Hut},
``A hierarchical $O(N\log N)$ force-calculation algorithm'',
\Na\ {\bf 324} (1986) 446--449.

\bib{Sorkin}
{\sc Sorkin}, Rafael D.,
``Introduction to topological geons'',
in Peter G. {\sc Bergmann} and Venzo {\sc de Sabbata}, eds.,
{\sl Topological Properties and Global Structure of Space-Time},
proceedings of the NATO Advanced Study Institute, Erice, Italy,
  12--22 May 1985
(New York:  Plenum 1986) 249--270.

\bib{Kelvin}
{\sc Kelvin}, William H. {\sc Thomson}, Baron, 
``On vortex atoms'',
\PRSE\ {\bf VI} (1867) 94--105.

\bib{Helmholtz}
{\sc Helmholtz}, Herman L. F. von, 
``{\it \"Uber Integrale der hydrodynamischen Gleichungen, welche den
  Wir\-belbewegung entsprechen}'',
\JRAM\ {\bf LV} (1858) 25--55.

\bib{Leonard}
{\sc Leonard}, Anthony, 
``Vortex methods for flow simulation'',
\JCP\ {\bf 37} (1980) 289--335.

\bib{Ruijgrok}
{\sc Ruijgrok}, Th., and M. {\sc Ruijgrok},
``A reaction-diffusion equation for a cyclic system with three
  components'',
\JSP\ {\bf 87} (1997) 1145--1164.

\bib{rSMD}
{\sc Sonnenschein}, Hugo,
``Do Walras' identity and continuity characterize the class of 
  community excess demand functions?'',
\JET\ {\bf 6} (1973) 345--354;\hfb
%
{\sc Mantel}, Rolf R., 
``On the characterization of aggregate excess demand'',
\JET\ {\bf 7} (1974) 348--353;\hfb
%
{\sc Debreu}, Gerard,
``Excess demand functions'',
\JME\ {\bf 1} (1974) 15--21.

\bib{Arrow}
{\sc Arrow}, Kenneth J.,
{\sl Social Choice and Individual Values\/}
(New York:  Wiley 1951).

\bib{rBP}
{\sc Boris}, Jay P.,
``New directions in computational fluid dynamics'',
\ARFM\ {\bf 21} (1989) 345--385;\hfb
%
{\sc Peyret}, Roger, ed.,
{\sl Handbook of Computational Fluid Mechanics\/}
(San Diego:  Academic Press 1996).

\bib{Rosenhead}
{\sc Rosenhead}, L.,
``The formation of vortices from a surface of discontinuity'',
\PRSLA\ {\bf 134} (1931) 170--192.

\bib{Aref}
{\sc Aref}, Hassan, 
``Integrable, chaotic, and turbulent vortex motion in two-dimensional
  flows'',
\ARFM\ {\bf 15} (1983) 345--389.

\bib{Christiansen}
{\sc Christiansen}, J. P.,
``Numerical simulation of hydrodynamics by the method of point 
  vortices'',
\JCP\ {\bf 13} (1973) 363--379.

\bib{Chorin}
{\sc Chorin}, Alexandre J., 
``Numerical study of slightly viscous flow'',
\JFM\ {\bf 57} (1973) 785--796.

\bib{Hald}
{\sc Hald}, Ole H.,
``Convergence of vortex methods for Euler's equations.  II.'',
\SIAMJNA\ {\bf 16} (1979) 726--755.

\bib{rSL}
{\sc Sinervo}, Barry, and Curt M. Lively,
``The rock-paper-scissors game and the evolution of alternative male
  strategies'',
\Na\ {\bf 380} (1996) 240--243.

\bib{Scarf}
{\sc Scarf}, Herbert,
``Some examples of global instability of the competitive 
  equilibrium'',
\IER\ {\bf 1} (1960) 157--172.

\bib{Walras}
{\sc Walras}, Leon,
{\it El\`ements d'\'economie politique pure, ou, Th\'eorie de la 
  richesse sociale\/}
(Lausanne:  Corbaz 1874--7).

\bib{Brouwer}
{\sc Brouwer}, Luitzen E. J.,
``{\it \"Uber Abbildung von Mannigfaltigkeiten}'',
\MA\ {\bf 71} (1912) 97--115.

\bib{Uzawa}
{\sc Uzawa}, Hirofumi, 
``Walras' existence theorem and Brouwer's fixed point theorem'',
\ESQ\ {\bf 12} (1962) 59--62.

\bib{rAD}
{\sc Arrow}, Kenneth J.,  and Gerard {\sc Debreu},
``Existence of an equilibrium for a competitive economy'',
\E\ {\bf 22} (1954) 265--290.

\bib{Condorcet}
{\sc Condorcet}, Marie-Jean-Antoine-Nicolas {\sc de Caritat}, Marquis de,
{\it Essai sur l'application de l'analyse \`a la probabilit\'e des 
     d\'ecisions rendues \`a la pluralit\'e des voix\/}
(Paris:  {\it l'Imprim\`erie Royale\/} 1785).

\bib{rPB}
{\sc Poincar\'e}, Jules Henri, 
``{\it M\`emoire sur les courbes d\'efinies par les \'equations
       diff\'erentielles, I.}'',
\JMPA, {\sl 3.\ s\'erie\/} {\bf 7} (1881) 375--422; 
{\it II.} {\bf 8} (1882) 251--286; 
{\it III.} {\sl 4.\ s\'erie\/} {\bf 1} (1885) 167--244;
{\it IV.} {\bf 2} (1886) 151--217;\hfb
%
{\sc Bendixson}, Ivar,
``{\it Sur les courbes d\'efinies par les \'equations 
       diff\'erentielles\/}'',
\AcM\ {\bf 24} (1901) 1--88.

\bib{rKS}
{\sc Kupka}, Ivan,
``{\it Contributions \`a la th\'eorie des champs g\'en\'erique\/}'',
\CDE\ {\bf 2} (1963) 457--484;\hfb
%
{\sc Smale}, Steve,
``Stable manifolds for differential equations and diffeomorphisms'',
\ANASP, {\sl ser.\ III\/} {\bf 17} (1963) 97--116.

\bib{rSPAKM}
{\sc Shannon}, Claude E.,
``A mathematical theory of communication'',
\BSTJ\ {\bf 27} (1948) 379--423; 623--656;\hfb
%
{\sc Parry}, William,
``Intrinsic Markov chains'',
\TAMS\ {\bf 112} (1964) 55--66;\hfb
%
{\sc Adler}, Roy L., Alan G. {\sc Konheim} and M. H. {\sc McAndrew},
``Topological entropy'',
\TAMS\ {\bf 114} (1965) 309--319.

\bib{rSB}
{\sc S\'eror}, Ann C., 
``Simulation of complex organizational processes:  a review of 
  methods and their epistemological foundations'',
in Nigel {\sc Gilbert} and Jim {\sc Doran}, eds.,
{\sl Simulating Societies:  The Computer Simulation of Social 
  Phenomena\/}
(London:  UCL Press 1994) 19--40;\hfb
%
{\sc Byrne}, David, 
``Simulation---a way forward?'',
\SRO\ {\bf 2} (1997)\hfb
http://www.socresonline.org.uk/socresonline/2/2/4.html.

\bib{rMBLAEA}
{\sc Minar}, Nelson, Roger {\sc Burkhart}, Chris {\sc Langton} and 
  Manor {\sc Askenazi},
``The Swarm simulation system:  a toolkit for building multi-agent
  simulations'',
SFI working paper 96-06-042 (1996);\hfb
%
{\sc Epstein}, Joshua M., and Robert {\sc Axtell},
{\sl Artificial Societies:  Social Science from the Bottom Up\/}
(Cambridge, MA:  MIT Press 1996).

\bib{rZRER}
{\sc Zlotkin}, Gilad, and Jeffrey S. {\sc Rosenschein},
``Mechanism design for automated negotiation, and its application
  to task oriented domains'',
\AI\ {\bf 86} (1996) 195--244;\hfb
%
{\sc Ephrati}, Eithan, and Jeffrey S. {\sc Rosenschein},
``Deriving consensus in multiagent systems'',
\AI\ {\bf 87} (1996) 21--74.

\bib{rWCW}
{\sc Wellman}, Michael P., 
``The economic approach to artificial intelligence'',
\ACMCS\ {\bf 27} (1995) 360--262;\hfb
%
{\sc Cheng}, John Q., and Michael P. {\sc Wellman},
``The WALRAS algorithm:  a convergent distributed implementation of
  general equilibrium outcomes'',
to appear in \CE

\bib{rHT}
{\sc Hasslacher}, Brosl, and Mark W. {\sc Tilden},
``Living machines'',
\RAS\ {\bf 15} (1995) 143--169.

\bib{rBWM}
{\sc Beni}, Gerardo, and Jing {\sc Wang},
``Theoretical problems for the realization of distributed robotic
  systems'',
in {\sl Proceedings of the 1991 IEEE International Conference on 
  Robotics and Automation}, 
Sacramento, CA 9--11 April 1991
(Los Alamitos, CA:  IEEE Computer Society Press 1991) 1914--1920;\hfb
%
{\sc Mataric}, Maja J., 
``Distributed approaches to behavior control'',
in Paul S. {\sc Schenker}, ed.,
{\sl Sensor Fusion V}, 
proceedings of the SPIE conference, {\bf 1828}, 
Boston, MA, 15--17 November 1992
(Bellingham, WA:  SPIE 1992) 373--382.

\bib{rHM}
{\sc Hraber}, Peter T., and Bruce T. {\sc Milne},
``Community assembly in a model ecosystem'',
SFI working paper 96-12-094 (1996).

\bib{rGDT}
{\sc Gmytrasiewicz}, Piotr J., and Edmund H. {\sc Durfee},
``A rigorous, operational formalization of recursive modelling'',
in {\sl ICMAS-95}, Proceedings of the First International 
  Conference on Multi-Agent Systems, 
San Francisco, 12--14 June 1995
(Menlo Park, CA:  AAAI Press 1995) 125--132;\hfb
%
{\sc Tesfatsion}, Leigh,
``A trade network game with endogenous partner selection'',
in Hans M. {\sc Amman}, Berc {\sc Rustem} and 
   Andrew B. {\sc Whinston}, eds.,
{\sl Computational Approaches to Economic Problems\/}
(Boston:  Kluwer Academic 1997) 249--269.

\bib{Godel}
{\sc G\"odel}, Kurt,
``{\it \"Uber formal unentscheidbare S\"atze der {\sl Principia
   Mathematica\/} und verwandter System I.}'',
\MMP\ {\bf 38} (1931) 173--198.

\bib{rVD}
{\sc Vidal}, Jos\'e M., and Edmund H. {\sc Durfee},
``Using recursive models effectively'',
in Michael J. {\sc Wooldridge}, J\"org P. {\sc M\"uller} and 
   Milind {\sc Tambe}, eds.,
{\sl Intelligent Agents II:  Agent Theories, Architectures, and
  Languages}, proceedings of the IJACI'95 Workshop (ATAL), 
Montr\'eal, 19--20 August 1995, LNCS {\bf 1037}
(New York:  Springer-Verlag 1996) 171--186. 

\end{thebibliography}
 }%end \small
\end{document}



