# strategic_voting_with_incomplete_information__ff86c894.pdf

Strategic Voting with Incomplete Information

Ulle Endriss University of Amsterdam

The Netherlands

Svetlana Obraztsova

Hebrew University

Jerusalem, Israel

Maria Polukarov University of Southampton

United Kingdon

Jeffrey S. Rosenschein

Hebrew University

Jerusalem, Israel

Classical results in social choice theory on the susceptibility of voting rules to strategic manipulation make the assumption that the manipulator has complete information regarding the preferences of the other voters. In reality, however, voters only have incomplete information, which limits their ability to manipulate. We explore how these limitations affect both the manipulability of voting rules and the dynamics of systems in which voters may repeatedly update their own vote in reaction to the moves made by others. We focus on the Plurality, Veto, k-approval, Borda, Copeland, and Maximin voting rules, and consider several types of information that are natural in the context of these rules, namely information on the current front-runner, on the scores obtained by each alternative, and on the majority graph induced by the individual preferences.

1 Introduction Most existing models of collective decision making adopt simplifying assumptions regarding the information available to individual decision makers about the preferences and intentions of their peers. For instance, the standard model employed for the analysis of strategic behaviour in elections presupposes that each voter has access to the full preferences of the other voters and is able to optimise their own ballot accordingly. This assumption is central to the classical Gibbard Satterthwaite Theorem [Gibbard, 1973; Satterthwaite, 1975], which shows that essentially all reasonable voting rules are subject to strategic manipulation. In practice, however, voters cannot be assumed to possess all of this information, and they cannot be assumed to hold with certainty the information to which they do have access. Exploring the consequences of such richer models of decision making is of particular interest in the domain of multiagent systems, where we can model the information available to agents in precise terms.

In this paper, to represent the incomplete information available to agents, we employ a model developed by Conitzer et al. [2011] and Reijngoud and Endriss [2012], in which each agent is endowed with an information set describing the range of proﬁles of preferences of the other agents he considers possible. We focus on information sets that arise naturally in the

context of voting, such as the range of all proﬁles that are consistent with a given candidate winning the election.

Our contributions are twofold. In the ﬁrst part of the paper, we establish results on the manipulability of voting rules under incomplete information, complementing previous results by Reijngoud and Endriss [2012]. We focus on the Plurality, Veto, k-approval, Borda, Copeland, and Maximin rules (all deﬁned in Section 2). While the Gibbard-Satterthwaite Theorem shows that all of these rules are susceptible to strategic manipulation when the manipulator has full information, this may in principle cease to be the case when we restrict their access to information. We show that, nevertheless, for several natural restrictions to a manipulator s information, manipulation can still occur for certain rules. At the same time, we are able to identify some combinations of voting rules and information sets where manipulation can be ruled out, thereby providing positive results of practical interest.

In the second part of the paper, we connect strategic voting under incomplete information with the growing literature on iterative voting [Meir et al., 2010; Lev and Rosenschein, 2012; Reijngoud and Endriss, 2012; Reyhani and Wilson, 2012; Grandi et al., 2013; Obraztsova et al., 2015]. We consider scenarios where voters are permitted to update their ballot any number of times, in response to the limited information they have regarding the other votes. The question then arises whether such a process will converge to a state where the election winner does not change anymore. As is well known, under complete information, convergence can only be guaranteed in very speciﬁc circumstances. Arbitrary improvement moves are not guaranteed to converge under any voting rule, best-response dynamics lead to equilibria only for Plurality and Veto, and other rules require more restrictions on allowed manipulations to guarantee convergence. In contrast to these largely negative results, we are able to show that, when the only information voters have access to is the identity of the candidate currently leading the polls, we obtain convergence results for all the voting rules considered here.

The remainder of this paper is structured as follows. In Section 2 we recall the deﬁnitions of the aforementioned voting rules and model of incomplete information. Section 3 is devoted to our results on both susceptibility and immunity to strategic manipulation, for different types of incomplete information, Section 4 contains our results on iterative voting under incomplete information, and Section 5 concludes.

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI-16)

2 Preliminaries

In this section, we recall relevant concepts from voting theory [Taylor, 2005] and deﬁne voting scenarios with incomplete information as introduced by Reijngoud and Endriss [2012].

2.1 Voting Rules

