# persuading_voters_in_districtbased_elections__abc32529.pdf

Persuading Voters in District-based Elections

Matteo Castiglioni, Nicola Gatti Politecnico di Milano, Piazza Leonardo da Vinci 32, I-20133, Milan, Italy matteo.castiglioni@polimi.it, nicola.gatti@polimi.it

We focus on the scenario in which an agent can exploit his information advantage to manipulate the outcome of an election. In particular, we study district-based elections with two candidates, in which the winner of the election is the candidate that wins in the majority of the districts. District-based elections are adopted worldwide (e.g., UK and USA) and are a natural extension of widely studied voting mechanisms (e.g., k-voting and plurality voting). We resort to the Bayesian persuasion framework, where the manipulator (sender) strategically discloses information to the voters (receivers) that update their beliefs rationally. We study both private signaling, in which the sender can use a private communication channel per receiver, and public signaling, in which the sender can use a single communication channel for all the receivers. Furthermore, for the first time, we introduce semi-public signaling in which the sender can use a single communication channel per district. We show that there is a sharp distinction between private and (semi-)public signaling. In particular, optimal private signaling schemes can provide an arbitrarily better probability of victory than (semi-)public ones and can be computed efficiently, while optimal (semi-)public signaling schemes cannot be approximated to within any factor in polynomial time unless P = NP. However, we show that reasonable relaxations allow the design of multi-criteria PTASs for optimal (semi-)public signaling schemes. In doing so, we introduce a novel property, namely comparative stability, and we design a bi-criteria PTAS for public signaling in general Bayesian persuasion problems beyond elections when the sender s utility function is state-dependent.

Introduction The fairness and efficiency of democratic elections largely depend on the news provided by the media. Indeed, often, citizens are called to express opinions on complex choices they do not know deeply enough to express informed judgments. Therefore, multiple and reliable sources of information providing fair and in-depth coverage of the public debate are crucial to guarantee the democratic process. However, most of the information shaping the voters opinions is not disclosed to inform in a disinterested way but instead aims to direct voters political orientation, thus persuading them to prefer one specific candidate over another.

Copyright c 2021, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

As recently showed by Allcott and Gentzkow (2017) and Guess, Nyhan, and Reifler (2018) for the 2016 US presidential election, the spread of fake news has become a major public concern for democracy. The problem of assessing the extent to which it is possible to manipulate an election has received considerable attention under the general framework of election control and has been investigated according to several perspectives, such as control by bribery (Faliszewski et al. 2009; Erd elyi, Reger, and Yang 2020) or by adding and deleting candidates and voters (Loreggia et al. 2015; Faliszewski, Hemaspaandra, and Hemaspaandra 2011; Liu et al. 2009; Chen et al. 2017). More recently, Sina et al. (2015), Faliszewski et al. (2018), Wilder and Vorobeychik (2018), Wilder and Vorobeychik (2019), and Castiglioni, Ferraioli, and Gatti (2020) studied social influence as a means of election control. In this paper, we pose the following question: can an informed agent use his information advantage to influence an election s outcome by the partial disclosure of information to rational voters?

According to the classical Bayesian persuasion framework by Kamenica and Gentzkow (2011), the above problem can be formulated as a game with asymmetric information, where a sender can influence the behavior of the receiver(s) through the strategic provision of payoff-relevant information. In particular, the sender can strategically reveal information by means of a signaling scheme that determines who knows what about the parameters that govern the payoff functions. Alonso and Cˆamara (2016), Chan et al. (2019), and Bardhi and Guo (2018) provide the seminal attempts to apply the Bayesian persuasion framework to voting. More recently, Castiglioni, Celli, and Gatti (2020a) and Castiglioni, Celli, and Gatti (2020b) investigated its computational issues. All the aforementioned works focus on kvoting or plurality-voting elections. Differently, in this paper, we study for the first time how Bayesian persuasion can be adopted in more challenging settings such as districtbased elections with two candidates, in which the winner of the election is the candidate winning in the majority of the districts. We focus on the setting with no inter-agent externalities where each receiver s utility depends only on his action and the realized state of nature, but not on the other receivers actions. This assumption is well-motivated, as voting for the most preferred candidate is a weakly dominant strategy in two-candidate elections.

The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21)

Two forms of signals are customarily investigated in the literature. With private signals, the sender can target different information to different receivers. Instead, with public signals, the sender can only communicate the same information to every receiver. Even if private persuasion may be more beneficial for the sender, sometimes, as in election settings where there are too many receivers, privately communicating to each receiver may be impracticable. At the same time, public communication is much easier to implement, e.g., through TVs or newspapers. We introduce a new form of signaling, called semi-public, to model situations between private and public settings in district-based elections, where all the receivers of the same district observe the same signal, but the sender can target different information to different districts. Indeed, the voters are often reached by local communication shared with the voters in the same location, e.g., local newspapers, electoral posters and rallies.

