Election control through social influence with voters’ uncertainty

Mohammad Abouei Mehrizi (), Federico Corò (), Emilio Cruciani () and Gianlorenzo D’Angelo ()
Additional contact information
Mohammad Abouei Mehrizi: Gran Sasso Science Institute
Federico Corò: Missouri University of Science and Technology
Emilio Cruciani: Paris-Lodron-Universität Salzburg
Gianlorenzo D’Angelo: Gran Sasso Science Institute

Journal of Combinatorial Optimization, 2022, vol. 44, issue 1, No 31, 635-669

Abstract: Abstract The problem of election control through social influence consists in finding a set of nodes in a social network of voters to be the starters of a political campaign aimed at supporting a particular target candidate. The voters reached by the campaign change their views on the candidates. The goal is to model the spread of the campaign in such a way as to maximize the chances of winning for the target candidate. Herein, differently from previous work, we consider that each voter is associated with a probability distribution over the candidates modeling the likelihood of the voter to vote for each candidate. In a first model we propose, we prove that, under the Gap-ETH, the problem cannot be approximated to within a factor better than $$1/n^{o(1)}$$ 1 / n o ( 1 ) , where n is the number of voters. In a second model, which is a slight relaxation of the first one, the problem instead admits a constant-factor approximation algorithm. Finally, we present simulations on both synthetic and real networks, comparing the results of our algorithm with those obtained by a standard greedy algorithm for Influence Maximization.

Keywords: Computational social choice; Election control; Influence maximization; Social influence (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-022-00852-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:44:y:2022:i:1:d:10.1007_s10878-022-00852-3

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-022-00852-3

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().