Let V = {1, . . . , n} denote a set of n voters (or agents) electing a winner from a set C = {c1, . . . , cm} of m candidates (or alternatives). Let L(C) be the set of all strict linear orders on C. Each voter i submits a vote (or ballot) bi 2 L(C), which may or may not coincide with his real preference order i 2 L(C). A proﬁle b = (b1, . . . , bn) 2 L(C)n is a vector of votes, one for each agent. We denote by b i the proﬁle of all votes except that of agent i, and we write (b0

i, b i) for the proﬁle we obtain when we replace bi in b by b0

i. A voting rule F : L(C)n ! 2C \ {;} takes a proﬁle and returns a nonempty subset of candidates, called the winners of the election. In this paper, we focus on resolute voting rules F : L(C)n ! C, which always return a single winner. Speciﬁcally, we assume ties are broken lexicographically (i.e., in favour of the candidate with the lowest index). Here are some of the most common voting rules [Taylor, 2005]:

Positional scoring rules. Each PSR is associated with a

scoring vector (s1, ..., sm) of integers with s1 > sm and s1 > s2 > . . . > sm. If a voter ranks a candidate at the jth position, that candidate receives sj points. The score of a candidate is the sum of her points over all ballots. This family of rules includes Plurality with the scoring vector (1, 0, . . . , 0), Veto with (1, 1, . . . , 1, 0), Borda with (m 1, m 2, ..., 0) and k-approval with (1, ..., 1, 0, ..., 0), i.e., k 1 s, followed by 0 s.

Maximin. The score of candidate c is the minimum num-

ber, across all other c0 2 C, of voters who prefer c to c0.

Copeland. The score of candidate c is the number of di-

rect majority contests she wins (i.e., the number of other c0 2 C for which the majority of voters prefer c to c0), minus the number of majority contests he loses.

The election winner is always the candidate with the highest score. A Condorcet winner is a candidate that wins every majority contest, and a weak Condorcet winner is one that does not lose any such contest, although she may tie some.

2.2 Information Functions

Even after a proﬁle of ballots has been elicited by the election chair, this information typically will not be communicated to the electorate, at least not in its entirety, e.g., due to privacy concerns. Let I denote the set of all possible pieces of information that might be communicated to the electorate in view of a given proﬁle. Following Reijngoud and Endriss [2012], an information function (IF) is a function : L(C)n ! I that maps proﬁles to elements of I. We focus on the following natural choices for I and the corresponding IF :

Winner (W). Given voting rule F, the corresponding W-

IF returns the winning candidate for the input proﬁle according to F: (b) = F(b).

Score (S). Given voting rule F, the corresponding S-IF

returns for each c 2 C her score s F(c, b) for proﬁle b under F (we omit F when clear from the context).

Majority Graph. A majority graph is a directed graph

with the nodes being the candidates: there is an edge (c, c0) from c to c0 if a majority of voters prefer c to c0. The MG-IF returns the majority graph of the proﬁle.

Given the signal (b), and assuming each voter i knows how the IF is deﬁned, his information set W (b)

i is the set of (partial) proﬁles he must consider possible in view of the information he holds after receiving (b):

