Sources for Algorithmic Evolutionary Game Theory

Question

I use the title term in a very loose sense.

There is a significant amount of work on evolutionary game theory, including its mathematical foundations. I was recommended "Evolutionary Games and Population Dynamics" but haven't delved into it yet.

There is also a significant amount of work on algorithmic game theory, which is a popular topic on this site.

What I'd like to see is work that makes computational complexity or convergence statements about certain evolutionary dynamics.

Examples (phrased very loosely):

1. Given a population and an evolutionary scheme, can we give a probabilistic regret bound for the long-term population optimality (compared to the best individual produced?). This seems to relate strongly to ensembles of experts and bandit problems. What about in nonstationary settings?
2. Given a set of populations of different species that interact in their environment, playing pretty much any sort of multi-player game, what statements can we make about the eventual stability of their strategies or strategy distributions, given their evolutionary strategies.
3. In any sort of environment with many "niches" (an overbroad way of phrasing it, I understand), either in terms of direct relationship with the environment or in terms of relationships with other species, what statements can we make about how populations will distribute across these niches.
4. Any problem I haven't asked but should - I'm coming at this with little AGT, TCS, Genetic Algorithms, evolutionary game theory or population biology background; I'm asking my questions from an optimization/machine learning/stats point of view, which may be the wrong one or incomplete.

Answer 1

This is one of the topics where I have been looking for connections for a while. However, they don't seem all the prevalent. The folks working on theoretical biology and economics that use EGT, usually stick to dynamic systems theory and don't don the algorithmic lens. Thus, most results are of the AMath/Physics style, and not of the algorithms and discrete math style. If you are willing to pursue the dynamic systems approach, then there a survey by Hofbauer and Sigmund which is shorter and more recent than their book (I mention it and some passing comments in a previous answer).

One of the places replicator dynamics have been used in complexity related results, is by Marcello Pelillo and co-authors as a heuristic for solving max-clique (reduce max-clique to quadratic programming, solve quadratic programming by using replicator dynamics as your heuristic):

[1] Immanuel M. Bomze, and Marcello Pelillo [2000]. "Approximating the Maximum Weight Clique Using Replicator Dynamics." IEEE Transactions on Neural Networks 11(6)

[2] Marcello Pelillo, and Andrea Torsello [2006]. "Payoff-Monotonic Game Dynamics and the Maximum Clique Problem." Neural Computation 18: 1215-1258.

You can use their results to show that many natural question associated with evolutionary stable strategies are NP-hard (this kind of addresses question 2). In fact, Etessami & Lochbihler showed that it is worse than that and the question of ESS existence is both NP and coNP-hard, but in $\Sigma^P_2$. Recently, Conitzer tightened this to show that "does an ESS exist?" is a $\Sigma^P_2$-complete problem.

[3] Kousha Etessami, and Andreas Lochbihler [2008] "The computational complexity of evolutionarily stable strategies". International Journal of Game Theory, 37(1): 93-113. (First available in 2004 as ECCC tech report TR04-055).

[4] Vincent Conitzer [2013] "The exact computational complexity of evolutionarily stable strategies". The 9th Conference on Web and Internet Economics (WINE). (pdf).

A lot of the interesting EGT questions today are about games on graphs, and although there are some cool dynamic system results, like (also see this question for extensions of this approach):

[5] Hisashi Ohtsuki, and Martin Nowak [2006] "The replicator equation on graphs." _ Journal of Theoretical Biology_, 243 (1), 86-97 (link, blog post)

Most of the work goes through agent-based modeling (see this answer for a spread-of-disease modeling context). These models are usually much more welcoming to complexity and convergence statements. Look at the following book for more:

[6] Yoav Shoham and Kevin Leyton-Brown [2009], "Multiagent systems: algorithmic, game-theoretic, and logical foundations", Cambridge University press.

I think machine learning is a pretty straightforward way to approach EGT, since it is a natural halfway point between the relevant physics (statistical mechanics) and computer science. This has definitely been done, it would take me a bit to find a good reference, but a random reference (which also shows that EGT folks have considered other popular equilibrium concepts, like correlated equilibrium):

[7] Sergiu Hart and Andreu Mas-Colell [2000], "A simple adaptive procedure leading to correlated equilibrium", Econometrica 68(5): 1127-1150

[8] Antonella Ianni [2001], "Learning correlated equilibria in population games", Mathematical Social Sciences 42(3): 271-294.

[9] Ludek Cigler and Boi Faltings [2011], "Reaching Correlated Equilibria Through Multi-agent Learning", AAMAS 2011: 509-516

I definitely hope others give more specific answers, since this is a question I've always wanted to know more about.

Answer 2

As others have said, there is less than you would expect. A couple of tangentially related papers:

"Multiplicative Weights in Coordination Games and the Theory of Evolution" by Chastain, Livnat, Papadimitriou, and Vazirani. This paper argues that evolutionary dynamics (in a simple model) is equivalent to a coordination game between genes being played with the multiplicative weights learning algorithm. They analyze the 2 gene variant, in a simplified model.

Note the multiplicative weights algorithm is a natural dynamic known to converge to Nash equilibrium in zero sum games, nonatomic potential games, and some others (see e.g. Freund and Schapire )

"The Price of Stochastic Anarchy" by Chung, Ligett, Pruhs, and myself (from awhile ago). Here we study stochastically stable states of a game, which are related to ESS. We don't worry about the complexity of finding them, but we show that in some games, the price of anarchy is lower over the set of stochastically stable equilibria as compared to arbitrary Nash equilibria.

Answer 3

I learned from the school of Ashlock. The big take away I got was how useful it was to take the $n^2$ table of outcomes between agents and use K-Means to cluster the rows into strategy groups for analysis.