Publications

An up to date list of my publications can be found on Google Scholar

Computational complexity is an ultimate constraint on evolution

Artem Kaznatcheev
BioRxiv 187682.

Experiments show that evolutionary fitness landscapes can have a rich combinatorial structure due to epistasis. For some landscapes, this structure can produce a computational constraint that prevents evolution from finding local fitness optima — thus overturning the traditional assumption that local fitness peaks can always be reached quickly if no other evolutionary forces challenge natural selection. Here, I introduce a distinction between easy landscapes of traditional theory where local fitness peaks can be found in a moderate number of steps and hard landscapes where finding local optima requires an infeasible amount of time. Hard examples exist even among landscapes with no reciprocal sign epistasis; on these semi-smooth fitness landscapes, strong selection weak mutation dynamics cannot find the unique peak in polynomial time. More generally, on hard rugged fitness landscapes that include reciprocal sign epistasis, no evolutionary dynamics — even ones that do not follow adaptive paths — can find a local fitness optimum quickly. Moreover, on hard landscapes, the fitness advantage of nearby mutants cannot drop off exponentially fast but has to follow a power-law that long term evolution experiments have associated with unbounded growth in fitness. Unlike prior examples of evolutionary constraints, this constraint arises solely from natural selection, it cannot be overpowered by other evolutionary forces, and it enables open-ended evolution on finite landscapes. Knowing this constraint allows us to use the tools of theoretical computer science and combinatorial optimization to characterize the fitness landscapes that we expect to see in nature. I present candidates for hard landscapes at scales from single genes, to microbes, to complex organisms with costly learning (Baldwin effect) or maintained cooperation (Hankshaw effect).

Fibroblasts and Alectinib switch the evolutionary games played by non-small cell lung cancer

Artem Kaznatcheev, Jeffrey Peacock, David Basanta, Andriy Marusyk, Jacob G. Scott
BioRxiv 179259.

Heterogeneity in strategies for survival and proliferation among the cells which constitute a tumour is a driving force behind the evolution of resistance to cancer therapy. The rules mapping the tumour’s strategy distribution to the fitness of individual strategies can be represented as an evolutionary game. We develop a game assay to measure effective evolutionary games in co-cultures of non-small cell lung cancer cells which are sensitive and resistant to the anaplastic lymphoma kinase inhibitor Alectinib. The games are not only quantitatively different between different environments, but targeted therapy and cancer associated fibroblasts qualitatively switch the type of game being played by the in-vitro population from Leader to Deadlock. This observation provides empirical confirmation of a central theoretical postulate of evolutionary game theory in oncology: we can treat not only the player, but also the game. Although we concentrate on measuring games played by cancer cells, the measurement methodology we develop can be used to advance the study of games in other microscopic systems by providing a quantitative description of non-cell-autonomous effects.

Two conceptions of evolutionary games: reductive vs effective

Artem Kaznatcheev
BioRxiv 231993.

Evolutionary game theory (EGT) was born from economic game theory through a series of analogies.Given this heuristic genealogy, a number of central objects of the theory (like strategies, players, and games) have not been carefully defined or interpreted. A specific interpretation of these terms becomes important as EGT sees more applications to understanding experiments in microscopic systems typical of oncology and microbiology. In this essay, I provide two interpretations of the central objects of games theory: one that leads to reductive games and the other to effective games. These interpretation are based on the difference between views of fitness as a property of individuals versus fitness as a summary statistic of (sub)populations. Reductive games are typical of theoretical work like agent-based models. But effective games usually correspond more closely to experimental work. However, confusing reductive games for effective games or vice-versa can lead to divergent results, especially in spatially structured populations. As such, I propose that we treat this distinction carefully in future work at the interface of EGT and experiment.

Moral externalization may precede, not follow, subjective preferences

Artem Kaznatcheev, Thomas R. Shultz
Behavioral and Brain Sciences, 41: e107. 2018

We offer four counterarguments against Stanford’s dismissal of moral externalization as an ancestral condition, based on requirements for ancestral states, mismatch between theoretical and empirical games, passively correlated interactions, and social interfaces that prevent agents’ knowing game payoffs. The fact that children’s externalized phenomenology precedes their discovery of subjectivized phenomenology also suggests that externalized phenomenology is an ancestral condition.

