Detailansicht

Selecting equilibria from an ample choice
an interplay of game theory, optimization and dynamics
Reinhard Ullrich
Art der Arbeit
Dissertation
Universität
Universität Wien
Fakultät
Fakultät für Wirtschaftswissenschaften
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Doctor of Philosophy-Doktoratsstudium Wirtschaftswissenschaften (Dissertationsgebiet: Statistik und Operations Research)
Betreuer*innen
Immanuel und Schachinger, Werner Bomze ,
Werner Schachinger
Alle Rechte vorbehalten / All rights reserved
URN
urn:nbn:at:at-ubw:1-25407.93988.263069-8
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)

Abstracts

Abstract
(Deutsch)
Starke Zusammenhänge bestehen zwischen den Gebieten Spieltheorie, Optimierung und Dynamische Systeme. Einige dieser Zusammenhänge waren schon zu Beginn der jeweiligen Gebiete sichtbar, andere wurden erst im Laufe der letzen Jahre erkannt oder vertieft. Die vorliegende Dissertation operiert an den Schnittstellen dieser drei Bereiche, es werden vier Artikel präsentiert, von denen sich drei im Spannungsfeld Spieltheorie und Optimierung bewegen, und einer im Bereich Spieltheorie und Dynamische Systeme angesiedelt ist. Ein großer Teil der Arbeit für diese Dissertation bestand in der Implementierung eines Algorithmus, welcher alle evolutionär-stabilen Strategien (ESS) eines Spiels mit paarweisem Wettbewerb und endlich vielen Strategien bestimmt. Diese Frage ist gleichbedeutend mit der Frage, wie sich alle strikt lokalen Maximierer eines Standard-Quadratischen Problems finden lassen. Mit Hilfe dieser Implementierung konnten interessante theoretische Resultate motiviert werden, einige davon sind eher der Spieltheorie zuzuordnen, andere eher der Optimierung. Bestehende untere Schranken für die maximale Anzahl koexistierender ESS konnten verbessert werden, und Methoden zur Konstruktion von Matrizen mit vielen ESS werden vorgestellt. In einem leicht veränderten Kontext dienten Matrizen mit einer großen Anzahl von globalen Maximierern als Ausgangspunkt, um eine 20 Jahre alte Vermutung über den cp-Rang von vollständig positiven Matrizen zu widerlegen, welche eine bedeutende Rolle in der Optimierung spielen. Im letzten Teil der Dissertation wird eine neue Dynamik in stetiger Zeit präsentiert, die zuvor für diskrete Zeit entwickelt wurde - die Infektions-Immunisierungs-Dynamik. Sie wurde vor allem zur rechnerisch raschen Auffindung von Nash-Gleichgewichten entwickelt. In stetiger Zeit zeigt diese plausible und unkomplizierte Dynamik jedoch ein sehr kompliziertes Verhalten, da unstetige Differentialgleichungen und Differentialinklusionen zur Behandlung der Dynamik verwendet werden müssen.
Abstract
(Englisch)
There exist strong connections between game theory, optimization and dynamics. Some of these connections were obvious from the beginning of these fields, some were worked out or strengthened in the last years. This thesis operates at the intersections of these areas and presents four publications, three of them in the area game theory and optimization, and one of them in the area game theory and dynamics. A known algorithm to detect all evolutionary stable strategies (ESS) of a game with pairwise contests and finitely many pure strategies was implemented. The question of finding all ESS is equivalent to the question of detecting all strict local maximizers of a standard quadratic problem. With the help of this implementation interesting theoretical results could be derived, some of them more from a game theoretical viewpoint, some of them more from the perspective of optimization. Existing lower bounds on the maximal number of co-existing ESS were improved and methods to construct matrices with many ESS are stated. In a slightly different context matrices with many global maximizers for the standard quadratic problem were utilized to reject a famous 20-year old conjecture about the cp-rank of completely positive matrices, which play an important role in optimization. The last part of this thesis presents a continuous-time version of a recently developed discretetime dynamics, the Infection-Immunization Dynamics, which was originally developed for fast computational equilibrium detection. In continuous time this reasonable and uncomplicated model exhibits non-trivial and non-standard behaviour, since discontinuous differential equations and differential inclusions become involved.

Schlagwörter

Schlagwörter
(Englisch)
Quadratic Optimization Evolutionary Stability Copositive Optimization Completely Positive Matrices cp-rank Nonnegative Factorization Equilibrium Selection Infection-Immunization Dynamics
Schlagwörter
(Deutsch)
Quadratische Optimierung Evolutionäre Stabilität Kopositive Optimierung Vollständig-positive Matrizen cp-Rang Nichtnegative Faktorisierung Gleichgewichtsauswahl Infektions-Immunisierungs-Dynamik
Autor*innen
Reinhard Ullrich
Haupttitel (Englisch)
Selecting equilibria from an ample choice
Hauptuntertitel (Englisch)
an interplay of game theory, optimization and dynamics
Paralleltitel (Deutsch)
Auswahl von Gleichgewichten: Ein Zusammenspiel von Spieltheorie, Optimierung und Dynamischen Systemen
Publikationsjahr
2016
Umfangsangabe
98 Seiten : Illustrationen, Diagramme
Sprache
Englisch
Beurteiler*innen
Georg Still ,
Vladimir Veliov
Klassifikation
31 Mathematik > 31.80 Angewandte Mathematik
AC Nummer
AC13269322
Utheses ID
40345
Studienkennzahl
UA | 794 | 370 | 136 |
Universität Wien, Universitätsbibliothek, 1010 Wien, Universitätsring 1