Election manipulation on social networks with messages on multiple candidates

In electoral contexts, the presence of manipulators attempting to corrupt the election's integrity is a source of major concern. In this thesis, the problem of election control through social influence is analyzed in the perspective that the manipulator can place seeds in the network for sending both positive and negative messages on multiple candidates. Our model widely extends the previous results available in the literature that only study the influence of a single message on a single candidate. In particular, hardness results and a tight characterization of the settings in which the maximum increase in the margin of victory cannot be approximated are provided. It is shown that this inapproximability result holds also for networks with simple topologies, as undirected graphs with every node having degree at most two or directed trees. In particular, the greedy approach, that represents the main class of algorithms adopted for social influence problems, fails when applied to those settings. Then, it is proved that, dropping the condition behind inapproximability, poly-time constant-approximation algorithms can be designed. Finally, a more detailed analysis is developed for the case of only three candidates running for the election, introducing also various extensions and generalization of the model.

In contesti elettorali, la presenza di manipolatori con l'intento di intaccare l'integrità dell'elezione è fonte di grande preoccupazione. In questa tesi viene analizzato il problema del controllo sulle elezioni tramite influenza sociale supponendo che il manipolatore possa agire su alcuni individui nella rete per diffondere messaggi sia positivi che negativi su più di un candidato, estendendo così i precedenti risultati presenti in letteratura che ipotizzano la diffusione di un singolo messaggio per un solo candidato. In particolare, sono introdotti risultati di hardness e una caratterizzazione stringente degli scenari in cui l'aumento massimo del margine di vittoria non può essere approssimato. Viene mostrato inoltre che questo risultato di inapprossimabilità vale anche per reti molto semplici, come grafi indiretti con ogni nodo di grado al più due o alberi diretti. Per essi infatti l'approccio greedy, che rappresenta la principale classe di algoritmi adottata per problemi di influenza sociale, fallisce. Viene poi dimostrato che, se la condizione legata all'inapprossimabilità non vale, possono essere definiti algoritmi di approssimazione costante in tempo polinomiale. Infine, un'analisi più dettagliata viene sviluppata per il caso in cui vi sono solo tre candidati a concorrere alle elezioni, introducendo anche varie estensioni e generalizzazioni del modello.