i 2 L(C)n 1 | (bi, b0

Conitzer et al. [2011] work with a similar model, but explicitly list the proﬁles a voter considers possible. Here we follow Reijngoud and Endriss [2012] and restrict attention to information sets that can be represented compactly via .

We say that 1 is at least as informative as 2, denoted 1 2, if W 1(b)

i for all b 2 L(C)n and i 2 V .

3 -Manipulability

In this section, we analyse the susceptibility of different voting rules to strategic manipulation by voters with incomplete information, encoded in the form of information sets. Along with a number of susceptibility results regarding the manipulability of certain rules given certain information, we also obtain two new immunity results, demonstrating the role of information in preventing strategic behaviour.

Suppose that before the election we conduct an opinion poll to elicit truthful preferences = ( i)i2V , and then communicate the result to the voters using IF . In the subsequent election, voter i then has an incentive to manipulate if there is a scenario in his information set for which some new ballot would result in a better election outcome for him, and there is no scenario where the same new ballot would result in a worse outcome than the truthful outcome. Thus, manipulation is safe .1 Formally, given proﬁle b, we say that voter i can use -manipulation bi

i for proﬁle b, if there exists a partial proﬁle b

i such that F(b

i) i F(b), and for all b0

i it is the case that F(b

i) i F(b) or F(b

i) = F(b).2 Now, a resolute voting rule F is susceptible to -manipulation (or simply, -manipulable) if there is a voter who can -manipulate the truthful proﬁle = ( i)i2V . If a rule is not susceptible to -manipulation, then it is immune to -manipulation.

If returns the full proﬁle, then -manipulability reduces to the standard notion of manipulability. In this case, the Gibbard-Satterthwaite Theorem [Gibbard, 1973; Satterthwaite, 1975] says that any resolute voting rule for three or more candidates that is surjective and nondictatorial is susceptible to manipulation. Reijngoud and Endriss [2012]

1Note that, just as in the classical setting [Taylor, 2005], we only address the case of one voter at a time considering to manipulate.

2Consult van Ditmarsch et al. [2013] for a discussion of different types of manipulation in view of the knowledge of the manipulator.

prove a simple generalisation of this theorem, stating that for any IF any resolute voting rule for three or more candidates that is surjective, nondictatorial, and strongly computable from -images, is susceptible to -manipulation. Here, a voting rule is strongly computable from -images if upon learning (b) for any proﬁle b, a voter i can compute the winners for any way of voting himself (i.e., not just for bi). Thus, for example, all PSRs are strongly computable from S-images.

In the sequel, we explore the -manipulability of Plurality, Veto, k-approval, Borda, Copeland, and Maximin, under IFs = W, S, MG. We start with the case of W-IF, intuitively providing the least amount of information.3 Note that S-IF is more informative than W-IF for all our voting rules. For Copeland, MG-IF is more informative than S-IF. For other rules, some pairs of IFs cannot be ranked in terms of their informativeness. For example, under Plurality we cannot compute the winner from the majority graph, nor vice versa. For a given proﬁle, if we increase the information available to a voter, manipulability could either increase (as the voter might be able to rule out some proﬁles where he would do worse when manipulating) or decrease (as he might also be able to exclude some proﬁles where he would beneﬁt from manipulating). However, as we will see next, manipulability across all proﬁles increases as information increases.4 This useful result applies to pairs of IFs that are both at least as informative as the W-IF (so they allow the voter to infer the winner).

Lemma 1. Let 1 and 2 be two information functions such that 1 2 W-IF. Then any voting rule that is 2manipulable is also 1-manipulable.

Proof. Suppose F is 2-manipulable, i.e., there exist a proﬁle b, a voter i, and a ballot b

i such that F(b

i) i F(b) for some b

i , while F(b) i F(b

i) for no b0

i . We will show that then F can also be manipulated by i using the same ballot b

i under IF 1 in case the truthful proﬁle is (bi, b

i). First, as b

we have W 2(b)

i) i and thus, as 2 W-IF, we know that F(b) = F(bi, b

i). As the actual proﬁle is always consistent with the information received, we have (bi, b

i) 2 W 1(bi,b

i). Thus, the ﬁrst condition is satisﬁed: there exists a b

i 2 W 1(bi,b

i) such that F(b

i) i F(b) = F(bi, b

i). As for the second condition, as 1 2 we have W

i) i and thus W

i , meaning there is no b0