Original Contributions We study the efficiency and complexity of signaling in district-based elections with two candidates. First, we compare private, public, and semi-public signaling schemes in terms of efficiency when used to manipulate elections, showing that private signaling schemes perform arbitrarily better than (semi-)public schemes. Then, we show that optimal private signaling schemes can be computed efficiently, while the direct use of the results provided by Castiglioni, Celli, and Gatti (2020a) shows that the problem is inapproximable with (semi-)public signaling. However, we prove that multi-criteria Polynomial-Time Approximation Schemes (PTASs) for public and semi-public signaling schemes are possible when some relaxations are made. In particular, in the case of semi-public persuasion, we allow ϵ-persuasiveness and lower the number of districts to control needed to win the election by an arbitrary constant factor w.r.t. the majority. Instead, in the case of public persuasion, we also need to lower the number of votes needed to win in a district by an arbitrary constant factor w.r.t. the majority. In doing so, we introduce a novel property, namely comparative stability, and we design a bi-criteria PTAS to compute public signaling schemes in general Bayesian persuasion problems beyond district-based elections. Our result extends that by Xu (2020), allowing state-dependent sender s utility functions and generalizing from stable to comparative stable sender s utility functions.

Related Works The seminal model of Bayesian persuasion with a single receiver is introduced by Kamenica and Gentzkow (2011). This model is extended, allowing multiple receivers, by Bergemann and Morris (2016a), Bergemann and Morris (2016b), Wang (2013), and Taneva (2019). Furthermore, Alonso and Cˆamara (2016), Bardhi and Guo (2018) and Chan et al. (2019) provide the first attempts of applying the Bayesian persuasion framework to voting. In particular, Bardhi and Guo (2018) and Chan et al. (2019) study unanimity voting and k-voting rules, respectively, in settings with binary actions and state spaces. Instead, Alonso and Cˆamara (2016) employ a novel geometric tool to characterize an optimal public signaling scheme in voting.

In addition to the works mentioned above, which provide the economic groundings of Bayesian persuasion in (simple) voting settings, other works study election problems from a computational perspective. In particular, Arieli and Babichenko (2019) study the problem of private Bayesian persuasion with no inter-agent externalities. In the case of binary state spaces and k-voting rule, they provide a characterization of the optimal private signaling schemes.1 Cheng et al. (2015) study the same k-voting problem with public persuasion, providing a polynomial-time approximation algorithm for a relaxed version of the problem in which the number of votes needed to win the election is reduced by an arbitrary constant factor and ϵ-persuasiveness is adopted. Castiglioni, Celli, and Gatti (2020a) extend the previous models to settings with an arbitrary number of states of nature and candidates. In particular, they prove that a private signaling scheme for k-voting can be computed in polynomial time, while the optimal public signaling scheme is NPhard to approximate within any factor. Castiglioni, Celli, and Gatti (2020b) strengthen this hardness result, showing that finding a public signaling scheme that is approximately optimal and ϵ-persuasive requires quasi-polynomial time, assuming the exponential time hypothesis. Our work is also closely related to Bayesian persuasion in general settings beyond elections and the relation between stability of the sender s utility function and the computation of approximations. In particular, Cheng et al. (2015) introduce the notion of stability and show that this is a sufficient property to compute approximately optimal ϵ-persuasive signaling schemes in polynomial time. Xu (2020) extends this framework to incorporate α-approximable sender s utility functions and shows that approximately optimal and ϵpersuasive signaling schemes can be computed in polynomial time when the sender s utility function is stable and independent of the state of nature.

Problem Formulation

In this section, we introduce the two frameworks we use in our work: district-based elections and Bayesian persuasion.

District-based Elections There is a set of candidates C = {c0, c1} and a set of voters R = {r1, . . . , r|R|} divided in a set D of districts. The set of voters of district d D is denoted with Rd. Each voter casts a vote for one of the two candidates. Once the voters expressed their preferences, the election process proceeds in two steps. For the sake of simplicity, we study the basic case in which both steps follow a majority-voting rule.2 The election works as follows.

1. For each d D, the votes expressed by all r Rd are locally aggregated, and the candidate with the majority of the votes is elected as the winner of the district.

2. The outcomes of all the districts are aggregated, and the candidate that is the winner in the majority of the districts is chosen as the winner of the district-based election.

1In k-voting, a candidate wins if he collects at least k votes. 2In majority voting, the candidate with the most votes wins.

We assume that the manipulator prefers c0 to be the winner of the election. Let c C be a tuple composed by the votes of all the voters, where C = C|R|. Similarly, cd is the tuple of the votes of the voters in district d. The manipulator s utility W : C {0, 1} is defined as the composition of a collection of functions W d : C|Rd| C, each representing the majority voting run in district d, and the function W : C|D| {0, 1}, representing the majority voting that aggregates the outcomes of all the districts. We define KD = |D|/2 and, for each district d, Kd = |Rd|/2 . Then, W is defined as W(c) = W(W 1(c1), . . . , W D(c|D|)), where W d(cd) assumes value c0 if at least Kd of the voters in district d vote for candidate c0, and W assumes value 1 if and only if c0 wins in at least KD districts. We introduce some relaxations for the majority-voting rules W d and W. In the first relaxation, we allow the number of votes that the target candidate c0 needs to win in each district d to be smaller than Kd. We denote with W d δ the resulting majority voting rule. Formally, W d δ : C|Rd| C assumes value c0 if at least (1 δ) Kd voters in district d vote for c0 and c1 otherwise. The manipulator s utility function of this first relaxed problem, denoted with Wδ, is defined as Wδ = W(W 1 δ (c1), . . . , W D δ (c|D|)). In the second, stronger relaxation, we also allow the number of districts that the target candidate c0 needs to control to win the election to be smaller than KD. We denote with W δ the resulting majority voting rule aggregating the outcomes of the districts. Formally, W δ : C|D| {0, 1} assumes value 1 when c0 wins in at least (1 δ) KD districts. The manipulator s utility function of this second relaxed problem, denoted with Wδδ, is defined as Wδδ(c) = W δ(W 1 δ (c1), . . . , W D δ (c D)).

