Convergence and Quality of Iterative Voting Under Non-Scoring Rules

1 Introduction

The topic of voting, that is, how to aggregate diverse individual preferences into a collective decision, is of great importance in many automated agent scenarios; it has thus been the topic of much research in multiagent systems. One innovative voting model that was proposed a few years ago is that of iterative voting [Meir et al., 2010]. Whereas classic voting rules usually consist of a single round of ballot submission and announcement of the winner, in iterative voting there can be many such rounds. After each iteration, voters reassess the outcome, and if any voter wishes to change their vote they may do so, and potentially a new winner replaces the previous one (when multiple such voters exist, an arbitrary voter is chosen according to some tie-breaking procedure). The process terminates when no voter wishes to change their vote.

Iterative voting thus embraces the inevitable manipulability of voting shown in the Gibbard-Satterthwaite theorem [Satterthwaite, 1975; Gibbard, 1973], and considers agents' uniform ability to vote strategically as a collective opportunity.

Besides being an intriguing method for reaching consensus, iterative voting has been proposed as a formal solution Jeffrey S. Rosenschein Hebrew University of Jerusalem jeff@cs.huji.ac.il concept for voting settings. Standard Nash equilibria are of limited usefulness in voting games, since they encompass situations that are unlikely to ever happen (e.g., all voters vote for their least favorite candidate). The set of iterative voting equilibria, however, is a subset of Nash equilibria, and in particular those iterative voting equilibria reachable from the truthful profile could be considered a more natural (or meaningful) solution concept.

The most salient questions regarding iterative voting thus have two interpretations. Regarding iterative voting as a method for reaching an outcome, we ask whether the process terminates; if so, with what complexity; and does it arrive at "good" outcomes. Regarding iterative voting as a solution concept, we must explore the existence of solutions; the equilibria computation; and notions of price of stability/anarchy.

Most previous research on iterative voting has focused on plurality, with several extensions to other scoring rules, focusing on best-response dynamics in which each voter calculated the optimal step to take at each stage. In this work, however, we explore two different-but connected-issues that have not received much attention so far:

Non-scoring Rules We look into iterative voting in previously less explored voting rules that are not scoring rules-Maximin, Copeland, Bucklin, STV, Second Order Copeland (SOC), and Ranked Pairs.

Dynamics Since many of the voting rules are NP-hard to manipulate, finding the best response is often a hard problem for players. Therefore we examine some heuristics a candidate might use for the dynamics; while not necessarily in P, they all define a much narrower search space (rankings to consider) than best-response dynamics.

While the issue of convergence in each case is proven, in order to examine the properties of the various dynamics and their outcomes, and to assess their behavior, we turn to an empirical approach. We show how some properties are heavily dependent on the voting rule, while others are significantly affected by the iterative dynamic used.

2 Related Literature

There has been extensive research on solution concepts of voting games, and an overview of the research can be seen in [Meir et al., 2014].