Effective games and the confusion over spatial structure

Artem Kaznatcheev
Proceedings of the National Academy of Sciences, USA, 115(8): E1709. 2018

A typical study of space in evolutionary game theory starts with a specification of how local interactions impact fitness, and then simulates that interaction over a model of space to show a surprising difference in dynamics between the spatial model and its nonspatial counterpart. Usually, this difference is revealed at the population level. Exceptional works like that of Nanda and Durrett (1) and Ohtsuki and Nowak (2) provide a general method for combining local interactions and spatial structure into dynamically equivalent nonspatial models. We call this microscopic local interaction “reductive game” and its macroscopic population-level summary “effective game” (3). …

Fractionated Follow-Up Chemotherapy Delays the Onset of Resistance in Bone Metastatic Prostate Cancer

Pranav I. Warman, Artem Kaznatcheev, Arturo Araujo, Conor C. Lynch, David Basanta
Games, 9(2): 19, 2018
BioRxiv 274704.

Prostate cancer to bone metastases are almost always lethal. This results from the ability of metastatic prostate cancer cells to co-opt bone remodeling, leading to what is known as the vicious cycle. Understanding how tumor cells can disrupt bone homeostasis through their interactions with the stroma and how metastatic tumors respond to treatment is key to the development of new treatments for what remains an incurable disease. Here we describe an evolutionary game theoretical model of both the homeostatic bone remodeling and its co-option by prostate cancer metastases. This model extends past the evolutionary aspects typically considered in game theoretical models by also including ecological factors such as the physical microenvironment of the bone. Our model recapitulates the current paradigm of the “vicious cycle” driving tumor growth and sheds light on the interactions of heterogeneous tumor cells with the bone microenvironment and treatment response. Our results show that resistant populations naturally become dominant in the metastases under conventional cytotoxic treatment and that novel schedules could be used to better control the tumor and the associated bone disease compared to the current standard of care. Specifically, we introduce fractionated follow up therapy—chemotherapy where dosage is administered initially in one solid block followed by alternating smaller doses and holidays—and argue that it is better than either a continuous application or a periodic one. Furthermore, we also show that different regimens of chemotherapy can lead to different amounts of pathological bone that are known to correlate with poor quality of life for bone metastatic prostate cancer patients.

Cancer treatment scheduling and dynamic heterogeneity in social dilemmas of tumour acidity and vasculature

Artem Kaznatcheev, Robert Vander Velde, Jacob G. Scott, David Basanta
British Journal of Cancer, 116: 785-792, 2017
ArXiv 1608.00985.

Background: Tumours are diverse ecosystems with persistent heterogeneity in various cancer hallmarks like self-sufficiency of growth factor production for angiogenesis and reprogramming of energy-metabolism for aerobic glycolysis. This heterogeneity has consequences for diagnosis, treatment, and disease progression.

Methods: We introduce the double goods game to study the dynamics of these traits using evolutionary game theory. We model glycolytic acid production as a public good for all tumour cells and oxygen from vascularization via VEGF production as a club good benefiting non-glycolytic tumour cells. This results in three viable phenotypic strategies: glycolytic, angiogenic, and aerobic non-angiogenic.

Results: We classify the dynamics into three qualitatively distinct regimes: (1) fully glycolytic, (2) fully angiogenic, or (3) polyclonal in all three cell types. The third regime allows for dynamic heterogeneity even with linear goods, something that was not possible in prior public good models that considered glycolysis or growth-factor production in isolation.

Conclusion: The cyclic dynamics of the polyclonal regime stress the importance of timing for anti-glycolysis treatments like lonidamine. The existence of qualitatively different dynamic regimes highlights the order effects of treatments. In particular, we consider the potential of vascular renormalization as a neoadjuvant therapy before follow up with interventions like buffer therapy.

Dark selection for JAK/STAT-inhibitor resistance in chronic myelomonocytic leukemia

Artem Kaznatcheev, David Robert Grimes, Robert Vander Velde, Vincent L Cannataro, Etienne Baratchart, Andrew Dhawan, Lin Liu, Daria Myroshnychenko, Jake P. Taylor-King, Nara Yoon, Eric Padron, Andriy Marusyk, David Basanta
BioRxiv: 211151. 2017

