Multi-winner election control via social influence

The extensive use of social media in political campaigns has motivated the recent study of election control problem in social networks. In an election, we are given a set of voters, each having a preference list over a set of candidates, that are distributed on a social network. The winners of the election are computed by aggregating the preference lists of voters according to a so-called voting rule. We consider a scenario where voters may change their preference lists as a consequence of the messages received by their neighbors in a social network. Specifically, we consider a political campaign that spreads messages in a social network in support or against a given candidate and the spreading follows a dynamic model for information diffusion. When a message reaches a voter, this latter changes its preference list according to an update rule. The election control problem asks to find a bounded set of nodes to be the starter of a political campaign in support (constructive problem) or against (destructive problem) a given target candidate c, in such a way that the margin of victory of c w.r.t. its most voted opponents is maximized. It has been shown that several variants of the problem can be solved within a constant factor approximation of the optimum, which shows that controlling elections by means of social networks is doable and constitutes a real problem for modern democracies. Most of the literature, however, focuses on the case of single-winner elections. In this paper, we define the election control problem in social networks for multi-winner elections with the aim of modeling parliamentarian elections. Differently from the single-winner case, we show that the multi-winner election control problem is -hard to approximate within any factor in both constructive and destructive cases. We then study a relaxation of the problem where votes are aggregated on the basis of parties (instead of single candidates), which is a variation of the so-called straight-party voting used in some real parliamentarian elections. We show that the latter problem remains -hard but can be approximated within a constant factor.