Theoretical Ecology, Learning, and Optimization.

In lieu of writing my thesis, I’m going to write up a collection of statements and results related to theoretical ecology, learning, and optimization which I’ve found of interest. I’m taking Prof. Levin’s Theoretical Ecology course, an interesting perspective on the process of theory-building in a natural science.

Evolutionary Game Theory and Learning

In evolutionary game theory, the payoff of a strategy is dependent on the frequency of its prevalence in the population. The solution concept of interest is an evolutionary stable strategy which is resistant to ‘invasion’ by mutant types. A sufficient condition is that a strategy does strictly better than other strategies, but only weakly better against itself. Interestingly enough, removing the strict inequality removes compactness of the set that the optimization is taken over - so Nash’s analysis on the existence of the Nash equilibrium doesn’t apply.

One thing that I’m curious about is the extent to which ecologists might be interested in the computability or complexity of ESS. After all, Rubinstein himself raised a concern on the interpretability of Nash equilibria in ‘vanilla’ game theory since they were generally computationally intractable (specifically, PPAD-Complete - a slightly weaker version of NP-completeness.

Sergiu Hart and Mas-Colell show in an ‘03 paper that no-regret learning algorithms generally converge to correlated equilibria, a more general solution concept than Nash equilibria. Correlated equilibria occur if no player has an incentive to deviate from a given strategy if signalled to take a certain strategy from a central authority before the start of the game. This raises the question of whether or not these no-learning algorithms represent computationally feasible alternatives to equilibrium convergence in games with algorithmic agents: one can imagine how this could lead to the design of incentive-compatible systems where each player has no incentive to deviate, given an algorithm to maximize their payoffs in the system of interacting agents. Katrina Ligett et al. have a neat paper in SIGECOM 2015 that shows that it is at least computationally difficult (NP-Hard) to find a coarse correlated equilibrium with social welfare better than the worst possible. “One cannot provide any nontrivial welfare guarantee for the resulting equilibrium”. This is rather unfortunate; however they do provide an algorithmic framework to identify problem instances where an efficient approximate equilibrium can be computed with near-optimal welfare guarantees.

Ecology and Optimization

This post on Off The Convex Path outlines a few interesting case studies in the relationship between dynamical systems and nonconvex optimization. (In particular there’s a cute anecdote about slime molds computing gradient descent on a manifold to solve an linear program. I think it demonstrates a flaw in thinking about logical connections between computation and the natural sciences: the fact that discrete models of age-structured populations resemble the power iteration method (for finding eigenvalues) doesn’t mean that nature is computing the largest eigenvalue - it means that in this model, the largest eigenvalue is governing the dynamics of evolution of the system. It’s the structure of the discrete-time updating which resembles the power method, which is more a consequence of the fundamental simplicity of matrix multiplication as projection, and the assumption that the projection matrix stays constant!

Theoretical ecology is interested in stability analysis of dynamical systems because this type of analysis stays robust (for the most part) to small changes in parameters - stability results arise from the main dynamics of the model. The claim is that there is no general theory for finding multiple fixed points of a dynamical system from the point of view of nonconvex optimization seems to overlook the type of stability analysis which exactly studies which equilibria are reached under which initial conditions.

Evolutionary Game Theory on Graphs

Prof. Tarnita’s thesis addresses the question of evolutionary game theory via structured populations. What if populations are spatially partitioned or their topological interactions are otherwise governed by some network structure? In finite populations, evolutionary game theory is best modeled via Moran’s stochastic process which models the death and reproduction process in a finite population, vs. the infinite well-mixed population. The analysis then (loosely) analyzes propagation of evolutionary game (including mutant strategies) via the dynamics of a finite Markov chain. The quantity of interest is the fixation probability, the ability of a mutant strategy to take over a finite structured population.

The analysis looks interesting and I’d like to go deeper through it: one question brought up at the end of a review raises the question of how temporally changing spatial structures might affect fixation probability and other questions relevant to the evolutionary game.

(I’m reminded of the utility of working with abstractions like graphs, since insights about dynamic topologies in one setting (I’m working with the properties of network flows on dynamic graphs) might add to our ability to make predictions in an entirely different field!)