Author name cluster

Josef Tkadlec

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

2 author rows

IJCAI Conference 2024 Conference Paper

Seed Selection in the Heterogeneous Moran Process

Petros Petsinis
Andreas Pavlogiannis
Josef Tkadlec
Panagiotis Karras

The Moran process is a classic stochastic process that models the rise and takeover of novel traits in network-structured populations. In biological terms, a set of mutants, each with fitness m ∈ (0, ∞) invade a population of residents with fitness 1. Each agent reproduces at a rate proportional to its fitness and each offspring replaces a random network neighbor. The process ends when the mutants either fixate (take over the whole population) or go extinct. The fixation probability measures the success of the invasion. To account for environmental heterogeneity, we study a generalization of the Standard process, called the Heterogeneous Moran process. Here, the fitness of each agent is determined both by its type (resident/mutant) and the node it occupies. We study the natural optimization problem of seed selection: given a budget k, which k agents should initiate the mutant invasion to maximize the fixation probability? We show that the problem is strongly inapproximable: it is NP-hard to distinguish between maximum fixation probability 0 and 1. We then focus on mutant-biased networks, where each node exhibits at least as large mutant fitness as resident fitness. We show that the problem remains NP-hard, but the fixation probability becomes submodular, and thus the optimization problem admits a greedy (1 − 1/e)-approximation. An experimental evaluation of the greedy algorithm along with various heuristics on real-world data sets corroborates our results.

PDF Details DOI

ECAI Conference 2023 Conference Paper

Reachability Poorman Discrete-Bidding Games

Guy Avni
Tobias Meggendorfer
Suman Sadhukhan
Josef Tkadlec
Dorde Zikelic

We consider bidding games, a class of two-player zero-sum graph games. The game proceeds as follows. Both players have bounded budgets. A token is placed on a vertex of a graph, in each turn the players simultaneously submit bids, and the higher bidder moves the token, where we break bidding ties in favor of Player 1. Player 1 wins the game iff the token visits a designated target vertex. We consider, for the first time, poorman discrete-bidding in which the granularity of the bids is restricted and the higher bid is paid to the bank. Previous work either did not impose granularity restrictions or considered Richman bidding (bids are paid to the opponent). While the latter mechanisms are technically more accessible, the former is more appealing from a practical standpoint. Our study focuses on threshold budgets, which is the necessary and sufficient initial budget required for Player 1 to ensure winning against a given Player 2 budget. We first show existence of thresholds. In DAGs, we show that threshold budgets can be approximated with error bounds by thresholds under continuous-bidding and that they exhibit a periodic behavior. We identify closed-form solutions in special cases. We implement and experiment with an algorithm to find threshold budgets.

Details

AAAI Conference 2022 Conference Paper

Fixation Maximization in the Positional Moran Process

Joachim Brendborg
Panagiotis Karras
Andreas Pavlogiannis
Asger Ullersted Rasmussen
Josef Tkadlec

The Moran process is a classic stochastic process that models spread dynamics on graphs. A single “mutant” (e. g. , a new opinion, strain, social trait etc.) invades a population of “residents” scattered over the nodes of a graph. The mutant fitness advantage δ ≥ 0 determines how aggressively mutants propagate to their neighbors. The quantity of interest is the fixation probability, i. e. , the probability that the initial mutant eventually takes over the whole population. However, in realistic settings, the invading mutant has an advantage only in certain locations. E. g. , the ability to metabolize a certain sugar is an advantageous trait to bacteria only when the sugar is actually present in their surroundings. In this paper, we introduce the positional Moran process, a natural generalization in which the mutant fitness advantage is only realized on specific nodes called active nodes, and study the problem of fixation maximization: given a budget k, choose a set of k active nodes that maximize the fixation probability of the invading mutant. We show that the problem is NP-hard, while the optimization function is not submodular, indicating strong computational hardness. We then focus on two natural limits: at the limit of δ → ∞ (strong selection), although the problem remains NP-hard, the optimization function becomes submodular and thus admits a constant-factor greedy approximation; at the limit of δ → 0 (weak selection), we show that we can obtain a tight approximation in O(n2ω ) time, where ω is the matrix-multiplication exponent. An experimental evaluation of the new algorithms along with some proposed heuristics corroborates our results.