Bayesian Persuasion Framework Our model includes a sender (the manipulator) and a set R of receivers (voters) that must choose an action (a candidate) from the set C = {c0, c1}. Each voter r s utility ur depends only on his own action and a state of nature θ Θ drawn from a prior distribution µ Θ, where Θ is the set of probability distributions supported on Θ. In particular, we define ur : Θ C [0, 1], where ur(θ, c) expresses how much receiver r appreciates candidate c when the state of nature is θ. We use ur(θ) = ur(θ, c0) ur(θ, c1) to denote how much voter r prefers candidate c0 over c1, in state of nature θ. In general Bayesian persuasion problems, the sender s utility, usually denoted with fθ, depends on the state of nature θ and maps the receivers action profiles to values in [0, 1]. In our setting, fθ does not depend on θ and is set equal to W, Wδ, Wδδ depending on the specific problem we tackle. The interaction among the sender and the receivers goes as follows (see Fig. 1). The sender commits to a randomized publicly known signaling scheme φ that maps states of nature to signals for the receivers. The signal set of a receiver r is denoted with Sr, while sr Sr is a signal for receiver r. The set of possible signals is then S = r RSr, while a profile of signals is denoted with s = (s1, . . . , s|R|). The sender observes the state of nature sampled from µ and computes s S according to φ. After observing the signal sr, each

time Sender

chooses φ observes θ µ

draws s according to φ and θ fθ(c)

observes φ observes sr updates beliefs votes for cr ur(θ, cr)

Figure 1: Interaction between the sender and a receiver.

receiver r performs a Bayesian update, and infers a posterior belief pr P (where P = Θ) as follows: the realized state of nature is θ with probability pr θ = µθ φ(θ,sr) P

θ Θ µθ φ(θ ,sr). Then, each receiver plays an action maximizing his expected utility according to posterior pr. We introduce three forms of signaling schemes. A private signaling scheme exploits a private communication channel toward each receiver. Sometimes this assumption is not realistic, and the sender has only a single communication channel observed by all the receivers, i.e., sr = s r for all r, r R. We call these signaling schemes public. Finally, we introduce a novel form of communication that suits our election model, where the sender has a communication channel toward each district d, and all the receivers in the same district receive the same signal, i.e., sr = s r for all r, r Rd. We call these signaling schemes semi-public. In all these settings, a revelation-principle style argument shows that there always exists a signaling scheme that is direct and persuasive. More precisely, a signaling scheme is direct if the signals are action recommendations, while it is persuasive if each receiver has the interest to follow the recommendations. Thus, a direct signaling scheme is a mapping φ : Θ C, and φ(θ, c) is the probability whereby the sender recommends c in state θ. In order for the signaling scheme to be persuasive, the receivers must have an incentive to follow the recommendation. This is customarily assured by forcing constraints on φ depending on the specific form of signaling. In particular, the incentive constraints associated with a receiver r in a district d are:

P θ,c:cr=c φ(θ, c)(ur(θ, c) ur(θ, c )) 0 c, c C (private signaling);

P θ φ(θ, c)(ur(θ, cr) ur(θ, c )) 0 c C, c C (public signaling);

P θ,c:cd= c φ(θ, c)(ur(θ, cr) ur(θ, c )) 0 c

C|Rd|, c C (semi-public signaling).

Similarly, a direct signaling scheme is ϵ-persuasive if the incentive constraints are violated by at most ϵ. Finally, we state the optimization problems we study in this paper. PRIVATE-DBE is the problem of designing a private signaling scheme maximizing the probability of having candidate c0 elected in district-based elections. PUBLICDBE and SEMIPUBLIC-DBE refer to the same problem with public and semi-public signaling, respectively.

An Example of Inefficiency of (Semi-)Public Persuasion To clarify better the Bayesian persuasion framework, we provide an example of its application to majority voting

without districts. This example is also useful to show that the restriction to (semi-)public signaling can decrease the sender s utility by an arbitrarily large factor. Example 1. Consider a (non-relaxed) majority-voting election with seven voters R = {r1, r2, r3, r4, r5, r6, r7} and two candidates C = {c0, c1}. The objective of the sender is to maximize the probability with which candidate c0 is elected. Therefore, he needs to persuade at least half of the voters (i.e., |R|/2 = 4) to make candidate c0 be the winner. There are three states of nature, namely, Θ = {θA, θB, θC}, and each state is equally probable. Tab. 1 provides the parameters ur(θ) of the voters, defined as ur(θ) = ur(θ, c0) ur(θ, c1) and capturing the net payoff of voter r from having candidate c0 elected, in state of nature θ.

