Markov Aggregation for Speeding Up Agent-Based Movement Simulations

Abstract

In this work, we investigate Markov aggregation for agent-based models (ABMs). Specifically, if the ABM models agent movements on a graph, if its ruleset satisfies certain assumptions, and if the aim is to simulate aggregate statistics such as vertex populations, then the ABM can be replaced by a Markov chain on a comparably small state space. This equivalence between a function of the ABM and a smaller Markov chain allows to reduce the computational complexity of the agent-based simulation from being linear in the number of agents, to being constant in the number of agents and polynomial in the number of locations. We instantiate our theory for a recent ABM for forced migration (Flee).We show that,even though the rulesets of Flee violate some of our necessary assumptions, the aggregated Markov chain-based model,Markov Flee,achieves comparable accuracy at substantially reduced computational cost. Thus, Markov Flee can help NGOs and policy makers forecast forced migration in certain conflict scenarios in a cost-effective manner, contributing to fast and efficient delivery of humanitarian relief.