# pollconfident_voters_in_iterative_voting__15081f42.pdf

The Thirty-Third AAAI Conference on Artiﬁcial Intelligence (AAAI-19)

Poll-Conﬁdent Voters in Iterative Voting

Ana elle Wilczynski Universit e Paris-Dauphine, PSL, CNRS, LAMSADE, Paris, France anaelle.wilczynski@lamsade.dauphine.fr

This article deals with strategic voting under incomplete information. We propose a descriptive model, inspired by political elections, where the information about the vote intentions of the electorate comes from public opinion polls and a social network, modeled as a graph over the voters. The voters are assumed to be conﬁdent in the poll and they update the communicated results with the information they get from their relatives in the social network. We consider an iterative voting model based on this behavior and study the associated poll-conﬁdent dynamics. In this context, we ask the question of manipulation by the polling institute.

Introduction Strategic voting occurs in many scenarios, principally in political elections. Voters may manipulate, by not revealing their true preferences in the ballot they submit, in order to avoid an unfortunate outcome. Although one would desire to prevent this behavior, no voting rule is immune to voter manipulation (Gibbard 1973; Satterthwaite 1975), leading to consider other ways to grasp strategic voting, via for instance game-theoretical analysis. Manipulation in voting is commonly modeled as a strategic game where the players are voters, assumed to be rational, who look for the appropriate ballot to obtain the best possible outcome in the election, according to their preferences. Iterative voting (Meir 2017) is an iterated version of this game where the voters deviate by rounds. The deviations can be interpreted as the responses to a succession of polls, or as the description of changes in voting intentions considering tactical voting strategies. The players are traditionally assumed to know all the others vote. However, this assumption appears highly unrealistic, especially for political elections where the set of voters is actually very large. From this observation, an important literature begins to develop in order to face with uncertainty in voting. Several approaches can be enumerated: the Bayesian approach assuming that the voters think in terms of probabilities over the possible voting proﬁles (Myerson and Weber 1993; Hazon et al. 2008), the knowledge-based approach via modal logic frameworks (Chopra, Pacuit, and Parikh 2004; Van Ditmarsch, Lang, and Safﬁdine 2012), the localdominance approach with uncertainty thresholds (Meir, Lev,

Copyright c 2019, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

and Rosenschein 2014; Meir 2015), the information function approach which assumes that only a given type of information is communicated to the voters (Endriss et al. 2016; Reijngoud and Endriss 2012), or the partial orders approach where the voters consider a set of possible proﬁles according to partial votes (Conitzer, Walsh, and Xia 2011; Dey, Misra, and Narahari 2016). The most part of these works considers a risk-averse behavior, in the sense that the voters manipulate if they are sure that their deviation does not produce a worse outcome. Even if it appears as a rational behavior, it does not really capture the behavior of real voters who might actually manipulate even if they are not guaranteed to obtain at least a better outcome in any case. We argue that the voters adopt an elementary behavior regarding the information they dispose of. Inspired by political elections, we assume that the voters have two sources of information: the public opinion polls and the social networks. Opinion polls punctuate the election campaign in many countries, and represent an important part of the election process. Many studies aim at understanding how they affect voting (Brams 1982; Forsythe et al. 1993; Fred en 2017). Concerning social networks (Easley and Kleinberg 2010; Jackson 2008), they occupy an increasingly important place in our lives. For a particular citizen, they constitute a tool to have an idea of the population opinions, even if this vision can be biased. The social networks are a natural channel for acquiring information in context of uncertainty in voting (Chopra, Pacuit, and Parikh 2004; Clough 2007; Sina et al. 2015; Tsang and Larson 2016). In a context where the polls offer a large part of the information available to the voters, a natural question is: what happens if the polling institute does not say the truth about the scores of the candidates? In fact, can the polling institute manipulate the election? This question is related to the problem of election control (Faliszewski and Rothe 2016), i.e., how an external agent can inﬂuence and manipulate the election. While usually this agent manipulates by adding / deleting candidates or votes, or even links of a social network (Sina et al. 2015), we suppose that the polling institute may lie during the communication of the results. We investigate an iterative voting model where the voters trust the results of an opinion poll and have all the same prior assumption about the distribution of the votes, which is given by the poll. The voters update this belief about the

vote intentions of the society by observing the strategic deviations of their relatives in the social network. The strategic behavior of voters is then conditioned by personal pivotal thresholds modeling their willingness to deviate and how strong is their belief, in a same way as non-myopic voters (Obraztsova et al. 2016), or as in local-dominance (Meir, Lev, and Rosenschein 2014). All these parameters enable to deﬁne a new best-response dynamics, called poll-conﬁdent. Two conﬁgurations are investigated: a local dynamics with one initial poll, and a global dynamics where the results of several polls are announced along the election. Convergence results are provided, stating that local dynamics are guaranteed to converge for some classes of graphs representing the social network. However, in general, it is computationally hard to recognize convergent instances for both dynamics. Experiments are given for testing the practical convergence of the dynamics and the quality of their outcomes. Then, we study the computational complexity of manipulation from the polling institute, proving that it is hard even for simple graphs. Beyond the general hardness of the problem, we provide simple heuristics that are efﬁcient in practice. We present in the ﬁrst section our model and the pollconﬁdent dynamics in their local and global version. Then we analyze their convergence, before ﬁnally investigating the manipulation from the polling institute.