State θA State θB State θC

r1,r2 +1/2 1 1 r3,r4 1 +1/2 1 r5,r6 1 1 +1/2 r7 +1/2 +1/2 +1/2

Table 1: Payoffs of the voters in Example 1.

The sender can design a direct and persuasive private signaling scheme such that at least four voters prefer candidate c0 over c1 for every signal profile s. Hence, this scheme ensures that candidate c0 is elected with a probability of 1. Specifically, in each state θ the scheme recommends candidate c0 to every voter r with utility ur(θ) 0 and to one voter among those with ur(θ) < 0 chosen randomly with uniform probability. It is easy to see that this private signaling scheme satisfies the incentive constraints. Consider, for example, voter r1. The marginal probabilities with which he is recommended to vote for candidate c0 are: φ1(θA, c0) = 1, φ1(θB, c0) = 1/4 and φ1(θC, c0) = 1/4. Therefore, when he receives the recommendation to vote for c0, he has a posterior distribution p with pθA = µθA φ1(θA,c0) P

θ Θ µθ φ1(θ,c0) = 1/3 1/3+1/3 1/4+1/3 1/4 = 2/3

and pθB = pθC = 1/6. Thus, the voter has expected utility u(θA)pθA + u(θB)pθB + u(θC)pθC = 0 and will follow the recommendation. Similarly, we can show that the incentive constraints associated with the other voters are satisfied. We switch to public signals and we show that we cannot design a public signaling scheme that guarantees candidate c0 to be elected with positive probability. Any public signaling scheme making candidate c0 win the election with positive probability must assign a strictly positive probability to at least one signal that makes at least four voters prefer candidate c0 over c1. We show that we cannot design such a public signal. In particular, we show that there is no posterior p P that provides an expected utility larger than or equal to zero to at least four voters.3 Since receiver r7 prefers candidate c0 in every state of nature, he votes for

3Recall that in a public signaling scheme, all the receivers observe the same signal, perform the same update of the belief, and have the same posterior belief.

c0 independently from the posterior induced by the signal. Therefore, it is sufficient to persuade three voters among the first six. Suppose that voters r1 and r2 vote for c0. This implies that pθA/2 pθB pθC = pθA/2 (1 pθA) 0 and pθA 2/3. Suppose, by contradiction, that also voters r3 and r4 vote for c0. This requires that pθA +pθB/2 pθC 0 and pθB 2/3, reaching a contradiction with p P. It is easy to see that, by the symmetry of the instance, all the other sets of four voters cannot vote for c0 at the same time. From the previous example, we can state the following: Proposition 1. There is an instance of majority-voting election in which the optimal private signaling scheme guarantees that candidate c0 wins the election with a probability of 1, while the optimal public signaling scheme cannot guarantee a winning probability strictly larger than 0. This inefficiency result can be easily generalized to the case of public and semi-public signaling scheme in districtbased elections. Indeed, with only a single district, semipublic signals correspond to public signals and a districtbased election reduces to a simple majority-voting election as the one presented above.

Private Persuasion in District-based Elections In this section, we show that an optimal private signaling scheme for district-based elections can be found in polynomial time. Our result is built upon the previous works by Arieli and Babichenko (2019) and Castiglioni, Celli, and Gatti (2020a) on k-voting. Let ad,θ be the probability with which Kd voters vote for c0 in district d when the state of nature is θ. Similarly, let αθ be the probability that c0 wins in at least KD districts with state of nature θ. Finally, given a direct private signaling scheme φ, we denote with φr(θ, c) = P c:cr=c φ(θ, c) the marginal probabilities of φ whereby c is recommended to r with state of nature θ. We can compute an optimal private signaling scheme by LP (1) (all the proofs are in the Supplemental Material). Theorem 1. LP (1) computes an optimal solution of PRIVATE-DBE in polynomial time.

Proof sketch. Constraints (1b) force the marginal probabilities φr(θ, c0) of the signaling scheme φ to satisfy the incentive constraints. For each state of nature θ, the maximum probability ad,θ with which at least Kd receivers in Rd vote for c0 given marginal probabilities φr(θ, c0) is:

ad,θ = min min m {0,...,Kd 1} 1 Kd mvθ,m; 1 ,

where vθ,m is the sum of the lowest |Rd| m elements in the set {φr(θ, c)}r Rd; for further details, see Arieli and Babichenko (2019). The above equation is enforced via Constraints (1f). Constraints (1g) and (1h) ensure that the values of vθ,m are consistent with the values of the other variables. The computation of the maximum probability αθ with which at least KD districts elect c0 given probabilities ad,θ is similar to the computation of ad,θ given φr(θ, c0). This is enforced by Constraints (1c), (1d), and (1e). Finally, Objective (1a) maximizes the sum over all θ Θ of the prior probability multiplied by αθ, i.e., the probability that that c0 wins when the state of nature is θ.

max α [0,1]|Θ|, a [0,1]|D| |Θ|

i,l R|Θ| KD , o R|D| |Θ| KD td,θ,m, vd,θ,m R d D,θ Θ,m {1,...,Kd} zd,θ,r,m R d D,θ Θ,r R,m {1,...,Kd} φr( ,c0) [0,1]|Θ| r R

θ Θ µθ αθ (1a)

θ Θ µθ φr(θ, co) ur(θ) 0 r R (1b)

αθ 1 KD miθ,m (1c)

θ Θ, m {0, . . . , KD 1}

iθ,m (|D| m)lθ,m + X

d D od,θ,m (1d)

θ Θ, m {0, . . . , KD 1} ad,θ lθ,m + od,θ,m (1e) d D, θ Θ, m {0, . . . , KD 1}

ad,θ 1 Kd mvd,θ,m (1f)

d D, θ Θ, m {0, . . . , Kd 1}

vd,θ,m (|Rd| m)td,θ,m + X

r Rd zd,θ,r,m (1g)

d D, θ Θ, m {0, . . . , Kd 1} φr(θ, c0) td,θ,m + zd,θ,r,m (1h)

d D, r Rd, θ Θ, m {0, . . . , Kd 1}

Public and Semi-public Persuasion in District-based Elections

We turn our attention to the design of optimal public and semi-public signaling schemes. There is a sharp distinction between the nature of these problems and that one of private signaling. Indeed, in addition to being inefficient w.r.t. private signals (see Proposition 1), optimal (semi-)public signaling schemes are also inapproximable. The hardness follows from previous results with public signaling. Specifically, Castiglioni, Celli, and Gatti (2020a) prove that it is NP-hard to approximate the optimal public signaling scheme within any factor in elections with majority voting. The extension of this hardness result to public and semi-public signaling in district-base elections is direct as a district-based election reduces to majority-voting when there is only a single district. Thus, we focus on possible relaxations that make the problem computationally tractable. Motivated by the fact that voters are somewhat biased to follow the sender s recommendations, several works relax the incentive constraints allowing the receivers to vote for the target candidate even if other candidates give them a slightly better expected utility (ϵ-persuasiveness). Recently, Castiglioni, Celli, and Gatti (2020b) prove that even allowing this relaxation the problem of designing an approximate public signaling scheme remains intractable with majority voting. Therefore, we focus on other different relaxations. In particular, Cheng et al. (2015) employ two forms of relaxation, adopting ϵ-persuasiveness and lowering the

number of votes needed to win the election by an arbitrary constant factor. With these two relaxations, they prove that an approximate public signaling scheme with majorityvoting can be computed efficiently. We prove that, adapting these two relaxations to our settings, both PUBLIC-DBE and SEMIPUBLIC-DBE admit a multi-criteria PTAS. As a preliminary step, we prove some results on the relation between the notion of stability and the design of approximately optimal signaling schemes that are of general interest in Bayesian persuasion beyond elections.

Comparative Stability and Public Signaling Schemes We refer to the notion of stability of a function introduced by Xu (2020). In particular, a function is said stable if, for every action profile, the introduction of small perturbations leads to small changes in the value of the function. Here, we extend the notion of stability to pairs of functions, and we call it comparative. Our extension is such that comparative stability corresponds to (simple) stability in the degenerate case in which the two functions of the pair are the same. Furthermore, if function g satisfies the comparative stability property w.r.t. function h, we also say that g is β-stable compared with h. Initially, we introduce the notion of perturbation by the concept of α-noisy distribution. Definition 1. Let c C be an action profile and y be a probability distribution supported on C. For any α (0, 1], we say that y is an α-noisy distribution around c if for all i {1, . . . , n} : Pr y y[ yi = ci] α. Hence, an α-noisy distribution bounds the marginal probability of any single element of {1, . . . , n} to be corrupted. However, no assumption is made on how the corruptions of the elements correlate with each other. Now, we define our notion of comparative stability. Definition 2. Given two functions g, h : C [0, 1] and a real number β 0, we say that g is β-stable compared with h if and only if the following holds for all action profiles c C, α (0, 1], and α-noisy distributions y around c: E y y [g( y)] h(c)(1 αβ).

Intuitively, if g satisfies the comparative stability property w.r.t. h, then, for every action profile, the value of h in that action profile is close to the value of g in the corresponding perturbed action profile. We exploit the notion of comparative stability to design an efficient algorithm that computes approximate public signaling schemes. More precisely, we study a generic multi-agent Bayesian persuasion problem, where the sender faces a set of receivers R, and each receiver needs to choose an action between a couple of alternatives. Let g, h be two sets of arbitrary functions depending on the state of nature θ and denoted with gθ : C [0, 1] and hθ : C [0, 1], respectively. According to Definition 2, we say that g is β-stable compared with h if gθ is β-stable with respect to hθ for all the states of nature θ Θ. For the sake of clarity, in the following, we use indirect signaling schemes, and we express a signaling scheme as a weighted set of posteriors to which the receivers respond at best. Now, we describe the optimal behavior of the receivers.