PDF Details

IJCAI Conference 2022 Conference Paper

Invasion Dynamics in the Biased Voter Process

Loke Durocher
Panagiotis Karras
Andreas Pavlogiannis
Josef Tkadlec

The voter process is a classic stochastic process that models the invasion of a mutant trait A (e. g. , a new opinion, belief, legend, genetic mutation, magnetic spin) in a population of agents (e. g. , people, genes, particles) who share a resident trait B, spread over the nodes of a graph. An agent may adopt the trait of one of its neighbors at any time, while the invasion bias r quantifies the stochastic preference towards (r>1) or against (r 1 and r 1, the optimization function is submodular and thus can be greedily approximated within a factor 1-1/e. An experimental evaluation of some proposed heuristics corroborates our results.

PDF Details DOI

AAAI Conference 2020 Conference Paper

All-Pay Bidding Games on Graphs

Guy Avni
Rasmus Ibsen-Jensen
Josef Tkadlec

In this paper we introduce and study all-pay bidding games, a class of two player, zero-sum games on graphs. The game proceeds as follows. We place a token on some vertex in the graph and assign budgets to the two players. Each turn, each player submits a sealed legal bid (non-negative and below their remaining budget), which is deducted from their budget and the highest bidder moves the token onto an adjacent vertex. The game ends once a sink is reached, and Player 1 pays Player 2 the outcome that is associated with the sink. The players attempt to maximize their expected outcome. Our games model settings where effort (of no inherent value) needs to be invested in an ongoing and stateful manner. On the negative side, we show that even in simple games on DAGs, optimal strategies may require a distribution over bids with inﬁnite support. A central quantity in bidding games is the ratio of the players budgets. On the positive side, we show a simple FPTAS for DAGs, that, for each budget ratio, outputs an approximation for the optimal strategy for that ratio. We also implement it, show that it performs well, and suggests interesting properties of these games. Then, given an outcome c, we show an algorithm for ﬁnding the necessary and sufﬁcient initial ratio for guaranteeing outcome c with probability 1 and a strategy ensuring such. Finally, while the general case has not previously been studied, solving the speciﬁc game in which Player 1 wins iff he wins the ﬁrst two auctions, has been long stated as an open question, which we solve.

PDF Details

IJCAI Conference 2016 Conference Paper

Robust Draws in Balanced Knockout Tournaments

Krishnendu Chatterjee
Rasmus Ibsen-Jensen
Josef Tkadlec

Balanced knockout tournaments are ubiquitous in sports competitions and are also used in decision-making and elections. The traditional computational question, that asks to compute a draw (optimal draw) that maximizes the winning probability for a distinguished player, has received a lot of attention. Previous works consider the problem where the pairwise winning probabilities are known precisely, while we study how robust is the winning probability with respect to small errors in the pairwise winning probabilities. First, we present several illuminating examples to establish: (a) there exist deterministic tournaments (where the pairwise winning probabilities are 0 or 1) where one optimal draw is much more robust than the other; and (b) in general, there exist tournaments with slightly suboptimal draws that are more robust than all the optimal draws. The above examples motivate the study of the computational problem of robust draws that guarantee a specified winning probability. Second, we present a polynomial-time algorithm for approximating the robustness of a draw for sufficiently small errors in pairwise winning probabilities, and obtain that the stated computational problem is NP-complete. We also show that two natural cases of deterministic tournaments where the optimal draw could be computed in polynomial time also admit polynomial-time algorithms to compute robust optimal draws.

PDF Details