Lie on the Fly: Iterative Voting Center with Manipulative Voters

1 Introduction

Iterative Voting (see e.g. [Meir et al., 2010]) proceeds in rounds. In every round the voters are allowed to change their profile, i.e., their reported preferences over the candidates. Voters might attempt to vote strategically, that is to state preferences that will increase the chance that the final outcome will match their truthful profile. Practical applications, such as Doodle (www.doodle.com) and SurveyMonkey (www.surveymonkey.com), provide a real world example of iterative voting processes. Currently, 20%-30% of the internet users use on-line calenders for their daily needs 1 , making online scheduling a natural next step. Therefore the importance of research into iterative voting can hardly be overstated. Changing the profile is known as strategic voting or as manipulation [Farquharson, 1969; Laffont, 1987], and is readily found in the real world as well (see e.g. [Zou et al.,

∗This research was partially supported by: European Union (European Social Fund - ESF) and Greek national funds through the Operational Program "Education and Lifelong Learning" of the National Strategic Reference Framework (NSRF) - Research Funding Program: THALES; RFFI 14-01-00156-a

1 http://en.blog.doodle.com/2011/07/13

2015]). Computing a manipulation is possible since the voters know the intermediate results of the voting process.

In this paper we claim that iterative voting can be applied when the voters' preferences are incomplete. Incomplete preferences are a realistic scenario for different reasons. First, due to privacy concerns full preference revelation should be treated with caution. Secondly, it is sometimes completely impractical to collect complete preferences due to the communication burden [Conitzer and Sandholm, 2005; Konczak and Lang, 2005] or to voter limitations. Consider, for example a meeting scheduling application whose purpose is to set a time for a conference [Kalech et al., 2011], or an application that recommends movies, such as Netflix (www.netflix.com). It is impractical to expect the voters to provide their preferences on all available options as there might be hundreds available.

As a result, a separate direction has developed which studies the iterative elicitation from non manipulative voters. The assumption is that voters submit only a part of their preferences and cannot change already submitted preferences. Also, the voters are not aware of the intermediate result but are only shown the final outcome. In the worst case for most voting protocols all the preferences are needed in order to determine a winning item, i.e., an item that most certainly suits the group's joint preferences [Conitzer and Sandholm, 2005; Xia and Conitzer, 2011]. Nevertheless, recent works [Naamani-Dery et al., 2014; 2015; Lu and Boutilier, 2011; 2013] show that in practice the required information can be cut by more than 50%. To the best of our knowledge, iterative preference elicitation has not been studied with manipulative voters before.

In this paper, we combine the two approaches of iterative processes: iterative preference elicitation and iterative voting and study the outcome and performance of a setting where manipulative voters submit partial preferences. In this scenario, the Voting Center proceeds in rounds. In each round the center selects one voter to query for her preference between two candidate items; we follow the terminology in [Lu and Boutilier, 2011] and term this a voter-item-item query. At the end of each round, the Voting Center exposes the set of possible winner candidates, i.e. the candidates that might win the elections. Thus the voters can attempt to manipulate by sending the Voting Center an insincere response in order to promote or avoid certain candidates according to their truthful preferences. The voters' responses to queries must not contradict previously stated preferences.

In the iterative voting setting with manipulation there are two main challenges. First, from the Voting Center's point of view: how to select a voter-item-item query which is the most manipulation proof. The second challenge, from the manipulative voters' point of view: find a manipulation which will increase the chance to achieve a better selfish outcome, as is done in the voting literature since the classical works [Gibbard, 1973; Satterthwaite, 1975]. We assume only one query is executed in each iteration. Since combining preference elicitation with voting manipulation is a novel idea, we chose to begin with the Borda voting rule, as it can easily be expanded to other voting rules. It must be noted that several general results have been obtained regarding the complexity of manipulating Borda with partial information [Conitzer et al., 2011; Xia and Conitzer, 2011]. However, these works assume that a complete preference order is submitted as a ballot. Since in our case only a very limited portion of an order is submitted, off hand it may still be possible to obtain a manipulation strategy efficiently. This, in turn, supports the need to resolve the first challenge.