Definition 3 (Receivers behavior with persuasiveness). Given a set of functions {fθ}θ Θ such that fθ : C [0, 1], the receivers optimal behavior bp C with persuasiveness given posterior p P is as follows. Let: A = {r R : P θ pθ ur(θ) > 0} the set of receivers whose unique best response is action c0, B = {r R : P θ pθ ur(θ) < 0} the set of receivers whose unique best response is action c1, E = {r R : P θ pθ ur(θ) = 0} the set of receivers who are indifferent between action c0 and c1. Then, we have: bp = arg max c C:cr=c0 r A, cr=c1 r B

θ pθ fθ(c).

Similarly, we define the notion of ϵ-best response. Definition 4 (Receivers behavior with ϵ-persuasiveness). Given a set of functions {fθ}θ Θ such that fθ : C [0, 1], the receivers optimal behavior bp,ϵ C with ϵpersuasiveness given posterior p P is as follows. Let: Aϵ = {r R : P θ pθ ur(θ) > ϵ} the set of receivers whose unique best response is action c0, Bϵ = {r R : P θ pθ ur(θ) < ϵ} the set of receivers whose unique best response is action c1, Eϵ = {r R : P θ pθ ur(θ) [ ϵ, ϵ]} the set of receivers who are indifferent between action c0 and c1. Then, we have: bp,ϵ = arg max c C:cr=c0 r Aϵ cr=c1 r Bϵ

θ pθ fθ(c).

Now, we show that computing a direct public signaling scheme is equivalent to derive a Bayes plausible distribution of posteriors γ P that maximizes the sender s utility. Let supp(γ) denote the set of posteriors induced with strictly positive probability. Similarly, let supp(φ) denote the set of posteriors induced by φ with strictly positive probability. Finding a public signaling scheme is equivalent to finding a probability distribution γ P on the set of posteriors P such that P p supp(γ) γp pθ = µθ for every θ Θ. Given a well-defined distribution over posteriors γ, we can recover a direct signaling schemes φ that induces such a probability distribution by setting φθ(c) = P p supp(γ):c=bp γp pθ. For this reason, in the following, we represent signaling schemes as probability distributions on the posteriors. We introduce some further notation. For every p P and set of functions f = {fθ}θ Θ, we define the sender s expected utility with persuasiveness as f(p) = P θ pθ fθ(bp), and with ϵpersuasiveness as fϵ(p) = P θ pθ fθ(bp,ϵ). Finally, we define q-uniform probability distributions as follows. Definition 5. A probability distribution x X is quniform if and only if it is the average of a multiset of q basis vectors in |X|-dimensional space. Therefore, we say that a probability distribution p P is q-uniform if each of its entry pθ is a multiple of 1/q. Moreover, we use the notation Q Θ to denote the set of all q-uniform distributions over Θ. Our first result shows that we can decompose each posterior in a convex combination γ Q of q-uniform posteriors (with q constant), such that

P p Q γp gϵ(p) closely approximates h(p ). This is a generalization of the result by Xu (2020) to state-dependent utility functions (and couples of functions), and it is crucial to prove the following results. Lemma 1. Let β, ϵ > 0, η (0, 1] and set q = 32 log 4 η min{1; 1/β} /ϵ2. Then, given a posterior p P and two sets of functions g, h with g β-stable compared with h, there exists a γ Q with P p Q γp p = p and X

θ pθ gθ(bp,ϵ) (1 η) X

θ p θ hθ(bp ). (2)

Now, we can prove the main result of this section. Consider a couple of sets of functions g, h where g is β-stable compared with h. With abuse of notation, we define g(φ) and h(φ) as the functions which evaluate the expected sender s utility of a public signaling scheme φ with h and g, respectively. We can resort to Lemma 1 to state the following result. The proof is based on solving a linear program that works only with q-uniform posteriors. Theorem 2. Let β, ϵ > 0 and η (0, 1]. Consider two arbitrary state-dependent sets of functions g, h such that gθ : C [0, 1] is β-stable compared with hθ : C [0, 1] for all θ Θ. Then there exists a poly |R| |Θ|log( 1 η min{1;1/β} )/ϵ2

time algorithm that returns an ϵ-persuasive public signaling scheme φϵ such that: g(φϵ) (1 η) max φ Φ h(φ),

where Φ is the set of persuasive signaling schemes. By setting h = g, we obtain a generalization of the result by Xu (2020) to state-dependent functions.

Comparative Stability of Voting Functions We apply this novel concept of stability to voting problems. Our first result proves that the two relaxed majority-voting functions previously introduced satisfy the comparative stability property. This result is similar to that by Cheng et al. (2015). However, we use multiplicative factors (in place of additive factors) and prove a slightly stronger result than stability. In particular, we prove that the decrease in utility is small even if only the perturbations from action c0 to c1 are bounded. Lemma 2. Wδ is 1/δ-stable compared with W. Moreover, for all c C, r R, α (0, 1], and y C such that Pry ( yr = c1 cr = c0 ) α, it holds:

E y y [Wδ( y)] W(c) 1 α

