Tags:Algorithm Design, Election Manipulation and Social Networks
Abstract:
We investigate the effects of the social influence in determining the behaviour of agents in a social network in the context of an election. In particular, we concentrate our attention on how the structure of a social network can be manipulated in order to determine the outcome of an election.
We consider an election with $m$ candidates and $n$ voters, each one with her own ranking on the candidates. Voters are part of a social network and the information that each voter has about the election is limited to what her friends are voting. We consider an iterative elective process where, at each round, each voter decides her vote strategically, based on what her neighbors voted in the previous round and her ranking. Thus, a voter may decide to vote for a candidate different from her favorite to avoid the election of a candidate she dislikes.
Following [Sina et al., 2015] we investigate how a central organization that knows rankings of all the voters and the structure of the social network can determine the outcome of the election by creating new connections among voters.
Our main result is an algorithm that, under mild conditions on the social network topology and on the voters' rankings, is able to produce a limited number of links to be added to the social network in order to make our designed candidate the winner of the election. Our results can be seen as another indication that who controls social media can have a great influence on our lives by strategically determining what information we are exposed.
Manipulating an Election in Social Networks through Edge Addition