2 citations · 3 across the 12 of their papers we have counts for
13 papers
Replacers and their evolutionary stability in the Moran process on graphs
Michal Pecho, Jakub Svoboda, Lenka Kopfová +2
Evolutionary dynamics in finite structured populations are commonly modeled by the Moran Birth-death process. A key quantity is the fixation probability of a single invader attempt…
Genotype specificity and spatial arrangement govern the direction and magnitude of selection in variable environments
Hossein Nemati, Kamran Kaveh, Jakub Svoboda +2
Spatial environmental variation can either amplify or suppress the fixation of beneficial mutants in structured populations, yet the interplay of ecological factors and spatial str…
Predicting success of cooperators across arbitrary heterogeneous environmental landscapes
Amir Kargaran, Kamran Kaveh, Krishnendu Chatterjee
Cooperation is central to the organization of complex biological and social systems. Most theoretical models assume homogeneous environments; in reality, populations inhabit spatia…
Approximating the Uniform Value in Hidden Stochastic Games with Doeblin Condition
Krishnendu Chatterjee, David Lurie, Raimundo Saona +1
We study \emph{zero-sum two-player hidden stochastic games}, where players receive partial observations of the state. We focus on a central solution concept for analyzing long-dura…
Boosting Payment Channel Network Liquidity with Topology Optimization and Transaction Selection
Krishnendu Chatterjee, Jan Matyáš Křišťan, Stefan Schmid +2
Payment channel networks (PCNs) are a promising technology that alleviates blockchain scalability by shifting the transaction load from the blockchain to the PCN. Nevertheless, the…
Value Iteration with Guessing for Markov Chains and Markov Decision Processes
Krishnendu Chatterjee, Mahdi JafariRaviz, Raimundo Saona +1
Two standard models for probabilistic systems are Markov chains (MCs) and Markov decision processes (MDPs). Classic objectives for such probabilistic models for control and plannin…
Maintaining diversity in structured populations
David A. Brewster, Jakub Svoboda, Dylan Roscow +3
We examine population structures for their ability to maintain diversity in neutral evolution. We use the general framework of evolutionary graph theory and consider birth-death (b…
Linear Equations with Min and Max Operators: Computational Complexity
Krishnendu Chatterjee, Ruichen Luo, Raimundo Saona +1
We consider a class of optimization problems defined by a system of linear equations with min and max operators. This class of optimization problems has been studied under restrict…
Limit-sure reachability for small memory policies in POMDPs is NP-complete
Ali Asadi, Krishnendu Chatterjee, Raimundo Saona +1
A standard model that arises in several applications in sequential decision making is partially observable Markov decision processes (POMDPs) where a decision-making agent interact…
Deterministic Sub-exponential Algorithm for Discounted-sum Games with Unary Weights
Ali Asadi, Krishnendu Chatterjee, Raimundo Saona +1
Turn-based discounted-sum games are two-player zero-sum games played on finite directed graphs. The vertices of the graph are partitioned between player 1 and player 2. Plays are i…
Uniform Value and Decidability in Ergodic Blind Stochastic Games
Krishnendu Chatterjee, David Lurie, Raimundo Saona +1
We study a class of two-player zero-sum stochastic games known as \textit{blind stochastic games}, where players neither observe the state nor receive any information about it duri…
Concurrent Stochastic Games with Stateful-discounted and Parity Objectives: Complexity and Algorithms
Ali Asadi, Krishnendu Chatterjee, Raimundo Saona +1
We study two-player zero-sum concurrent stochastic games with finite state and action space played for an infinite number of steps. In every step, the two players simultaneously an…
Amplifiers of selection for the Moran process with both Birth-death and death-Birth updating
Jakub Svoboda, Soham Joshi, Josef Tkadlec +1
Populations evolve by accumulating advantageous mutations. Every population has some spatial structure that can be modeled by an underlying network. The network then influences the…