We can use the result above to prove that Wδδ satisfies the property of comparative stability with respect to W. Intuitively, the result follows from the observation that W is the composition of two majority-voting steps. Lemma 3. Wδδ is 1 δ2 -stable with respect to W. Finally, we derive a stronger decomposition lemma for majority-voting. Specifically, Lemma 1 shows that the decrease in the expected sender s utility when decomposing a posterior in q-uniform posteriors can be bounded. However, in generic settings, the sender s expected utility in a given state of nature can change arbitrarily. This is not the case in

majority voting, where, instead, this decrease is bounded. In particular, we can show the following, that is crucial when addressing the SEMIPUBLIC-DBE problem. Lemma 4. Let ϵ > 0, η (0, 1] and set q = 32 log 4 ηδ /ϵ2. Then, given a posterior p P, there exists a γ Q with P p Q γp p = p and X

p Q γp pθ Wδ(bp,ϵ) (1 η) p θ W(bp ) θ Θ.

Computing Public and Semi-public Signaling Schemes in District-based Elections We present two multi-criteria PTASs for the SEMIPUBLIC-DBE and PUBLIC-DBE problems, respectively, when our relaxations are adopted. First, we focus on the problem of designing public signaling schemes. We assume ϵ-persuasive signaling schemes, and we replace function W with Wδδ (this corresponds to relaxing both the majority voting within every single district and the majority voting aggregating the outcomes of all the districts). Let W(φ) and Wδδ(φ) denote the functions returning the sender s expected utility provided by a public signaling scheme φ with voting rules W and Wδδ, respectively. We show that it is possible to compute efficiently an ϵpersuasive public signaling scheme φϵ that approximates the optimal persuasive signaling scheme with an approximation factor arbitrarily close to 1. Since the relaxed function Wδδ is 1/δ2-stable compared to the non-relaxed function W by Theorem 3, we can immediately apply Theorem 2 to these functions and then derive the following. Corollary 1. Let ϵ > 0, δ (0, 1) and η (0, 1], then there

exists a poly |R| |Θ| log 1 η δ2 /ϵ2 time algorithm that re-

turns an ϵ-persuasive public signaling scheme φϵ such that: Wδδ(φϵ) (1 η) max φ Φ W(φ), (3)

where Φ is the set of persuasive signaling schemes. Then, we focus on the SEMIPUBLIC-DBE problem. As highlighted above, to overcome the intractability result, also in this setting, it is necessary to relax the problem. Specifically, we use ϵ-persuasive signaling schemes and we replace function W with Wδ (this corresponds to relaxing the majority voting aggregating the outcomes of all the districts). We show that it is possible to compute efficiently an ϵ-persuasive semi-public signaling scheme φϵ that approximates the optimal persuasive signaling scheme with an approximation factor arbitrarily close to 1. Computing a semi-public signaling scheme φ amounts to determining a collection {φd}d D of |D| public signaling schemes, one for each district, and correlate them. The crucial point concerns the computation of good marginal probabilities of the signaling scheme. Indeed, their aggregation is equivalent to computing a private signaling scheme in majority-voting elections, and this can be done efficiently (see LP (1) and Theorem 1). The main idea of our proof is that there are approximately optimal marginal probabilities of the signaling scheme that use only q-uniform posteriors (with q constant). Let αθ be the probability that c0 wins in at least KD districts with state of nature θ, aδ d,θ be the probability that candidate c0 receives at least (1 δ) Kd

votes in district d with state of nature θ, and γd be a probability distribution over posteriors for the receivers in district d. Finally, let I[E] denote the indicator function for the event E. Then, the following formulation computes an approximately optimal signaling scheme in polynomial time.

max α [0,1]|Θ|, aδ [0,1]|D| |Θ|

i,l R|Θ| KD , o R|D| |Θ| KD γd Q d D

θ Θ µθαθ (4a)

s.t. αθ 1 KD miθ,m (4b)

θ Θ, m {0, . . . , KD 1}

iθ,m (|D| m)lθ,m + X

d D od,θ,m (4c)

θ Θ, m {0, . . . , KD 1}

aδ d,θ lθ,m + od,θ,m (4d)

d D, θ Θ, m {0, . . . , KD 1}

µθ I W d δ (bp,ϵ) = c0 (4e)

p Q γd p pθ = µθ d D, θ Θ (4f)

Theorem 3. Let ϵ > 0, δ (0, 1) and η (0, 1], then there exists a poly |R| |Θ|log( 1

η δ)/ϵ2 time algorithm that outputs an ϵ-persuasive semi-public signaling scheme φϵ such that: Wδ(φϵ) (1 η) max φ Φ W(φ), (5)

where Φ is the set of persuasive signaling schemes.

Conclusions and Future Works

In this paper, we study how a manipulator can exploit his information advantage to manipulate a district-based election through the strategic provision of information to rational voters. We show that private signaling schemes can be computed efficiently while computing optimal (semi-)public signaling schemes is intractable. However, we show that reasonable relaxations allow the design of multi-criteria PTASs for (semi-)public persuasion. An interpretation of these relaxations is that (semi-)public signaling is often tractable, except when the target candidate wins in at least half of the districts, but it is impossible to make slightly more than half of them elect such a candidate. In most cases, the receivers are slightly biased to follow the sender recommendations, and the manipulator s preferred candidate can either win or not win by at least a small, but not negligible, margin. With these assumptions, our algorithm approximates arbitrarily well the optimal signaling scheme in polynomial time. In the future, we will study classes of instances in which optimal (semi-)public signaling schemes can be computed efficiently. We are also interested in settings in which the sender is uncertain about the voters preferences.

