Strategic Voting with Incomplete Information

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 GibbardSatterthwaite 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 profiles of preferences of the other agents he considers possible. We focus on information sets that arise naturally in the Maria Polukarov University of Southampton United Kingdon Jeffrey S. Rosenschein Hebrew University Jerusalem, Israel context of voting, such as the range of all profiles that are consistent with a given candidate winning the election.

Our contributions are twofold. In the first 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 defined 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 specific 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 definitions 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.

2 Preliminaries

In this section, we recall relevant concepts from voting theory [Taylor, 2005] and define 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 profile b = (b1↪ ▷ ▷ ▷ ↪ bn) 2 L(C)n is a vector of votes, one for each agent. We denote by b-i the profile of all votes except that of agent i, and we write (b0i ↪ b-i) for the profile we obtain when we replace bi in b by b0i .

A voting rule F : L(C)n ! 2C ∩ ¶;♦ takes a profile 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. Specifically, 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 number, across all other c0 2 C, of voters who prefer c to c0 .
• ÷ Copeland. The score of candidate c is the number of direct 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 profile 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 profile. Following Reijngoud and Endriss [2012], an information function (IF) is a function ⇡ : L(C)n ! I that maps profiles 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 WIF returns the winning candidate for the input profile according to F: ⇡(b) = F(b).
• ÷ Score (S). Given voting rule F, the corresponding S-IF returns for each c 2 C her score sF(c↪ b) for profile 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 profile.

Given the signal ⇡(b), and assuming each voter i knows how the IF ⇡ is defined, his information set W⇡(b) i is the set of (partial) profiles he must consider possible in view of the information he holds after receiving ⇡(b):

Conitzer et al. [2011] work with a similar model, but explicitly list the profiles 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 ✓W⇡2(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 profile b, we say that voter i can use ⇡-manipulation bi i! b⇤i for profile b, if there exists a partial profile b⇤-i 2 W⇡(b) i such that F(b⇤i ↪ b⇤-i ) ≻i F(b), and for all b0-i 2 W⇡(b) i it is the case that F(b⇤i ↪ b0-i ) ≻i F(b) or F(b⇤i ↪ b0-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 profile ≻ = (≻i)i2V . If a rule is not susceptible to ⇡-manipulation, then it is immune to ⇡-manipulation.

If ⇡ returns the full profile, 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]

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

2 Consult 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 profile 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 profile, if we increase the information available to a voter, manipulability could either increase (as the voter might be able to rule out some profiles where he would do worse when manipulating) or decrease (as he might also be able to exclude some profiles where he would benefit from manipulating). However, as we will see next, manipulability across all profiles 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 profile b, a voter i, and a ballot b⇤i such that F(b⇤i ↪ b⇤-i ) ≻i F(b) for some b⇤-i 2 W⇡2(b) i , while F(b) ≻i F(b⇤i ↪ b0-i ) for no b0-i 2 W⇡2(b) 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 profile is (bi↪ b⇤-i ). First, as b⇤-i 2 W⇡2(b) i , we have W⇡2(b) i = W⇡2(bi↪b⇤-i ) i and thus, as ⇡2 ✓ W-IF, we know that F(b) = F(bi↪ b⇤-i ). As the actual profile is always consistent with the information received, we have (bi↪ b⇤-i ) 2 W⇡1(bi↪b⇤-i ) . Thus, the first condition is satisfied: there exists a b⇤-i 2 W⇡1(bi↪b⇤-i ) such that F(b⇤i ↪ b⇤-i ) ≻i F(b) = F(bi↪ b⇤-i ). As for the second condition, as ⇡1 ✓ ⇡2 we have W⇡1(bi↪b⇤-i ) i ✓ W⇡2(bi ↪b⇤-i ) i and thus W⇡1(bi↪b⇤-i ) i ✓ W⇡2(b) i , meaning there is no b0-i 2 W⇡1(bi↪b⇤-i ) i for which F(bi↪ b⇤-i ) = F(b) ≻i F(b⇤i ↪ b0-i ).

In the remainder of this section we prove several results on the ⇡-manipulability of specific voting rules for specific 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 sufficient conditions for immunity to manipulation.

3 As 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].