Contributions: For the first challenge, we present a Careful Voting Center which tries to prevent manipulation. For the second, we provide a practical manipulation algorithm for voters in an iterative voting setting. In order to evaluate the manipulation impact on the preference elicitation process, we constructed an experiment on real-world data. We compared manipulative voters to truthful voters in a Careful and in a Naive Voting Center setting and examined three research questions: (1) How often does manipulation occur in practice? (2) Does manipulation impact the final result? (3) How does manipulation impact the number of iterations required to reach the final result? We show that in practice, manipulation happens in a low percentage of the settings and has a low impact on the final outcome. A Careful Voting Center reduces the manipulation even further.

2 RelatedWork

Practical vote elicitation has been addressed recently. Ding and Lin define a candidate winning set as the set of queries needed in order to determine whether the candidate is a necessary winner and show that for rules other than the plurality voting, computing this set is NP-Hard [Ding and Lin, 2013].

Therefore heuristics are needed for preference elicitation. Practical elicitation heuristic algorithms that aim to minimize preference communication have been addressed in a few papers. Lu and Boutilier propose a practical elicitation process for the Borda voting protocol using the minmax regret concept. The outcome is a definite or an approximate winner [Lu and Boutilier, 2011; 2013]. Naamani-Dery et. al. suggest practical elicitation algorithms that incorporate probabilistic information for the Range and Borda voting protocol [Naamani-Dery et al., 2014; 2015].

In iterative voting, it is assumed that rather than simply finding the election outcome, voters behave strategically [Farquharson, 1969]. Voters are allowed to iteratively examine the currently recorded intermediate election results and ballot alteration (e.g. [Meir et al., 2010; Lev and Rosenschein, 2012; Branzei et al., 2013; Kukushkin, 2011; Reyhani and Wilson, 2012]). Works in this direction can be roughly broken into two categories: the characterization of the stable points of the iterative voting process, echoing the older interest in equilibrium characterization (e.g. [Rabinovich et al., 2015]), and the research into the conditions that guarantee the iterative voting dynamics to converge (e.g. [Reijngoud and Endriss, 2012; Grandi et al., 2013; Obraztsova et al., 2015; Meir et al., 2014]).

It has been proven that it is computationally hard to compute the possible and necessary winners, or to manipulate elections in incomplete voting settings [Walsh, 2007; Pini et al., 2007] Our paper is orthogonal to these claims and proposes a practical manipulation strategy for iterative voting. We challenge the separation of iterative preference elicitation and iterative voting and focus on the questions of how the interaction of these two concepts affects the elections' outcome.

3 The Model

A voting model consists of a set of candidates C = {c1, ..., cm} and the set voters V = {v1, ..., vn}. At the beginning of the process, none of the voters' preferences are known. In an iterative process, the Voting Center selects a voter-item-item query, i.e., a voter vi and two items cj, ck ∈ C. The selected voter is requested to submit her preferences between the two items. A voter's profile Pi is a vector of ordered preferences: Pi = [ci1 , ..., cim ] where ci1 is vi's most preferred candidate. The voter responds cj ≻ ck when cj is preferred over ck or vice versa. The Voting Center maintains a set Qi ∈ Q of partial preferences of each voter. Based on the partial preferences of all voters Q, the voting center computes a set of the Possible Winners PW. The center gradually expands the set until a Necessary Winner is found. We follow [Konczak and Lang, 2005] definitions of Possible and Necessary winners. The tie-breaking policy when a few Necessary Winners exist is that the winner with the smallest lexicographical order is chosen.

Previous work using an iterative center [Naamani-Dery et al., 2014; Lu and Boutilier, 2013] assumed that the voters always submit their true preferences and that they have no knowledge of the voting process's intermediate results [Walsh, 2007]. However, we follow [Gibbard, 1973; Satterthwaite, 1975] and assume that voters attempt to manipulate the elicitation process in order to achieve a better selfish outcome. The voters are allowed to observe the current ballot summary similarly to [Conitzer et al., 2011; Reijngoud and Endriss, 2012]. The summary is expressed by a set of Possible Winners PW.