Poll-Conﬁdent Iterative Voting Model Notations

Let N = {1, . . . , n} be a set of n agents (or voters), and M = {x1, . . . , xm} a set of m candidates. Each voter i has a strict preference order i over M. The whole preference proﬁle is denoted by = ( 1, . . . , n). A voting rule computes the winner of the election. We consider single-winner elections and use, in case of ties, a deterministic tie-breaking rule, based on a linear order over the candidates. We focus on the Plurality rule, and we denote Plurality associated with by f. Plurality corresponds to a mapping f : M n M, where each voter is asked to submit a ballot bi M, meant to represent her preferred candidate. Given a proﬁle of ballots b M n, the score of each candidate x under Plurality is given by sb(x) = |{i N : bi = x}|. The winner of Plurality in voting proﬁle b maximizes score sb, i.e., f(b) arg maxx M sb(x). By simplicity, we sometimes write f(s) to designate the Plurality winner of a voting proﬁle having s as a vector of scores. We consider a strategic game where at each step, a single voter can change her vote if she thinks that she will be better off with this new strategy. The strategy proﬁle at step t is denoted by bt. If different voters can deviate at the same step t, the deviator is arbitrarily chosen among them, unless we specify a particular turn function τ as part of the instance. An opinion poll is undertaken from the initial voting proﬁle b0, where the voters are assumed to give their real preferences (the agents do not have enough information to manipulate yet), i.e., b0 is truthful. The result 0 of this initial poll is communicated to the agents, via a vector of scores describing the Plurality score of each candidate. Though the agents are aware of the initial poll, they do

not know all the deviations of the agents. We suppose that the agents are embedded into a social network G = (N, E), which is a directed graph over the agents. We denote by G[N ] the subgraph induced by N N. We always care about the direction in the graph: a complete graph contains all the arcs, a clique refers to a complete subgraph, and a cycle to a closed directed path. The graph is transitive if the binary relation over N represented by E is transitive. An arc (i, j) E means that agent i can observe the ballot of agent j at any time. We denote by Γ(i) the set of agents that agent i can observe, i.e., Γ(i) = {j N : (i, j) E} {i}. For a voting proﬁle b, the score of candidate x that agent i is able to observe is denoted by si b(x) = |{j Γ(i) : bj = x}|. An instance of the game is a tuple I = (N, M, , b0, G, {pi}i N), where {pi}i N are integer thresholds deﬁning the strategic type of the voters.

Poll-conﬁdent dynamics The voters have two sources of information about the current scores: the results of the initial poll and the current votes of their relatives, i.e., their direct successors in the network. The question is how they aggregate these informations. We assume that the voters base their belief on the results of the poll, updated with the votes of their relatives. The strength of this belief is conditioned by personal pivotal thresholds. In fact, each voter has her own belief about the score of the candidates. We denote by Bt i : M N the believed score function of agent i at the tth step of the game. Initially, B0 i = 0 for all voters i since the voters trust the poll. We may see Bt i and 0 as m-tuples where the jth coordinate represents the believed and the announced score of candidate xj, respectively. At a step t of the game, the believed score function of the agents is updated only if a relative deviates.

Deﬁnition 1 (Score Belief Update). The update of the believed score function of agent i at step t + 1, after the deviation of an agent j from candidate x to candidate y at step t is given by Bt+1 i := Bt i (j, x, y), where

[Bt i (j, x, y)](z) =

Bt i(z) 1 if z = x and j Γ(i) Bt i(z) + 1 if z = y and j Γ(i) Bt i(z) otherwise

Note that for any voter i and any step t, Bt i = 0 if Γ(i) = {i} and i did not deviate, and Bt i = sbt if Γ(i) = N. We deﬁne a best response for agent i at step t, w.r.t. her belief and her strategic behavior. A pivotal threshold pi is associated with each voter i; we denote it by p when pi is the same for all the voters. The pivotal threshold of a voter represents her willingness to deviate to a new strategy on the basis of her belief about the scores. This can measure how much the voters are uncertain about their belief or represent the threshold from which they think that their vote is pivotal and matters in the election, notably by inﬂuencing the other votes. It also enables to model sincere voters, averse to manipulation. This threshold deﬁnes for each voter i a set of potential winners at step t, denoted by PW t i , representing the candidates that are still able to win the election, according to voter i. The believed winner of agent i at step t w.r.t. Bt i is denoted by ωt i. We denote by Bt,\i i the believed score

function of voter i at step t where the current vote of agent i is not taken into account, and by ωt,\i i its associated winner. Deﬁnition 2 (Potential winner). A candidate x belongs to PW t i for voter i at step t if, without considering the current vote of i, at most pi votes are necessary to x for winning the election, i.e., Bt,\i i (ωt,\i i ) Bt,\i i (x) + 1{ωt,\i i x} pi.