Acquired therapy resistance to cancer treatment is a common and serious clinical problem. The classic U-shape model for the emergence of resistance supposes that: (1) treatment changes the selective pressure on the treatment-naive tumour; (2) this shifting pressure creates a proliferative or survival difference between sensitive cancer cells and either an existing or de novo mutant; (3) the resistant cells then out-compete the sensitive cells and — if further interventions (like drug holidays or new drugs or dosage changes) are not pursued — take over the tumour: returning it to a state dangerous to the patient. The emergence of ruxolitinib resistance in chronic myelomonocytic leukemia (CMML) seems to challenge the classic model: we see the global properties of resistance, but not the drastic change in clonal architecture expected with the selection bottleneck. To study this, we explore three population-level models as alternatives to the classic model of resistance. These three effective models are designed in such a way that they are distinguishable based on limited experimental data on the time-progression of resistance in CMML. We also propose a candidate reductive implementation of the proximal cause of resistance to ground these effective theories. With these reductive implementations in mind, we also explore the impact of oxygen diffusion and spatial structure more generally on the dynamics of CMML in the bone marrow concluding that, even small fluctuations in oxygen availability can seriously impact the efficacy of ruxolitinib. Finally, we look at the ability of spatially distributed cytokine signaling feedback loops to produce a relapse in symptoms similar to what we observe in the clinic.

Toxicity Management in CAR T cell therapy for B-ALL: Mathematical modelling as a new avenue for improvement

Shalla Hanson, David Robert Grimes, Jake P. Taylor-King, Benedikt Bauer, Pravnam I. Warman, Ziv Frankenstein, Artem Kaznatcheev, Michael J. Bonassar, Vincent L. Cannataro, Zeinab Y. Motawe, Ernesto A. B. F. Lima, Sungjune Kim, Marco L. Davila, Arturo Araujo
BioRxiv: 049908. 2016

Advances in genetic engineering have made it possible to reprogram individual immune cells to express receptors that recognise markers on tumour cell surfaces. The process of re-engineering T cell lymphocytes to express Chimeric Antigen Receptors (CARs), and then re-infusing the CAR-modified T cells into patients to treat various cancers is referred to as CAR T cell therapy. This therapy is being explored in clinical trials – most prominently for B Cell Acute Lymphoblastic Leukaemia (B-ALL), a common B cell malignancy, for which CAR T cell therapy has led to remission in up to 90% of patients. Despite this extraordinary response rate, however, potentially fatal inflammatory side effects occur in up to 10% of patients who have positive responses. Further, approximately 50% of patients who initially respond to the therapy relapse. Significant improvement is thus necessary before the therapy can be made widely available for use in the clinic. To inform future development, we develop a mathematical model to explore interactions between CAR T cells, inflammatory toxicity, and individual patients’ tumour burdens in silico. This paper outlines the underlying system of coupled ordinary differential equations designed based on well-known immunological principles and widely accepted views on the mechanism of toxicity development in CAR T cell therapy for B-ALL – and reports in silico outcomes in relationship to standard and recently conjectured predictors of toxicity in a heterogeneous, randomly generated patient population. Our initial results and analyses are consistent with and connect immunological mechanisms to the clinically observed, counterintuitive hypothesis that initial tumour burden is a stronger predictor of toxicity than is the dose of CAR T cells administered to patients. We outline how the mechanism of action in CAR T cell therapy can give rise to such non-standard trends in toxicity development, and demonstrate the utility of mathematical modelling in understanding the relationship between predictors of toxicity, mechanism of action, and patient outcomes.

Edge effects in game theoretic dynamics of spatially structured tumours

Artem Kaznatcheev, Jacob G. Scott, David Basanta
Journal of The Royal Society Interface, 12(108): 20150154, 2015
ArXiv 1307.6914v3.