Our model does not assume any specific query selection protocol and several possibilities for selecting the voteritem-item queries exist [Naamani-Dery et al., 2015; Lu and Boutilier, 2011]. The interaction between the voting center and the voters proceeds as follows: At the beginning, each voter holds her true set of preferences Pi = Pitrue . As long as the necessary winner has not been identified: a) the Center selects a voter-item-item query, 〈vi〈cj, ck〉〉; b) the voter is provided with the current set of Possible Winners PW; c) the voter decides if to change her profile from Pi to P ′ i ; d) the voter responds with either cj ≻ ck or ck ≻ cj; e) the Center updates the incomplete profile by incorporating vi's answer and applying transitive closure.

4 Locally Dominant Manipulation

The voter will change her current profile from Pi to P ′ i if she recognizes that the change will increase the chance that the final outcome will match her truthful profile. The set Pi represents all the alternatives of P ′ i , including the current Pi. For example, assume the set of possible winners is PW = {c2, c5}, and v1 received a query for her preferences between c2 and c3, where v1's current profile is: P1 = [c3, c2, c5...]. v1 will recognize that c3 has no chance of winning since it is not in the Possible Winners set. Therefore she will update her profile to be: P ′1 = [c2, ..., c3, ...] and respond with c2 ≻ c3. The voter's change of profile is always consistent with her set of previously stated preferences (Qi).

We first describe under what conditions voters manipulate and then present algorithms for voter manipulation in an iterative voting process.

4.1 Conditions for Manipulation

The voters manipulate and state false preferences by employing a local dominance manipulation model (see e.g. [Meir et al., 2014; Reijngoud and Endriss, 2012; Conitzer et al., 2011]). Local Dominance is defined as:

Definition 1. [Local Dominance] Let Pitrue be vi's true preference. A preference order P ′ i is a local dominant over preference order Pi if in at least one outcome the Necessary Winner is ranked closer to vi's true preferences, and in none of the outcomes the Necessary Winner is ranked lower.

When queried, the voter is requested to submit her preference between two candidates only. However, in order to manipulate, more than a single change in preferences might be needed. From all of the possible changes in Pi, our algorithm selects the change that requires the minimal number of swaps, i.e., the voter performs the minimal change in her preferences. To compare two profiles, we use the swap distance [Kendall, 1938] defined for two linear orders P and P ′ . The distance counts the number of candidate pairs that are ordered differently by two ballots or linear orders.

The voter will change her profile to P ′ i ∈ Pi under the following conditions only:

• VM-Condition-1: The new preference profile P ′ i is a local dominant over Pi.
• VM-Condition-2: The new preference profile P ′ i has the minimal swap distance out of all possible local dominant profiles. P ′ i ∈ arg min P ′ i ∈Pi dswap(P ′ i , Pi).

We now define the scenarios were manipulation can be performed. For a given set of Possible Winners PW = {pw1, ..., pwl} we define PWi as the ordered vector of possible winners for voter vi: PWi = [pwi1 , ..., pwil ]. We define Ei as the ordered vector of preferences which contains all possible winners and candidates between these possible winners; e.g, if PW = {c2, c5} and P1 = [c3, c2, c4, c5, c1] then E1 = [c2, c4, c5].

Assume that for a given query 〈vi〈cj, ck〉〉, according to vi's current profile Pi : cj ≻ ck. We define two special subsets, Eiup and Eidown , of candidates that come from Ei whose relative position wrt cj and ck we can not change due to our previous obligations recorded by Qi:

In our running example, E1up = [c2, c4], when the query is 〈v1〈c3, c5〉〉 and Qi = Closure({(c2 ≻ c4), (c4 ≻ c5)}).

To set the conditions for local dominance, we use the following set of Common Givens:

