Back to search

Georgia Institute of Technology

Evolutionary Markov chains, potential games and optimization under the lens of dynamical systems

Abstract

dc:description.abstract

The aim of this thesis is the analysis of complex systems that appear in different research fields such as evolution, optimization and game theory, i.e., we focus on systems that describe the evolution of species, an algorithm which optimizes a smooth function defined in a convex domain or even the behavior of rational agents in potential games. The mathematical equations that describe the evolution of such systems are continuous or discrete dynamical systems (in particular they can be Markov chains). The challenging part in the analysis of these systems is that they live in high dimensional spaces, i.e., they exhibit many degrees of freedom. Understanding their geometry is the main goal to analyze their long-term behavior, speed of convergence/ mixing time (if convergence can be shown) and to perform average-case analysis. In particular, the stability of the equilibria (fixed points) of these systems plays a crucial role in our attempt to characterize their structure. However, the existence of many equilibria (even uncountably many) makes the analysis more difficult. Using mathematical tools from dynamical systems theory, Markov chains, game theory and non-convex optimization, we have a series of results: As far as evolution is concerned, (i) we show that mathematical models of haploid evolution imply the extinction of genetic diversity in the long term limit (for fixed fitness matrices) and moreover, (ii) we show that in case of diploid evolution the diversity usually persists, but it is NP-hard to predict it. Finally, (iii) we extend the results of haploid evolution when the fitness matrix changes per a Markov chain and we examine the role of mutation in the survival of the population. Furthermore, we focus on a wide class of Markov chains, inspired by evolution. Our key contribution is (iv) connecting the mixing time of these Markov chains and the geometry of the dynamical systems that guide them. Moreover, as far as game theory is concerned, (v) we propose a novel quantitative framework for analyzing the efficiency of potential games with many equilibria. Last but not least, using similar techniques, (vi) we show that gradient descent converges to local minima with probability one, even when the set of critical points is uncountable.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Computer Science
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2016

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Panageas, Ioannis
Advisor dc:contributor.advisor
  • Tetali, Prasad
Committee members dc:contributor.committeemember
  • Dey, Santanu
  • Mehta, Ruta
  • Piliouras, Georgios
  • Vazirani, Vijay

Subjects

dc:subject × 7

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/55617

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Panageas, Ioannis. Evolutionary Markov chains, potential games and optimization under the lens of dynamical systems. Doctoral thesis, Georgia Institute of Technology, 2016. http://hdl.handle.net/1853/55617