Document Open Access Logo

The Computational Complexity of Genetic Diversity

Authors Ruta Mehta, Ioannis Panageas, Georgios Piliouras, Sadra Yazdanbod

PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.65.pdf
  • Filesize: 0.6 MB
  • 17 pages

Document Identifiers

Author Details

Ruta Mehta
Ioannis Panageas
Georgios Piliouras
Sadra Yazdanbod

Cite As Get BibTex

Ruta Mehta, Ioannis Panageas, Georgios Piliouras, and Sadra Yazdanbod. The Computational Complexity of Genetic Diversity. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 65:1-65:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ESA.2016.65

Abstract

A key question in biological systems is whether genetic diversity persists in the long run under evolutionary competition, or whether a single dominant genotype emerges. Classic work by [Kalmus, J. og Genetics, 1945] has established that even in simple diploid species (species with chromosome pairs) diversity can be guaranteed as long as the heterozygous (having different alleles for a gene on two chromosomes) individuals enjoy a selective advantage. Despite the classic nature of the problem, as we move towards increasingly polymorphic traits (e.g., human blood types) predicting diversity (and its implications) is still not fully understood. Our key contribution is to establish complexity theoretic hardness results implying that even in the textbook case of single locus (gene) diploid models, predicting whether diversity survives or not given its fitness landscape is algorithmically intractable.

Our hardness results are structurally robust along several dimensions, e.g., choice of parameter distribution, different definitions of stability/persistence, restriction to typical subclasses of fitness landscapes. Technically, our results exploit connections between game theory, nonlinear dynamical systems, and complexity theory and establish hardness results for predicting the evolution of a deterministic variant of the well known multiplicative weights update algorithm in symmetric coordination games; finding one Nash equilibrium is easy in these games. In the process we characterize stable fixed points of these dynamics using the notions of Nash equilibrium and negative semidefiniteness. This as well as hardness results for decision problems in coordination games may be of independent interest. Finally, we complement our results by establishing that under randomly chosen fitness landscapes diversity survives with significant probability. The full version of this paper is available at http://arxiv.org/abs/1411.6322.

Subject Classification