• The current preference profile of vi is Pi
• The query is: 〈vi〈cj, ck〉〉, and according to Pi: cj ≻ ck
• The ordered vector of Possible Winners of vi is PWi
• The closure of the set of current query responses is Qi

Now, denote SG(c, c′ , Pi) the set of candidates in preference profile Pi between two candidates, c ≻ c′ , inclusive of the two candidates themselves. The following Theorem states that a manipulative response to a query has to maintain the same implied order of possible winners. Furthermore, for at least one pair of consecutive possible winners the distance between them grows. In turn, the Corollary states that these ordering and distance properties can be consistently traced from the truth profile throughout all responses of a voter.

Theorem 1. A preference profile P ′ i is a local dominant over Pi if and only if the following holds:

• pwl ≻ pwl+1 for all l ∈ [1, ..., k - 1]
• |SG(pwl, pwl+1, P ′ i )| ≥ |SG(pwl, pwl+1, Pi)| for all l ∈ [1, ..., k - 1]
• Exists l ∈ [1, ..., k - 1] so that |SG(pwl, pwl+1, P ′ i )| ⪈ |SG(pwl , pwl+1, P )|

Corollary 1. Let τ > t, and P t i , P τ i are the preference profiles of voter vi at times t and τ respectively. Then the set of possible winners PW at time τ will be ordered the same way by Pitrue (the truthful preference of vi), P t i and P τ i . Furthermore, the size of each segment between consecutive possible winners in PW will monotonically grow from Pitrue to P t i to P τ i , and the total size of these segments will grow strictly monotonically.

It is possible to devise an algorithm that implements the properties described by Theorem 1, i.e. looks for a possible manipulation. Taking into account the swap distance limitations, it essentially means that for a given query we will be testing whether one candidate of the query is in Ei and the other is not. If it is the case, we will test which ordering between them would imply the smallest distance between Pi and P ′ i constructed by adding the considered query response. It is possible to give a set of formal lemmata that provide the sufficient and the necessary conditions used by the aforementioned tests. We omit them due to space limitations, however we do provide the algorithms they entail. The algorithms find all possible manipulations that meet VM-Conditions 1&2.

4.2 Manipulation Algorithms

We identify six situations where a profile can be changed. Given a query 〈vi〈cj , ck〉〉, when according to Pi, cj ≻ ck and a set of l Possible Winners PW, the situations are grouped into two symmetrical families:

• Family I: cj ≻ pwi1
• Case-A: ck ∈ PW \ {pwi1 , pwil },
• Case-B: ck = pwi1 ,
• Case-C: ck ∈ Ei \ PW.
• Family II: pwil ≻ ck
• Case-D: cj ∈ PW \ {pwi1 , pwil },
• Case-E: cj = pwil ,
• Case-F: cj ∈ Ei \ PW.

We describe algorithms for Family I only, since the Family II algorithms are symmetric to Family I. Algorithms 1-3 correspond to Case-A through Case-C respectively.

Algorithm 1 VoterManipulation function: Case-A

Require:

Common Givens

Holds cj ≻ pwi1 , ck = pwik

• 1: if Eidown ∩ SG(pwi1 , ck, Pi) ̸= ∅ then
• 2: return Pi
• 3: end if
• 4: Sgood ← {c ∈ C|c ≻ p1)} \ (Eidown ∪ {ck})
• 5: Sbad ← {c ∈ C|c ≻ p1)} ∩ Eidown
• 6: Yhead ← Eiup
• 7: Ytail ← {c ∈ C|ck ≻ c)}
• 8: Order Sgood, Sbad, Yhead and Ytail by Pi
• 9: Compose P ′ i = (Sgood, Yhead, x, Sbad, Ytail)
• 10: return P ′ i .

Algorithm 2 VoterManipulation function: Case-B

Require:

Common Givens

• 1: Set O← ∅
• 2: Set Z ← [cj, ..., ck]
• 3: for d ∈ [1 : length(Z)] do
• 4: Xgood ← {c ∈ C|c ≻ zd} \ (Eidown ∪ {cj})
• 5: Xbad ← {c ∈ C|c ≻ zd} ∩Eidown
• 6: Ygood ← {c ∈ C|zd ≻ c}∨ c = zj} \ (Eiup ∪ {ck})
• 7: Ybad ← {c ∈ C|zd ≻ c} ∨ c = zj} ∩Eiup
• 8: Order Xgood, Xbad, Ygood and Ybad by Pi
• 9: Compose P ′ i = (Xgood, Ybad, y, x, Xbad, Ygood)
• 10: Set O←O∪ {P ′ i }
• 11: end for
• 12: Set Pibest = arg min Pi∈O dswap(Pi, P ′ i )
• 13: return Pibest

Algorithm 1 identifies that since cj is not a Possible Winner and ck ∈ PW, it is better to switch between them. The algorithm first checks whether any of voter vi's previously declared preferences in Qi, are inconsistent with switching the order of cj and ck. If it is consistent, it shifts cj and all candidates that are declared in Qi as candidates with a lower

Algorithm 3 VoterManipulation function: Case-C Require:

Common Givens

Holds cj ≻ pwi1 , ck ∈ Ei \ PW

• 1: Let pwl ∈ PW be closest to ck from above
• 2: if Eidown ∩SG(pwi1 , pwl+1, Pi) ̸= ∅ then
• 3: return Pi
• 4: end if
• 5: Set O← ∅
• 6: Set Z ← [pwil , ..., ck]
• 7: for d ∈ [1 : length(Z)] do
• 8: Xgood ← {c ∈ C|c ≻ zd} \ (Eidown ∪ {cj})
• 9: Xbad ← {c ∈ C|c ≻ zd} ∩Eidown
• 10: Ygood ← {c ∈ C|zd ≻ c} \ (Eiup ∪ {ck})
• 11: Ybad ← {c ∈ C|zd ≻ c} ∨ c = zd} ∩ Eiup
• 12: Order Xgood, Xbad, Ygood and Ybad by Pi
• 13: Compose P ′ i = (Xgood, Ybad, y, x, Xbad, Ygood)
• 14: Set O←O∪ {P ′ i }
• 15: end for
• 16: Set Pibest = argmin b∈O dswap(Pi, P ′ i )
• 17: return Pibest

preference than cj, to be positioned as less preferred than ck in the new preference profile P ′ i .

Algorithm 2 and Algorithm 3 attempt the same shift of priority for cj and relevant candidates. However, the location of ck in the current profile Pi makes the process more intricate. We therefore demonstrate the operation of Algorithm 3 with an example. Consider a situation where the query is: 〈v1〈c5, c2〉〉 and the current preference profile of v1 has the following order of preferences:

This means that: c5 ≻ c2 and the ordered vector of Possible Winners for v1 is: PW1 = [pw11 , pw12 , pw13 ]. Assume that Q1 = {(c5 ≻ c1)}. Then E1down = [c1]. Hence, the preference profile remains unchanged, since the intersection between E1down and [pw11 , c1, pw12 ] is not empty.

Let us now assume a different scenario, where Q1 is more complex: Q1 = {(c5 ≻ c4), (c5 ≻ c8), (c6 ≻ c2)}. The safety check in line 2 of the algorithm is now satisfied, since E1down = [c4, c8, c2] and E1 = [pw11 , c1, pw12 ]. The algorithm now searches for the best new preference profile P ′1 , where v1 will manipulate and declare that c2 ≻ c5. First, different positions for the sub-sequence [c2, c5] are considered. The possible positions are all the positions that are above c2 and below the possible winner that is closest to c2 from above, in this case pw12 . Thus in our case the possible positions are: [c3, c4, c6, c8, c7, c2]. If [c2, c5] appears before c3 in the new preference profile, then c5good = [pw11 , c1, pw12 ] will be placed before c5. Similarly, c2good = [c3, c4, c8, c7, pw13 ] will be placed after c2. We now check for inconsistencies with Q1. If c5 is moved to be preferred over c3 and is positioned directly before c3, the set c5bad is empty, thus this move is consistent with Q1. However, c2bad = [c6] meaning we cannot move c6 to be preferred over c2, since (c6 ≻ c2) ∈ Q1.