A best response at step t for voter i is deﬁned as the candidate that i prefers among the potential winners PW t i \{ωt i}. Deﬁnition 3 (Best response). A ballot approving candidate y is a best response for voter i at step t if y PW t i \ {ωt i} and for all x PW t i such that x = y, y i x. A strategy proﬁle is a 0-equilibrium iff for every agent there is no best response or the best response corresponds to her current vote. Observe that the classical iterative voting setting, where the current votes are common knowledge and the voters consider that they are pivotal if they are able to change the outcome, corresponds in our model to an instance where the social network is a complete graph and p = 1. In such a context, our formulated best response is a direct best response (Meir et al. 2010), and a 0-equilibrium is a Nash equilibrium, i.e., a stable state regarding unilateral deviations with complete information about the current votes (Aumann and Brandenburger 2014). When the social network is a complete graph, our best response corresponds to an NM-Plurality response (Obraztsova et al. 2016) and to a local-dominant strategy (Meir, Lev, and Rosenschein 2014) if b0 is truthful, where the distance metric between voting proﬁles is an ℓ1-norm. A sequence of best response deviations is illustrated in the following example. Example 1. Consider an instance where n = m = 4, with x1 x2 x3 x4, p1 = 2 and p2 = p3 = p4 = 1. The social network G and the preferences are as follows.

1 : x1 x3 x2 x4 2 : x2 x4 x3 x1 3 : x3 x4 x1 x2 4 : x4 x2 x3 x1 Consider the following sequence of best responses. Each state bt is represented by sbt and f(bt). At each step t, an arrow designates the deviation performed by voter i mentioned below the arrow, believing the score function Bt,\i i mentioned above the arrow. The deviations are in bold. (1, 1, 1, 1):x1 (1,0,1,1) 2 (1, 0, 1, 2):x4 (1,1,0,1) 3 (1, 0, 0, 3):x4

(1,1,1,0) 4 (1, 1, 0, 2):x4 (1,2,0,0) 3 (2, 1, 0, 1):x1 From b0, agent 2 changes her vote to candidate x4 because she prefers x4 to the winner x1. Agent 1 observes this move but has a pivotal threshold of 2: she still believes that x1 can win so her best response is her current vote. Agent 3 did not observe any move, and thus believes in the initial scores, leading to her deviation to x4. This belief also holds for agent 4 who deviates to x2. Agent 3 observes this move while believing that agent 2 has not deviated and so she moves to x1. Now, no agent can deviate given the information she gets, so proﬁle b4 := (x1, x4, x1, x2) is an equilibrium. The information contained in the poll, updated by the observations given by the network, as well as the pivotal

thresholds characterizing the best responses, enable to deﬁne a dynamics of the strategic game, that we call pollconﬁdent dynamics. We say that the poll-conﬁdent dynamics converges if any sequence of deviations leads to a 0equilibrium, and we say that the dynamics can cycle if there exists a sequence of deviations where we come back to a previous strategy proﬁle. Such a poll-conﬁdent dynamics, deﬁned according to one initial poll, is said to be local.

Global poll-conﬁdent dynamics We deﬁne, analogously to the local poll-conﬁdent dynamics, a global poll-conﬁdent dynamics where several polls are communicated to the voters. In fact, each time the (local) poll-conﬁdent dynamics converges, the scores at the equilibrium are communicated via a poll. A sequence of deviations within global dynamics is a sequence of states (b0, b0,1, . . . , b0,t0, b1,1, . . . , b1,t1, . . . , bt,1, . . . , bt,tt), where bi,j is the strategy proﬁle at ith global step and jth local step. For each 0 k t 1, there is a poll k+1 between state bk,tk and state bk+1,1 which announces the scores of bk,tk. Initial poll 0 is given between initial state b0 and state b0,1. For all 0 k t, sequence (bk,1, . . . , bk,tk) represents the deviations of the local dynamics with initial poll k, which leads to the k-equilibrium bk,tk. We assume that the voters do not keep in memory the history of the previous global steps. At each global step, the voters behave in the same way as in the initial one. The global poll-conﬁdent dynamics can cycle if there exists a sequence of deviations (b0, b0,1, . . . , b0,t0, . . . , bt,1, . . . , bt,tt) such that there are k < k where bk ,tk = bk,tk or bk ,tk = b0, or if the associated local pollconﬁdent dynamics cycles. A stable state regarding the global dynamics is called a global equilibrium. Observation 1. For a unanimous pivotal threshold p = 1, a state b is a global equilibrium iff b is a Nash equilibrium. A global equilibrium b is either b0 or a t-equilibrium for some step t. In any case, its scores are announced either by 0 or by t+1, leading to complete information about b.

Convergence to Poll Equilibria In this section, we study the convergence of the pollconﬁdent dynamics and the quality of the equilibria. Despite some positive results, in the general case, it is difﬁcult to recognize the instances for which the dynamics converges.

Convergence properties The deviation of each agent depends on the information she has about the game. If she sees nobody deviating after her deviation, then a voter has no reason to deviate again. Observation 2. Any agent i such that Γ(i) = {i} deviates at most once for any voting rule and any threshold pi. Obs. 2 implies that the local dynamics converges for any voting rule if E is empty. A condition on the graph can be further derived to ensure the convergence of the dynamics. Proposition 1. If G is a directed acyclic graph (DAG), then the local dynamics converges from any initial state within O(n2) steps, for any voting rule and any thresholds pi.

Proof. Suppose the dynamics cycles within the subset of agents N N. Obs. 2 implies that the outdegree of each agent i in N in G is not equal to zero. Yet, a DAG contains at least one sink, i.e., a vertex of null outdegree, and a subgraph of a DAG is still a DAG. Contradiction. A deviation of a sink can push at most n 1 other agents to deviate. By iteratively removing a sink of G and counting the deviations caused by a sink in the new graph, we get that the sequence of deviations is of size O(n2).

If the network does not contain cycles, then convergence is ensured. Actually, this is especially the presence of cycles in the graph that enables the dynamics to cycle. However, we can prevent cycles in the dynamics to occur if the cycles of the graph are in fact cliques, i.e., the network is transitive, and the dynamics converges in a complete graph.

Proposition 2. If the local dynamics eventually converges from any initial state after g(n, m) steps for a complete graph, then the dynamics converges from any initial state within O(n g(n, m)) steps when the network is transitive.

Proof. Let N be a minimal subset of agents for who the dynamics cycles. All the agents i in a clique C of G have the same believed scores Bt i at any step t: by transitivity, Γ(i) = Γ(j) for all i, j C. So, since the dynamics is guaranteed to converge when all the current votes are known, G[N ] is not a clique. By Prop. 1, there must be a cycle in G[N ]. But a cycle along agents N N in a transitive graph implies that G[N ] is a clique. So, G[N ] includes a set of cliques. Since there is no visibility of the deviations between two disjoint connected components, G[N ] is connected. The agents in N can be partitioned into the groups N 1, . . . , N k w.r.t. their level of knowledge: each G[N i] for i [k] is a set of disjoint cliques and any agent in N i can only observe some agents in N j for j i. Each agent in a group N i deviates according to the deviations of agents in S

j i N j, because she cannot observe other deviations. So, a cycle in the dynamics within N implies a cycle in the dynamics within S

j i N j. By minimality of N , N is a single clique, contradiction. It is possible to see a transitive graph as a DAG whose nodes are cliques. So, any sequence of deviations is of length O(n g(n, m)).

When the thresholds are heterogeneous, the dynamics may cycle even for a complete graph (Obraztsova et al.[2016] s Thm. 3). However, from Meir et al.[2010] s Thm. 3, the local dynamics converges from any initial state within O(nm) steps when p = 1 and the graph is complete.

Corollary 1. The local dynamics is guaranteed to converge from any initial state within O(n2m) steps when p = 1 and the graph is transitive.

Moreover, this can be generalized to unanimous pivotal thresholds under some condition on the turn function τ, in the spirit of (Meir, Lev, and Rosenschein 2014) s Prop. 6. A deviation of agent i from x to y is called a (1)-compromise move if x i y and a (2)-opportunity move if y i x.

Proposition 3. If the turn function τ always selects (2)- moves before (1)-moves, then the local dynamics converges

within O(nm) steps from any initial state when p is unanimous and the graph is complete.

Proof. A (2)-move implies that the rank, in the deviator s preferences, of the candidate approved in the new ballot is strictly better than the previous approved candidate. So, there are at most n(m 1) consecutive (2)-moves. By deﬁnition of τ, there exists a state t0 where no agent has incentive to perform a (2)-move. One can prove by a complete induction that, for any step t t0, where an agent i deviates from x to y, the following holds: (I) the score of the winner does not decrease, (II) S j N PW t+1 j S j N PW t j , (III) x i y, and (IV ) after this move, no agent can deviate to x. The details are omitted due to space limitations.

Corollary 2. If τ selects (2)-moves before (1)-moves, then the local dynamics converges within O(n2m) steps from any initial state when p is unanimous and the graph is transitive.

However, for a general graph, knowing whether the local dynamics can cycle is difﬁcult, even when p = 1.

Theorem 1. Knowing whether the local dynamics can cycle is NP-hard, even for unanimous pivotal threshold p = 1.

Proof. We perform a reduction from the NP-complete problem 2P1N-SAT (Yoshinaka 2005) deﬁned as follows: given a set C = {C1, . . . , Cr} of r clauses over a set X = {x1, . . . , xv} of v variables, where each variable occurs twice as a positive literal and once as a negative literal, is C satisﬁable? The clauses can be indexed such that each ﬁrst occurrence of a variable is a positive literal, because the original proof of NP-hardness relies on such an instance. We assume such a restriction. Each clause Ci contains ri literals. We construct an instance I = (N, M, , b0, G, p = 1). The set M of candidates includes candidates a, d, y, z and clause-candidates ci for each i [r]. The tie-breaking is deﬁned as: d y z cr cr 1 c1 a. The set N of agents includes agents A, D, Y and Z, and literalagents Li j for each jth literal of clause Ci. The preferences are as follows (all candidates not listed are ranked in arbitrary order within [. . . ]): Li j : y ci cr ci 1 [. . . ] A : a y d [. . . ] Y : y z d [. . . ] D : a d y [. . . ] Z : z y cr [. . . ] We add 3v(r + 2) + r dummy voters, where 3v + 1 among them rank ci ﬁrst for each candidate ci, 3v rank d ﬁrst and 3v rank z ﬁrst. Every candidate, except a and d, obtains 3v + 1 votes, and d has 3v votes. The initial winner is y, thanks to . In the network G, all the agents of a same clause form a clique. There is an arc from each agent of clause Ci to each agent of clause Ci 1. There is an arc from each agent of clause C1 to agents D and Z, and from agents Z and Y to the agents of clause Cr. Agent Z points to A and Y , and A points to D. There is an arc from agent Li j to agent Lℓ k if i < ℓand the agents correspond to opposite literals. The graph construction is illustrated in Fig. 1. We claim that C is satisﬁable iff the local dynamics can cycle in I. One can prove that the only possible cycle within the dynamics involves the agents Y , Z and exactly one agent

