Invasion Dynamics in the Biased Voter Process

Loke Durocher, Panagiotis Karras, Andreas Pavlogiannis, Josef Tkadlec

Publikation: Bidrag til bog/antologi/rapport/proceedingKonferencebidrag i proceedingsForskningpeer review

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 ∈ (0, ∞) 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.

OriginalsprogEngelsk
TitelProceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)
Antal sider7
Forlag IJCAI Organization
Publikationsdato2022
Sider265-271
DOI
StatusUdgivet - 2022
Begivenhed31st International Joint Conference on Artificial Intelligence, IJCAI 2022 - Vienna, Østrig
Varighed: 23 jul. 202229 jul. 2022

Konference

Konference31st International Joint Conference on Artificial Intelligence, IJCAI 2022
Land/OmrådeØstrig
ByVienna
Periode23/07/202229/07/2022
SponsorArtificial Intelligence Journal, DiDi Chuxing, et al., FinVolution Group, International Joint Conferences on Artifical Intelligence (IJCAI), Shanghai Artificial Intelligence Industry Association
NavnIJCAI International Joint Conference on Artificial Intelligence
ISSN1045-0823

Fingeraftryk

Dyk ned i forskningsemnerne om 'Invasion Dynamics in the Biased Voter Process'. Sammen danner de et unikt fingeraftryk.

Citationsformater