As a result, the generated new preference profile is:

In P ′1a , c5 is lower in 5 position than it was in P1, c3 and c4 are lower in 2 positions and c6 and c2 are lower in 1 position. Hence, the swap distance is: dswap(P ′1a , P1) = 5 + 2 + 2 + 1 + 1 = 11.

Another option is to create a preference profile where [c2, c5] appears before [c4, c6, c8] or before [c7]. Considering the constraints induced by c5bad and c2bad , the new preference profile is:

This results in swap distance of dswap(P ′1b , P1) = 10.

The last option is to position c5 directly after c2, resulting in a preference profile: P ′1c = (pw11 , c1, pw12 , c3, c6, c7, c2, c5, c4, c8, pw13 ) with a swap distance: dswap(P ′1c , P1) = 12.

Out of the set of locally dominant alternative preference profiles O = {P ′1a , P ′1b , P ′1c } the profile with the smallest swap distance is selected: P ′1 = P ′1b .

The resulting new preference profile P ′1 satisfies both VM-Condition-1 and VM-Condition-2: (1) the profile is a local dominant over P1, since both pw1 and pw2 now have a higher relative preference; and (2) the profile is the most similar to P1 according to the swap-distance measure.

Theorem 2. Assume Common Givens. Algorithms 1-3 and their symmetric counterparts for Family II always find a new preference profile P ′ i that satisfies both VM -Condition1 and VM - Condition - 2, if such a profile exists. The computational complexity of finding the profile is O(m3 ).

Having mapped all possible cases of manipulation, we now construct a voting center which is less prone to manipulation by prevention: the center actively selects queries which will not enable the voter to manipulate. Specifically, we define a Careful Voting Center as a Center that selects queries where both candidates are in the Possible Winners set.

5 Experimental Validation

In order to evaluate the manipulation impact on the preference elicitation process, we compared manipulative voters to truthful voters in a Careful and in a Naive Voting Center setting and examined:(1) How often manipulations occur; and (2) The manipulation impact on the final result. Experiments were performed on the real-world Sushi dataset [Kamishima et al., 2005]. The dataset contains 5000 preference rankings over 10 kinds of sushi. The dataset was used to generate responses to elicitation queries, assuming a Borda voting rule. A random set of preference profiles (P ) was chosen out of the Sushi dataset, according to the amount of users in the experiment setting. For each experiment setting, 20 sets of random profiles were evaluated. For each set of profiles, the experiment was conducted 40 times. Thus we reach an amount of 800 experiments for each experiment setting.

Algorithms that perform preference elicitation in iterations can be found in [Naamani-Dery et al., 2014; 2015; Lu and Boutilier, 2011; 2013]. In this paper we use the Expected Scored (ES) algorithm found in [Naamani-Dery et al.,

2015]. The ES algorithm selects a voter-item-item pair where one of the items is the item with the current maximum score. This algorithm is publicly available whereas some others are used commercially and cannot be tampered with [Lu and Boutilier, 2011; 2013]. As a baseline we used an algorithm which randomly chooses the next query (denoted as RANDOM). Each algorithm (ES and RANDOM) was studied in three states: (a) the voters always answer truthfully (ES+T, RANDOM+T), (b) the voters attempt to manipulate (ES+M, RANDOM+M), and (c) manipulative voters with a Careful Voting Center (Careful-ES+M, Careful-RANDOM+M). For RANDOM we used a Center that selects queries where both candidates are in the Possible Winners set or when both candidates are not in the Possible Winners set. If none such queries exist (since they have been previously used), the Voting Center stops being careful. The amount of candidates was set to 10, which is the maximum amount of candidates in the Sushi dataset. The amount of voters was varied on a range of 10, 50, 100, 150, 200, 250.

