Exploiting Social Influence to Control Elections Based on Scoring Rules

Federico Corò, Emilio Cruciani, Gianlorenzo D'Angelo, Stefano PonzianiIJCAI 2019 · DOI

TL;DR

This paper introduces a new model, Linear Threshold Ranking (LTR), to understand how social influence can be leveraged to manipulate election outcomes. They develop a (1-1/e)-approximation algorithm for controlling elections using scoring rules, demonstrating its effectiveness on real-world social networks.

What Problem Does This Paper Address?

In today's digital age, social media platforms are powerful tools for disseminating information and shaping public opinion, especially during political campaigns. This has opened up new avenues for manipulating election results. While previous work has explored election control, this paper addresses the challenge of doing so within a more realistic social influence model. Specifically, they tackle the problem of how an "attacker" can strategically influence a subset of voters in a social network to alter the outcome of an election, aiming to make a target candidate win or lose, using general scoring rule voting systems.

Methods

The core of this paper is the introduction of the Linear Threshold Ranking (LTR) model. This model extends the well-known Linear Threshold Model for opinion diffusion by incorporating the degree of influence voters have on each other and how this influence can shift opinions about a specific candidate.

Key methodological contributions include:

  • Linear Threshold Ranking (LTR): A novel diffusion model that quantifies how influence propagates and changes voter preferences, specifically focusing on a target candidate.
  • Submodularity Proof: The authors prove that the objective function (maximizing a candidate's score) is monotone and submodular with respect to the set of influential voters. This is a crucial theoretical result that allows for efficient approximation algorithms.
  • Greedy Algorithm (Algorithm 1): Leveraging the submodularity property, they propose a greedy algorithm that iteratively selects influential voters to maximize the target candidate's score. This algorithm achieves a (1-1/e) approximation guarantee.
  • Generalization to Scoring Rules: The framework is designed to work with arbitrary scoring rule voting systems, not just simple plurality, making it broadly applicable.
  • Constructive to Destructive Reduction: A clever reduction is presented to adapt the constructive election control problem (making a candidate win) to the destructive case (making a candidate lose).

Datasets

The paper evaluates its algorithm on four real-world social and communication networks:

  • facebook: An undirected network of 10 Facebook users.
  • irvine: A directed network of instant messages from UC Irvine students.
  • netscience: An undirected network of research collaborations.
  • polblogs: A directed network of hyperlinks between US politics blogs.

These networks are used to simulate election scenarios with varying numbers of candidates (m=2, 5, 10) and different influence parameters.

Key Insights and Ideas

  • Social Influence is a Powerful Lever: The research demonstrates that even a small, strategically chosen set of influential voters can significantly impact election outcomes, especially when influence is modeled realistically.
  • Submodularity is Key to Efficiency: The theoretical finding that the influence spread is submodular is critical. It allows for efficient, provably good approximation algorithms, making the problem tractable despite its NP-hard nature.
  • LTR Captures Nuance: The LTR model's ability to account for varying degrees of influence and how it shifts preferences offers a more nuanced understanding of opinion dynamics than simpler models.
  • Generalizability of Scoring Rules: The framework's applicability to various scoring rules (like plurality and Borda count) highlights its broad relevance to different electoral systems.

Key Results

  • The proposed Greedy algorithm achieves a (1-1/e) approximation ratio for both constructive and destructive election control problems under general scoring rules.
  • Experimental results on real-world networks show that the algorithm can significantly increase the Probability of Victory (POV) and Margin of Victory (MOV) for a target candidate.
  • For a scenario with 10 candidates, the algorithm was able to make the target candidate win between 50% and 88% of the times using only 5 seed nodes, depending on the influence parameter 'a'.
  • The algorithm performs well across different datasets and voting systems, though performance can be affected by network topology (e.g., disconnected components in netscience).

Limitations and Future Work

  • Data Availability: The model assumes knowledge of voter preferences and influence degrees, which are often difficult to obtain in real-world scenarios. The paper acknowledges that while estimation is possible, it's a challenge.
  • Model Realism: While LTR is more realistic than previous models, it still relies on certain assumptions about influence propagation.
  • Future Directions:
    • Exploring multi-winner and proportional representation systems.
  • Investigating hybrid approaches combining constructive and destructive control.
  • Developing models for scenarios with unknown voter preferences.
  • Researching methods to prevent election control and ensure the integrity of voting processes (e.g., through network monitoring).

Summary updated

BibTeX
@inproceedings{coro2019exploiting,
  author = {Federico Corò and Emilio Cruciani and Gianlorenzo D'Angelo and Stefano Ponziani},
  title = {{Exploiting Social Influence to Control Elections Based on Scoring Rules}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/29},
}
Figure