Formalization and Metastability Analysis of Agent-Based Evolutionary Models

Abstract

This thesis is concerned with the formal description (Part I) and metastability analysis (Part II) of agent-based evolutionary models. Part I discusses the need for specifations as an intermediate layer between implementations and narrative descriptions of computer-based models. We present the basic structure of a functional framework for the specification of agent-based models of exchange. The focus is to expose the relationship of agent-based models of exchange with existing economic theory. We represent the models as discrete-time Markov processes and show that they differ from stochastic evolutionary games only in that their fitness function is in general not deterministic. We apply the framework to demonstrate how to formulate the research question behind agent-based models of exchange precisely, which establishes a direct relationship with general equilibrium theory. Moreover, we discuss how it constitutes a starting point for formal model analysis and further numerical investigations. Part II presents a novel approach to the analysis of stochastic evolutionary games, which are simple agent-based models. We motivate this approach by the observation that stochastic evolutionary games often exhibit metastable dynamics but the existing approaches to their analysis are not able to capture this behavior. We derive the aggregated strategy updating process for general stochastic evolutionary games as a discrete-time Markov chain on a finite state space. We present two characterizations of metastability and investigate both of these characterizations for stochastic evolutionary games. In particular, we show that every decomposition of state space into limit sets of the unperturbed Markov chain of the stochastic evolutionary game is metastable according to both characterizations. We furthermore consider for stochastic evolutionary games the core set Markov state modeling approach to the construction of Markov models that capture the essential, metastable dynamics on a considerably smaller state space and that are thus of reduced complexity. The underlying idea is the best approximation and thus orthogonal projection of a transfer operator of the evolutionary game onto the subspace spanned by the committor functions on given disjoint subsets of population state, the so- called core sets. The matrix representation of this projected transfer operator represents the transition matrix of the reduced Markov chain. We elaborate on the relationship between the original Markov chain and the core set Markov state model. We show that the construction preserves stochastic stability. Building on the analysis of the approximation error, we present an algorithmic strategy to the identification of core sets such that the resulting core set model represents well the dominant time scales and in this sense the metastable dynamic behavior of the evolutionary game. Both the core sets as well as the transition matrix can be estimated from simulated trajectory data. The approach is thus appealing in the context of agent-based modeling. Although the approach is built on the assumption that the original Markov chain is reversible, it constitutes a proof of concept for the applicability of the core set Markov state modeling approach to agent-based models. We give two important examples of classes of stochastic evolutionary games with reversible dynamics and an overview of the state-of-the-art of Markov models on reduced state space for Markov chains with non-reversible dynamics.

Inhalt dieser Arbeit ist die Formalisierung (Teil I) und Metastabilitätsanalyse (Teil II) agenten-basierter, evolutionärer Modelle. Teil I diskutiert die Notwendigkeit von Spezifikationen als komplementärer Bestandteil der Beschreibung agenten-basierter Modelle neben der Implementierung und einer Beschreibung in natürlicher Sprache. Wir präsentieren die Grundstruktur eines funktionalen Frameworks für die Spezifizierung agenten-basierter Austauschmodelle. Der Hauptfokus dabei liegt auf der Herausarbeitung des Zusammenhangs agenten-basierter Austauschmodelle mit traditioneller ökonomischer Theorie. Es zeigt sich, dass die untersuchten Modelle sich von evolutionären Spielen nur darin unterscheiden, dass die Fitnessfunktion nicht deterministisch ist. Das Framework wird weiterhin benutzt um die Fragestellung der Modelle präzise herauszuarbeiten und damit einen direkten Bezug zu allgemeinen Gleichgewichtsmodellen herzustellen. Darüberhinaus wird aufgezeigt, wie das Framework unerlässliche Grundlage für die formale und numerische Analyse ist. Teil II beinhaltet die Metastabilitätsanalyse evolutionärer Spiele in endlichen Populationen, welche einfache agenten-basierte Modelle sind. Die Motivation basiert auf der Beobachtung, dass evolutionäre Spiele häufig metastabile Dynamik aufweisen, bisherige Analyseansätze diese Dynamik jedoch nicht beschreiben können. Die evolutionären Spiele werden als zeit-diskrete Markovketten repräsentiert. Darauf aufbauend werden zwei formale Charakterisierungen von Metastabilität vorgestellt und in den Kontext evolutionärer Spiele gebettet. Es zeigte sich, dass bestimmte Partitionen des Zustandsraumes metastabil hinsichtlich beider Charakterisierungen ist. Weiterhin betrachten wir für die evolutionären Spiele den Ansatz der Core-Set Markov-State-Modellierung zur Konstruktion von zeit- diskreten Markovketten, welche die essentielle, metastabile Dynamik erfassen, dabei jedoch einen wesentlich kleineren Zustandsraum und dadurch eine reduzierte Komplexität aufweisen. Grundlegende Idee ist die Bestapproximation und damit orthogonale Projektion eines Transfer-Operators des evolutionären Spiels auf den Unterraum, welcher aufgespannt wird durch die Committor- Funktionen bzgl. gegebener, disjunkter Teilmengen des Zustandsraumes, der sogenannten Core-Sets. Die darstellende Matrix dieser Projektion ist die Übergangsmatrix der reduzierten Markovkette. Zusammenhänge zwischen der ursprünglichen und der reduzierten Markovkette werden detailliert herausgearbeitet. Es wird gezeigt, dass die Konstruktion stochastische Stabilität erhält. Aufbauend auf der Analyse des Approximationsfehlers wird ein Algorithmus zur Identifikation von Core-Sets präsentiert, sodass das resultierende Core-Set Modell die dominanten Zeitskalen und in diesem Sinne die Metastabilität gut wiedergibt. Sowohl die Core-Sets als auch die Übergangsmatrix des reduzierten Modells können aus simulierten Trajektionsdaten geschätzt werden. Der Ansatz ist somit auch im Rahmen der agenten-basierten Modellierung reizvoll. Obwohl der Anwendungsbereich durch die Annahme reversibler Dynamik für allgemeine agenten-basierte Modelle eingeschränkt ist, legt diese Arbeit einen Grundstein für zukünftige Arbeiten in diesem Bereich. Wir geben zwei Beispiele für Klassen reversibler evolutionärer Spiele und einen Überblick über Ansätze für nicht-reversible Markovprozesse.