In order to conclude which algorithm performs best over multiple datasets, we followed a robust non-parametric procedure proposed by [Garc´ıa et al., 2010]. We first used the Friedman Aligned Ranks test in order to reject the null hypothesis that all heuristics perform the same. This was followed by the Bonferroni-Dunn test to find whether one of the heuristics performs significantly better than other heuristics.

5.1 Results

Manipulation impact on the final result: Experiments show that when the amount of voters is 50-250 the manipulations do not alter the final result, i.e., in all experiments for all three states of each algorithm, the same necessary winner was found. However, for 10 voters, the outcome changes in 4.25%, 0.37%, 15%, 0.37% of the experiments for ES+M, Careful-ES+M, RANDOM+M, CarefulRANDOM+M respectively.

Manipulation rate in a Careful and a regular Voting Center: Manipulations occur in a small portion of the queries. The manipulation rate is a mere 0.001-0.01. Figure 1 illustrates the average manipulation rate per experiment for a changing number of voters. Fewer manipulations occur at the ES+M and Careful-ES+M than at the RANDOM algorithms. The ES algorithm variations reach the stopping condition of the algorithm earlier and thus less queries and manipulations are used. Furthermore, Careful-ES+M reduces the number of manipulations since it tends to select queries where both items are possible winners, i.e., queries in which manipulations are not possible. The algorithms are significantly different according to a Friedman test with at a 95% confidence level. The Careful-ES+MCenter significantly reduces the manipulation percentage when compared with the regular ES+M algorithm, at a 95% confidence level according to the Bonefferi-Dunn test (Figure 2 shows a zoom on these two variations). The RANDOM+M and Careful-RANDOM+M algorithms are not significantly different.

Manipulations impact on the number of iterations: Figures 3 and 4 illustrate the average percentage of the dataset queried until a necessary winner is found, for a changing number of voters. All variations of the ES algorithm (Figure 3) significantly outperform all variations of the RANDOM algorithm (Figure 4). There is no significant difference between ES+M and Careful-ES+M. However, there is a significant difference to the favor of an ES+T algorithm with no manipulations: when no manipulations occur, the result is reached faster. A possible explanation is that the Voting Center is confused by the manipulations; although the manipulations occur in a small percentage of the queries, they do impact the algorithms performance.

Surprisingly, for the RANDOM algorithms the trend is opposite: the non-manipulating algorithm performs worse than the manipulating one. It seems that when the queries are chosen at Random, the manipulations actually assist the Voting Center. This definitely requires further investigation.

We can conclude that in practice, manipulations do not pose a big threat on an incremental iterative voting process when the voters submit one preference at a time, since they rarely modify the outcome. A Careful Voting Center can reduce the manipulation rate, but the tradeoff is that in turn, there is an increase in the amount of queries needed in order to end the iterative process and find a winner.

6 Conclusions and FutureWork

In this work we have developed and studied a novel combination of two iterative processes found in social choice: iterative preference elicitation using a Voting Center, and the manipulative modification of preferences by voters in Iterative Voting. The design of the former intends to reduce the amount of query requests the Voting Center sends in order to obtain the elections outcome, but assumes voters will reveal their true preference. The latter, on the other hand, presumes that voters may change their preferences. We illustrated how a voter may attempt to manipulate a Voting Center. We provided a set of algorithms to detect and exploit manipulation opportunities that would drive the Voting Center to declare an election outcome that is more beneficial to the manipulating voter. We experimentally showed that manipulation has only a slight impact on the outcome of an election when advanced elicitation schemes such as the one found in [Naamani-Dery et al., 2015] are used. The surprising finding of our experiments is that manipulation does not necessarily have a negative effect. In fact, for a Voting Center with random query generation, manipulation attempts speed-up the convergence process. Nonetheless, our manipulation detection algorithms allow us to build a Careful Voting Center that avoids manipulable queries. Our experiments show that a Careful Voting Center is effective. In the future, we would like to drill down and study cases with less than 50 voters, since our finding imply that these cases are more manipulation prone. We would like to investigate in what settings and which manipulation scenarios lead to a change in the elections outcome.