Re: Theorems for Agent Based Models (order of sync update)

[address@hidden]

On Mon, 12 Jul 1999, Chris Landauer wrote:

> 
> hihi -
> 
> there are a couple of other styles of agent update that are relevant to Paul's
> question about theorems
> 
> the first one is whether the updates are synchronous or asynchronous (that is,
> does the update cycle go through all the agents in the same order before going
> to the next update cycle, or does it update agents at possibly different rates
> that depend independently only on the agent being updated)
> 
> the next one is whether the agent cycle in the synchronous case goes through
> the agents in the same order each time or not
> 
This should NOT make any difference (as far as I understand); 
synchronicity is supposed to be some sort of parallel updating rule, so
all is supposed to happen at once, 
at the beginning
of a time step the state of all agents is fixed, during the update all
agents get a new state based on the original state of any other agent, at
the end of the time step all agents update their state to the new state.



> the two alternatives in the original question were about whether the agent
> update takes into account updates that have already occurred for agents that
> have already been processed in the cycle, or always uses the values from the
> previous cycle (the latter, for example, is the rule in Conway's Game of Life)

So alternative 1) is synchronous and alternative 2) is asynchronous.

For the async case it does matter what the order is. Also, one can choose
between updating all agents exactly once, or N agents drawn with
replacement. In the latter case some agents (+\- 30%!!) will not be
updated in a given time step, some will
be updated more than once per time step. Apparently, the first case (async
with all agents once) can lead to synchronous effects in the patterns
formed; I know somebody did some work on it but I don't know details (of
work or writer).
This is not to say that one is better than the other; in general results
are better (=more robust) if they do not depend very much on
model peculiarities. Of course, synchronous updating has a lot of
peculiarities ;-)

And then there is a continuum from synchronous to asynchronous; per
time step choose N/k times k agents and update those k agents in a
synchronous manner; k=1 = async, k=N = sync. I know of nobody how used or
studied this.

> 
> in both cases, the original question assumed the synchronous case above, so
> that the updates in each time step are separated from those in other time
> steps - even so, if the order of the agent updates is randomly selected at
> each step, then the activity is much more like the asynchronous case
> 
> it can be proved (i believe) that the asynchronous case and the synchronous,
> random update ordering case will have similar behaviors in the long run - for
> example, they almost never get into loops, whereas the synchronous,
same order
> case can get into loops in its behavior (e.g., the GoL), and often does get
> into many small loops (especially when the agent interaction rules require
> proximity, as the GoL does)
> 
> there are theorems also about the asynchronous case that relate its behavior
> to that of markov chains, thereby providing a lot of computable information
> about their asymptotic behavior

But please remember that Markov chains are also often wrong about lots of
spatial explicit discrete variable/discrete time models when it comes to
predicting asymptotic behavior.

For theorems and such maybe you should look at Ising models and spin-glass
models and such. I doubt however that it is very useful for sparsely
populated or spatial-pattern dependent systems???

(and wasn't it an economist who asked about the theorems? ;-))

Ludo Pagie
address@hidden
Bioinformatics group
Utrecht University
Holland






                  ==================================
   Swarm-Modelling is for discussion of Simulation and Modelling techniques
   esp. using Swarm.  For list administration needs (esp. [un]subscribing),
   please send a message to <address@hidden> with "help" in the
   body of the message.
                  ==================================