Sources for Algorithmic Evolutionary Game Theory
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]. &quot;Approximating the Maximum Weight Clique Using Replicator Dynamics.&quot; IEEE Transactions on Neural Networks 11(6)
[2] Marcello Pelillo, and Andrea Torsello [2006]. &quot;Payoff-Monotonic Game Dynamics and the Maximum Clique Problem.&quot; 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 &amp; 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 &quot;does an ESS exist?&quot; is a $\Sigma^P_2$-complete problem.

[3] Kousha Etessami, and Andreas Lochbihler [2008] &quot;The computational complexity of evolutionarily stable strategies&quot;. International Journal of Game Theory, 37(1): 93-113. (First available in 2004 as ECCC tech report TR04-055).
[4] Vincent Conitzer [2013] &quot;The exact computational complexity of evolutionarily stable strategies&quot;. 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] &quot;The replicator equation on graphs.&quot; _ 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], &quot;Multiagent systems: algorithmic, game-theoretic, and logical foundations&quot;, 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], &quot;A simple adaptive procedure leading to correlated equilibrium&quot;, Econometrica 68(5): 1127-1150
[8] Antonella Ianni [2001], &quot;Learning correlated equilibria in population games&quot;, Mathematical Social Sciences 42(3): 271-294.
[9] Ludek Cigler and Boi Faltings [2011], &quot;Reaching Correlated Equilibria Through Multi-agent Learning&quot;, 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.