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 |