Cancer dynamics are an evolutionary game between cellular phenotypes. A typical assumption in this modelling paradigm is that the probability of a given phenotypic strategy interacting with another depends exclusively on the abundance of those strategies without regard for local neighbourhood structure. We address this limitation by using the Ohtsuki–Nowak transform to introduce spatial structure to the go versus grow game. We show that spatial structure can promote the invasive (go) strategy. By considering the change in neighbourhood size at a static boundary—such as a blood vessel, organ capsule or basement membrane—we show an edge effect that allows a tumour without invasive phenotypes in the bulk to have a polyclonal boundary with invasive cells. We present an example of this promotion of invasive (epithelial–mesenchymal transition-positive) cells in a metastatic colony of prostate adenocarcinoma in bone marrow. Our results caution that pathologic analyses that do not distinguish between cells in the bulk and cells at a static edge of a tumour can underestimate the number of invasive cells. Although we concentrate on applications in mathematical oncology, we expect our approach to extend to other evolutionary game models where interaction neighbourhoods change at fixed system boundaries.

Fidelity drive: a mechanism for chaperone proteins to maintain stable mutation rates in prokaryotes over evolutionary time

Julian Z. Xue, Artem Kaznatcheev, Andre Costopoulos, Frederic Guichard
Journal of Theoretical Biology, 364: 162-167. 2015

We show a mechanism by which chaperone proteins can play a key role in maintaining the long-term evolutionary stability of mutation rates in prokaryotes with perfect genetic linkage. Since chaperones can reduce the phenotypic effects of mutations, higher mutation rate, by affecting chaperones, can increase the phenotypic effects of mutations. This in turn leads to greater mutation effect among the proteins that control mutation repair and DNA replication, resulting in large changes in mutation rate. The converse of this is that when mutation rate is low and chaperones are functioning well, then the rate of change in mutation rate will also be low, leading to low mutation rates being evolutionarily frozen. We show that the strength of this recursion is critical to determining the long-term evolutionary patterns of mutation rate among prokaryotes. If this recursion is weak, then mutation rates can grow without bound, leading to the extinction of the lineage. However, if this recursion is strong, then we can reproduce empirical patterns of prokaryotic mutation rates, where mutation rates remain stable over evolutionary time, and where most mutation rates are low, but with a significant fraction of high mutators.

Evolving useful delusions: Subjectively rational selfishness leads to objectively irrational cooperation

Artem Kaznatcheev, Marcel Montrey, Thomas R. Shultz
Proceedings of the 36th annual conference of the cognitive science society, ArXiv 1405.0041. 2014

We introduce a framework within evolutionary game theory for studying the distinction between objective and subjective rationality and apply it to the evolution of cooperation on 3-regular random graphs. In our simulations, agents evolve misrepresentations of objective reality that help them cooperate and maintain higher social welfare in the Prisoner’s dilemma. These agents act rationally on their subjective representations of the world, but irrationally from the perspective of an external observer. We model misrepresentations as subjective perceptions of payoffs and quasi-magical thinking as an inferential bias, finding that the former is more conducive to cooperation. This highlights the importance of internal representations, not just observed behavior, in evolutionary thought. Our results provide support for the interface theory of perception and suggest that the individual’s interface can serve not only the individual’s aims, but also society as a whole, offering insight into social phenomena such as religion.

Complexity of evolutionary equilibria in static fitness landscapes

Artem Kaznatcheev
ArXiv 1308.5094. 2013

A fitness landscape is a genetic space — with two genotypes adjacent if they differ in a single locus — and a fitness function. Evolutionary dynamics produce a flow on this landscape from lower fitness to higher; reaching equilibrium only if a local fitness peak is found. I use computational complexity to question the common assumption that evolution on static fitness landscapes can quickly reach a local fitness peak. I do this by showing that the popular NK model of rugged fitness landscapes is PLS-complete for K >= 2; the reduction from Weighted 2SAT is a bijection on adaptive walks, so there are NK fitness landscapes where every adaptive path from some vertices is of exponential length. Alternatively — under the standard complexity theoretic assumption that there are problems in PLS not solvable in polynomial time — this means that there are no evolutionary dynamics (known, or to be discovered, and not necessarily following adaptive paths) that can converge to a local fitness peak on all NK landscapes with K = 2. Applying results from the analysis of simplex algorithms, I show that there exist single-peaked landscapes with no reciprocal sign epistasis where the expected length of an adaptive path following strong selection weak mutation dynamics is even though an adaptive path to the optimum of length less than n is available from every vertex. The technical results are written to be accessible to mathematical biologists without a computer science background, and the biological literature is summarized for the convenience of non-biologists with the aim to open a constructive dialogue between the two disciplines.