4 We 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 profile, 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 first k+1 positions, this manipulation is safe for any profile in WW(≻) i , and there exists a profile 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 profile is ranked below the second position in his preference order. Let i swap his first and second best choices. This manipulation does not affect the Copeland/Maximin score of the truthful winner and does not harm i in any profile in WW(≻) i , but there exists a profile 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 GibbardSatterthwaite 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 profile in the information set of voter i where this manipulation is beneficial for him. Let the division of w ▷ ▷ ▷ w bcm-2 w ▷ ▷ ▷ bcm-2 w votes on the edges in the graph induced by c1↪ c2↪ ▷ ▷ ▷ ↪ cm-1 be b n2 c + 1 against b n2 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.

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

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

We now turn to positive results. For sufficiently 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 sufficiently 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 profile in his information set in which that manipulation may be harmful to i. To this end, we construct a profile with these properties:

• ÷ the majority graph is identical to the given MG;
• ÷ w is a top choice alternative of any fixed voter i, and it wins the election in the constructed profile;
• ÷ 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 McGarvey Theorem [Moon, 1968], that, for any given majority graph, such a profile 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, finally, smax the maximum score of any candidate induced by the profile 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 C 0 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.

first sub-block, and w0 ≻ b Block-3 contains 2 · (s - s0 ) voters and comes in two variants, depending on the relation between s and s0 . Specifically, if s > s0 then Block-3 consists of (s - s0 ) pairs of voters, where the first voter has preference w0 ≻ b C ≻ w and the

Block-2 consists of two sub-blocks, each containing 2 · smax + 4 voters, with profile w ≻ b C ≻ w0 repeated in the C 0 ≻ w repeated in the second.

w ▷ ▷ ▷ w bcm-2 w0 ▷ ▷ ▷ bcm-2 w0

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

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

second has the preference order b 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 profile. So at least in this profile 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 profiles without a weak Condorcet winner (when interpreting this result, note that every Condorcet winner is also a weak Condorcet winner).

Theorem 6. For profiles 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 profile in voter i's information set it is profitable 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 profile in i's information set such that the above manipulation is harmful to him. Again, we use the McGarvey Theorem [Moon, 1968] to construct a preference profile (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 n2 + 2 against n2 - 2 if ck loses to the top alternative ci due to tie-breaking, and it is n2 +3 against n2 -3 if ck is prioritised over ci by the tie-breaking order.
• ÷ The edge between ck and ci has the ratio of votes n2 + 2 against n2 -2 if it is directed from ck to ci, and otherwise it has the ratio n2 -1 against n2 +1.
• ÷ All other directed edges incoming to ci have the ratio of votes n2 +2 against n2 -2.
• ÷ All other directed edges incoming to ck have the ratio of votes n2 +1 against n2 -1.
• ÷ All other directed edges in the graph have the ratio of votes n2 + 3 against n2 - 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 n2 -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 n2 +1 against n2 -1, thus increasing the score of ck and making her the winner, which is not beneficial for i. Similarly, if ck wins against ci due to tie-breaking, then the score of ci is n2 - 2, the score of ck is n2 - 3, and ci wins the election. However, after the manipulation by i, the division of votes on the edge between cj and ck becomes n2 +2 against n2 -2, thus increasing the score of ck and making her the winner after tiebreaking with ci, which again is not beneficial 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 profiles such that, for every k > 1, there exists a unique voter, say i, for which bk = (b0i ↪ bk-1 -i ) for some b0i 6= bk-1 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 profile 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 define 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 profile) if every ⇡-improvement path that contains only moves allowed by D returns a stable winner after a finite number of steps, i.e., it either terminates or moves back and forth between several profiles 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 profiles that is required to (weakly) increase along any allowed improvement path. Formally, given system (F↪ ⇡↪D) and profile b, let

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 profile b under F, increased by a number between 0 and 1 that reflects 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 satisfies FM converges to a stable outcome.

Thus, to prove convergence it suffices to show that a given system satisfies FM. We first apply this technique to Copeland and Maximin under the unrestricted improvement dynamics allowing the full range of W-manipulations.

Theorem8. Under the winner information functionW-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 sF(c↪ b) + (m - index(c))◁(m + 1) the G-score of candidate c in profile b. Thus, G defines 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 profile does not decrease as we move to the next profile. 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 ballot 6 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 profile, i.e., it is possible that the voters will update their ballots indefinitely, 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

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

Figure 1: Cycle of safe W-manipulations from the truthful profile (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 profile, 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 first profile.

Closer inspection of Figure 1 shows that the first two manipulation moves, while safe, arguably are not the most natural choices for our voters. For instance, in the initial profile 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 defining 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 significantly 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 first 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 specific 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 significantly 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 field. 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 profile 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 significance 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 profile 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 profiles possible that differ from some specific profile 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).