You are here: University of Vienna PHAIDRA Detail o:1263594
Title (eng)
Co-evolutionary dynamics of networks and play
Parallel title (deu)
Co-evolutionäre Dynamiken von Netzwerken und Spielen
Author
Mathias Staudigl
Adviser
Immanuel Bomze
Assessor
Manfred Nermuth
Assessor
Fernando Vega-Redondo
Abstract (deu)
Diese Dissertation präsentiert drei inhaltlich zusammenhängende Artikel zu Ko-evolutionären Dynamiken von Netzwerken und Spielen. Ein Ko-evolutionärer Prozess besteht aus drei elementaren Ereignissen- Revision von gewählten Aktionen, Kreation eines links, Zerstörung eines links- welche zusammengefasst eine aggregierte Spieldynamik generieren. Unser Augenmerk liegt in der Charakterisierung des asymptotischen Verhaltens derartiger Prozesse. Kapitel 2, "On a general class of stochastic co-evolutionary dynamics", beschreibt den abstrakten mathematischen Rahmen eines Ko-evolutorischen Modells. Die Spieler sind charakterisiert durch eine Nutzenfunktionen auf einem gemeinsamen Aktionenraum und verwenden probabilistische Verhaltensregeln in den eingangs genannten Ereignissen. Zulässige Verhaltensregeln erfüllen eine Irreduzibilitätsannahme sowie ein Prinzip der großen Abweichungen. Neben diesen technischen Annahmen werden substantielle Annahmen an das Verhalten der Spieler auf ein Minimum reduziert. Dies generiert eine wohl definierte Markov-Kette, dessen langfristiges Verhalten durch Graphen-theoretische Methoden nach Freidlin und Wentzell [Random perturbations of dynamical systems, Springer, 1998] studiert werden kann. Wir beschreiben eine allgemeine Methode mit der stochastisch-stabile Zustände identifiziert werden können. Unter weiteren schwachen Annahmen lässt sich das induzierte Zufallsgraphemodell vollständig charakterisieren. Es zeigt sich eine äußerst interessante und unerwartete Beziehung zwischen Ko-evolutorischen Modellen und dem Modell der inhomogenen Zufallsgraphen. Kapitel 4 präsentiert den Artikel "Potential games played in volatile environments". Dort diskutieren wir ein Ko-evolutorisches Modell in der Klasse von Potentialspielen und Logit-Verhaltensregeln. Die invariante Verteilung sowie das generierte Zufallsgraphenmodell sind vollständig bestimmbar. Weiteres werden einige Statistiken des Zufallsgraphemodells in geschlossener Form präsentiert, wie etwa die ``degree distribution'' des Zufallsgraphen. Kapitel 5 erweitert dieses Modell durch Heterogenität in den Präferenzen der Spieler. Wir definieren eine neue Klasse von Spielen, ``structured Bayesian interaction games'', aufbauend auf einer jungen Literatur der evolutionären Spieltheorie die sich mit ``Bayesian population games'' beschäftigt. Kapitel 3 stellt eine Verbindung zwischen den Markov-Ketten von Kapitel 2, und den Markov-Prozessen der Kapitel 4 und 5 her. Ein abschließendes Kapitel resümiert die Ergebnisse der Dissertation und gibt Ausblicke für zukünftige Forschungsvorhaben.
Abstract (eng)
This dissertation presents three interrelated papers on the co-evolution of networks and play. The general structure of these models combines three elementary events- action adjustment, link creation and link destruction- to one stochastic game dynamics, and focuses on the asymptotic properties of these processes. Chapter 2 presents the general mathematical framework of a co-evolutionary model. The players have arbitrary utility functions, defined on a common set of actions, and employ probabilistic behavioral rules in the above mentioned events. Admissible rules satisfy irreducibility and a large deviations assumption. Beside these technical assumptions, we try to avoid making substantial behavioral assumptions. This generates a well-defined Markov chain, whose long-run properties can be studied analytically by making use of tree-characterization methods due to Freidlin and Wentzell [Random perturbations of dynamical systems, Springer, 1998]. We provide a general technique to compute stochastically stable states in such co-evolutionary models, by defining suitable cost-functions. Making some mild additional assumptions on the structure of the behavioral rules, we demonstrate an interesting and unforeseen connection between the derived ensemble of networks and inhomogeneous random graphs. The models presented in chapters 4 and 5 particularize the general framework to the class of potential games and behavioral rules of the logit-response form. Under these assumptions, chapter 4 gives a full description of the induced ensemble of networks, and provides additionally closed-form expression for statistics of this ensemble, such as the degree-distribution. The model presented in chapter 5 is more general by allowing the players to have idiosyncratic preferences. This leads us to the definition of structured Bayesian interaction games, following a recent literature of evolutionary game theory studying Bayesian population games. Chapter 3 establishes a connection between the Markov chain constructed in the general framework of chapter 2 and the continuous-time Markov processes considered in the models of chapters 4 and 5. Chapter 6 recapitulates the results of the thesis and gives an outlook for future research projects.
Keywords (eng)
evolutionary game theoryRandom graph theoryMarkov processesstochastic stability
Keywords (deu)
Evolutionäre SpieltheorieZufallsgraphenMarkov ProzessStochastische Stabilität
Subject (deu)
Type (deu)
Persistent identifier
https://phaidra.univie.ac.at/o:1263594
rdau:P60550 (deu)
168 S.
Number of pages
188
Members (1)
Title (eng)
Co-evolutionary dynamics of networks and play
Parallel title (deu)
Co-evolutionäre Dynamiken von Netzwerken und Spielen
Author
Mathias Staudigl
Abstract (deu)
Diese Dissertation präsentiert drei inhaltlich zusammenhängende Artikel zu Ko-evolutionären Dynamiken von Netzwerken und Spielen. Ein Ko-evolutionärer Prozess besteht aus drei elementaren Ereignissen- Revision von gewählten Aktionen, Kreation eines links, Zerstörung eines links- welche zusammengefasst eine aggregierte Spieldynamik generieren. Unser Augenmerk liegt in der Charakterisierung des asymptotischen Verhaltens derartiger Prozesse. Kapitel 2, "On a general class of stochastic co-evolutionary dynamics", beschreibt den abstrakten mathematischen Rahmen eines Ko-evolutorischen Modells. Die Spieler sind charakterisiert durch eine Nutzenfunktionen auf einem gemeinsamen Aktionenraum und verwenden probabilistische Verhaltensregeln in den eingangs genannten Ereignissen. Zulässige Verhaltensregeln erfüllen eine Irreduzibilitätsannahme sowie ein Prinzip der großen Abweichungen. Neben diesen technischen Annahmen werden substantielle Annahmen an das Verhalten der Spieler auf ein Minimum reduziert. Dies generiert eine wohl definierte Markov-Kette, dessen langfristiges Verhalten durch Graphen-theoretische Methoden nach Freidlin und Wentzell [Random perturbations of dynamical systems, Springer, 1998] studiert werden kann. Wir beschreiben eine allgemeine Methode mit der stochastisch-stabile Zustände identifiziert werden können. Unter weiteren schwachen Annahmen lässt sich das induzierte Zufallsgraphemodell vollständig charakterisieren. Es zeigt sich eine äußerst interessante und unerwartete Beziehung zwischen Ko-evolutorischen Modellen und dem Modell der inhomogenen Zufallsgraphen. Kapitel 4 präsentiert den Artikel "Potential games played in volatile environments". Dort diskutieren wir ein Ko-evolutorisches Modell in der Klasse von Potentialspielen und Logit-Verhaltensregeln. Die invariante Verteilung sowie das generierte Zufallsgraphenmodell sind vollständig bestimmbar. Weiteres werden einige Statistiken des Zufallsgraphemodells in geschlossener Form präsentiert, wie etwa die ``degree distribution'' des Zufallsgraphen. Kapitel 5 erweitert dieses Modell durch Heterogenität in den Präferenzen der Spieler. Wir definieren eine neue Klasse von Spielen, ``structured Bayesian interaction games'', aufbauend auf einer jungen Literatur der evolutionären Spieltheorie die sich mit ``Bayesian population games'' beschäftigt. Kapitel 3 stellt eine Verbindung zwischen den Markov-Ketten von Kapitel 2, und den Markov-Prozessen der Kapitel 4 und 5 her. Ein abschließendes Kapitel resümiert die Ergebnisse der Dissertation und gibt Ausblicke für zukünftige Forschungsvorhaben.
Abstract (eng)
This dissertation presents three interrelated papers on the co-evolution of networks and play. The general structure of these models combines three elementary events- action adjustment, link creation and link destruction- to one stochastic game dynamics, and focuses on the asymptotic properties of these processes. Chapter 2 presents the general mathematical framework of a co-evolutionary model. The players have arbitrary utility functions, defined on a common set of actions, and employ probabilistic behavioral rules in the above mentioned events. Admissible rules satisfy irreducibility and a large deviations assumption. Beside these technical assumptions, we try to avoid making substantial behavioral assumptions. This generates a well-defined Markov chain, whose long-run properties can be studied analytically by making use of tree-characterization methods due to Freidlin and Wentzell [Random perturbations of dynamical systems, Springer, 1998]. We provide a general technique to compute stochastically stable states in such co-evolutionary models, by defining suitable cost-functions. Making some mild additional assumptions on the structure of the behavioral rules, we demonstrate an interesting and unforeseen connection between the derived ensemble of networks and inhomogeneous random graphs. The models presented in chapters 4 and 5 particularize the general framework to the class of potential games and behavioral rules of the logit-response form. Under these assumptions, chapter 4 gives a full description of the induced ensemble of networks, and provides additionally closed-form expression for statistics of this ensemble, such as the degree-distribution. The model presented in chapter 5 is more general by allowing the players to have idiosyncratic preferences. This leads us to the definition of structured Bayesian interaction games, following a recent literature of evolutionary game theory studying Bayesian population games. Chapter 3 establishes a connection between the Markov chain constructed in the general framework of chapter 2 and the continuous-time Markov processes considered in the models of chapters 4 and 5. Chapter 6 recapitulates the results of the thesis and gives an outlook for future research projects.
Keywords (eng)
evolutionary game theoryRandom graph theoryMarkov processesstochastic stability
Keywords (deu)
Evolutionäre SpieltheorieZufallsgraphenMarkov ProzessStochastische Stabilität
Subject (deu)
Type (deu)
Persistent identifier
https://phaidra.univie.ac.at/o:1263595
Number of pages
188