(110b) A Coarse-Grained Approach to Agent-Based Computations: Coarse Bifurcation Analysis, Rare Event Analysis, and a Patch Dynamics Scheme

Over the last years agent-based modeling has become a well-used simulation and modeling approach for a number of applications, varying from ecology (e.g. [1]) to economics and financial systems [2], and from traffic and supply chain networks [3] to biological [4] and social systems [5]. In many of these applications there exists a spatio-temporal gap between the available description level (individual, microscopic-level) and the desired description level (population, system-level). This gap poses a critical challenge in connecting traditional numerical methods (e.g initial/boundary value problem solvers, eigensolvers) with state-of-art agent-based modeling. Traditional computational tools usually require a coarse-grained model in closed form (i.e. macroscopic equations at the population level).

The Equation-Free approach [6, 7] is a systematic computational methodology aimed at extracting coarse-grained, emergent dynamical information by bridging modern fine-scale (e.g. agent-based) modeling with macroscopic, systems-level, continuum numerical analysis. The methodology is termed ?Equation-Free? as it bypasses the derivation of macroscopic evolution equations when these equations conceptually exist but are not available in closed form. This is achieved by using appropriately initialized short bursts of the agent-based simulator to estimate coarse-grained quantities required for continuum numerics (e.g. coarse-grained residuals, actions of coarse-grained Jacobians, etc.).

We illustrate this methodology in a financially motivated agent-based model based on the work of Omurtag and Sirovich [8]. By first constructing what we refer to as the ?coarse time stepper' [7], coarse bifurcation analysis was performed. For qualitatively different parameter sets we observed both saddle-node and pitchfork bifurcations. Conventionally such coarse bifurcation analysis can only be performed when we know the macroscopic equations in closed form. In the second part of the work we illustrate coarse-grained rare event analysis. Due to the intrinsic stochasticity, close to the turning point the dynamics of the system is better described by a stochastic differential equation (SDE) instead of partial differential equation (PDE). We coarse grained the system first using a 1D coarse reaction coordinate based on the dynamical behavior of the system in that parameter region. Then using the Equation-Free approach we constructed the corresponding effective Fokker-Planck equation of the underlying SDE along this coarse reaction coordinate through short bursts of simulation. After that, the mean escape time for the rare events (in this case, the ?explosion' of the distribution of the agents' internal states) was estimated using Kramers' formula. The mean escape time from this coarse-grained approach approximates well the one obtained by brute-force temporal agent-based simulations. The required computational time for the Equation-Free approach can be as little as 3.2% of the one required for the brute-force simulations in our computational experiment.

A data mining technique -diffusion maps [9, 10] - is then applied as an alternative approach to extract the coarse variables (the coarse reaction coordinate, previously identified based on physical intuition). The diffusion map technique is a nonlinear dimensionality reduction technique that systematically extracts dynamically meaningful coarse variables directly from the data generated from simulations. We observed that the intuition based coarse variable showed a good linear correlation with the diffusion map-based coarse variable.

In the third part of this work we illustrate another important building block of the Equation-Free approach ? the patch dynamics scheme [7, 11]. Evolving microscopic evolution laws over long time and large space can be computationally expensive, and sometimes even infeasible. In order to overcome this difficulty, the patch dynamics computational scheme is designed to perform numerical simulations of unavailable equations on macroscopic time and length scales by exploiting smoothness of the macroscopic properties. In the patch dynamics scheme, expensive microscopic simulations are only run in a small fraction of both the space and the time domain. The combined savings in the space and time domain can yield significant overall savings in terms of the computational cost. Furthermore, considering the fact that the microscopic simulations can be executed in parallel using multi-core computer clusters, it can provide us with additional overall savings in terms of the wall-clock time. Currently we are working on applying this scheme to accelerate agent-based simulations. As a start, we applied the patch dynamics scheme to a toy PDE model based on the same agent-based financial market problem, and we have promising initial results. We expect that as more effort is spent and as experience accumulates, the benefits from a patch dynamics scheme in agent-based multi-scale simulations will be more readily realized.

1. E. Blanchart, N. Marilleau, J. L. Chotte, A. Drogoul, E. Perrier, and C. Cambier. Swarm: an agent-based model to simulate the effect of earthworms on soil structure. EUROPEAN JOURNAL OF SOIL SCIENCE, 60(1):13?21, 2009.

2. E. Samanidou, E. Zschischang, D. Stauffer, and T. Lux. Agent-based models of financial markets. REPORTS ON PROGRESS IN PHYSICS, 70(3):409?450, 2007.

3. E. Ilie-Zudor and L. Monostori. Agent-based framework for pre-contractual evaluation of participants in project-delivery supply-chains. ASSEMBLY AUTOMATION, 29(2):137?153, 2009.

4. F. Castiglione, F. Pappalardo, M. Bernaschi, and S. Motta. Optimization of haart with genetic algorithms and agent-based models of hiv infection. BIOINFORMATICS, 23(24):3350?3355, 2007.

5. L. Hamill and N. Gilbert. Social circles: A simple structure for agent-based social network models. JASSS-THE JOURNAL OF ARTIFICIAL SOCIETIES AND SOCIAL SIMULATION, 12(2):?, 2009.

6. I. G. Kevrekidis, C. W. Gear, and G. Hummer. Equation-free: The computer-aided analysis of complex multiscale systems. AIChE Journal, 50(7):1346?1355, 2004.

7. I. G. Kevrekidis and G. Samaey. Equation-free multiscale computation: Algorithms and applications. Annual Review of Physical Chemistry, 60:321?344, 2009.

8. Ahmet Omurtag and Lawrence Sirovich. Modeling a large population of traders: Mimesis and stability. Journal of Economic Behavior Organization, 61(4):562?576, 2006.

9. Coifman, R.R. Lafon, S. Lee, A.B. Maggioni, M. Nadler, B. Warner, F. Zucker, S.W. ?Geometric Diffusions as a Tool for Harmonic Analysis and Structure Definition of Data: Diffusion Maps? Proc. Natl. Acad. Sci. U.S.A. 2005, 102, 21, 7426-7431.

10. Nadler, B. Lafon, S. Coifman, R.R. Kevrekidis, I.G. ?Diffusion Maps, Spectral Clustering and Eigenfunctions of Fokker-Planck Operators? in Advances in Neural Information Processing Systems, MIT Press: Boston, 2005, 955-962.

11. I.G. Kevrekidis, C.W. Gear, J.M. Hyman, P.G. Kevrekidis, O. Runborg, and K. Theodoropoulos, Equation-free multiscale computation: Enabling microscopic simulators to perform system-level tasks, Commun. Math. Sci., 1(2003), pp. 751-762.