Exploiting Social Influence to Control Elections Based on Scoring Rules

摘要

We consider the election control problem in social networks which consists in exploiting social influence in a network of voters to change their opinion about a target candidate with the aim of increasing his chances to win (constructive control) or lose (destructive control) the election. Previous works on this problem focus on plurality voting systems and on a influence model in which the opinion of the voters about the target candidate can only change by shifting its ranking by one position, regardless of the amount of influence that a voter receives. We introduce Linear Threshold Ranking, a natural extension of Linear Threshold Model, which models the change of opinions taking into account the amount of exercised influence. In this general model, we are able to approximate the maximum score that a target candidate can achieve up to a factor of 1 - 1/e by showing submodularity of the objective function. We exploit this result to provide a 1/3 (1 - 1/e)-approximation algorithm for the constructive election control problem and a 1/2(1 - 1/e)-approximation ratio in the destructive scenario. The algorithm can be used in arbitrary scoring rule voting systems, including plurality rule and borda count.