Figure 1: Construction of G for a 2P1N-SAT instance where C1 = (x1 x2 x3), C2 = (x1 x2 x4), C3 = (x2 x3 x4) and C4 = (x1 x3 x4). The literals (we keep for the ﬁgure the literal name) in a same circle are in a same clause; the arcs from or to the circles concern every agent inside.

related to each clause. Moreover, if there are two agents corresponding to opposite literals among the deviating agents related to the clauses, then the cycle does not occur. The proof of the equivalence is omitted by lack of space.

Concerning the global poll-conﬁdent dynamics, they are not guaranteed to converge, even when the associated local dynamics always converges and for pivotal threshold p = 1.

Proposition 4. The global dynamics may cycle even when G is empty and for unanimous pivotal threshold p = 1.

Proof. Consider an instance where n = 4 and m = 3, with x1 x2 x3, p = 1, an empty graph and the preferences: 1: x2 x1 x3, 2: x3 x1 x2, 3: x1 x2 x3 and 4: x3 x1 x2. Here is a cycle within 2 global steps (the polls are given in bold at the beginning of the lines):

[1,1,2] (1, 1, 2):x3 (1,0,2) 1 (2, 0, 2):x1 (0,1,2) 3 (1, 1, 2):x3

[1,1,2] (1, 1, 2):x3 (0,1,2) 1 (0, 2, 2):x2 (1,0,2) 3 (1, 1, 2):x3 In this case, the cycle mimics simultaneous moves.

For a general graph, we can prove that it is NP-hard to know whether the global dynamics can cycle, even for unanimous pivotal threshold p = 1, through another reduction from 2P1N-SAT. We omit this proposition by lack of space.

Experiments on the quality of poll equilibria To conclude this section, we present some experiments over 10,000 generated instances with 100 voters and 10 candidates, under impartial culture for the preferences and random Erd os and R enyi[1959] s graphs (see Fig. 2). We observe the frequency of convergence of the dynamics and the frequency of electing a Condorcet winner (for Condorcet domains) within the equilibria. We stop the iterative process only when an equilibrium is reached or a cycle is hit. The results are given w.r.t. the density of the graphs and the pivotal thresholds. We examine unanimous thresholds of value 1, 5 and 10 and heterogeneous ones uniformly distributed over the voters with values in [1..5] or [1..10]. The dynamics, both in their local and global version, mostly converge, especially for sparse or dense graphs. When p = 1 or p = 10, they almost always converge, contrary to the other thresholds for which we observe less

0 0.2 0.4 0.6 0.8 1

Frequency of convergence

p = 1 p = 5 p = 10 pi [1..5] pi [1..10]

0 0.2 0.4 0.6 0.8 1

local global

0 0.25 0.5 0.75 1 0.2

Condorcet efﬁciency

local p = 1 p = 5 p = 10 global pi [1..5] pi [1..10]

Figure 2: Frequency of convergence and Condorcet efﬁciency for local/global dynamics under different thresholds

convergent proﬁles, in particular when the density is around 0.25. This can be explained by the fact that when p = 10, most voters stay with their truthful ballot, and when p = 1 only a few candidates are potential winners. This is not the case for heterogeneous thresholds and p = 5, because the agents can have very various best strategies. Concerning the Condorcet efﬁciency, we observe a slight increase when the graph is denser, which can be explained by the gain of information. Moreover, the quality of the outcome is better for global dynamics, which appears natural since the voters regularly obtain more information about the current proﬁle. We have conducted the same experiments for graphs closer to real social networks, such as scale-free networks or networks with homophily where the agents are linked w.r.t. their preferences. However, it seems that the poll-conﬁdent dynamics behave as in random graphs of corresponding density. This highlights the role of the quantity of information possessed by the voters in the quality of poll equilibria.

Manipulation of the Opinion Poll In our model, the voters base their belief on the results of the poll. If we consider the polling institute as an agent who has her own preferences over the candidates, then the question of manipulation from the polling institute naturally arises. The polling institute as an agent is denoted by π and her preferences are expressed via a linear order π over the candidates. We assume in this section that all the voters have the same pivotal threshold p. Concretely, the manipulations of π must be restricted in order to satisfy some likelihood conditions. For instance, π could not announce that a candidate has no point if at least one voter has voted for it, otherwise this voter would know that the polling institute is lying. This credibility requirement is described more generally in the following deﬁnition.

Deﬁnition 4 (Likelihood condition). The vector of scores is a plausible result to the poll under strategy proﬁle b if (x) maxi N si b(x), for every candidate x.

