Election Manipulation on Social Networks with Positive and Negative Messages
share
We study the problem of election control through social influence when the manipulator is allowed to use the locations that she acquired on the network for sending both positive and negative messages. We investigate the tie-breaking rules that can emerge in this scenario and explore various generalizations, widely extending the previous results available in the literature. In particular, we provide a tight characterization of the settings in which the maximum increase in the margin of victory can be efficiently approximated and of those in which any approximation turns out to be impossible. We also show that, in simple networks, a large class of algorithms, mainly including all approaches recently adopted for social-influence problems, fail to compute a bounded approximation even on very simple networks, as undirected graphs with every node having a degree at most two or directed trees.
READ FULL TEXT