i) i for which F(bi, b

i) = F(b) i F(b

In the remainder of this section we prove several results on the -manipulability of speciﬁc voting rules for speciﬁc choices of , thereby complementing the partial picture drawn by Reijngoud and Endriss [2012]. Most of our results are negative, but for the case of the MG-IF we are able to identify two sets of sufﬁcient conditions for immunity to manipulation.

3As an aside, note that even when produces no information at all, there exist examples for voting rules, albeit not natural rules, that are susceptible to -manipulation [Reijngoud and Endriss, 2012].

4We are grateful to an anonymous reviewer for pointing this out.

3.1 Winner Information Function Reijngoud and Endriss [2012] proved that Plurality and Borda are W-manipulable, while Veto is immune to Wmanipulation. We complement these results by showing that also k-approval, Copeland, and Maximin are W-manipulable.

Theorem 2. The k-approval (for k 6 m 2), Copeland, and Maximin voting rules are all susceptible to W-manipulation.

Proof. First, let F be k-approval and assume that there is a voter i such that the winner in the truthful proﬁle, F( ), is ranked below the (k + 1)st position in his preference order.5 We now show that such a voter can W-manipulate by swapping the kth and (k + 1)st highest choices in his ballot. Indeed, since the current winner is less preferable to i than any candidate in the ﬁrst k +1 positions, this manipulation is safe for any proﬁle in WW ( )

i , and there exists a proﬁle in this set in which the (k + 1)st preferred candidate of voter i needs only one additional point to win.

We similarly prove W-manipulability of Copeland and Maximin. Let voter i be such that the winner in the truthful proﬁle is ranked below the second position in his preference order. Let i swap his ﬁrst and second best choices. This manipulation does not affect the Copeland/Maximin score of the truthful winner and does not harm i in any proﬁle in WW ( )

i , but there exists a proﬁle in this set where i s second best choice wins the election after the manipulation.

3.2 Score Information Function Since all PSRs are strongly computable from images under S-IF, it follows from the generalisation of the Gibbard Satterthwaite Theorem [Reijngoud and Endriss, 2012] that these rules are S-manipulable. By Theorem 2 and Lemma 1, Maximin and Copeland are S-manipulable as well.

Corollary 3. The Maximin and Copeland voting rules are susceptible to S-manipulation.

3.3 Majority Graphs We now turn to the case where the information made available to voters consists of the majority graph.

Theorem 4. The Copeland and Borda voting rules are susceptible to MG-manipulation.

Proof. For Copeland, as the winner can be computed given the majority graph, the result follows immediately from Theorem 2 together with Lemma 1.

For Borda, consider the following majority graph. Assume candidates c1, c2, . . . , cm 1 have the same number of incoming and outgoing edges between them, and candidate cm is a Condorcet loser i.e., it loses all pairwise majority contests. It follows then that cm cannot be the winner, as Borda never elects a Condorcet loser [Fishburn and Gehrlein, 1976].

Let voter i be such that cm i cm 1 i c2 i c1. Since his top choice is not winning, swapping it with the second best choice is a safe manipulation for voter i. We now show that there is a proﬁle in the information set of voter i where this manipulation is beneﬁcial for him. Let the division of

5Note that for Veto, with k = m 1, this would be impossible.

Block-2 Block-3

w . . . w w0 . . . w0 w0 bcm 2 . . . w0 bcm 2 bc1 . . . bc1 bcm 2 . . . bcm 2 bc1 bcm 3 . . . bc1 bcm 3 ...

... bcm 2 . . . bcm 2 bc1 . . . bc1 bcm 3 bc1 . . . bcm 3 bc1 w0 . . . w0 w . . . w bcm 2 w . . . bcm 2 w w w0 . . . w w0

Table 1: Plurality under MG-IF. Preferences for case s > s0.

votes on the edges in the graph induced by c1, c2, . . . , cm 1 be b n

2 c + 1 against b n

2 c 1 (for odd n), and let it be n 1 against 1 on the edges between c1, c2, . . . , cm 1 and cm. This implies that all the candidates c1, c2, . . . , cm 1 have equal Borda scores, and c1 wins by the tie-breaking. Now, after the manipulation by voter i, the score of candidate cm 1 increases, and she wins the election.

We now turn to positive results. For sufﬁciently large values of n, Plurality is known to be immune to MG-manipulation [Reijngoud and Endriss, 2012]. Here we extend this result to all k-approval rules with k 6 m 2 (i.e., excluding Veto).

Theorem 5. For sufﬁciently large numbers of voters n, kapproval with k 6 m 2 is immune to MG-manipulation.

Proof sketch. We give an alternative proof for Plurality that can be extended to k-approval, except for the Veto case. The idea is to show that, for any given majority graph, for any voter i and associated manipulation, there is a proﬁle in his information set in which that manipulation may be harmful to i. To this end, we construct a proﬁle with these properties:

the majority graph is identical to the given MG;

w is a top choice alternative of any ﬁxed voter i, and it

wins the election in the constructed proﬁle;

w0 is the least favourite alternative of voter i, and by

construction it either has the same score as w but loses to w by the tie-breaking, or has one point less than w if it is prioritised over w by the tie-breaking order.

Our construction consists of three blocks. Block-1 includes ballots that induce the given majority graph. We know, due to the Mc Garvey Theorem [Moon, 1968], that, for any given majority graph, such a proﬁle exists. Now, let s be the score of w induced by voters in Block-1, s0 the score of w0 induced by voters in Block-1, and, ﬁnally, smax the maximum score of any candidate induced by the proﬁle of Block-1. Also, let b C = {bc1, . . . , bcm 2} = C \ {w, w0} be the set of candidates enumerated according to the tie-breaking order, and

b C0 the same set enumerated in reverse order. Then, Block-2 and Block-3 (also depicted in Tables 1 and 2), will consist of 4 smax + 8 + 2|s s0| voters arranged as follows.

Block-2 consists of two sub-blocks, each containing 2 smax + 4 voters, with proﬁle w b C w0 repeated in the ﬁrst sub-block, and w0 b C0 w repeated in the second.

Block-3 contains 2 (s s0) voters and comes in two variants, depending on the relation between s and s0. Speciﬁcally, if s > s0 then Block-3 consists of (s s0) pairs of voters, where the ﬁrst voter has preference w0 b C w and the

Block-2 Block-3

w . . . w w0 . . . w0 w bcm 2 . . . w bcm 2 bc1 . . . bc1 bcm 2 . . . bcm 2 bc1 bcm 3 . . . bc1 bcm 3 ...

... bcm 2 . . . bcm 2 bc1 . . . bc1 bcm 3 bc1 . . . bcm 3 bc1 w0 . . . w0 w . . . w bcm 2 w0 . . . bcm 2 w0

w0 w . . . w0 w

Table 2: Plurality under MG-IF. Preferences for case s0 > s.

second voter has preference b C0 w w0. If, on the other hand, s0 > s, then Block-3 consists of (s0 s) pairs of voters, where the ﬁrst voter has the preference w b C w0 and the second has the preference order b C0 w0 w.

Now, any manipulation by voter i will take a point from alternative w and make his least favourite candidate w0 win the election in the constructed proﬁle. So at least in this proﬁle the manipulation is harmful for i.

The above idea extends to the case of k-approval; however, it requires a more complicated construction, which we omit from this paper for the sake of brevity. We do need to point out, though, that this construction requires at least two zeroscore positions in the scoring rule that is, k < m 1.

The Maximin rule is known to be susceptible to MGmanipulation, at least for the case of an even number of voters [Reijngoud and Endriss, 2012]. We now show that this negative result can be circumvented for proﬁles without a weak Condorcet winner (when interpreting this result, note that every Condorcet winner is also a weak Condorcet winner). Theorem 6. For proﬁles without a weak Condorcet winner, the Maximin voting rule is immune to MG-manipulation.

Proof. Take any majority graph without weak Condorcet winners, and assume there exists a voter i that has an improving MG-manipulation. Thus, for some proﬁle in voter i s information set it is proﬁtable to change the order between some alternatives cj and ck (w.l.o.g., assume that in the truthful ballot of voter i alternative cj is ranked above ck).

Let ci be the top alternative of voter i. We now show that there exists a proﬁle in i s information set such that the above manipulation is harmful to him. Again, we use the Mc Garvey Theorem [Moon, 1968] to construct a preference proﬁle (with n even) that corresponds to the given majority graph such that the votes in each pairwise majority contest are as follows:

The division of votes on the edge between cj and ck is

n 2 + 2 against n

2 2 if ck loses to the top alternative ci due to tie-breaking, and it is n

2 + 3 against n

2 3 if ck is prioritised over ci by the tie-breaking order. The edge between ck and ci has the ratio of votes n

2 + 2 against n

2 2 if it is directed from ck to ci, and otherwise it has the ratio n

2 1 against n

2 + 1. All other directed edges incoming to ci have the ratio of

2 + 2 against n

2 2. All other directed edges incoming to ck have the ratio of

2 + 1 against n

2 1. All other directed edges in the graph have the ratio of

2 + 3 against n

2 3 (in the corresponding order).

Assume that ck loses to ci due to tie-breaking. In this case, the Maximin score of both ci and ck is n

2 2, and ci is the winner due to tie-breaking. However, after the manipulation by i, the division of votes on the edge between cj and ck becomes

n 2 +1 against n

2 1, thus increasing the score of ck and making her the winner, which is not beneﬁcial for i. Similarly, if ck wins against ci due to tie-breaking, then the score of ci is

n 2 2, the score of ck is n

2 3, and ci wins the election. However, after the manipulation by i, the division of votes on the edge between cj and ck becomes n

2 +2 against n

2 2, thus increasing the score of ck and making her the winner after tiebreaking with ci, which again is not beneﬁcial for i.

4 Iterative Voting

As the results in the previous section demonstrate, although limiting the information that is communicated to voters may have a positive effect on the manipulability of a rule, there are still only very few cases in which we can fully rule out manipulation. Nevertheless, we now demonstrate that strategic behaviour under incomplete information converges to a stable outcome more often than in the case of complete information. We focus on the case of W-IF, providing only winner information, which is the most realistic IF we have considered, in the sense of requiring the least amount of information.

A path is a sequence (b0 ! b1 ! ) of proﬁles such that, for every k > 1, there exists a unique voter, say i, for which bk = (b0

i ) for some b0

i in L(C). It is a -improvement path if, for all k > 1, the move made by the unique deviator at step k is a -manipulation. The set of allowed paths may be further restricted by a suitable improvement dynamics. For example, some previous work has assumed that voters always choose the best manipulation available to them. Iterative voting is based on such myopic improvement dynamics: the voters start by announcing an initial vote, and then repeatedly change their ballots in turn, one at a time. As in most previous work, we make the natural assumption that the initial proﬁle is the truthful one that is, b0 = ( 1, . . . , n). We do not impose any restrictions on the order in which the voters apply their updates.

Following Obraztsova et al. [2015], we deﬁne an iterative voting system with incomplete information (F, , D) as the process based on the improvement dynamics D under the voting rule F with IF . We say that such a system converges to a stable outcome (though not necessarily a stable proﬁle) if every -improvement path that contains only moves allowed by D returns a stable winner after a ﬁnite number of steps, i.e., it either terminates or moves back and forth between several proﬁles that all produce the same winner.

We now generalise a condition for convergence, termed function monotonicity (FM), introduced by Obraztsova et al. [2015]. FM is based on the idea of exploiting a potential argument [Monderer and Shapley, 1996]. It uses a real-valued function G : L(C)n ! R over the set of proﬁles that is required to (weakly) increase along any allowed improvement path. Formally, given system (F, , D) and proﬁle b, let

G(b) = s F(F(b), b) + m index (F(b))

where, for any candidate c, the number index(c) indicates her position in the tie-breaking order. Thus, G(b) is the score of the winner for proﬁle b under F, increased by a number between 0 and 1 that reﬂects the bonus score each candidate receives due to her position in the tie-breaking order. Then, FM holds if and only if, for any allowed improvement path (b0 ! b1 ! ), we have G(bk) 6 G(bk+1) for all k > 0.

The following result generalises the corresponding result of Obraztsova et al. [2015] to the case of incomplete information. Its proof is routine and omitted for the sake of brevity.

Lemma 7. Every iterative voting system (F, , D) that satisﬁes FM converges to a stable outcome.

Thus, to prove convergence it sufﬁces to show that a given system satisﬁes FM. We ﬁrst apply this technique to Copeland and Maximin under the unrestricted improvement dynamics allowing the full range of W-manipulations.

Theorem 8. Under the winner information function W-IF, the Copeland and Maximin voting rules converge to a stable outcome for any kind of improvement dynamics.

Proof. We will show that both Copeland and Maximin satisfy FM. The claim then follows from Lemma 7. Let F stand for either one of them (we can use the same proof for both).

Call s F(c, b) + (m index(c))/(m + 1) the G-score of candidate c in proﬁle b. Thus, G deﬁnes a resolute voting rule that is equivalent to F with lexicographic tie-breaking, so we can reason about G rather than F. We will show that the G-score of the winner in a given proﬁle does not decrease as we move to the next proﬁle. Thus, in case the identity of the winner does not change when we move from bk to bk+1, we have G(bk) 6 G(bk+1). Furthermore, in case the identity of the winner does change, we get G(bk) < G(bk+1), as the G-score of the old winner cannot decrease and the G-score of the new winner must be high enough to beat the old one.

What remains to be shown is that, indeed, for both Copeland and Maximin the G-score of the current winner does not decrease during a manipulation. First, observe that, under W-IF, for these rules no voter will ever change the ranking of his least-preferred alternative. The reason is that, knowing only the identity of the winner, any kind of upgrade of the worst candidate risks increasing that candidate s score and beating the former winner. So every voter will always rank his worst candidate at the bottom of his ballot6 and thus have no opportunity to demote her even further. But this means that no manipulator can afford to allow the G-score of the current winner to decrease, as his worst candidate could currently be runner-up, so any kind of demotion of the current winner could cause his least-preferred candidate to win.

We stress that we can only guarantee convergence to a stable outcome, not to a stable proﬁle, i.e., it is possible that the voters will update their ballots indeﬁnitely, although eventually these updates will not affect the identity of the winner anymore. For example, in an election in which candidate c is winning by a large margin, a (memory-less) voter i with true

6Note that at this point we make use of the assumption that the initial proﬁle is truthful (at least w.r.t. least preferred candidates).

a 1 b 1 c b 2 c 2 a c 3 a 3 b

a 1 b 1 c c 2 a 2 b c 3 a 3 b

b 1 c 1 a c 2 a 2 b c 3 a 3 b

b 1 c 1 a b 2 c 2 a c 3 a 3 b

Figure 1: Cycle of safe W-manipulations from the truthful proﬁle (top, left) for the PSR with scoring vector (3, 2, 0).

preferences a i b i c who only knows that c is winning but is unaware of her margin of victory will keep attempting to manipulate by swapping a and b in her ballot, not realising that he has no chance of affecting the outcome.

Theorem 8 cannot be extended to the PSRs, as the example in Figure 1 shows. Winners are underlined. In the initial truthful proﬁle, a wins by tie-breaking. Then voter 2 (for whom a is worst) can safely manipulate and make c win. Then voter 1 manipulates, but unsuccessfully (c still wins). Now voter 2 manipulates again, making b win. Note that his manipulation is safe: there is no risk in demoting c, as a is demoted as well (losing more points than c). Finally, voter 1 manipulates analogously, and we are back at the ﬁrst proﬁle.

Closer inspection of Figure 1 shows that the ﬁrst two manipulation moves, while safe, arguably are not the most natural choices for our voters. For instance, in the initial proﬁle voter 2 could have also manipulated by voting c 2 b 2 a, which would have achieved the same goal and which, intuitively, seems the more natural choice. This intuition can be formalised in a number of ways, e.g., by deﬁning a suitable notion of best response. Here, instead, we opt for a much simpler solution. Under the conservative improvement dynamics, when choosing which of the available safe -manipulations to play, a voter will always choose one that minimises the Kendall tau distance to his current ballot. Theorem 9. Under the winner information function W-IF and the conservative improvement dynamics, every positional scoring rule converges to a stable outcome.

Proof. We use the same technique as for Theorem 8, i.e., we are done if we can show that no manipulator will ever remove his least preferred candidate from the bottom spot in his ballot. But this is clearly the case under W-IF and conservative improvements: if voter i s least preferred candidate c is currently winning, no manipulation can make things worse, so i can choose one that keeps c at the bottom of his ballot. And if some other candidate is currently winning, it is not safe to put c in a position where she would get more than the minimum number of points, so i must keep c at a minimum-score spot and he can choose the bottom spot (the latter distinction only matters in case sm 1 = sm, e.g., for Plurality).

To put Theorems 8 and 9 into perspective, let us recall what other convergence results are known to date. We restrict attention to results that apply when agents initially vote truthfully and when ties are broken lexicographically (without these assumptions, results often are signiﬁcantly weaker). Under complete information and best-response dynamics,

Plurality converges [Meir et al., 2010]. Lev and Rosenschein [2012] extended this result to the case of Veto, but also demonstrated that many other rules do not converge under these conditions [see also Reyhani and Wilson, 2012]. Several other authors introduced more restricted types of manipulation moves, e.g., with voters attempting to manipulate only by swapping the ﬁrst two candidates in their ballot [Grandi et al., 2013] or by promoting their most preferred candidate amongst the current k front-runners [Reijngoud and Endriss, 2012], and were able to establish convergence results under those assumptions for a wider range of voting rules [see also Obraztsova et al., 2015]. However, for the game-theoretical setting considered here, the only known positive results for the full information case concern Plurality and Veto.

The early work of Chopra et al. [2004] already hinted at the fact that the information each voter has access to will impact convergence, but these authors did not establish any concrete convergence results for speciﬁc voting rules. Reijngoud and Endriss [2012] used the same model of incomplete information as we do, but their convergence results concern heavily restricted forms of manipulation only. Meir et al. [2014] used a similar model of information, but focused only on Plurality. Thus, Theorems 8 and 9 signiﬁcantly broaden the range of positive results regarding convergence in iterative voting.

5 Conclusion

We have studied the impact of incomplete information effects on the susceptibility of voting rules to strategic manipulation, and closed a number of gaps in existing research in this ﬁeld. For one, although in many cases strategic behaviour by voters cannot be ruled out, even under heavy restrictions on the information they have access to, we have been able to obtain positive results on the immunity of certain voting rules when voters only have access to the majority graph, rather than to the full proﬁle of individual preferences.

Our most important results concern the scenario of iterative voting, where we have been able to demonstrate that a process of repeated manipulations will converge for a number of voting rules when voters only have access to the information of which candidate is winning the election. This convincingly demonstrates the signiﬁcance of the assumptions regarding information access we are willing to make, as similarly positive results so far have only been available for the very simplest of voting rules, namely Plurality and Veto.

Our results suggest a number of possible avenues for future work. First, both our study of manipulation under incomplete information and our study of convergence in iterative voting with incomplete information should be extended to a wider range of voting rules. Second, while we have considered particular forms of incomplete information that are natural abstractions of a full proﬁle of preferences (and that might, e.g., get published in an opinion poll), other forms more closely associated with notions of uncertainty are also of interest (e.g., a voter may consider all those proﬁles possible that differ from some speciﬁc proﬁle on at most k pairwise rankings). Such ideas have been explored by Meir et al. [2014] and could be applied to both the immunity and the convergence questions we have asked here. Third, in cases

where convergence can be guaranteed, we should seek a better understanding of the properties of the election outcomes produced by iterative voting, in line with previous work by Reijngoud and Endriss [2012] and Grandi et al. [2013] for the case of restricted manipulation moves.

Acknowledgments

This work has been partly supported by COST Action IC1205 on Computational Social Choice, by Israel Science Foundation grant number #1227/12, and by the Israeli Center of Research Excellence in Algorithms (I-CORE-ALGO).

References [Chopra et al., 2004] S. Chopra, E. Pacuit, and R. Parikh.

Knowledge-theoretic properties of strategic voting. In Proceedings of the 9th European Conference on Logics in Artiﬁcial Intelligence (JELIA-2004), 2004. [Conitzer et al., 2011] V. Conitzer, T. Walsh, and L. Xia.

Dominating manipulations in voting with partial information. In Proceedings of the 25th AAAI Conference on Artiﬁcial Intelligence (AAAI-2011), 2011. [van Ditmarsch et al., 2013] H. van Ditmarsch, J. Lang, and

A. Safﬁdine. Strategic voting and the logic of knowledge. In Proceedings of the 14th Conference on Theoretical Aspects of Rationality and Knowledge (TARK-2013), 2013. [Fishburn and Gehrlein, 1976] P. C. Fishburn and W. V.

Gehrlein. Borda s rule, positional voting, and Condorcet s simple majority principle. Public Choice, 28(1):79 88, 1976. [Gibbard, 1973] A. Gibbard. Manipulation of voting schemes: A general result. Econometrica, 41(4):587 601, 1973. [Grandi et al., 2013] U. Grandi, A. Loreggia, F. Rossi, K. B.

Venable, and T. Walsh. Restricted manipulation in iterative voting: Condorcet efﬁciency and Borda score. In Proceedings of the 3rd International Conference on Algorithmic Decision Theory (ADT-2013), 2013. [Lev and Rosenschein, 2012] O. Lev and J. S. Rosenschein.

Convergence of iterative voting. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2012), 2012. [Meir et al., 2010] R. Meir, M. Polukarov, J. S. Rosenschein,

