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

Dynamical systems;Markov chains;Price of anarchy;Evolution;Convergence;Stability;Manifold

Panageas, Ioannis ; Tetali, Prasad Computer Science Dey, Santanu Mehta, Ruta Piliouras, Georgios Vazirani, Vijay ; Tetali, Prasad

University:Georgia Institute of Technology

Department:Computer Science

关键词: Dynamical systems;    Markov chains;    Price of anarchy;    Evolution;    Convergence;    Stability;    Manifold;   

Others  :  https://smartech.gatech.edu/bitstream/1853/55617/1/PANAGEAS-DISSERTATION-2016.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

The aim of this thesis is the analysis of complex systems that appear indifferent researchfields 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 agentsin 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 highdimensional 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 (forfixed 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 gametheory 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 withprobability one, even when the set of critical points is uncountable.