Acknowledgments This work has been partially supported by the Italian MIUR PRIN 2017 Project ALGADIMAR Algorithms, Games, and Digital Market .

References Allcott, H.; and Gentzkow, M. 2017. Social media and fake news in the 2016 election. Journal of economic perspectives 31(2): 211 236.

Alonso, R.; and Cˆamara, O. 2016. Persuading voters. American Economic Review 106(11): 3590 3605.

Arieli, I.; and Babichenko, Y. 2019. Private bayesian persuasion. J ECON THEORY 182: 185 217.

Bardhi, A.; and Guo, Y. 2018. Modes of persuasion toward unanimous consent. Theoretical Economics 13(3): 1111 1149.

Bergemann, D.; and Morris, S. 2016a. Bayes correlated equilibrium and the comparison of information structures in games. THEOR ECON 11(2): 487 522.

Bergemann, D.; and Morris, S. 2016b. Information design, Bayesian persuasion, and Bayes correlated equilibrium. AM ECON REV 106(5): 586 591.

Castiglioni, M.; Celli, A.; and Gatti, N. 2020a. Persuading Voters: It s Easy to Whisper, It s Hard to Speak Loud. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, 1870 1877. AAAI Press. URL https://aaai.org/ ojs/index.php/AAAI/article/view/5555.

Castiglioni, M.; Celli, A.; and Gatti, N. 2020b. Public Bayesian Persuasion: Being Almost Optimal and Almost Persuasive. Ar Xiv abs/2002.05156.

Castiglioni, M.; Ferraioli, D.; and Gatti, N. 2020. Election Control in Social Networks via Edge Addition or Removal. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, 1878 1885. AAAI Press. URL https: //aaai.org/ojs/index.php/AAAI/article/view/5556.

Chan, J.; Gupta, S.; Li, F.; and Wang, Y. 2019. Pivotal persuasion. Journal of Economic Theory 180: 178 202.

Chen, J.; Faliszewski, P.; Niedermeier, R.; and Talmon, N. 2017. Elections with few voters: candidate control can be easy. J ARTIF INTELL RES 60: 937 1002.

Cheng, Y.; Cheung, H. Y.; Dughmi, S.; Emamjomeh-Zadeh, E.; Han, L.; and Teng, S. 2015. Mixture Selection, Mechanism Design, and Signaling. In FOCS, 1426 1445.

Erd elyi, G.; Reger, C.; and Yang, Y. 2020. The complexity of bribery and control in group identification. Autonomous Agents and Multi-Agent Systems 34(1): 8.

Faliszewski, P.; Gonen, R.; Kouteck y, M.; and Talmon, N. 2018. Opinion Diffusion and Campaigning on Society Graphs. In IJCAI, 219 225. Faliszewski, P.; Hemaspaandra, E.; and Hemaspaandra, L. A. 2011. Multimode control attacks on elections. Journal of Artificial Intelligence Research 40: 305 351. Faliszewski, P.; Hemaspaandra, E.; Hemaspaandra, L. A.; and Rothe, J. 2009. Llull and Copeland voting computationally resist bribery and constructive control. Journal of Artificial Intelligence Research 35: 275 341. Guess, A.; Nyhan, B.; and Reifler, J. 2018. Selective exposure to misinformation: Evidence from the consumption of fake news during the 2016 US presidential campaign. European Research Council 9. Kamenica, E.; and Gentzkow, M. 2011. Bayesian persuasion. AM ECON REV 101(6): 2590 2615. Liu, H.; Feng, H.; Zhu, D.; and Luan, J. 2009. Parameterized computational complexity of control problems in voting systems. THEOR COMPUT SCI 410(27-29): 2746 2753. Loreggia, A.; Narodytska, N.; Rossi, F.; Venable, K. B.; and Walsh, T. 2015. Controlling elections by replacing candidates or votes. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, 1737 1738. Sina, S.; Hazon, N.; Hassidim, A.; and Kraus, S. 2015. Adapting the social network to affect elections. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, 705 713. Taneva, I. 2019. Information Design. American Economic Journal: Microeconomics 11(4): 151 85. doi:10.1257/mic. 20170351. URL https://www.aeaweb.org/articles?id=10. 1257/mic.20170351. Wang, Y. 2013. Bayesian persuasion with multiple receivers. Available at SSRN 2625399 . Wilder, B.; and Vorobeychik, Y. 2018. Controlling elections through social influence. In Proceedings of the 17th international conference on autonomous agents and multiagent systems, 265 273. International Foundation for Autonomous Agents and Multiagent Systems. Wilder, B.; and Vorobeychik, Y. 2019. Defending elections against malicious spread of misinformation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, 2213 2220. Xu, H. 2020. On the Tractability of Public Persuasion with No Externalities. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2708 2727. SIAM.