| Title: | Evolutionary Markov Chains, Potential Games and Optimization Under the Lens of Dynamical Systems |
| Advisor: | Dr. Prasad Tetali, School of Mathematics |
| Committee: | Dr. Santanu Dey, School of Industrial and Systems Engineering |
| Dr. Ruta Mehta, Department of Computer Science, University of Illinois, Urbana-Champaign | |
| Dr. Georgios Piliouras, Engineering Systems and Design, Singapore University of Technology and Design | |
| Dr. Vijay Vazirani, School of Computer Science | |
| Reader: | Dr. Jugal Garg, University of Illinois, Urbana-Champaign |
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 play 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) resolving a conjecture in genetics 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. These Markov chains are guided by a dynamical system defined in the simplex. 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. The notion we use is not so pessimistic as price of anarchy and not so optimistic as price of stability; it captures the expected long-term performance of a system. Informally, we define the expected system performance as the weighted average of the social costs of all equilibria where the weight of each equilibrium is proportional to the (Lebesgue) measure of its region of attraction. Using replicator dynamics as our benchmark, we provide bounds of this notion for several classes of potential games.
Last but not least, using similar techniques, (vi) we show that gradient descent converges to local minima with probability one, for cost functions in several settings of interest, even when the set of critical points is uncountable.
