Abstract | ||
---|---|---|
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\in(0,\infty)$ quantifies the stochastic preference towards ($r>1$) or against ($r<1$) adopting $A$ over $B$. Success is measured in terms of the fixation probability, i.e., the probability that eventually all agents have adopted the mutant trait $A$. In this paper we study the problem of fixation probability maximization under this model: given a budget $k$, find a set of $k$ agents to initiate the invasion that maximizes the fixation probability. We show that the problem is NP-hard for both $r>1$ and $r<1$, while the latter case is also inapproximable within any multiplicative factor. On the positive side, we show that when $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. |
Year | DOI | Venue |
---|---|---|
2022 | 10.24963/ijcai.2022/38 | European Conference on Artificial Intelligence |
Keywords | DocType | Citations |
Agent-based and Multi-agent Systems: Agent Theories and Models,Agent-based and Multi-agent Systems: Agent Societies,Agent-based and Multi-agent Systems: Agent-Based Simulation and Emergence,Agent-based and Multi-agent Systems: Multi-agent Learning,Machine Learning: Optimisation | Conference | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Loke Durocher | 1 | 0 | 0.68 |
Panagiotis Karras | 2 | 0 | 1.35 |
Andreas Pavlogiannis | 3 | 79 | 13.21 |
Josef Tkadlec | 4 | 0 | 0.68 |