We assume that any manipulation performed by π satisﬁes the likelihood condition. Let the manipulation margin be the number of points which are available after having fulﬁlled the likelihood condition. We ﬁrstly ask whether it is possible for institute π to enforce the election of a given candidate x.

Deﬁnition 5 (ELECTION ENFORCING). Given candidate x

and instance I, is there a poll score vector such that the local dynamics converges to a -equilibrium electing x?

This problem is computationally hard even when the network is a DAG. We denote by PW( ) the set of potential winners announced by , w.r.t. the unanimous pivotal threshold p. The set PW( ) includes all the candidates for which the addition of p votes approving them is sufﬁcient to win the election, according to .

Theorem 2. ELECTION ENFORCING is NP-hard even when the social network is a DAG and p = 1.

Proof. We reduce from 3-SAT and consider an instance of r 3-clauses {C1, . . . , Cr} and v variables {x1, . . . , xv}. We construct a set of agents N including: a set Y of r clause-agents Yi for i [r], sets Y and L of 3r literalagents Yij and Lij for i [r] and j [3], a set L of agents L ijk for i [r], j [3] and k [3] referring to 3 copies of the literals, sets Z1 and Z2 (whose union is denoted by Z) of respective agents Z1 i and Z2 j for i [4r 1] and j [11], a set X of agents Xi for i [10], and agents X 1 and X 2. The set of candidates M contains candidates z, x and x, the set Cℓof clause-candidates ci for i [r], and the set Lit of literal-candidates ℓij for i [r] and j [3]. In graph G, there is an arc from Yi to Lij and from Y ij to L ijk, for all i [r], j, k [3]. There is an arc from Lij to Li j if i > i

and the jth literal of ith clause is the opposite of the j th literal of i th. In the sets Z2 and X, there is one agent, say respectively Z2 1 and X1, who is connected to all the agents in the set. Let ρ be a linear order over Cℓ Lit and ρ 1 its reverse order. The preferences are as follows (i + 1 = 1 if i = s): Yi : z ci x ρ Zj i : z ρ 1 x Y ij : z ℓij x ρ 1 Xi : x z ρ Lij : ci ℓij z ρ 1 x X 1 : x z ρ L ijk : ℓij ℓi+1 k z ρ x X 2 : x z ρ 1

where ρ and ρ 1 are assumed to be deﬁned without the candidates already mentioned in the preference order. The turn function τ is such that {L, L } τ {Y, Y }, and Lij τ Li j for i > i. The tie-breaking rule is such that x z ℓ11 ℓ13 ℓr1 ℓr3, and p = 1. We claim that all the clauses are satisﬁable iff polling institute π can enforce the election of x in the local dynamics. At b0, each Lij and L ijk vote respectively for ci and ℓij, and agents Yi and Y ij respectively observe it. So, by the likelihood condition, each candidate y Cℓ Lit must have at least 3 points in the poll, i.e., (y) 3. Each agent in X votes for x and this is visible for X1, thus (x) 10. All the sets Y , Y and Z vote for candidate z, but only agent Z2 1 has a non-null outdegree for observing that, and thus (z) 11, whereas the real score of z is 8r + 10. X 1 and X 2 vote for x so (x ) 1. To summarize, the margin of manipulation for institute π is 8r. We can prove that the only strategy for π to make x win is to assign 8 more points to one literal-candidate associated with each clause, and the new points cannot be given to literal-candidates corresponding to opposite literals. The winner announced in this poll is z. We omit the details of the equivalence, by lack of space.

Beyond the computational hardness of manipulating the poll in the worst-case, we explore a heuristic perspective. For all experiments, we run 10,000 instances of 100 voters and 10 candidates, where the preferences are generated in impartial culture, and the graphs are randomly generated via Erd os and R enyi[1959] s model for different densities. Algm. 1 constructs a poll score vector where, as much as possible, there are only two best candidates. The intuition is that, if π wants to make a target candidate x elected then, as much as the manipulation margin allows, she predicts as the winner a specter candidate y, that π wants to show as a threat to the voters, and x as a potential winner. More precisely, after having fulﬁlled the likelihood condition (l. 24), points are added to x until it becomes a potential winner (l. 5-6). Then, we rise the score of y until one more point to y would remove x from the set of potential winners (l. 7-8), in order to quickly increase the gap with other candidates while keeping x in PW( ). At this point, y is the winner in and x is at the limit of PW( ). Now we simultaneously increase the scores of x and y (l. 9-11) in order to further eliminate other candidates from PW( ). If there remains one point at the end, we assign it to x if that does not make it the winner, or otherwise to the last ranked candidate in by safety (l. 12-14). The process stops if at some step the manipulation margin is not sufﬁcient.

Algorithm 1: Margin rebalance on two candidates

Input: I, state b, target x M, specter y M Output: : communicated scores of the poll from b

1 margin n ;

2 foreach z M do

3 (z) maxi N si b(z);

4 margin margin (z);

5 while margin > 0 and x / PW( ) do

6 (x) (x) + 1; margin margin 1;

7 while margin > 0 and x remains in PW( ) if (y) is increased by 1 do

8 (y) (y) + 1; margin margin 1;

9 while margin > 1 do

10 (x) (x) + 1; (y) (y) + 1;

