Kitzler, F. (2016). Analyse von agentenbasierten Modellen mithilfe von Markovketten [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2016.36747
agent-based modelling; markov chains; model analysis
en
Abstract:
Die Bedeutung agentenbasierter Modellierung nimmt stetig zu. Agentenbasierte Modelle werden in vielen unterschiedlichen Bereichen eingesetzt, unter anderem in der Ökonomie, den Sozialwissenschaften oder zur Modellierung im Gesundheitssystemmanagement. Vorstellbare Gründe für den verstärkten Einsatz dieser eher jungen Modellierungstechnik sind die einfache Darstellbarkeit, die Flexibilität von agentenbasierten Modellen sowie die Möglichkeit heterogene Systeme einfach zu beschreiben. Eine weitere wichtige Eigenschaft und das größte Unterscheidungsmerkmal zu anderen Modellierungstechniken ist die Interaktionsfähigkeit der einzelnen Komponenten des Modells. Aus diesem Grund ist es möglich auch sehr komplexe Systeme aus einer Bottom-up Perspektive zu beschreiben. Bei der Analyse von agentenbasierten Modellen kann es jedoch auch zu Problemen kommen. So gibt es üblicherweise eine viel größere Anzahl an unbekannten Parametern, was die Parametrisierung bzw. Kalibrierung erschwert. Außerdem gibt es noch kaum spezifische Analyseund Validierungsmethoden, die auf die speziellen Eigenschaften agentenbasierter Modelle zugeschnitten sind. Aufgrund dieser Tatsache stellt sich oft die Frage, ob es nicht eine andere Beschreibung des Modells gibt. Diese Arbeit beschäftigt sich mit einer Methode, bestehende agentenbasierte Modelle als Markovkette darzustellen. Dies ist ein stochastische Prozesse, der die Eigenschaft der 'Gedächtnislosigkeit' besitzt. Das bedeutet, dass der weitere Verlauf des Prozesses nur von dem aktuellen Zustand abhängig ist und Ereignisse in der Vergangenheit keinen Einfluss darauf haben. Dazu wird zuerst die Dynamik des Modells auf dem Raum aller Konfigurationen beschrieben. Ausgehend von dieser sogenannten Mikrobeschreibung des agentenbasierten Modells als Markovkette kann man durch das Zusammenlegen von Zuständen zu einer Makrobeschreibung gelangen. Eine entscheidende Eigenschaft dabei ist die sogenannte 'Lumpability' der mikroskopischen Markovkette, die sicherstellt, dass auch der makroskopische Prozess wiederum gedächtnislos und damit eine Markovkette ist. Anhand ausgewählter Beispielen wird gezeigt, wie man von einem bestehenden agentenbasierten Modell zur Darstellung als makroskopische Markovkette gelangt. Die Fallbeispiele erfüllen dabei wichtige Eigenschaften agentenbasierter Modelle und sind auf der anderen Seite einfach genug um sie schnell zu implementieren und Ergebnisse zu erhalten. Als Beispiele werden einfache Bewegungsmodelle, dynamische Entscheidungsmodelle und dynamische Spiele betrachtet. Auf die unterschiedlichen Interaktionsformen der Agenten wird zudem genauer eingegangen. Im Zuge der Behandlung der Fallbeispiele wird der Fokus auf die Möglichkeit gelegt, die dabei entstandenen Markovketten mit spezifischen Verfahren zu analysieren und wichtige Kennzahlen des Modells zu berechnen. Da es sich dabei lediglich um das Lösen linearer Gleichungssysteme handelt, wird dazu wenig Rechenzeit benötigt. Dies ist ein großer Vorteil zu üblichen Analysemethoden wie Monte-Carlo-Simulation des agentenbasierten Modells. Es zeigt sich, dass die vorgestellte Methode sehr gut dazu geeignet ist, eine große Klasse von agentenbasierten Modellen als Markovkette darzustellen und zu analysieren.
de
The importance of agent-based modeling has increased more and more in recent years. Agentbased models have become a widely used tool for example in economy, social sciences and health care management. Some reasons for this development might be the picturesqueness of agent-based models, their flexibility, and the possibility to easily describe heterogeneous systems. Another advantage over other modeling techniques is the possibility of the model entities to interact with each other. Therefore it is possible to describe very complex systems from a bottom-up perspective. This means that the parts of the models are defined seperately and the dynamic of the system arises from interactions of the model entities. Nevertheless problems occur when it comes to analyse those models. Agent-based models usually have a bigger set of unknown parameters, which makes it harder to parameterize or calibrate them. Additionally methods to analyse and validate, which exploit the specific properties of agent-based models, barely exist. This raises the question of whether it is possible to describe the model in a different, easier analysable, way. This work describes a method to represent given agent-based models as markov chains. These are very simple stochastic processes that have the property to be 'memoryless'. This means that the further development of the process only depend on the current state and not on events in the past. To do so it is first necessary to describe the dynamics of the model on the set of configurations. This generated markov chain is also called the microdynamic of the model. Lumping together states of the microdynamics then creates a markov chain in a macroscopic sense, which is called the macrodynamics. It turns out that it is not always possible to create the markov chain of the macrodynamics, but in case it is, we can benefit from it by a reduced dimension of the state space. Based on selected examples it is shown how to create a markov chain of the microdynamics, and if possible, lump together states to obtain a markov chain of the macrodynamics. The case studies hold important properties of agent-based models and are easy enough to be implemented and to create output data fast. The regarded examples are models of movement, opinion dynamic models and dynamic games. It was also focused on the different ways of interaction between the agents in the different models. Another focus is on the methods to analyse the created markov chains with specific procedures and to calculate characteristic numbers of the model. This is done by just solving systems of linear equations and therefore really fast, which is a big advantage over other analysing methods like monte-carlo-simulation. Our case studies imply that this method can be a powerful tool when it comes to analysing for a big class of agent-based models.
en
Additional information:
Abweichender Titel nach Übersetzung der Verfasserin/des Verfassers Zusammenfassung in englischer Sprache