Computational complexity of evolutionary stable strategies

John Maynard Smith and John Forbes Nash, Jr.

John Maynard Smith and John Forbes Nash, Jr.

Yesterday, I shared a video of John Maynard Smith introducing evolutionary game theory (EGT) to the London Mathematical Society. I suggested that at its foundation, EGT was just like classical game theory, and based on equilibrium analysis — the evolutionary stable strategy (Maynard Smith & Price, 1973). Given a utility function U(\sigma,\sigma') that gives the expected payoff for mixed strategy \sigma interacting with mixed strategy \sigma, we say that \sigma^* is an evolutionary stable strategy (ESS) if:

  1. For all \sigma' \neq \sigma^* we have \quad U(\sigma^*,\sigma^*) \geq U(\sigma',\sigma^*), and
  2. If U(\sigma^*,\sigma^*) = U(\sigma',\sigma^*) then U(\sigma^*,\sigma') > U(\sigma',\sigma').

Or we look at the contrapositive: a strategy \sigma' can invade a host strategy \sigma if (1) it has a better payoff in a population of \sigmas than \sigmas have against themselves, or (2) if they are neutral then a small population of \sigma' benefits themselves more than they benefit the host population. If some strategy \sigma^* has no invading strategy \sigma' then it is an evolutionary stable strategy.

If you are an observant reader and familiar with classical game theory then you probably noticed that the first condition of the direct definition is equivalent to the definition of a Nash equilibrium (NE). The second clause joined with an “and” means that every NE is an ESS, but not every ESS is an NE. However, that second condition seems innocuous enough, surely it can’t change the the qualitative nature of the equilibrium concept?

It does — it changes everything. The second condition transforms the \geq of NE into > of ESS, and that is not a minor — it is the difference between closed and open sets in topology. Without \geq, we can’t use Brouwer’s fixed point theorem anymore, and thus can’t guarantee the existence of an ESS. Although a NE exists in every game, you can already find examples of games without an ESS just by looking at the Rock-Paper-Scissors game with +1 for wins, -1 for losses, and a small penalty of \epsilon for ties. This change to strict inequalities also makes the computational aspects of ESS much more difficult than the corresponding concepts for NE.

If we switch to the dynamic point of view and look at the replicator equation (Taylor & Jonker, 1978) then — as is so often the case in simple models of evolution — the problem starts to look like optimization. In particular, since we care about the behavior of strategies playing against themselves (as opposed to a static fitness landscape), we start to get equation that are quadratic in the weights of agent’s mixed strategies. It is unsurprising that replicator dynamics becomes closely related to quadratic programming which is NP-hard; it becomes possible to encode problems like the maximum clique problem in the game payoff matrix and use evolution to solve it (Bomze et al., 2000; Pelillo & Torsela, 2006). However, this is only a lower bound on the complexity of finding an ESS.

Etessami & Lochbihler (2008; preprint appeared in 2004) looked at the complexity of answering if a given game has an ESS. They showed that the problem is both NP-hard and coNP-hard, and inside \Sigma_2^P (NP with a coNP oracle). In fact, Nisan (2006) showed that given a game and a candidate ESS, it is already coNP-hard to check if the candidate is in fact ESS or not. Recently, Conitzer (2013) finished this direction by showing that the existence of an ESS is \Sigma_2^P-complete by a reduction from the Minmax-clique problem (Ko & Lin, 1995).

I am not sure of the consequences of this for biology, since the question of ESS existing is not a central biological problem. The bigger problem is if an ESS exists, can we find it in a reasonable amount of time? These result tell us that there is no simple classification of games into ones that have or don’t have an ESS, but they say nothing about the complexity of finding the equilibrium if one exists. Since we can’t have simple necessary and sufficient conditions for ESS, I would be interested in looking at the complexity of finding equilibrium in classes of games that satisfy some nice sufficient conditions. Will it be PPAD-complete like NE (and similar to the PLS-completness of the NK-model of static fitness landscapes)? Or will it be more difficult? Easier? What is we further restrict the games to random graphs?

References

Bomze, I. R., Pelillo, M., & Stix, V. (2000). Approximating the maximum weight clique using replicator dynamics. Neural Networks, IEEE Transactions on, 11(6): 1228-1241.

Conitzer, V. (2013). The exact computational complexity of evolutionarily stable strategies. The 9th Conference on Web and Internet Economics (WINE).

Etessami, K., & Lochbihler, A. (2008). The computational complexity of evolutionarily stable strategies. International Journal of Game Theory, 37(1): 93-113. First available in 2004 in ECCC Tech Report TR04-055.

Ko, K.I., & Lin, C.L. (1995). On the complexity of min-max optimization problems and their approximation. Nonconvex optimization and its applications, 4: 219-240.

Maynard Smith, J., & Price, G.R. (1973). The logic of animal conflict. Nature, 246: 15-18.

Nisan, N. (2006). A note on the computational hardness of evolutionary stable strategies. In Electronic Colloquium on Computational Complexity (ECCC) 13(076).

Pelillo, M., & Torsello, A. (2006). Payoff-monotonic game dynamics and the maximum clique problem. Neural Computation, 18(5): 1215-1258.

Taylor, P.D. & Jonker, L. (1978). Evolutionary stable strategies and game dynamics. Math. Biosci., 40: 145-156.

About these ads

About Artem Kaznatcheev
From the ivory tower of the School of Computer Science and Department of Psychology at McGill University, I marvel at the world through algorithmic lenses. My specific interests are in quantum computing, evolutionary game theory, modern evolutionary synthesis, and theoretical cognitive science. Previously I was at the Institute for Quantum Computing and Department of Combinatorics & Optimization at the University of Waterloo and a visitor to the Centre for Quantum Technologies at the National University of Singapore.

2 Responses to Computational complexity of evolutionary stable strategies

  1. Pingback: Computational complexity of evolutionary stable...

  2. Pingback: Cataloging a year of blogging: the algorithmic world | Theory, Evolution, and Games Group

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 2,060 other followers