@article{8793,
abstract = {We study optimal election sequences for repeatedly selecting a (very) small group of leaders among a set of participants (players) with publicly known unique ids. In every time slot, every player has to select exactly one player that it considers to be the current leader, oblivious to the selection of the other players, but with the overarching goal of maximizing a given parameterized global (“social”) payoff function in the limit. We consider a quite generic model, where the local payoff achieved by a given player depends, weighted by some arbitrary but fixed real parameter, on the number of different leaders chosen in a round, the number of players that choose the given player as the leader, and whether the chosen leader has changed w.r.t. the previous round or not. The social payoff can be the maximum, average or minimum local payoff of the players. Possible applications include quite diverse examples such as rotating coordinator-based distributed algorithms and long-haul formation flying of social birds. Depending on the weights and the particular social payoff, optimal sequences can be very different, from simple round-robin where all players chose the same leader alternatingly every time slot to very exotic patterns, where a small group of leaders (at most 2) is elected in every time slot. Moreover, we study the question if and when a single player would not benefit w.r.t. its local payoff when deviating from the given optimal sequence, i.e., when our optimal sequences are Nash equilibria in the restricted strategy space of oblivious strategies. As this is the case for many parameterizations of our model, our results reveal that no punishment is needed to make it rational for the players to optimize the social payoff.},
author = {Zeiner, Martin and Schmid, Ulrich and Chatterjee, Krishnendu},
issn = {0166218X},
journal = {Discrete Applied Mathematics},
number = {1},
pages = {392--415},
publisher = {Elsevier},
title = {{Optimal strategies for selecting coordinators}},
doi = {10.1016/j.dam.2020.10.022},
volume = {289},
year = {2021},
}
@inproceedings{9296,
abstract = { matching is compatible to two or more labeled point sets of size n with labels {1,…,n} if its straight-line drawing on each of these point sets is crossing-free. We study the maximum number of edges in a matching compatible to two or more labeled point sets in general position in the plane. We show that for any two labeled convex sets of n points there exists a compatible matching with ⌊2n−−√⌋ edges. More generally, for any ℓ labeled point sets we construct compatible matchings of size Ω(n1/ℓ) . As a corresponding upper bound, we use probabilistic arguments to show that for any ℓ given sets of n points there exists a labeling of each set such that the largest compatible matching has O(n2/(ℓ+1)) edges. Finally, we show that Θ(logn) copies of any set of n points are necessary and sufficient for the existence of a labeling such that any compatible matching consists only of a single edge.},
author = {Aichholzer, Oswin and Arroyo Guevara, Alan M and Masárová, Zuzana and Parada, Irene and Perz, Daniel and Pilz, Alexander and Tkadlec, Josef and Vogtenhuber, Birgit},
booktitle = {15th International Conference on Algorithms and Computation},
isbn = {9783030682101},
issn = {16113349},
location = {Virtual},
pages = {221--233},
publisher = {Springer Nature},
title = {{On compatible matchings}},
doi = {10.1007/978-3-030-68211-8_18},
volume = {12635},
year = {2021},
}
@article{9293,
abstract = {We consider planning problems for graphs, Markov Decision Processes (MDPs), and games on graphs in an explicit state space. While graphs represent the most basic planning model, MDPs represent interaction with nature and games on graphs represent interaction with an adversarial environment. We consider two planning problems with k different target sets: (a) the coverage problem asks whether there is a plan for each individual target set; and (b) the sequential target reachability problem asks whether the targets can be reached in a given sequence. For the coverage problem, we present a linear-time algorithm for graphs, and quadratic conditional lower bound for MDPs and games on graphs. For the sequential target problem, we present a linear-time algorithm for graphs, a sub-quadratic algorithm for MDPs, and a quadratic conditional lower bound for games on graphs. Our results with conditional lower bounds, based on the boolean matrix multiplication (BMM) conjecture and strong exponential time hypothesis (SETH), establish (i) model-separation results showing that for the coverage problem MDPs and games on graphs are harder than graphs, and for the sequential reachability problem games on graphs are harder than MDPs and graphs; and (ii) problem-separation results showing that for MDPs the coverage problem is harder than the sequential target problem.},
author = {Chatterjee, Krishnendu and Dvořák, Wolfgang and Henzinger, Monika and Svozil, Alexander},
issn = {00043702},
journal = {Artificial Intelligence},
number = {8},
publisher = {Elsevier},
title = {{Algorithms and conditional lower bounds for planning problems}},
doi = {10.1016/j.artint.2021.103499},
volume = {297},
year = {2021},
}
@article{9311,
abstract = {Partially observable Markov decision processes (POMDPs) are standard models for dynamic systems with probabilistic and nondeterministic behaviour in uncertain environments. We prove that in POMDPs with long-run average objective, the decision maker has approximately optimal strategies with finite memory. This implies notably that approximating the long-run value is recursively enumerable, as well as a weak continuity property of the value with respect to the transition function. },
author = {Chatterjee, Krishnendu and Saona Urmeneta, Raimundo J and Ziliotto, Bruno},
issn = {0364-765X},
journal = {Mathematics of Operations Research},
keywords = {Management Science and Operations Research, General Mathematics, Computer Science Applications},
publisher = {Institute for Operations Research and the Management Sciences},
title = {{Finite-memory strategies in POMDPs with long-run average objectives}},
doi = {10.1287/moor.2020.1116},
year = {2021},
}
@article{9393,
abstract = {We consider the core algorithmic problems related to verification of systems with respect to three classical quantitative properties, namely, the mean-payoff, the ratio, and the minimum initial credit for energy property. The algorithmic problem given a graph and a quantitative property asks to compute the optimal value (the infimum value over all traces) from every node of the graph. We consider graphs with bounded treewidth—a class that contains the control flow graphs of most programs. Let n denote the number of nodes of a graph, m the number of edges (for bounded treewidth 𝑚=𝑂(𝑛)) and W the largest absolute value of the weights. Our main theoretical results are as follows. First, for the minimum initial credit problem we show that (1) for general graphs the problem can be solved in 𝑂(𝑛2⋅𝑚) time and the associated decision problem in 𝑂(𝑛⋅𝑚) time, improving the previous known 𝑂(𝑛3⋅𝑚⋅log(𝑛⋅𝑊)) and 𝑂(𝑛2⋅𝑚) bounds, respectively; and (2) for bounded treewidth graphs we present an algorithm that requires 𝑂(𝑛⋅log𝑛) time. Second, for bounded treewidth graphs we present an algorithm that approximates the mean-payoff value within a factor of 1+𝜖 in time 𝑂(𝑛⋅log(𝑛/𝜖)) as compared to the classical exact algorithms on general graphs that require quadratic time. Third, for the ratio property we present an algorithm that for bounded treewidth graphs works in time 𝑂(𝑛⋅log(|𝑎⋅𝑏|))=𝑂(𝑛⋅log(𝑛⋅𝑊)), when the output is 𝑎𝑏, as compared to the previously best known algorithm on general graphs with running time 𝑂(𝑛2⋅log(𝑛⋅𝑊)). We have implemented some of our algorithms and show that they present a significant speedup on standard benchmarks.},
author = {Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus and Pavlogiannis, Andreas},
issn = {15728102},
journal = {Formal Methods in System Design},
publisher = {Springer},
title = {{Faster algorithms for quantitative verification in bounded treewidth graphs}},
doi = {10.1007/s10703-021-00373-5},
year = {2021},
}
@article{9402,
abstract = {Direct and indirect reciprocity are key mechanisms for the evolution of cooperation. Direct reciprocity means that individuals use their own experience to decide whether to cooperate with another person. Indirect reciprocity means that they also consider the experiences of others. Although these two mechanisms are intertwined, they are typically studied in isolation. Here, we introduce a mathematical framework that allows us to explore both kinds of reciprocity simultaneously. We show that the well-known ‘generous tit-for-tat’ strategy of direct reciprocity has a natural analogue in indirect reciprocity, which we call ‘generous scoring’. Using an equilibrium analysis, we characterize under which conditions either of the two strategies can maintain cooperation. With simulations, we additionally explore which kind of reciprocity evolves when members of a population engage in social learning to adapt to their environment. Our results draw unexpected connections between direct and indirect reciprocity while highlighting important differences regarding their evolvability.},
author = {Schmid, Laura and Chatterjee, Krishnendu and Hilbe, Christian and Nowak, Martin A.},
issn = {2397-3374},
journal = {Nature Human Behaviour},
publisher = {Springer Nature},
title = {{A unified framework of direct and indirect reciprocity}},
doi = {10.1038/s41562-021-01114-8},
year = {2021},
}
@inbook{9403,
abstract = {Optimal decision making requires individuals to know their available options and to anticipate correctly what consequences these options have. In many social interactions, however, we refrain from gathering all relevant information, even if this information would help us make better decisions and is costless to obtain. This chapter examines several examples of “deliberate ignorance.” Two simple models are proposed to illustrate how ignorance can evolve among self-interested and payoff - maximizing individuals, and open problems are highlighted that lie ahead for future research to explore.},
author = {Schmid, Laura and Hilbe, Christian},
booktitle = {Deliberate Ignorance: Choosing Not To Know},
editor = {Hertwig, Ralph and Engel, Christoph},
isbn = {978-0-262-04559-9},
pages = {139--152},
publisher = {MIT Press},
title = {{The evolution of strategic ignorance in strategic interaction}},
volume = {29},
year = {2021},
}
@phdthesis{8934,
abstract = {In this thesis, we consider several of the most classical and fundamental problems in static analysis and formal verification, including invariant generation, reachability analysis, termination analysis of probabilistic programs, data-flow analysis, quantitative analysis of Markov chains and Markov decision processes, and the problem of data packing in cache management.
We use techniques from parameterized complexity theory, polyhedral geometry, and real algebraic geometry to significantly improve the state-of-the-art, in terms of both scalability and completeness guarantees, for the mentioned problems. In some cases, our results are the first theoretical improvements for the respective problems in two or three decades.},
author = {Goharshady, Amir Kafshdar},
issn = {2663-337X},
pages = {278},
publisher = {IST Austria},
title = {{Parameterized and algebro-geometric advances in static program analysis}},
doi = {10.15479/AT:ISTA:8934},
year = {2021},
}
@inproceedings{8193,
abstract = {Multiple-environment Markov decision processes (MEMDPs) are MDPs equipped with not one, but multiple probabilistic transition functions, which represent the various possible unknown environments. While the previous research on MEMDPs focused on theoretical properties for long-run average payoff, we study them with discounted-sum payoff and focus on their practical advantages and applications. MEMDPs can be viewed as a special case of Partially observable and Mixed observability MDPs: the state of the system is perfectly observable, but not the environment. We show that the specific structure of MEMDPs allows for more efficient algorithmic analysis, in particular for faster belief updates. We demonstrate the applicability of MEMDPs in several domains. In particular, we formalize the sequential decision-making approach to contextual recommendation systems as MEMDPs and substantially improve over the previous MDP approach.},
author = {Chatterjee, Krishnendu and Chmelik, Martin and Karkhanis, Deep and Novotný, Petr and Royer, Amélie},
booktitle = {Proceedings of the 30th International Conference on Automated Planning and Scheduling},
issn = {23340843},
location = {Nancy, France},
pages = {48--56},
publisher = {Association for the Advancement of Artificial Intelligence},
title = {{Multiple-environment Markov decision processes: Efficient analysis and applications}},
volume = {30},
year = {2020},
}
@inproceedings{8272,
abstract = {We study turn-based stochastic zero-sum games with lexicographic preferences over reachability and safety objectives. Stochastic games are standard models in control, verification, and synthesis of stochastic reactive systems that exhibit both randomness as well as angelic and demonic non-determinism. Lexicographic order allows to consider multiple objectives with a strict preference order over the satisfaction of the objectives. To the best of our knowledge, stochastic games with lexicographic objectives have not been studied before. We establish determinacy of such games and present strategy and computational complexity results. For strategy complexity, we show that lexicographically optimal strategies exist that are deterministic and memory is only required to remember the already satisfied and violated objectives. For a constant number of objectives, we show that the relevant decision problem is in NP∩coNP , matching the current known bound for single objectives; and in general the decision problem is PSPACE -hard and can be solved in NEXPTIME∩coNEXPTIME . We present an algorithm that computes the lexicographically optimal strategies via a reduction to computation of optimal strategies in a sequence of single-objectives games. We have implemented our algorithm and report experimental results on various case studies.},
author = {Chatterjee, Krishnendu and Katoen, Joost P and Weininger, Maximilian and Winkler, Tobias},
booktitle = {International Conference on Computer Aided Verification},
isbn = {9783030532901},
issn = {16113349},
pages = {398--420},
publisher = {Springer Nature},
title = {{Stochastic games with lexicographic reachability-safety objectives}},
doi = {10.1007/978-3-030-53291-8_21},
volume = {12225},
year = {2020},
}
@inproceedings{8533,
abstract = {Game of Life is a simple and elegant model to study dynamical system over networks. The model consists of a graph where every vertex has one of two types, namely, dead or alive. A configuration is a mapping of the vertices to the types. An update rule describes how the type of a vertex is updated given the types of its neighbors. In every round, all vertices are updated synchronously, which leads to a configuration update. While in general, Game of Life allows a broad range of update rules, we focus on two simple families of update rules, namely, underpopulation and overpopulation, that model several interesting dynamics studied in the literature. In both settings, a dead vertex requires at least a desired number of live neighbors to become alive. For underpopulation (resp., overpopulation), a live vertex requires at least (resp. at most) a desired number of live neighbors to remain alive. We study the basic computation problems, e.g., configuration reachability, for these two families of rules. For underpopulation rules, we show that these problems can be solved in polynomial time, whereas for overpopulation rules they are PSPACE-complete.},
author = {Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus and Jecker, Ismael R and Svoboda, Jakub},
booktitle = {45th International Symposium on Mathematical Foundations of Computer Science},
isbn = {9783959771597},
issn = {18688969},
location = {Prague, Czech Republic},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{Simplified game of life: Algorithms and complexity}},
doi = {10.4230/LIPIcs.MFCS.2020.22},
volume = {170},
year = {2020},
}
@inproceedings{8534,
abstract = {A regular language L of finite words is composite if there are regular languages L₁,L₂,…,L_t such that L = ⋂_{i = 1}^t L_i and the index (number of states in a minimal DFA) of every language L_i is strictly smaller than the index of L. Otherwise, L is prime. Primality of regular languages was introduced and studied in [O. Kupferman and J. Mosheiff, 2015], where the complexity of deciding the primality of the language of a given DFA was left open, with a doubly-exponential gap between the upper and lower bounds. We study primality for unary regular languages, namely regular languages with a singleton alphabet. A unary language corresponds to a subset of ℕ, making the study of unary prime languages closer to that of primality in number theory. We show that the setting of languages is richer. In particular, while every composite number is the product of two smaller numbers, the number t of languages necessary to decompose a composite unary language induces a strict hierarchy. In addition, a primality witness for a unary language L, namely a word that is not in L but is in all products of languages that contain L and have an index smaller than L’s, may be of exponential length. Still, we are able to characterize compositionality by structural properties of a DFA for L, leading to a LogSpace algorithm for primality checking of unary DFAs.},
author = {Jecker, Ismael R and Kupferman, Orna and Mazzocchi, Nicolas},
booktitle = {45th International Symposium on Mathematical Foundations of Computer Science},
isbn = {9783959771597},
issn = {18688969},
location = {Prague, Czech Republic},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{Unary prime languages}},
doi = {10.4230/LIPIcs.MFCS.2020.51},
volume = {170},
year = {2020},
}
@inproceedings{8600,
abstract = {A vector addition system with states (VASS) consists of a finite set of states and counters. A transition changes the current state to the next state, and every counter is either incremented, or decremented, or left unchanged. A state and value for each counter is a configuration; and a computation is an infinite sequence of configurations with transitions between successive configurations. A probabilistic VASS consists of a VASS along with a probability distribution over the transitions for each state. Qualitative properties such as state and configuration reachability have been widely studied for VASS. In this work we consider multi-dimensional long-run average objectives for VASS and probabilistic VASS. For a counter, the cost of a configuration is the value of the counter; and the long-run average value of a computation for the counter is the long-run average of the costs of the configurations in the computation. The multi-dimensional long-run average problem given a VASS and a threshold value for each counter, asks whether there is a computation such that for each counter the long-run average value for the counter does not exceed the respective threshold. For probabilistic VASS, instead of the existence of a computation, we consider whether the expected long-run average value for each counter does not exceed the respective threshold. Our main results are as follows: we show that the multi-dimensional long-run average problem (a) is NP-complete for integer-valued VASS; (b) is undecidable for natural-valued VASS (i.e., nonnegative counters); and (c) can be solved in polynomial time for probabilistic integer-valued VASS, and probabilistic natural-valued VASS when all computations are non-terminating.},
author = {Chatterjee, Krishnendu and Henzinger, Thomas A and Otop, Jan},
booktitle = {31st International Conference on Concurrency Theory},
isbn = {9783959771603},
issn = {18688969},
location = {Virtual},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{Multi-dimensional long-run average problems for vector addition systems with states}},
doi = {10.4230/LIPIcs.CONCUR.2020.23},
volume = {171},
year = {2020},
}
@article{8671,
abstract = {We study relations between evidence theory and S-approximation spaces. Both theories have their roots in the analysis of Dempsterchr('39')s multivalued mappings and lower and upper probabilities, and have close relations to rough sets. We show that an S-approximation space, satisfying a monotonicity condition, can induce a natural belief structure which is a fundamental block in evidence theory. We also demonstrate that one can induce a natural belief structure on one set, given a belief structure on another set, if the two sets are related by a partial monotone S-approximation space. },
author = {Shakiba, A. and Goharshady, Amir Kafshdar and Hooshmandasl, M.R. and Alambardar Meybodi, M.},
issn = {20089473},
journal = {Iranian Journal of Mathematical Sciences and Informatics},
number = {2},
pages = {117--128},
publisher = {ACECR Tarbiat Modares University},
title = {{A note on belief structures and s-approximation spaces}},
doi = {10.29252/ijmsi.15.2.117},
volume = {15},
year = {2020},
}
@article{8767,
abstract = {Resources are rarely distributed uniformly within a population. Heterogeneity in the concentration of a drug, the quality of breeding sites, or wealth can all affect evolutionary dynamics. In this study, we represent a collection of properties affecting the fitness at a given location using a color. A green node is rich in resources while a red node is poorer. More colors can represent a broader spectrum of resource qualities. For a population evolving according to the birth-death Moran model, the first question we address is which structures, identified by graph connectivity and graph coloring, are evolutionarily equivalent. We prove that all properly two-colored, undirected, regular graphs are evolutionarily equivalent (where “properly colored” means that no two neighbors have the same color). We then compare the effects of background heterogeneity on properly two-colored graphs to those with alternative schemes in which the colors are permuted. Finally, we discuss dynamic coloring as a model for spatiotemporal resource fluctuations, and we illustrate that random dynamic colorings often diminish the effects of background heterogeneity relative to a proper two-coloring.},
author = {Kaveh, Kamran and McAvoy, Alex and Chatterjee, Krishnendu and Nowak, Martin A.},
issn = {1553-7358},
journal = {PLOS Computational Biology},
keywords = {Ecology, Modelling and Simulation, Computational Theory and Mathematics, Genetics, Ecology, Evolution, Behavior and Systematics, Molecular Biology, Cellular and Molecular Neuroscience},
number = {11},
publisher = {Public Library of Science},
title = {{The Moran process on 2-chromatic graphs}},
doi = {10.1371/journal.pcbi.1008402},
volume = {16},
year = {2020},
}
@article{8788,
abstract = {We consider a real-time setting where an environment releases sequences of firm-deadline tasks, and an online scheduler chooses on-the-fly the ones to execute on a single processor so as to maximize cumulated utility. The competitive ratio is a well-known performance measure for the scheduler: it gives the worst-case ratio, among all possible choices for the environment, of the cumulated utility of the online scheduler versus an offline scheduler that knows these choices in advance. Traditionally, competitive analysis is performed by hand, while automated techniques are rare and only handle static environments with independent tasks. We present a quantitative-verification framework for precedence-aware competitive analysis, where task releases may depend on preceding scheduling choices, i.e., the environment can respond to scheduling decisions dynamically . We consider two general classes of precedences: 1) follower precedences force the release of a dependent task upon the completion of a set of precursor tasks, while and 2) pairing precedences modify the characteristics of a dependent task provided the completion of a set of precursor tasks. Precedences make competitive analysis challenging, as the online and offline schedulers operate on diverging sequences. We make a formal presentation of our framework, and use a GPU-based implementation to analyze ten well-known schedulers on precedence-based application examples taken from the existing literature: 1) a handshake protocol (HP); 2) network packet-switching; 3) query scheduling (QS); and 4) a sporadic-interrupt setting. Our experimental results show that precedences and task parameters can vary drastically the best scheduler. Our framework thus supports application designers in choosing the best scheduler among a given set automatically.},
author = {Pavlogiannis, Andreas and Schaumberger, Nico and Schmid, Ulrich and Chatterjee, Krishnendu},
issn = {19374151},
journal = {IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems},
number = {11},
pages = {3981--3992},
publisher = {IEEE},
title = {{Precedence-aware automated competitive analysis of real-time scheduling}},
doi = {10.1109/TCAD.2020.3012803},
volume = {39},
year = {2020},
}
@article{8789,
abstract = {Cooperation is a ubiquitous and beneficial behavioural trait despite being prone to exploitation by free-riders. Hence, cooperative populations are prone to invasions by selfish individuals. However, a population consisting of only free-riders typically does not survive. Thus, cooperators and free-riders often coexist in some proportion. An evolutionary version of a Snowdrift Game proved its efficiency in analysing this phenomenon. However, what if the system has already reached its stable state but was perturbed due to a change in environmental conditions? Then, individuals may have to re-learn their effective strategies. To address this, we consider behavioural mistakes in strategic choice execution, which we refer to as incompetence. Parametrising the propensity to make such mistakes allows for a mathematical description of learning. We compare strategies based on their relative strategic advantage relying on both fitness and learning factors. When strategies are learned at distinct rates, allowing learning according to a prescribed order is optimal. Interestingly, the strategy with the lowest strategic advantage should be learnt first if we are to optimise fitness over the learning path. Then, the differences between strategies are balanced out in order to minimise the effect of behavioural uncertainty.},
author = {Kleshnina, Maria and Streipert, Sabrina and Filar, Jerzy and Chatterjee, Krishnendu},
issn = {22277390},
journal = {Mathematics},
number = {11},
publisher = {MDPI},
title = {{Prioritised learning in snowdrift-type games}},
doi = {10.3390/math8111945},
volume = {8},
year = {2020},
}
@phdthesis{7196,
abstract = {In this thesis we study certain mathematical aspects of evolution. The two primary forces that drive an evolutionary process are mutation and selection. Mutation generates new variants in a population. Selection chooses among the variants depending on the reproductive rates of individuals. Evolutionary processes are intrinsically random – a new mutation that is initially present in the population at low frequency can go extinct, even if it confers a reproductive advantage. The overall rate of evolution is largely determined by two quantities: the probability that an invading advantageous mutation spreads through the population (called fixation probability) and the time until it does so (called fixation time). Both those quantities crucially depend not only on the strength of the invading mutation but also on the population structure. In this thesis, we aim to understand how the underlying population structure affects the overall rate of evolution. Specifically, we study population structures that increase the fixation probability of advantageous mutants (called amplifiers of selection). Broadly speaking, our results are of three different types: We present various strong amplifiers, we identify regimes under which only limited amplification is feasible, and we propose population structures that provide different tradeoffs between high fixation probability and short fixation time.},
author = {Tkadlec, Josef},
issn = {2663-337X},
pages = {144},
publisher = {IST Austria},
title = {{A role of graphs in evolutionary processes}},
doi = {10.15479/AT:ISTA:7196},
year = {2020},
}
@article{7212,
abstract = {The fixation probability of a single mutant invading a population of residents is among the most widely-studied quantities in evolutionary dynamics. Amplifiers of natural selection are population structures that increase the fixation probability of advantageous mutants, compared to well-mixed populations. Extensive studies have shown that many amplifiers exist for the Birth-death Moran process, some of them substantially increasing the fixation probability or even guaranteeing fixation in the limit of large population size. On the other hand, no amplifiers are known for the death-Birth Moran process, and computer-assisted exhaustive searches have failed to discover amplification. In this work we resolve this disparity, by showing that any amplification under death-Birth updating is necessarily bounded and transient. Our boundedness result states that even if a population structure does amplify selection, the resulting fixation probability is close to that of the well-mixed population. Our transience result states that for any population structure there exists a threshold r⋆ such that the population structure ceases to amplify selection if the mutant fitness advantage r is larger than r⋆. Finally, we also extend the above results to δ-death-Birth updating, which is a combination of Birth-death and death-Birth updating. On the positive side, we identify population structures that maintain amplification for a wide range of values r and δ. These results demonstrate that amplification of natural selection depends on the specific mechanisms of the evolutionary process.},
author = {Tkadlec, Josef and Pavlogiannis, Andreas and Chatterjee, Krishnendu and Nowak, Martin A.},
issn = {15537358},
journal = {PLoS computational biology},
publisher = {PLoS},
title = {{Limits on amplifiers of natural selection under death-Birth updating}},
doi = {10.1371/journal.pcbi.1007494},
volume = {16},
year = {2020},
}
@article{7343,
abstract = {Coinfections with multiple pathogens can result in complex within‐host dynamics affecting virulence and transmission. While multiple infections are intensively studied in solitary hosts, it is so far unresolved how social host interactions interfere with pathogen competition, and if this depends on coinfection diversity. We studied how the collective disease defences of ants – their social immunity – influence pathogen competition in coinfections of same or different fungal pathogen species. Social immunity reduced virulence for all pathogen combinations, but interfered with spore production only in different‐species coinfections. Here, it decreased overall pathogen sporulation success while increasing co‐sporulation on individual cadavers and maintaining a higher pathogen diversity at the community level. Mathematical modelling revealed that host sanitary care alone can modulate competitive outcomes between pathogens, giving advantage to fast‐germinating, thus less grooming‐sensitive ones. Host social interactions can hence modulate infection dynamics in coinfected group members, thereby altering pathogen communities at the host level and population level.},
author = {Milutinovic, Barbara and Stock, Miriam and Grasse, Anna V and Naderlinger, Elisabeth and Hilbe, Christian and Cremer, Sylvia},
issn = {1461-023X},
journal = {Ecology Letters},
number = {3},
pages = {565--574},
publisher = {Wiley},
title = {{Social immunity modulates competition between coinfecting pathogens}},
doi = {10.1111/ele.13458},
volume = {23},
year = {2020},
}