11 margin margin 2;

12 if margin = 1 then

13 if p > 1 then (x) (x) + 1;

14 else ℓ arg minz M (z); (ℓ) (ℓ) + 1;

15 return ;

Algm. 2 is a heuristic based on Algm. 1 where we choose, as a specter candidate y, the candidate that is the most disliked compared to target candidate x. We aim at creating a situation where only two candidates, x and y, are favorites in the election. One of them, the specter y, is mostly disliked by the population but is announced the winner with a slight lead over x. One could think that, in reaction, a large part of the electorate will report her ballot to the other candidate x. We present experiments in Fig. 3, where the targets are the Condorcet winner (for Condorcet domains), the Borda

Algorithm 2: Heuristic for ELECTION ENFORCING

Input: I, state b, target x M Output: : communicated scores of the poll from b

1 Sort the candidates M \ {x} in decreasing order of the number of voters who prefer x to the candidate;

2 foreach specter y M \ {x} do

3 Algm. 1(I, b, x, y);

4 if f( ) = y and x PW( ) then return ;

5 return Algm. 1(I, b, x, arg maxz =x maxi N si b(z));

winner, the truthful winner (the winner of b0) and the best candidate in . The frequency of election of the target candidate is given in a context of poll manipulation via Algm. 2 or no manipulation. For the sparsest graphs, this frequency is at least twice higher with Algm. 2 than without manipulation. In global dynamics, there is manipulation from π at each global step, that is why the results are slightly better.

Election frequency

0 0.5 0.625 0.75

Truthful Condorcet Borda Top

Global manip. Local manip. Global no manip. Local no manip. p = 1 p = 5

Figure 3: Algm. 2 in global/local dynamics (p = 1 or 5)

From a different perspective, instead of enforcing the election of a speciﬁc candidate, institute π could try to perform best responses at each global step, with immediate beneﬁts in the associated local dynamics, in the same myopic spirit as a voter in iterative voting. In other words, π manipulates at each global step in order to make elected her best possible candidate at the end of the next local dynamics. However, as Thm. 2 states, such a best response is hard to compute, even for a DAG. Consequently, we restrict the manipulation of π to a simple move exposed in Algm. 1: trying to favor only two candidates. We derive Algm. 3 where a manipulated poll score vector is built by Algm. 1 for every couple of candidates (x, y), and the associated sequence of local deviations is tested. We choose the poll score that leads to an equilibrium, in the tested local dynamics, electing the best candidate for π. In order to efﬁciently test the sequence of local deviations, we restrict to cases where the dynamics is guaranteed to converge after a polynomial number of steps, i.e., when the network is acyclic or transitive (Prop. 1 and cases of Cor. 1 and 2). We thus consider spanning subgraph G of network G that is either empty, acyclic or transitive. Since Maximal Acyclic Subgraph and Maximum Transitive Subgraph are NP-complete problems, we use simple classical approximations for computing these subgraphs. The results, presented in Fig. 4, are good for π. These results show the average of the rank in π of the ﬁnal winner when the dynamics converges (lower is better). For both

Algorithm 3: Restricted poll manipulation move

Input: I, turn function τ, preferences π, state b, acyclic / transitive spanning subgraph G of G Output: : communicated scores of the poll from b

1 foreach target x M do

2 foreach specter y M \ {x} do

3 y Algm. 1(I, b, x, y);

4 R(y) f( y-eq.) in I with G G and τ;

5 return y for which R(y) is the best in π;

types of dynamics, the rank with manipulation is clearly better than without manipulation, with a large gap for sparse graphs. The gap decreases with the increase of the density. For global dynamics, the results are very good for π, especially for sparse graphs until density 0.4. Like Algm. 2, the results deteriorate with the increase of the density. This is related to the likelihood condition, making the manipulation margin decreasing with the increase of the density, until the complete graph, where no manipulation is possible for π since every agent has complete information.

0 0.2 0.4 0.6 0.8

Average rank in π s pref.

Manip-empty

Manip-DAG Manip-transitive

0 0.2 0.4 0.6 0.8

local global

0 0.2 0.4 0.6 0.8

Manip-empty

Manip-DAG Manip-transitive

0 0.2 0.4 0.6 0.8

local global

Figure 4: Algm. 3 in global/local dynamics (p = 1 or 5)

Conclusion We have studied a best response dynamics where the voters aggregate the informations from opinion polls and social networks, and adopt a strategic behavior conditioned by pivotal thresholds. We showed the convergence of the dynamics for some classes of graphs but in general it is difﬁcult to recognize instances with cycles. However, it turns out that practically, the dynamics mostly converges. The quality of the equilibria depends on the density of the network: better outcomes are found in dense graphs (there is more information). The equilibrium analysis allows to underline the bias produced by partial information and the dependency on the information sources, raising the question of election control. Actually, manipulation of the poll can be hard to compute, even for simple sparse graphs. However, simple heuristics, based on the idea of announcing a specter candidate (that is mostly disliked) as winner, are very efﬁcient. The manipulation is less beneﬁcial in dense graphs where the knowledge of the voters is close to be complete. These heuristics are not too demanding regarding the network structure, but