and N. R. Jennings. Convergence to equilibria in plurality voting. In Proceedings of the 24th AAAI Conference on Artiﬁcial Intelligence (AAAI-2010), 2010. [Meir et al., 2014] R. Meir, O. Lev, and J. S. Rosenschein.

A local-dominance theory of voting equilibria. In Proceedings of the 15th ACM Conference on Economics and Computation (EC-2014). ACM, 2014. [Monderer and Shapley, 1996] D. Monderer and L. Shap-

ley. Potential games. Games and Economic Behavior, 14(1):124 143, 1996. [Moon, 1968] J. W. Moon. Topics on Tournaments. Holt,

Rinehart and Winston, 1968.

[Obraztsova et al., 2015] S. Obraztsova, E. Markakis, M. Polukarov, Z. Rabinovich, and N. R. Jennings. On the convergence of iterative voting: How restrictive should restricted dynamics be? In Proceedings of the 29th AAAI Conference on Artiﬁcial Intelligence (AAAI-2015), 2015. [Reijngoud and Endriss, 2012] A. Reijngoud and U. Endriss.

Voter response to iterated poll information. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2012), 2012. [Reyhani and Wilson, 2012] R. Reyhani and M. Wilson.

Best reply dynamics for scoring rules. In Proceedings of the 20th European Conference on Artiﬁcial Intelligence (ECAI-2012), 2012. [Satterthwaite, 1975] M. A. Satterthwaite. Strategyproofness and Arrow s conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of Economic Theory, 10(2):187 217, 1975. [Taylor, 2005] A. D. Taylor. Social Choice and the Math-

ematics of Manipulation. Cambridge University Press, 2005.