The evolutionary dominance of ethnocentric cooperation

Max Hartshorn, Artem Kaznatcheev, and Thomas R. Shultz
Journal of Artificial Societies and Social Simulation, 16(3). 2013

Recent agent-based computer simulations suggest that ethnocentrism, often thought to rely on complex social cognition and learning, may have arisen through biological evolution. From a random start, ethnocentric strategies dominate other possible strategies (selfish, traitorous, and humanitarian) based on cooperation or non-cooperation with in-group and out-group agents. Here we show that ethnocentrism eventually overcomes its closest competitor, humanitarianism, by exploiting humanitarian cooperation across group boundaries as world population saturates. Selfish and traitorous strategies are self-limiting because such agents do not cooperate with agents sharing the same genes. Traitorous strategies fare even worse than selfish ones because traitors are exploited by ethnocentrics across group boundaries in the same manner as humanitarians are, via unreciprocated cooperation. By tracking evolution across time, we find individual differences between evolving worlds in terms of early humanitarian competition with ethnocentrism, including early stages of humanitarian dominance. Our evidence indicates that such variation, in terms of differences between humanitarian and ethnocentric agents, is normally distributed and due to early, rather than later, stochastic differences in immigrant strategies.

Limitations of the Dirac formalism as a descriptive framework for cognition

Artem Kaznatcheev and Thomas R. Shultz
Behavioral and Brain Sciences, 36(3):292-293. 2013

We highlight methodological and theoretical limitations of the authors’ Dirac formalism and suggest the von Neumann open systems approach as a resolution. The open systems framework is a generalization of classical probability and we hope it will allow cognitive scientists to extend quantum probability from perception, categorization, memory, decision making, and similarity judgments to phenomena in learning and development.

Ethnocentrism maintains cooperation, but keeping one’s children close fuels it

Artem Kaznatcheev and Thomas R. Shultz
Proceedings of the 33rd annual conference of the cognitive science society, 3174-3179. 2011

Ethnocentrism, commonly thought to rely on complex social cognition, can arise through biological evolution in populations with minimal cognitive abilities. In fact, ethnocentrism is considered to be one of the simplest mechanisms for establishing cooperation in the competitive environment of natural selection. Here we study a recent agent-based model. Through our simulations and analysis, we establish that the mechanism responsible for the emergence of cooperation is children residing close to their parents. Our results suggest that group tags maintain cooperation, but do not create it. We formalize this observation as the dual direct hypothesis: ethnocentric agents dominate humanitarian agents by exploiting the unconditional cooperation of humanitarians of dierent tags to maintain the number of ethnocentric agents after world saturation. We affirm previous observations on the importance of world saturation, finding its drastic effect on dynamics in both spatial tag-based and tag-less models.

Robustness of ethnocentrism to changes in inter-personal interactions

Artem Kaznatcheev
Complex Adaptive Systems – AAAI Fall Symposium. pdf, slides. 2010

We use the methods of evolutionary game theory and computational modelling to examine the evolution of ethnocentrism. We show that ethnocentrism evolves in a spatially structured population not only under prisoner’s dilemma interactions, but also hawk-dove, assurance, harmony, and leader games. In the case of harmony, ethnocentrism evolves even when defection is irrational. This suggests that the pressure of competing for a common resource (in our model: free space) can produce irrational hostility between groups. The minimal cognitive assumptions in our model also suggest that the ethnocentrism observed in humans and elsewhere in nature has an evolutionary basis that is robust over changes in interaction types.

A connectionist study on the interplay of nouns and pronouns in personal pronoun acquisition

Artem Kaznatcheev
Cognitive Computation, 2(4): 280-284. 2010

Cascade-correlation learning is used to model pronoun acquisition in children. The cascade-correlation algorithm is a feed-forward neural network that builds its own topology from input and output units. Personal pronoun acquisition is an interesting non-linear problem in psychology. A mother will refer to her son as you and herself as me, but the son must infer for himself that when he speaks to his mother, she becomes you and he becomes me. Learning the shifting reference of these pronouns is a difficult task that most children master. We show that learning of two different noun-and-pronoun addressee patterns is consistent with naturalistic studies. We observe a surprising factor in pronoun reversal: increasing the amount of exposure to noun patterns can decrease or eliminate reversal errors in children.

The cognitive cost of ethnocentrism

Artem Kaznatcheev
Proceedings of the 32nd annual conference of the cognitive science society, 967-971, slides. 2010

Recent computational studies suggest that ethnocentrism, commonly thought to rely on complex social cognition, may arise through biological evolution in populations with minimal cognitive abilities. We use the methods of evolutionary game theory and computational modelling to examine the evolution of ethnocentrism. Since ethnocentric agents differentiate between in- and out-group partners, and adjust their behavior accordingly, they are more cognitively complex than humanitarian or selfish agents that always cooperate or defect, respectively. We associate a fitness cost with this complexity and test the robustness of ethnocentrism, concluding that ethnocentrism is not robust against increases in cost of cognition. Our model confirms that humanitarians are suppressed largely by ethnocentrics. Paradoxically, we observe that the proportion of cooperation is higher in worlds dominated by ethnocentrics. We conclude that suppressing free-riders, such as selfish and traitorous agents, allows ethnocentrics to maintain higher levels of cooperative interactions.

Self-esteem and the matching effect in mate selection

Artem Kaznatcheev, Kyler Brown, and Thomas R. Shultz
Proceedings of the 32nd annual conference of the cognitive science society, 972-977. 2010

The matching effect is the empirical finding that romantic couples have a high correlation in physical attractiveness. It remains a debate as to whether this correlation is based purely on similarity preference – the matching hypothesis – or marketplace forces. We present a new marketplace model for romantic relationships. Previous models granted every person access to his/her own attractiveness. In reality, people have only a vague idea of their own attractiveness ratings. We introduce a concept analogous to self-esteem to model this phenomenon. Further, we extend beyond previous models by dealing explicitly with both the initialization and development of a relationship. Our model accounts for the experimental tendency to choose more attractive partners, while still explaining observed intra-couple attractiveness correlation and the difference in correlation between casual and serious daters.

Structure of exact and approximate unitary t-designs

Artem Kaznatcheev
pdf 1, pdf 2.

When studying “random” operators it is essential to be able to integrate over the Haar measure, both analytically and algorithmically. Unitary t-designs provide a method to simplify integrating polynomials of degree less than t over U(d). In particular, by replacing averages over the Haar measure by averages over a finite set, they allow applications in algorithms. We provide three equivalent definitions for unitary t-designs and introduce group and approximate designs. The main tool in this note is our generalization of an important result — the trace double sum inequality — into the trace 2p-sum inequality. We use the trace double sum inequality to produce a correspondence between minimal designs and unique minimal weight functions. We culminate our exploration of the structure of t-designs by showing that t-designs span . This result produces two conjectures which we believe are an important step in the classification of minimum unitary t-designs.

Why is ethnocentrism more common than humanitarianism?

Thomas R. Shultz, Max Hartshorn, and Artem Kaznatcheev
Proceedings of the 31st annual conference of the cognitive science society, 2100-2105. 2009

A compelling agent-based computer simulation suggests that ethnocentrism, often thought to rely on complex social cognition and learning, may have arisen through biological evolution (Hammond & Axelrod, 2006). From a neutral start, ethnocentric strategies evolve to dominate other possible strategies (selfish, traitorous, and humanitarian) that differentiate patterns of cooperation with in-group and out-group agents. We present new analyses and simulations to clarify and explain this outcome by formulating and testing two hypotheses for explaining how ethnocentrism eventually dominates its closest competitor, humanitarianism. Results indicate support for the direct hypothesis that ethnocentrics exploit humanitarian cooperation along the frontiers between ethnocentric and humanitarian groups as world population saturates. We find very little support for the contrasting free-rider-suppression hypothesis that ethnocentrics are better than humanitarians at suppressing non-cooperating free riders, although both hypotheses correctly predict a close temporal relation between population saturation and ethnocentric dominance.