Keywords
  • Dynamical Systems
  • Stability
  • Complexity
  • Optimization
  • Equilibrium

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. E. Chastain, A. Livnat, C. H. Papadimitriou, and U. Vazirani. Algorithms, games, and evolution. PNAS, 2014. URL: http://dx.doi.org/10.1073/pnas.1406556111.
  2. E. Chastain, A. Livnat, C. H. Papadimitriou, and U. V. Vazirani. Multiplicative updates in coordination games and the theory of evolution. In ITCS, pages 57-58, 2013. URL: http://dx.doi.org/10.1145/2422436.2422444.
  3. X. Chen, X. Deng, and S.-H. Teng. Settling the complexity of computing two-player Nash equilibria. Journal of the ACM, 56(3), 2009. Google Scholar
  4. V. Conitzer. The exact computational complexity of evolutionarily stable strategies. In The 9th Conference on Web and Internet Economics (WINE), 2013. Google Scholar
  5. V. Conitzer and T. Sandholm. New complexity results about Nash equilibria. Games and Economic Behavior, 63(2):621-641, 2008. Google Scholar
  6. T. H. Cormen, C. Stein, R. L. Rivest, and C. E. Leiserson. Introduction to Algorithms. McGraw-Hill Higher Education, 2nd edition, 2001. Google Scholar
  7. C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou. The complexity of computing a Nash equilibrium. SIAM Journal on Computing, 39(1):195-259, 2009. Google Scholar
  8. K. Etessami and A. Lochbihler. The computational complexity of evolutionarily stable strategies. International Journal of Game Theory, 37(1):93-113, 2008. Google Scholar
  9. R. A. Fisher. The Genetical Theory of Natural Selection. Clarendon Press, Oxford, 1930. Google Scholar
  10. J. Garg, R. Mehta, V. V. Vazirani, and S. Yazdanbod. Etr-completeness for decision versions of multi-player (symmetric) nash equilibria. In ICALP, 2015. Google Scholar
  11. I. Gilboa and E. Zemel. Nash and correlated equilibria: Some complexity considerations. Games Econ. Behav., 1:80-93, 1989. Google Scholar
  12. J. Hofbauer and K. Sigmund. Evolutionary Games and Population Dynamics. Cambridge University Press, Cambridge, 1998. Google Scholar
  13. V. I. Istratescu. Fixed Point Theory: An Introduction. Mathematics and Its Applications. Springer Netherlands, 2001. URL: http://books.google.com/books?id=2bsDnwEACAAJ.
  14. H. Kalmus. Adaptive and selective responses of a population of drosophila melanogaster containing e and e+ to differences in temperature, humidity, and to selection for development speed. Journal of Genetics, 47:58-63, 1945. Google Scholar
  15. A. Kawamura. Lipschitz continuous ordinary differential equations are polynomial-space complete. Computational Complexity, 19(2):305-332, 2010. Google Scholar
  16. A. Kawamura, H. Ota, C. R\:osnick, and M. Ziegler. Computational complexity of smooth differential equations. In In Mathematical Foundations of Computer Science, pages 578-589, 2012. Google Scholar
  17. A. Kaznatcheev. Complexity of evolutionary equilibria in static fitness landscapes. arXiv preprint arXiv:1308.5094, 2013. Google Scholar
  18. R. Kleinberg, K. Ligett, G. Piliouras, and É. Tardos. Beyond the Nash equilibrium barrier. In Symposium on Innovations in Computer Science (ICS), 2011. Google Scholar
  19. R. Kleinberg, G. Piliouras, and É. Tardos. Multiplicative updates outperform generic no-regret learning in congestion games. In STOC, 2009. Google Scholar
  20. A. Livnat, C. H. Papadimitriou, J. Dushoff, and M. W. Feldman. A mixability theory for the role of sex in evolution. PNAS, 2008. URL: http://dx.doi.org/10.1073/pnas.0803596105.
  21. V. Losert and E. Akin. Dynamics of games and genes: Discrete versus continuous time. Journal of Mathematical Biology, 1983. Google Scholar
  22. Y. Lyubich. Mathematical Structures in Population Genetics. Springer-Verlag, 1992. Google Scholar
  23. R. Mehta, I. Panageas, and G. Piliouras. Natural selection as an inhibitor of genetic diversity: Multiplicative weights updates algorithm and a conjecture of haploid genetics. In ITCS, 2015. Google Scholar
  24. R. Meir and D. Parkes. A note on sex, evolution, and the multiplicative updates algorithm. In Proceedings of the 12th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 15), 2015. Google Scholar
  25. J. Nash. Equilibrium points in n-person games. PNAS, pages 48-49, 1950. Google Scholar
  26. N. Nisan. A note on the computational hardness of evolutionary stable strategies. Electronic Colloquium on Computational Complexity (ECCC), 13(076), 2006. Google Scholar
  27. I. Panageas, P. Srivastava, and N. K. Vishnoi. Evolutionary dynamics in finite populations mix rapidly. In Proc. of the 27th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA'16), pages 480-497, 2016. URL: http://dx.doi.org/10.1137/1.9781611974331.ch36.
  28. C. Papadimitriou and G. Piliouras. From nash equilibria to chain recurrent sets: Solution concepts and topology. In Proc. of the 2016 ACM Conf. on Innovations in Theoretical Computer Science, ITCS'16, pages 227-235, New York, NY, USA, 2016. ACM. URL: http://dx.doi.org/10.1145/2840728.2840757.
  29. C. H. Papadimitriou and N. K. Vishnoi. On the computational complexity of limit cycles in dynamical systems. In ITCS, 2016. Google Scholar
  30. L. Perko. Differential Equations and Dynamical Systems. Springer, 1991. Google Scholar
  31. G. Piliouras, C. Nieto-Granda, H. I. Christensen, and J. S. Shamma. Persistent patterns: Multi-agent learning beyond equilibrium and utility. In Proceedings of the 2014 International Conference on Autonomous Agents and Multi-agent Systems, AAMAS'14, pages 181-188, Richland, SC, 2014. International Foundation for Autonomous Agents and Multiagent Systems. Google Scholar
  32. G. Piliouras and J. S. Shamma. Optimization despite chaos: Convex relaxations to complex limit sets via Poincaré recurrence. In SODA, 2014. Google Scholar
  33. K. C. Rasmus Ibsen-Jensena and M. A. Nowak. Computational complexity of ecological and evolutionary spatial dynamics. In PNAS, 2015. Google Scholar
  34. M. Schaefer and D. Štefankovič. Fixed points, Nash equilibria, and the existential theory of the reals. Manuscript, 2011. Google Scholar
  35. S.-M. Sun and N. Zhong. Computability aspects for 1st-order partial differential equations via characteristics. Theoretical Computer Science, 583:27-39, 2015. Google Scholar
  36. B. von Stengel. Equilibrium computation for two-player games in strategic and extensive form. Algorithmic Game Theory, eds. Nisan, Roughgarden, Tardos, and Vazirani, 2007. Google Scholar
  37. E. D. Weinberger. Np completeness of kauffman’s nk model, a tuneable rugged fitness landscape. Technical report, Santa Fe Institute, 1996. Google Scholar
  38. Wikipedia. Sylvester’s law of inertia. URL: https://en.wikipedia.org/wiki/Sylvester's_law_of_inertia.
  39. A. H. Wright, R. K. Thompson, and J. Zhang. The computational complexity of nk fitness functions. IEEE Transactions on Evolutionary Computation, 4(4):373-379, 2000. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact