Abstract
Discovering and studying emergent phenomena are among the most important activities in social research. Replicating this phenomenon in “the lab” using simulation is an important tool for understanding it. Multi-Agent Systems (MAS) provide a suitable framework for such simulation. When such simulations are used to represent social processes there are necessarily indeterministic and arbitrary aspects, which are typically represented as either random choices (or numbers) or constants chosen by the programmer. Each such ‘choice’ means that the simulation takes one of the possible ‘trajectories’. The implicit theory that a simulation represents is precisely not in the individual choices but rather in the ‘envelope’ of possible trajectories – what is important is the shape of the whole envelope. Typically a huge amount of computation is required when experimenting with factors bearing on the dynamics of a simulation to tease out what affects the shape of this envelope. In this paper we present a methodology aimed at systematically exploring this envelope. Thus it complements methods like Monte Carlo analysis, the inspection of single scenarios and syntactical proof. We propose a method for searching for tendencies and proving their necessity relative to a range of parameterisations of the model and agents’ choices, and to the logic of the simulation language. The exploration consists of a forward chaining generation of the trajectories associated to such a range of parameterisations and agents’ choices. Additionally, we propose a computational procedure that helps implement this exploration by translating the MAS simulation into a constraint-based search over possible trajectories by ‘compiling’ the simulation rules into a more specific form, namely by partitioning the simulation rules using appropriate modularity in the simulation. An example of this procedure is exhibited.
KEYWORDS: Social Simulation, Multi-agent Systems, Model, Proof, Emergence, Tendencies
1. Social Simulation and the Exploration of Simulation Trajectories
A social simulation necessarily abstracts from some idea about processes that produce social phenomena. Typically this means that: firstly, many of the simulation parameters will be in essence chosen arbitrarily and, secondly, that there will be indetermistic choice processes in the simulation to ‘stand in’ for processes which we do not want to simulate. In particular a pseudo-random number generator often ‘stands in’ for some aspect of a real choice made by a social actor or some unpredictable aspect of the target environment. One can think of each choice as resulting in a branch point in the simulation – where the simulation trajectory ‘branches out’ into a separate trajectory for each possibility. The intended content of the simulation is exactly not the individual trajectories, but the envelope of these trajectories.
It may be that every branch diverges from the others so that the result is completely contingent upon the exact choices made. On the other hand it may be that all branches share a common tendency or converge to the others in certain aspects. This commonality could be explicitly ‘forced’ by the design of the simulation in the form of an explicit constraint: for example if a room has only one exit then the actors in that room may all exit by the same door eventually whatever the nature of their individual choice processes. In other simulations the commonality is emergent in the sense that it is difficult to explain the commonality between possibilities in terms of the simulation design – this is what we call emergent tendencies. This paper documents some steps in the search for ways to understand such emergent tendencies.
A simulation study can have many purposes, including these: it may help in the understanding of some phenomena and also it may inform the design of future simulations. Exploring possible simulation trajectories and analysing the resulting dynamics of the simulation are central to both these tasks. Usually there is a trade-off between the richness of the study in terms of the number of explored trajectories (sometimes related to how fine-grained the model is) and the amount of required computational resources. The finer the model the more “realistic” the simulation model will be, but also the more intricate the analysis of the simulation will be.
A typical case where this analysis is crucial is in Multi-Agent Based Social Simulation. There, modellers may attempt to generate in the lab certain “complex” behaviours in a whole population as the result of the interaction of simpler. Unforeseen behaviour of individuals and unpredictable tendencies in the behaviour of the whole population can arise [4].
The lack of alternative methodologies and tools for appropriate exploration and analysis of the dynamics of a simulation are presently a factor, which limits the comprehension of emergent tendencies. Present methods include examining individual trajectories as in Scenario Analysis [3] and statistical sampling as in Monte Carlo techniques [12]. Each of these has its limitations. It is our purpose in this paper to complement these with an alternative way of exploring and analysing the simulation by systematically and automatically mapping the envelope of all possible trajectories in a substantial fragment of a simulation.
2. Enveloping Tendencies in Simulation Trajectories: a Constrained Search over Possible Models
The traditional methods for examining simulation trajectories are: Scenario Analysis and Monte Carlo techniques.
Via Scenario Analysis trajectories are inspected one at a time and as many alternatives as possible examined. Nevertheless, it is usually unviable to map all the possibilities, as the number of alternative trajectories is far too large. Additionally, the high amount of data increases the difficult task of searching for exceptional behaviour displayed by (groups of) agents in a simulation. Moreover, it is left up to the modeller to make conclusions about the persistence and sensitivity of certain behavioural outcomes with respect to a certain range of the factors.
On the other hand, a Monte Carlo analysis explores the dynamics of the simulation via statistical analysis of quantitative change (or quantitative measures of qualitative changes) observed in a sample of trajectories. The sample is done over the range of possibilities given by random variables introduced in the model to simplify uncertainties. The difficulties with this are that: it tells us what is a probable outcome rather than what is a necessary outcome and it can involve the use of inappropriate statistical assumptions.
2.1 Constrained exploration of trajectories
We propose the use of an exhaustive constraint-based search over a range of possible trajectories in order to establish the necessity of postulated emergent tendencies. Thus a subset of the possible simulation parameterisations and agent choices are specified; the target emergent tendencies are specified in the form of negative constraints; and an automatic search over the possible trajectories performed. The tendencies are shown to be necessary with respect to the range of parameterisations and indeterministic choices by first finding a possible trajectory without the negative constraint to show the rules are consistent and then showing that all possible trajectories violate the negation of the hypothetical tendency when this is added as a further constraint. (See figure 1).
2.2 Characterising the envelope of tendencies
In order to distinguish between the exceptional and the representative in a simulation, we will formally describe the envelope of certain tendencies in a simulation. This might be done by:
· Certain properties satisfied by the observed tendency.
· A mathematical description of a subspace of the tendencies or of a subspace given a bound of the tendencies.
· Representative or typical instances of such a tendency.
· A mapping from the setting of trajectories, as given by the alternative arrangement of parameters and agents’ choices, to certain knowledge (maybe properties) about the tendency: (parameters X choices)à (know. of the tend.)
2.3 Proving the necessity of a tendency
We want to be able to generalise about tendencies
going from observation of individual trajectories to observation of a group of
trajectories generated for certain parameters and choices. Actually, we want to
know if a particular tendency is a necessary consequence of the system or a
contingent one. For doing this we propose to translate the original MAS
along with the range of parameterisations and agents’ choices into a platform
(described in the next section) where the alternative trajectories can be
unfolded. Each trajectory will correspond to a possible trajectory in the
original MAS. 
Once
one trajectory is shown to satisfy the postulated tendency another set of
parameters and agents’ choices is selected and the new trajectory is similarly
checked. If all possible trajectories are successfully tested, the
tendency is proved to be necessary relative to the logic of the
simulation language, the range of parameterisations and agents’ choices.
The idea is to translate the MAS into a constraint-based platform in an automatic or near automatic way without changing the meaning of the rules that make it up in order to perform this automatic testing. In this way a user can program the system using the agent-based paradigm with all its advantages; inspect single runs of the system to gain an intuitive understanding of the system and then check the generality of this understanding for fragments of the system via this translation into a constraint-based architecture.
In the example shown below, all trajectories are explored for one combination of parameters, eight agents’ choices per iteration and seven iterations. A simple tendency was observed characterised by a mathematical description of its boundaries. This characterisation was handled as a theorem. The theorem was proved to be necessary following a procedure similar to the one described in the previous paragraph.
2.4 What is new in this model-constrained methodological approach
It is our goal in this paper to propose an alternative approach for exploring and analysing simulation trajectories. It will allow the entire exploration and subsequent analysis of a subspace of the whole space of simulation trajectories. We are suggesting the generation of trajectories in a semantically constrained way. Constrictions will be context-dependent (over the semantics of the trajectory itself) and will be driven via the introduction of a controller or meta-module.
Like Scenario Analysis, the idea is to generate individual trajectories for different parameterisations and agents’ choices but unlike Scenario Analysis the exploration is constrained to only certain range of parameters and choices.
Akin to Monte Carlo techniques it explores only part of the total range of possible trajectories. But, unlike Monte Carlo studies it explores an entire subspace of (rather than some randomly generated sample) trajectories and is able to give definitive answers for inquires related to the dynamics of the simulation in that subspace.
3. Towards the implementation of a suitable platform for the envelope of trajectories: using SDML and Declarative Programming Paradigm
SDML (Strictly Declarative Modelling Language) [8] is the declarative Multi-Agent System in which we have developed our experiments. As a source of comparisons and ideas, we have also programmed our model in a Theorem Prover [2,7,10,11]
In general, declarative programming (and in particular SDML) offers desirable features for simulation experiments as compared to imperative programming. For the social simulation community those features seem to be of particular interest when facilitating the exploring and analysis of the dynamics of the simulation [9].
3.1 Some characteristics of Declarative Programming
· Modularity. Any part of the model is constructed as a group of standardised units (i.e. rules) allowing flexibility and variety in use. The declarative paradigm facilitates a greater level of modularity than the imperative paradigm because the control of the program is separated from the content. This flexibility is useful both when representing the static structure of the system and when generating the dynamics of the simulation. In our case, it facilitates the introduction of alternatives for agents’ choices and parameters of the model.
· Expressiveness. Effective conveyance of meaning is a consequence of the representation of the system as linguistic clauses on a set of databases. It facilitates the interpretation of a set of social phenomena into a simulation by allowing the dual interpretation of clauses as pseudo-linguistic tokens and as entities to be computationally manipulated.
· Easier analysis. Context situated analysis of detailed data, tracks of trajectories as well as analysis of group of trajectories is much more straightforward than in imperative programs because the resulting databases can be flexibly browsed and queried.
·