Our model of iterative voting was initiated by [Meir et al., 2010], who showed that plurality voting converges under a natural restricted best-response dynamic and linear ordered tie-breaking (a dynamic refined in [Meir, 2015]). [Lev and Rosenschein, 2012] (and in parallel [Reyhani and Wilson, 2012]) later showed that veto, with a similarly natural restricted best-response dynamic, also converges. However, in negative results for best-response dynamics, [Lev and Rosenschein, 2016] showed that no other scoring rules converge, [Obraztsova et al., 2015c] showed that Maximin does not converge, [Gourv`es et al., 2016] showed that STV 1 does not converge (in parallel with the publication of this work [Koolyk et al., 2016b]), and for Copeland, [Reijngoud and Endriss, 2012] showed that best-response does not converge. 2 More recently, [Obraztsova et al., 2015b] began exploring the topic of non-myopic iterative voting, focusing on plurality and veto.

[Reijngoud and Endriss, 2012] added an epistemic element by varying the amount of information revealed at each stage, and also showed that any scoring rule converges under the k-pragmatism dynamic. [Grandi et al., 2013] showed that, for two additional restrictive dynamics, scoring rules (as well as Copeland and Maximin), converge, and [Loreggia, 2012] added another very restrictive dynamic, showing that Copeland and Maximin converge under it. [Obraztsova et al., 2015c] abstracted these ideas and put forth two theoretical properties that suffice to guarantee convergence. Not in connection to iterative voting, [Obraztsova and Elkind, 2012] proposed several dynamics, of which we adopt, for example, the Kendall-Tau dynamic. [Brˆanzei et al., 2013] examined the quality of iterative voting, via the notion of the dynamic price of anarchy. They showed lower bounds for plurality, veto, and Borda, and a tight upper bound for plurality.

In parallel, other extensions of iterative voting included [Meir et al., 2014; Meir, 2015], which showed that a generalization of iterative voting, where voters act under uncertainty, also converges for plurality. [Rabinovich et al., 2015; Obraztsova et al., 2015a] considered questions of computational complexity related to iterative voting, with and without assumptions about "truth bias" and "lazy bias" on the part of voters. Recently, [Meir, 2016] generalized the various concepts involved in iterative voting, but we shall use the ones commonly used in iterative voting research.

Additional work on the quality of iterative voting includes that of [Meir et al., 2014; Reijngoud and Endriss, 2012; Grandi et al., 2013] who showed through simulations some improvements in the outcome of elections, in their various versions of iterative voting. However, the closest work in its pattern of simulations and quality measures is [Thompson et al., 2013], which analyzed truth-biased equilibria, without any assumption regarding their dynamics.

Software-wise, we extend the iterative voting simulation framework of [Meir et al., 2014], 3 to new voting rules and dynamics, and will publish our code there.

1 Their example works for SWAP and KT dynamics, too.

2 Their example works for TOP, KT, and SWAP as well; TOP was also shown by [Obraztsova et al., 2015c].

3 http://www.preflib.org/tools/ivs.php

3 Preliminaries

Our setting will be the standard voting model that includes a set of voters V, |V | = n, and a set of candidates C, |C| = m. Each voter i has a strict preference order ≻i over C, that is, a complete, transitive, and antisymmetric binary relation over C. Denote the set of all such preference orders as π(C). A profile

is a vector of n preference orders, one for each voter. We denote by

the profile of the voters excluding i and (⃗≻-i,≻i) = ⃗≻. We shall denote the truthful preferences of voters as ⃗ tr = (≻tr 1 , . . . , ≻tr n ).

We model a collective decision through one of two functions. A social welfare function is a function f : π(C)n → π(C)\{∅} and a voting rule is a function F : π(C)n → 2C \{∅}. So, given a (not necessarily truthful) vector of preferences, a social welfare function chooses a preference order and a voting rule chooses a set of candidates. When a voting rule is irresolute, and we would like a unique winner, we use a tie breaking rule, a function t : 2C → C. A linear-ordered tie breaking rule is a rule that breaks ties according to a fixed linear order. It will be assumed without loss of generality throughout this paper that the linear-ordered tie breaking rule is the lexicographic tie breaking rule, where ties are broken according to the lexicographic order of candidates' names.

3.1 Voting Rules

For each pair of candidates c1, c2 let P(c1, c2) = |{x ∈ V |c1 ≻x c2}|. We investigate the following voting rules:

Maximin For each candidate c, let sc(c) = min c′ ̸=c∈CP (c, c′ ).

The candidates with the maximum score, arg max c∈C sc(c),

win.

Copelandα For α ∈ [-1, 1], let sc(c) = |{c′ |P(c, c′ ) > n/2}| - |{c′ |P(c, c′ ) < n/2}| + α · |{c′ |P(c, c′ ) = n/2}|, and the candidates with the maximum score, arg max c∈C sc(c), win. (Generally α = 0 is assumed.)

Bucklin For each c ∈ C, let

sc(c) = mink<m |{x ∈ V |∃c1 ̸= c2 ̸= . . . cm-k s.t. ∀cj ∈ {c1, . . . , cm-k}c ≻x cj}| > n/2 The winner is the candidate with the smallest score, arg min c∈C sc(c).

STV Under Single Transferable Voting (STV), the election proceeds in rounds. In each round, the candidate with the lowest plurality score is eliminated and any voter voting for them transfers their vote to their next ranked candidate. The last remaining candidate is the winner.

SOC Second Order Copeland (SOC) chooses winners as in Copeland, except that ties are broken according to the score of defeated candidates. If sc(c) is the Copeland score of c, then Second Order Copeland chooses c ∈ arg max c∈C sc(c) s.t. ∑ sc(c′ ) c′ :P (c,c′ )>n/2 is maximal.

Ranked Pairs (RP) Let

be the sorted list of pairs of candidates' P-score such that

iff ij,1 < ij+1,1 or ij,1 = ij+1,1 and ij,2 < ij+1,2; i.e., break ties in order lexicographically (first candidate, second candidate). A ranking is constructed by the following algorithm. For j=0 to (m2 ) fix cij,1 ≻ cij,2 unless this contradicts a previous step (including by transitivity). The candidate at the top of the constructed ranking is selected as the winner.

An interesting property of which we will make use regards the Condorcet winner. A Condorcet winner is a candidate who is preferred to each other candidate by more than half of the voters; however, such a winner does not always exist. A voting rule is Condorcet consistent if whenever there is such a Condorcet winner, it is the election's outcome. Among the voting rules we discuss, Maximin, Copeland, SOC and Ranked Pairs are Condorcet consistent, while Bucklin and STV are not. See [Brandt et al., 2016] for more information.

3.2 Dynamics

We will call a binary relation D ⊂ π(C)n × π(C)n a dynamic. We call a (possibly finite) sequence of profiles (⃗≻1, ⃗≻2, ...) ∈ π(C)∗ a profile sequence and a (possibly finite) sequence of voters (v1, v2, ...) ∈ V ∗ a voter sequence. A profile sequence (⃗≻1, ⃗≻2, ...) for which ⃗≻1 are the truthful preferences, is called an initially truthful profile sequence.

We will say a profile sequence is valid for a dynamic D if ∀i(⃗≻i, ⃗≻i+1) ∈ D. We will mainly be concerned with dynamics for which all elements differ in a single preference, i.e.,

In such a case, a profile sequence induces a voter sequence (v1, v2, ...) where vi is the voter whose preference changed at stage i. Likewise, a voter sequence defines a set of profile sequences by which it is induced. A voter sequence will be called valid if it is induced by some valid profile sequence.

The final element of a (finite) valid profile sequence (⃗≻1, ⃗≻2, ..., ⃗≻k) will be called an equilibrium if there is no ⃗≻k′ such that (⃗≻k, ⃗≻k′) ∈ D.

For a dynamic D and voting rule F with tie breaking rule t, let I(D, Ft) = {s|s is a valid profile sequence for D(Ft)}. We will say that iterative-F converges under D if every element of I(D, Ft) is finite. Otherwise, we will say that iterative-F under D cycles or does not converge (or may not converge). Notice that, as defined, the semantics of convergence are asynchronous, so I(D, Ft) converges if every element is finite, and is not limited to, say, a "fair schedule of play" (this is termed FDBRP in the terminology of [Meir, 2016]). Also, following the existing literature, we consider only cases where the "scheduler" selects a single agent to make a move at each point, and not several agents in parallel.

The dynamics we shall consider will be influenced by the truthful preferences, i.e., a dynamic in which a voter's vote changed must have increased the utility of that vote. Two main dynamics have been investigated (e.g., in [Meir et al., 2010]). An ordered pair of profiles is in the better response dynamic if the preferences of all voters but one are identical in the two profiles, and the voter whose preference changes prefers the outcome of the second profile to that of the first profile. In game-theoretic terms, any time a single player can make a better response to a given state, such a move is included in the dynamic. Formally, for two profiles ⃗≻(1) , ⃗≻(2) and a voting rule F, (⃗≻(1) , ⃗≻(2) ) ∈ BetterResponse iff:

Such an i is called the manipulator, ≻(2) i is called the new vote, and ≻(1) i is called the old vote. Notice that a stable state under this dynamic is a Nash equilibrium.

Similarly, an ordered pair of profiles is in the best response (BR) dynamic if the preferences of all voters but one are identical; the voter whose preference changes prefers the outcome of the second profile to that of the first profile (so it is contained in the better response dynamic); and of all possible changes to his preferences, the outcome under the second profile is preferred at least as much as the outcome under any

other possible profile. Formally, (⃗≻(1) , ⃗≻(2) ) ∈ BR iff:

and

The above description clearly defines a game form. The set of voters is the set of players, the set of preferences is the set of strategies available to each player, and the voting rule determines the outcome of a strategy profile. Ordinal utilities are given by true preference orders. An equilibrium under Best Response (or Better Response) is a Nash equilibrium.

4 Dynamics

The study of best response dynamics is prolific, but in the iterative voting context, particular forms of best response (as BR is not necessarily unique) have been utilized in the convergence proofs of both plurality [Meir et al., 2010] and veto [Lev and Rosenschein, 2012]. For non-scoring rules, however, there is no immediately clear choice of best response form (indeed, in some cases, like STV, it is NP-complete to calculate what it is). We present here several dynamics that may serve as natural heuristics for a potential voter. There have been dynamics designed with the express purpose of ensuring convergence, as in k-pragmatism, M1, and M2 [Reijngoud and Endriss, 2012; Grandi et al., 2013]. However, we propose the following dynamics as more natural correspondences to the strategic behavior of self-interested agents.

TOP: This dynamic assigns the candidate which the voter wishes to make a winner the top spot in the new preference order. 4 In many of the voting rules we consider (and any weaklymonotone rule) this dynamic is a subset of the best-response dynamic (i.e., TOP(π(C)) ⊂ BR(π(C))), and, indeed, it generalizes the dynamic used in [Meir et al., 2010].

4 The ordering of the remaining candidates can be arbitrary.

TB: This dynamic requires the new winner to be at the top of the new ballot, and the previous winner to be at the bottom. 4 While in many scoring rules (e.g., plurality and veto) this is a subset of best response moves (generalizing those used in [Lev and Rosenschein, 2012]), this is not true in general, and particularly in the voting rules we study in this work.

KT: This dynamic restricts best response to those with minimum Kendall-Tau distance from the previous vote. That is, among all possible moves whose outcome will be the most preferred possible candidate, one with the minimal KendallTau distance 5 from the current vote is chosen.

SWAP: This dynamic, inspired in part by notions from the literature on bribery (see, e.g., [Elkind et al., 2009; Bredereck et al., 2014]), is quite restrictive. It restricts manipulations to a single adjacent swap (called a 'shift' in the bribery literature), that is, changing to a vote within KendallTau distance of one from the current vote (a 'swap' in the bribery nomenclature).

5 Convergence

In this section we consider the convergence of iterative voting for several voting rules. We distinguish between the first three, for which there exists a polynomial time algorithm for a single voter to compute a best response manipulation, and the last three for which such a computation is NP-Complete [Bartholdi III et al., 1989; Bartholdi III and Orlin, 1991; Xia et al., 2009]. In reversal of the common situation in computational social choice, for iterative voting polynomial manipulation is actually quite felicitous.

A note on reading the examples that follow: each column represents a profile of submitted ballots (beginning with the truthful one). The final row in the column indicates the winner of the profile (after ties are broken). The i-th row in a column represents voter i's submitted preferences, where, for example, ABC is to be read A ≻i B ≻i C. Arrows highlight the changed preference between two profiles at a given stage. The profile sequence formed by continual repetition of the indicated profiles thus forms an infinite element of I(D, Ft) and proves non-convergence. Due to space constraints, we omit several proofs (see [Koolyk et al., 2016a]).

5.1 Maximin

Similar to plurality and veto, Maximin changes gradually. That is the difference in score between the previous winner and the new one, when a single voter manipulates, can go up or down by at most one point. One might thus expect there to be an argument for convergence, similar to plurality/veto. But in fact, convergence with Maximin turns out to be elusive even after major restrictions on the admissible moves.

Theorem 1. Maximin with linear order tie-breaking does not converge for the dynamics BR, TOP, TB, KT, and SWAP.

5 For a, b ∈ π(C), the Kendall-Tau distance between them is defined as dist(a, b) = |{i, j} ∈ C×C|(i ≻a j and j ≻b i) or (j ≻a i and i ≻b j)}|.

Proof. We only include the example for BR:

Although the changes to the winner's score are as gradual in Maximin as in plurality and veto, the exponential blowup in strategy space seems to make convergence harder. Whereas in plurality and veto, a voter's ballot reduces to a single candidate, in Maximin a ballot depends on the entire ranking.

5.2 Copeland

Theorem 2. Copeland with linear order tie-breaking does not converge for the dynamics BR, TOP, TB, KT, and SWAP. This holds for Copelandα for any α.

Proof. Since the number of voters in all our examples is odd, they hold for Copelandα for any α. We will only show the example for the TOP dynamic:

5.3 Bucklin

Theorem 3. Bucklin with linear order tie-breaking does not converge for the dynamics BR, TOP, TB, KT, and SWAP.

5.4 STV

Theorem 4. STV with linear order tie-breaking does not converge for the dynamics BR, TOP, TB, KT, and SWAP.

Proof. We will only show the example for the KT dynamic.

5.5 Second Order Copeland

Theorem 5. SOC with linear order tie-breaking does not converge for the dynamics BR, TOP, TB, KT, and SWAP.

5.6 Ranked Pairs

In Ranked Pairs, as in other rules that output a complete ranking, a stronger convergence property could be defined for the entire ranking, but convergence is elusive even for the top element of the ranking (the winner of Ranked Pairs).

Theorem 6. Ranked pairs with linear order tie-breaking does not converge for the dynamics BR, TOP, TB, KT, and SWAP.

6 Empirical Analysis

In order to analyze the qualitative effects on outcome of iterative voting, we turn to empirical simulations. What makes one outcome better than another is a subtle question as there is no agreed-upon measure of quality. Furthermore, voting rules are defined with different goals in mind. For example, Maximin ensures that the core number of supporters a candidate has, against any other, is maximal (an objective not shared by other rules).

As we wish to see general properties of the interaction of voting rules and dynamics, we focused on a particular setting: 10 voters and 4 candidates. Profiles are generated by either sampling from a uniform distribution or a single-peaked one. For each voting rule, response dynamic, and distribution we sample 1000 different games, and because of the nondeterministic nature of iterative voting each of these games is repeated 100 times, each time with a different order of voter responses. Thus for each pair of game and dynamic we have up to 200,000 different executions. Iterative voting is executed until an equilibrium is reached, a cycle is detected, or some maximum number of iterations have elapsed. Though many sampled profiles start in equilibrium, we are interested in the effects of the iterative process, and focus on profiles where iterative voting occurred.

For both our voting rules and response dynamics, ties are broken in a deterministic fashion. In the case of a tie in a voting rule, out of all the potential winning candidates the lexicographical first is selected. For response dynamics that encounter ties, the first profile that was discovered is chosen.

One may ask why bother with iterative voting simulations, considering we have just shown they are not guaranteed to converge. However, despite these proofs, we did not encounter a single cycle in our millions of simulations (fewer than 6000 runs were stopped after reaching the cut-off number of 10,000 steps, and may have turned out to be cycles, but that still is a very low share). This indicates the relevance of examining iterative voting properties, even for voting rules that are not guaranteed to converge.

6.1 The Truthful Winner

While there is no guarantee that the truthful winners will emerge as the overall winners from iterative voting, it is often the case that they do (albeit in a non-truthful profile). As truthful winners are, in a sense, what the mechanism designers wanted the voting method to achieve, it is desirable that using iterative voting, they will be the rule's outcome.

Approximately 78% of all sampled truthful profiles were an equilibrium (with single-peaked profiles almost 20% more likely to be an equilibrium than uniform profiles). Unsurprisingly, the more restrictive response dynamics had a higher ratio of truthful profile equilibrium. Hence, best response and Kendall-Tau had fewer truthful equilibria than SWAP. A similar disparity in the fraction of truthful profile equilibria is seen when examining the voting rules: the Condorcet consistent rules, Maximin, Copeland, etc., were more often initially in equilibrium than the non-Condorcet consistent rules, STV and Bucklin. Since the initial profiles are truthful, the Condorcet consistent rules will initially pick the Condorcet winner, if one exists. Moreover, as will be noted below, because of the Condorcet winner's appeal over each of the other candidates, it is less likely that iterative voting would lead to a "better" winner (for some metrics detailed below).

When iterative voting does occur, there does not appear to be a relation between how often the truthful winner emerges and the response dynamic. Instead the voting rule seems to be the more significant factor in determining how likely it is for the truthful winner to be chosen. For any dynamic and preference type none of the non-Condorcet consistent rules selected the truthful winner more than 45% of the time (all but one selected the truthful winner less than 40% of the time). However we will show they are likely to improve, in some regard, on their truthful winner, due to the iterative dynamic. On the other hand, Copeland, under any dynamic and preference type, selected it at least 55% of the time. More generally, except for Maximin with single-peaked preferences, Condorcet consistent rules select the truthful winner over 50% of the time under any combination of dynamic and profile type.

6.2 Convergence to Equilibrium

In games in which iterative voting did take place, most dynamic and voting rule combinations converged, on average, within 10 steps, and except for SOC, reached fewer than 15 overall equilibria states. In general, while each voting rule is different, we mainly noticed significant differences between the dynamics. When using the KT dynamic, the pace to convergence was significantly longer than other dynamics in all voting rules except Bucklin (and for SOC, with uniform distribution, KT along with BR took far longer to converge than the rest). With KT for all rules, except Bucklin, the number of different equilibrium states reached was significantly higher. See Figure 1. For example, Copeland with KT averaged more than 25 steps to convergence with single-peaked preferences (and over 10 steps with uniform). Almost all cases of runs that had to be cut-off after 10,000 steps were the KT dynamic (for Copeland, just under 800 runs).

KT's behavior might be a bit surprising, since it is, fundamentally, a best response dynamic with a different tiebreaking rule-favoring votes close to one another (instead of lexicographic, pre-determined ordering). It would seem that for most voting rules, bias towards smaller, more local, changes when manipulating has a significant adverse effect on the convergence properties of the iterative game. 6

A somewhat connected issue is the difference between SOC and Copeland, which differ in their tie-breaking rules. Unlike Copeland (which only had this with KT), all SOC dynamics had cases that did not converge after 10,000 steps (single-peaked struggled more than uniform ones).

This subtlety with tie breaking can be hard to pinpoint. With many voting rules, especially non-scoring ones, how a profile is set up in the short term can have a substantial impact in the long term. What may seem like an optimal move now may make certain candidates currently ranked lower more viable down the line. With more complex tie breaking rules, in addition to optimizing for the current winner, there is now a secondary tie breaking condition that may not be explicitly optimized against, but that can come into play in the long term. Candidates that would be vanquished under a predetermined tie breaking procedure could be lifted up by these more fluid rules and continue to compete in the long run, greatly affecting the convergence properties.

6.3 Voter Utility

While the social welfare of the voters would be a compelling measure of the quality of an outcome, we, naturally, do not have access to the voters' utility functions. However, as has been suggested in previous research [Thompson et al., 2013; Meir et al., 2014], we can use the Borda score on the truthful preferences as a proxy for utility. Here the utility for each voter of a chosen candidate c ∈ C which the voter ranks in place i is m-i. The Borda score for a set of voters is the sum of the individual utilities. We study how iterative voting affects the Borda score of the winning candidate (see Figure 2).

Generally, the effect of dynamics on the Borda score of winners seems minimal. STV consistently showed significant improvements to the Borda scores under iterative voting (with single-peaked preferences doubling this effect). 7 This effect was much less pronounced with Bucklin, although singlepeaked again had a larger improvement. But with Maximin, winners' Borda scores went down more often than not, and again the effect was more pronounced under single-peaked preferences. Since Copeland frequently had the truthful winner emerge, its Borda scores were largely unchanged (especially under single-peaked preferences). It seems that when a Condorcet winner exists, Condorcet-consistent rules are less likely to find with iterative voting a candidate with higher Borda scores. Intuitively, this is because Condorcet winners commonly have a high Borda score, so it is harder to improve on the Borda score of the winner in these rules.

6 Conversely, TB influences most voting rules towards a faster and more focused, fewer equilibrium states, convergence.

7 It has a very high rate of selecting the Condorcet winner.

7 Conclusion and Discussion

In this work we have continued the exploration of iterative voting. We have done so in two dimensions. In the first, we expanded the set of dynamics to include some that reflect strategic behavior, but restrict best response in a natural way (to a certain extent)-whether by constraining the placement of affected candidates, or by prioritizing small ballot changes. In the second dimension, we have ventured beyond scoring rules, and have shown that for a variety of common nonscoring rules, iterative voting under best response dynamics does not always converge. Even after restricting the dynamics to allow voters only limited changes to their ballots, they still do not always converge.

On the other hand, we have shown empirically that cycles seem to occur infrequently with all of these rules. Furthermore, we observed the effects that iterative voting has on the election outcome, and seen how in many voting rules (e.g., STV) winners are mostly candidates with desirable properties (truthful, Condorcet, or high Borda score). We are also able to better elucidate the effect of dynamics on the outcome, and while their effect on the eventual winner is not extremely significant, it is highly impactful on the convergence speed, and how many equilibrium states are encountered.

Continuation of this line of work would include analysis of convergence conditions for more voting rules and dynamics, finding either convergence dynamics or broader impossibility results. The empirical aspect of this work would benefit from expanding the analysis, for example by analyzing more distributions (e.g., the Mallows model). Moreover, exploring the heuristic dynamics people use in the real world may help us to understand the eventual outcomes in iterative voting, and the properties of the equilibria, reached in realistic settings.

Acknowledgements

This research has been partly funded by the HUJI Cyber Security Research Center in conjunction with the Israel National Cyber Bureau in the Prime Minister's Office, by Israel Science Foundation grant #1227/12, and by NSERC grant 482671.