Persuading voters in district-based elections

Following the 2016 US presidential elections a number of commentators have suggested that Donald Trump would not have been elected president were it not for the influence of fake news. As we approach the next presidential election, the question of how the spread of false and misleading news can affect the election result has gain renewed interest. In this work, we model this problem by means of the Bayesian persuasion framework and ask whether it is computationally tractable to design a signaling scheme maximizing the probability with which a target candidate is elected in a district-based election. Given the variety of possible media over which fake news can circulate, we analyse three different types of signaling schemes: private, public and the novelty concept of semi-public signaling scheme. We show that the sender is not indifferent with respect to which kind of media is chosen to disclose fake news. In particular, we prove that the sender can perform arbitrarily worse when restricted to use public or semi-public signaling schemes. The different signaling schemes show a stark contrast also in terms of their computational complexity. When private signals are allowed, we show that an optimal signaling scheme can be efficiently computed. On the other hand, the sender’s optimal expected utility cannot be even approximated in polynomial time, using public or semi-public signaling schemes. In an attempt to overcome these inapproximability results, we introduce a new concept of stability, and we study the general problem of computing approximately optimal public signaling schemes when the sender's objective is replaced by another function, that approximates and is stable compared to the original objective. In this context, we provide an important contribution by extending the previous results to the case of state-dependent objective functions. Finally, we employ this result to provide efficient tri-criteria approximation algorithms for computing public and semi-public signaling schemes in district-based elections.

A seguito delle elezioni presidenziali del 2016 in Stati Uniti, alcuni commentatori hanno suggerito che Donald Trump non sarebbe stato eletto presidente se non fosse stato per l'influenza esercitata sugli elettori attraverso la diffusione di fake news. Ora che si avvicinano le nuove elezioni presidenziali, la questione di come la diffusione di notizie false e fuorvianti possa influenzare il risultato elettorale ha suscitato un rinnovato interesse. In questo lavoro, viene studiato il problema attraverso il modello di persuasione Bayesiana, analizzando la complessità computazionale insita nel progettare uno schema di segnalazione che massimizzi la probabilità con cui un dato candidato viene eletto in un'elezione distrettuale. Data la varietà di media su cui possono circolare le fake news, vengono analizzati tre diversi tipi di schemi di segnalazione: privato, pubblico e semi-pubblico, introducendo con quest’ultima categoria un nuovo concetto nell’ambito dei possibili schemi di segnalazione. Viene mostrato che la scelta del canale comunicativo nel quale far circolare le fake news ha un ruolo rilevante. In particolare, viene mostrato come i risultati ottenibili utilizzando schemi di segnalazione privati possano peggiorare in maniera arbitraria quando ci si limita a considerare schemi di segnalazione pubblici o semi-pubblici. I diversi schemi di segnalazione non solo si differenziano in termini di prestazioni, ma mostrano inoltre un netto contrasto anche in termini di complessità computazionale. In particolare, viene mostrato che quando sono consentiti segnali privati, uno schema di segnalazione ottimo può essere calcolato in modo efficiente. Viceversa, lo schema di segnalazione ottimo non può neppure essere approssimato in tempo polinomiale se si usano schemi di segnalazione pubblici o semi-pubblici. Nel tentativo di superare questi risultati di inapprossimabilità, introduciamo un nuovo concetto di stabilità di una funzione e studiamo il problema di calcolare schemi di segnalazione pubblici approssimativamente ottimali, quando la funzione obbiettivo viene sostituita con un'altra funzione che la approssima ed è stabile rispetto a questa. In questo contesto apportiamo un importante contributo estendendo i precedenti risultati al caso di funzioni obbiettivo dipendenti dallo stato. Infine, sfruttando questo risultato dimostriamo come sia possibile calcolare in maniera efficiente un'approssimazione a tre criteri per progettare schemi di segnalazione pubblici e semi-pubblici nel contesto di un'elezione distrettuale.