they need to know the preferences and thresholds. Nevertheless, this is not a strong assumption that the polling institute knows the preferences of the voters since she collects them. Moreover, we have conducted experiments (not presented here) where the polling institute computes her strategy with thresholds that do not correspond to the real ones, and the results are similar to those presented in the article. In addition to classical perspectives such as the study of other voting rules, coalitional manipulation and more sophisticated heuristics, one could think about voters who are not memory-less in the global dynamics or relaxing the assumption of a poll on the entire electorate. The links with opinion diffusion in networks could also be examined.

References Aumann, R., and Brandenburger, A. 2014. Epistemic conditions for Nash equilibrium. In The Language of Game Theory: Putting Epistemics into the Mathematics of Games. World Scientiﬁc. 113 136. Brams, S. J. 1982. Strategic information and voting behavior. Society 19(6):4 11. Chopra, S.; Pacuit, E.; and Parikh, R. 2004. Knowledgetheoretic properties of strategic voting. In Proceedings of the 9th European Conference on Logics in Artiﬁcial Intelligence (JELIA-04), 18 30. Clough, E. 2007. Strategic voting under conditions of uncertainty: A re-evaluation of Duverger s law. British Journal of Political Science 37(2):313 332. Conitzer, V.; Walsh, T.; and Xia, L. 2011. Dominating manipulations in voting with partial information. In Proceedings of the 25th Conference on Artiﬁcial Intelligence (AAAI2011), 638 643. Dey, P.; Misra, N.; and Narahari, Y. 2016. Complexity of manipulation with partial information in voting. In Proceedings of the 25th International Joint Conference on Artiﬁcial Intelligence (IJCAI-16), 229 235. Easley, D., and Kleinberg, J. 2010. Networks, Crowds, and Markets: Reasoning about a Highly Connected World. Cambridge University Press. Endriss, U.; Obraztsova, S.; Polukarov, M.; and Rosenschein, J. S. 2016. Strategic voting with incomplete information. In Proceedings of the 25th International Joint Conference on Artiﬁcial Intelligence (IJCAI-16), 236 242. Erd os, P., and R enyi, A. 1959. On random graphs I. Publicationes Mathematicae (Debrecen) 6:290 297. Faliszewski, P., and Rothe, J. 2016. Control and bribery in voting. In Brandt, F.; Conitzer, V.; Endriss, U.; Lang, J.; and Procaccia, A. D., eds., Handbook of Computational Social Choice. Cambridge University Press. chapter 7, 146 168. Forsythe, R.; Myerson, R. B.; Rietz, T. A.; and Weber, R. J. 1993. An experiment on coordination in multi-candidate elections: The importance of polls and election histories. Social Choice and Welfare 10(3):223 247. Fred en, A. 2017. Opinion polls, coalition signals and strategic voting: Evidence from a survey experiment. Scandinavian Political Studies 40(3):247 264.

Gibbard, A. 1973. Manipulation of voting schemes: a general result. Econometrica 41(4):587 601. Hazon, N.; Aumann, Y.; Kraus, S.; and Wooldridge, M. 2008. Evaluation of election outcomes under uncertainty. In Proceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-08), 959 966. Jackson, M. O. 2008. Social and Economic Networks. Princeton University Press. Meir, R.; Polukarov, M.; Rosenschein, J. S.; and Jennings, N. R. 2010. Convergence to equilibria in plurality voting. In Proceedings of the 24th Conference on Artiﬁcial Intelligence (AAAI-10), 823 828. Meir, R.; Lev, O.; and Rosenschein, J. S. 2014. A localdominance theory of voting equilibria. In Proceedings of the 15th ACM Conference on Economics and Computation (EC-14), 313 330. Meir, R. 2015. Plurality voting under uncertainty. In Proceedings of the 29th Conference on Artiﬁcial Intelligence (AAAI-15), volume 15, 2103 2109. Meir, R. 2017. Iterative voting. In Endriss, U., ed., Trends in Computational Social Choice. AI Access. chapter 4, 69 86. Myerson, R. B., and Weber, R. J. 1993. A theory of voting equilibria. American Political Science Review 87(01):102 114. Obraztsova, S.; Lev, O.; Polukarov, M.; Rabinovich, Z.; and Rosenschein, J. S. 2016. Nonmyopic voting dynamics: An optimistic approach. In Proceedings of the10th Multidisciplinary Workshop on Advances in Preference Handling (MPREF-16). Reijngoud, A., and Endriss, U. 2012. Voter response to iterated poll information. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-12), 635 644. Satterthwaite, M. A. 1975. Strategy-proofness and Arrow s conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of Economic theory 10(2):187 217. Sina, S.; Hazon, N.; Hassidim, A.; and Kraus, S. 2015. Adapting the social network to affect elections. In Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-15), 705 713. Tsang, A., and Larson, K. 2016. The echo chamber: Strategic voting and homophily in social networks. In Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-16), 368 375. Van Ditmarsch, H.; Lang, J.; and Safﬁdine, A. 2012. Strategic voting and the logic of knowledge. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-12), 1247 1248. Yoshinaka, R. 2005. Higher-order matching in the linear lambda calculus in the absence of constants is NP-complete. In Proceedings of the 16th International Conference on Rewriting Techniques and Applications (RTA-05), 235 249.