# iterative_calculus_of_voting_under_plurality__9013d984.pdf

Iterative Calculus of Voting Under Plurality

Fabricio Vasselai University of Michigan - Ann Arbor, MI, USA vasselai@umich.edu

We formalize a voting model for plurality elections that combines Iterative Voting and Calculus of Voting. Each iteration, autonomous agents simultaneously maximize the utility they expect from candidates. Agents are aware of neither other individuals preferences or choices, nor of the distribution of preferences. They know only of candidates latest vote shares and with that calculate expected rewards from each candidate, considering the probability that voting for each would alter the election. We define the general form of those pivotal probabilities, then derive efficient exact and approximated calculations. Lastly, we prove formally the model converges with asymptotically large electorates and show via simulations that it nearly always converges even with very few agents.

Introduction In many multi-agent systems, agents with diverse preferences have to settle on a single choice or course of action - a challenge often solved by voting. Yet, it is known from the Gibbard-Satterthwaite theorem that if there are more than two alternatives and no one can dictate the result, intelligent agents best response may differ from their sincere preference (Gibbard 1973; Satterthwaite 1975). While, traditionally, the Computational Social Choice literature has treated such a misrepresentation of preferences as a manipulation to be prevented or diminished (see Bartholdi, Tovey, and Trick 1989; Conitzer, Sandholdm, and Lang 2007), in the last decade a new view has emerged. Desmedt and Elkind (2010) deemed such a strategic voting an unavoidable attribute of an electoral system with rational voters (p.347). Crucially, Meir et. al. s (2010) Iterative Voting (IV) allowed agents with ordinal preferences to sequentially and deterministically re-evaluate their choices over iterations, after learning the most current election score. Conversely, analytical Game-Theory has embraced strategic voting for decades, but with works focusing on the exact opposite. They usually investigate solution concepts of non-atomic games where players know the distribution of voter types and decide their optimal vote simultaneously in a single one-shot iteration (for a review, see Meir 2018). In its most renowned approach, the Calculus of Voting (CV) model inaugurated by Riker and Ordeshook (1968), each

Copyright 2022, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

agent maximizes its expected reward via weighting candidates cardinal utility differences by the probability that voting for a candidate would be pivotal to determine the election result (see Palfrey 1988; Myerson and Weber 1993). Here we formally derive the Iterative Calculus of Voting (ICV), a voting model that joins main aspects of IV and CV. Agents re-evaluate their choices over multiple iterations, like in IV, but each time doing a simultaneous expected reward optimization, like in CV. This is naturally akin to growing applications based on simulating CV in discrete-time (e.g. Clough 2007; Tsang and Larson 2016; Fairstein et al. 2019). ICV encompasses those and aims at offering a rigorously formalized and more general framework. Additionally, ICV deals with how to transition CV assumptions to an iterated setting, it is defined for both small and large electorates and it jointly addresses limitations of both CV and IV. More specifically, ICV can be described as follows. In each iteration, agents learn only candidates latest vote shares and use those to estimate the probability that currently voting for each candidate would alter the election outcome. Agents use those pivotal probabilities to weight the utility differences they see between candidates and then update their choices. Therefore, similarly to IV and CV, agents are unaware of each other s preferences or individual choices. However, like in IV and differently from most CV, agents are even unaware of the distribution of preferences. Also, like in CV but differently from most IV, agents update simultaneously in electorates that can be reasonably small or arbitrarily large. Finally, ICV agents require low information and are boundedly rational in the strategic sense.1

After deriving several generalizations and novel pivotal probability calculations - exact and heuristics - convergence properties of ICV under plurality are studied in two ways. In non-atomic ICV games of standard characteristics and pivotal probabilities, we prove that convergence always results, as well as the bounds on convergence rates. Also, we show that similarly to CV, under weak assumptions ICV usually converges to only two candidates receiving positive vote counts, which is known as Duvergerian equilibria (Palfrey 1988; Meir 2018). In atomic ICV games, while the exis-

1Like in CV, they must be computationally sophisticated enough to estimate their probabilities of being pivotal. As will be discussed, conceptually principled heuristics can be developed.

The Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI-22)

tence of cycles cannot be theoretically excluded, we argue why, under reasonable specifications, they will be rare. We also show through simulations that empirically, convergence is nearly always achieved even with small electorates.2

Related Work Meir et. al. s (2010) inaugural IV analyzes convergence to a Nash Equilibrium under plurality voting when agents are allowed to iteratively re-evaluate their choices in light of the current election outcome. Working with ordinal candidate utilities, they show that convergence is only guaranteed if agents update sequentially and under linear ordered tiebreaking rules. Similar convergence properties were shown to apply to veto rule (Lev and Rosenschein 2012), but no convergence is guaranteed under any other scoring rule (Lev and Rosenschein 2016), nor under Single-Transferable Vote (Koolyk et al. 2017). On the other hand, it was shown that convergence under plurality holds even if IV agents operate under uncertainty (Meir, Lev, and Rosenschein 2014) and are boundedly rationally using heuristics (Meir 2015). Furthermore, nearly all work on IV focus on atomic games. Meir et.al. (2010) already pointed that their original model was particularly suited for small electorates and that an analysis in the spirit of Myerson and Weber (1993) - i.e. of the CV - would be more suitable when the number of voters increases (p.828). As a consequence, the subsequent IV literature also focused mostly on sequential agent updates, since it is rarely possible to guarantee that atomic games with simultaneous updating will be free of cycles (Fabrikant, Jaggard, and Schapira 2013). An exception is Meir (2015), where a deterministic model is proposed that allows simultaneous updates in large electorates. Meir says his model is like Myerson and Weber s (1993) plurality CV, without probabilities (and requiring ordinal utilities) - yet it could not be immediately generalized beyond plurality. CV has been extensively generalized and is defined for non-atomic electorates of cardinal utilities. In fact, due to its one-shot nature, its equilibrium conditions actually rely entirely on asymptotically large electorates and on agents knowing the distribution of preference orderings. While agents are unaware of other individuals preferences or choices just like in IV, Palfrey (1988) showed it is because they know the distribution of voter types that, simultaneously and at once, they choose an optimal strategic vote under plurality that leads to Duvergerian equilibria. Or, more generally, always to an equilibrium - under plurality, approval or Borda (Myerson and Weber 1993), SNTV (Cox 1994), PR (Cox and Shugart 1996) or Runoff (Bouton 2013). Of course, that information requirement is as unrealistic in human elections (Myatt 2007) as it is limiting in practical AI applications. But without it, Meir (2018, p.86) s assertion about CV becomes irreproachable: it is not clear how [agents] are supposed to reach [equilibrium] in a game that is only played once without some means for coordination . Despite not satisfying those assumptions, applications implementing CV as computational simulations exist. Clough

2Online Appendix and all code necessary to replicate the paper can be found at https://github.com/vasselai/aaai22-icv-plurality.

(2007) uses a simplified simulation of CV to study the effects of information uncertainty on voter s strategic choices, while Tsang and Larson (2016) expand that to agents connected through networks. Fairstein et al. (2019) also employ a similar CV simulation, alongside others, to predict voting behavior observed in human online voting experiments. Being discrete-time simulations, they are allowed to have multiple time iterations, which approximates them to ICV. However, largely non-formalized, those applications do not explore the iterative aspect of vote re-evaluation and do not engage in much of the theoretical details required to bridge IV and CV. Moreover, they consider only the pivotal probability of breaking ties (not the probability of making ties) for first and disregard the possibility of multi-way ties - both approaches that only make sense with asymptotic electorates. ICV rigorously formalizes a general iterative CV model, thus encompassing those applications, and with a definition that includes all probabilities and considers multi-way ties3 - such that any electorate size is covered (Mc Kelvey and Ordeshook 1972; Hoffman 1982). Besides, ICV is defined such that the only information agents access each iteration are candidates latest vote shares (from past iteration), like in IV. For simplicity, those are assumed to be public information.4 Hence, differently from CV, in ICV eventual convergence is constructed by strategic choices made over multiple iterations. It neither relies on distributional assumptions nor requires agents aware of the distribution of preferences. Meir, Lev, and Rosenschein (2014) claim that another issue with CV models - one that would be inherited by ICV - lays in assuming agents capable of optimizing complex expected utility functions. We do not see that as a problem for general AI applications, where human-realism is not always the goal. Nonetheless, boundedly rational agents in the computational sense may be desired for computational efficiency (Zilberstein 2008) or for purely theoretical reasons (Conlisk 1996). As we will show, in ICV the comparison of utilities by agents amounts to a simple sum of weighted subtractions; all challenge is in calculating pivotal probabilities. This is why, since Black (1978), many heuristics have been proposed for CV pivotal probabilities of breaking two-way ties (Hoffman 1982; Cranor 1996; Myerson 1998; Smith, de Mesquita, and La Gatta 2016). Recently, Tsang, Salehi Abari, and Larson (2018) proposed sampling simplifications to Palfrey (1988) s Multinomial pivotal probabilities. We first define ICV pivotal probabilities under plurality generically. Next, we derive exact calculations for when electorate size is known (generalizing Palfrey 1988) or unknown - generalizing Myerson (1998) to multicandidate plurality through the novel Poisson pivotal probabilities. Then, we prove the Skellam pivotal probability approximation (generalizing a path explored e.g. by Smith, de Mesquita, and La Gatta 2016; Tsang, Salehi-Abari, and Larson 2018). With general framework and key pivotal probabilities defined for ICV, as well as conditions for convergence all laid out, our idea is to offer a benchmark through which other proper heuristics may be proposed and tested.

3For an exploration of the likelihood of ties, see Xia (2021). 4But could be defined as coming from polls, like in Fey (1997).

Model Definition Recapitulating, in each iteration of ICV, agents simultaneously maximize the rewards they expect from the election, with respect to their current vote choice. Knowing only of candidates latest vote shares, agents ponder the probability that voting for each candidate would alter the election outcome and use those probabilities as weights to calculate the expected rewards. In this section we formalize that. For consistency, whenever possible we follow the notation from the game theoretical CV literature. Like in IV, however, ICV games have multiple iterations, here indexed by δ N 0, where δ = 0 is the initial condition. Let i be the focal agent (hereafter, elector) on whom all derivations will focus, without loss of generality, and N N>1 be the number of electors. Their voting choices (hereafter, candidates) are represented by the set J , s.t. m = |J | N 3 is the number of candidates. Then, let vector n ,δ Nm 0 hold actual candidates vote counts in iteration δ and vector ni,δ Nm 0 hold candidates expected vote counts in δ in the eyes of elector i (hence random variables) not including i s vote - we discuss, later, how those are estimated. Finally, vector ui Qm [0,1] holds normalized cardinal utilities that i would accrue in case each candidate won.5 The final reward i gets from the election is represented by ui w, where w is the election winner - with ties resolved randomly:

Assumption 1. w is equiprobably randomly chosen from W J , nonempty set of candidates that end tied for first.

Not knowing future W, elector i cannot know final reward ui w. Instead, i can only estimate which ui w to currently expect in iteration δ, given i s current electoral choice in δ. Formally, this can be written as E[ui w|πi,δ], where πi,δ represents the electoral choice of i in δ. In general, the choice electors are faced with is to either abstain or to choose one of the candidates in J . Note, however, that like in CV models, rationality imposes that electors never vote for their sincerely least preferred candidate, since that can only lead to i s maximum regret (see Myerson and Weber 1993; Cox 1994). Therefore, if abstention is loosely represented by , then πi,δ J \ argmin h J (ui h). In other words, E[ui w|πi,δ = j] and E[ui w|πi,δ = ] are the utility elector i sees in whoever she currently thinks will win if, respectively, she were to vote for j or if she were to abstain. Hence, every iteration δ, i chooses the electoral choice πi,δ that maximizes E[ui w|πi,δ]. Importantly, while here we will work with full turnout only,6 considering abstention in the definition is important not only for generality, but because as we will discuss, calculating the final formula for E[ui w|πi,δ =j] E[ui w|πi,δ = ] turns out to be much easier than the one for E[ui w|πi,δ]. The reason those are, in the end, equivalent, is that i abstains iff

5We follow the usual game-theoretical assumption of strict preferences, so ui j = ui h, j, h J : j = h. 6Given the bounds on utilities chosen and assuming it never happens that all electors prefer a same single candidate, the condition for abstaining in Definition 1 is never achieved unless a cost to voting is introduced. For simplicity, here it is not, but elsewhere we explore a variation of this model where voting is costly.

E[ui w|πi,δ = ] E[ui w|πi,δ =j], j J . In summary, the electoral choice of elector i in iteration δ is defined as: Definition 1. Let J i = J \ argmin h J (ui h).

if Ei,δ j Ei,δ 0, j J i

argmax j J i (Ei,δ j Ei,δ ) otherwise

where Ei,δ j :=E[ui w|πi,δ = j] and Ei,δ :=E[ui w|πi,δ = ]

Now, to find the formula for Ei,δ j Ei,δ we start from partitioning E[ui w|πi,δ] into three exhaustive election scenarios. The first two correspond to when i believes it will be pivotal, i.e. when i voting for j instead of abstaining would make a difference to the election. The third is their complement. Under plurality, the two pivotal scenarios happen in the events when i s vote either creates or breaks a tie for first. Formally, Ai,δ j,T is the event that, in δ, in i s perception, candidates in the set T Sm 1 r=1 J \{j} r are the only tied for first and j is in second with one vote less than those in T (so a vote for j would create a tie for first). Bi,δ j,T is the event that, in δ, in i s perception, candidates in T and j are tied for first, with all others behind (so a vote for j would isolate j in first). To define that in detail, for convenience let K = J \ {j, T } be the set of remaining trailing candidates. Then: Definition 2. Ai,δ j,T := {ni,δ j = ni,δ t 1, ni,δ t > ni,δ k , ni,δ j ni,δ k } and Bi,δ j,T :={ni,δ j =ni,δ t , ni,δ t >ni,δ k , ni,δ j >ni,δ k }, t T , k K where T Sm 1 r=1 J \{j} r and K = J \ {j, T }.

The probabilities of those events happening, Pr(Ai,δ j,T ) and Pr(Bi,δ j,T ), are called pivotal probabilities. Representing them by αi,δ j,T and βi,δ j,T to shorten notation, we can finally partition E[ui w|πi] into the three scenarios. For a fixed T : Lemma 1. Elector i s expected reward from choice πi,δ is: E[ui w|πi,δ]=αi,δ j,T E[ui w|πi,δ, Ai,δ j,T ] + βi,δ j,T E[ui w|πi,δ, Bi,δ j,T ]

+ (1 αi,δ j,T βi,δ j,T )E[ui w|(Ai,δ j,T Bi,δ j,T ) ]

Proof. From cond. expect. and Definition 2. Note in event (Ai,δ j,T Bi,δ j,T ) , ui w is independent from πi,δ i, δ since election outcome W does not change regardless of i s vote.

Last term in Lemma 1 is hard to calculate because there is myriad possible non-pivotal scenarios. But since it is the same regardless of πi,δ, it gets canceled out in Ei,δ j Ei,δ , which is why working with that is easier. Other terms are easily defined (see Mc Kelvey and Ordeshook 1972). From Assumption 1 and Definition 2, and considering all possible T , we get an extension of Merrill s (1981) linear program: Proposition 1 (Expected reward in plurality voting).

Ei,δ j Ei,δ = X

αi,δ j,T |T | + βi,δ j,T

! P t T (ui j ui t) |T | + 1

Proof. See the regular Appendix at the end.

The only thing left to define is how to calculate the pivotal probabilities - which are, clearly, also the only that may vary per iteration δ. Next we discuss how they can be calculated.

Pivotal Probabilities Multiple authors have described pivotal probabilities, with rigorous definitions offered for probability of breaking twoway ties in special cases (e.g. Hoffman 1982; Palfrey 1988; Myerson 2000). Here we start by proposing a generic formalization required for what comes next. Note that throughout this section, the iteration superscript δ will be omitted for readability (except for the next paragraph where it is needed for definitions): Proposition 2 (General pivotal probs. in plurality voting).

αi j,T =Pr(Ai j,T ) := Pr( \

t T ni j = ni t 1 \

k K ni j ni k)

βi j,T = Pr(Bi j,T ) := Pr( \

t T ni j = ni t \

k K ni j > ni k)

Proof. Immediate from Definition 2, noting that in event Ai j,T , because ni t = ni j + 1, then ni j ni k guarantees ni t > ni k, t T , k K. Hence the latter are not considered to avoid double-counting. Analogous for Bi j,T , but then j cannot be tied with those in K, by definition of T .

For elector i, to calculate its pivotal probability regarding candidate j in iteration δ means to estimate the probability that the yet unknown current election state (in i s eyes), ni,δ, corresponds to an event where i s vote for j would alter the election. Still unaware of what the candidate vote shares will be in δ (since electors update simultaneously), elector i relies on the latest publicly known7 candidate vote shares (i.e. resulting from electors updates in δ 1)8, represented by the vector sδ Qm [0,1]. How electors use it to estimate pivotal probabilities depends on whether N is known or, if each elector i has a different guess N i N>1 about N , what they assume about it.

Known Electorate Size Consider that vote share is equivalent to the probability that an elector chosen at random voted for a given candidate. Then, following Palfrey (1988), pivotal probabilities in CV plurality elections can be calculated as functions of Multinomial distribution PMFs with parameters N 1 and s - provided that those are known (which here we assume is true). We generalize this for multi-candidate cases, like in Cox (1994); Fey (1997); Tsang and Larson (2016), but with both probabilities of breaking and making multi-way ties. Let Vα be the set of all possible ni that correspond to an election state where one more vote for j would create a tie with candidates in T . Similarly for Vβ in relation to breaking a tie with candidates in T . Note that Vα and Vβ do not vary, so we can drop the elector superscript i:

7If latest vote shares come from (unbiased) polls like in Fey (1997), it is assumed, of course, that elector i treats them as if they are the population vote shares. For an application with non-unique vote shares, coming from networks, see Tsang and Larson (2016). 8When δ = 0, sδ can be initialized in many ways. For instance, it can hold proportions of sincere votes each candidate would get in the absence of strategic voting (truthful initial condition). Or it can be simply randomized (random initial condition). While here we focus on the latter, results qualitatively hold with the former.

Definition 3. Constraining P hnh=N 1, from (2) we have:

Vα = n n: nt = nj+1 t T nj nk k K o

Vβ = n n: nt = nj t T nj > nk k K o (3)

Proposition 3 (Multinomial piv. probs. in plurality voting). i, i ,αi j,T = αi j,T = αj,T and βi j,T = βi j,T = βj,T , s.t.:

(N 1)! n1!n2!...nm!

h=1 (sh)nh (4)

and same for βj,T , just summing over all n Vβ instead.

Proof. Consider any n Vα. Unaware of others votes, in the eyes of i that election state is a collection of other N 1 stochastic decisions over m possible options whose probabilities are given by s. That experiment follows a Multinomial distribution with support n and number of trials N 1. Then, αj,T is the convolution of the Multinomial PMFs of every pivotal state n Vα, same for βj,T and n Vβ. Finally, note that since Vα, Vβ, m, N and s are the same for all electors, αi j,T =αi j,T and βi j,T =βi j,T , i, i .

Clearly, (4) scales poorly - each pair αj,T , βj,T taking O m(|Vα|+|Vβ|) (see regular Appendix for the equation for |Vα| and |Vβ|). That can be ameliorated by memoizing expensive terms, but another critical computational cost is that of merely finding Vα and Vβ. The naive approach is to find the m-fold cartesian product 0, 1, . . . , N m and drop subvectors that do not follow conditions in (3). Algorithm 1 decreases the problem by realizing that for each fictitious vote of the focal candidate, those tied for first rank can only have same or one extra vote, which limits the max and total votes others can have (see Online Appendix for details).

Algorithm 1: Listing pivotal outcomes Vα and Vβ

1: function LISTPIVOTALOUTCOMES(N , J , T ) 2: Vα, Vβ 3: for x 0 to (N 1)/(|T | + 1) do 4: A 0, . . . , x N |T | 1 cartesian power 5: B 6: for all a A do 7: append a to B if max(a) < x 8: end for 9: y x + 1 |T | x : concatenation 10: z x |T |+1

11: for all n y A do 12: append n to Vα if sum(n) = N 1 13: end for 14: for all n z B do 15: append n to Vβ if sum(n) = N 1 16: end for 17: end for 18: return Vα, Vβ

19: end function

Unknown Electorate Size Consider now that electors do not know the electorate size, which happens in many applications, from voting in online forums to any larger electorate. Then, following Myerson (1998) it can be assumed that unknown N comes from a Poisson distribution with mean λ. In which case, Myerson proved that players guesses about total number of players would be random variables coming from same distribution:9

Lemma 2. i, N i Pois(λ) iff N Pois(λ). From environmental equivalence, Theorem 2 in Myerson (1998).

Then in any iteration δ, candidates expected votes n j are also distributed Poisson with mean equal to λ times the probability a voter chosen at random votes for that candidate:

Lemma 3. n j Pois(sjλ), j J . From Poisson decomposition property (see Myerson 2000).

Furthermore, candidates expected votes are then Poisson random variables independent from each other:

Lemma 4. n j n h, j, h J : j = h. From independent action property, Theorem 1 in Myerson (1998).

With that, Myerson (2000) showed the pivotal probability of breaking a tie in two-candidate plurality to be equivalent to the probability mass function of a Skellam distribution evaluated at zero (Smith, de Mesquita, and La Gatta 2016). After all, the subtraction of two Poisson random variables results in a Skellam: if T = {h} and K = , because n j n h Skellam(sjλ, shλ), then βi j,T = f S(0, sjλ, shλ). Yet, this does not extend naturally to more general scenarios. Recent work have suggested approximations to generalize that Skellam treatment to multi-candidate cases with twoway ties, based on arbitrary and more-or-less defined simplifying assumptions (Tsang, Salehi-Abari, and Larson 2018; Mebane, Vasselai, and Baltz 2019). However, properties of those approximations have not been studied yet, it is unclear how good they are, what their quality depends on or whether they are computationally worth it. So instead, we now prove the exact generalization of Myerson s pivotal probabilities - to breaking or making multi-way ties, in multi-candidate plurality - which we call Poisson pivotal probabilities.

Proposition 4 (Poisson pivotal probs. in plurality voting). i, i ,αi j,T = αi j,T = αj,T and βi j,T = βi j,T = βj,T , s.t.:

f P (d, sjλ) Y

t T f P (d+1, stλ) Y

k K FP (d, skλ)

f P (d, sjλ) Y

t T f P (d, stλ) Y

k K FP (d 1, skλ) (5)

where f P and FP are Poisson distributions PMF and CDF.

Proof. Since ni j is part of all intersecting events in (2), by Lemma 4 conditioning on ni j makes the events independent:

Pr(ni j =d) Q

t T Pr(ni t =d+1) Q

k K Pr(ni k d)

9Hence λ = N means electors on average guess N correctly.

Algorithm 2: Joint calculation of Poisson pivotal probs.

1: function POISSONPIVOTALPR(j, T , K, s,λ, maxd)

2: ϵ Q|s| [0,1] vector with exp( shλ) h=1 . . . |s|

3: κ Q|K| [0,1] zero vector of length |K|

4: τ Q|T | [0,1] vector with ϵt t T 5: a, b ϵj 6: α, β, α , β , d 0 7: q 1 8: while (α =α orβ =β ord=0) and d < maxd do 9: a b 10: b b sjλ (d+1) 11: for all t T , r = 1 . . . |T | do 12: τr τr stλ (d+1) 13: end for 14: for all k K, r = 1 . . . |K| do

15: κr κr + ϵk (skλ)d

q 16: end for 17: α α 18: β β 19: z Q t T (τt) Q k K(κk) if |K| > 0 else 1 20: α α + a z 21: β β + b z 22: d d + 1 23: q q d 24: end while 25: return (α, β) 26: end function

Pr(ni j =d) Q

t T Pr(ni t =d) Q

k K Pr(ni k < d)

Now, by Lemma 2 and noting that ni j is a partition of N i

just as n j is of N in Lemma 3, then ni j Pois(sjλ), i, j. Which also implies αi j,T =αi j,T and βi j,T =βi j,T , i, i .

Crucially, note that the proof also shows that despite each elector holding a different guess N i, pivotal probabilities end being the same for all voters. This is useful to enable agent simulations in large electorates, since it prevents having to otherwise calculate the set of probabilities N times per iteration. Besides, while the inexistence of a closed form for the summations in (5), whose theoretical rate of convergence is unknown, may look challenging, in practice they converge quickly. Furthermore, Algorithm 2 shows how (5) can be simplified such that αj,T and βj,T are found jointly and efficiently, with no explicit calculation of f P or FP (see the regular Appendix at the end for details). Finally, we specify exactly under which (unrealistic) simplifying assumptions the above can be indeed approximated, in a principled manner, solely by Skellam PMFs and CDFs. Then, we derive the proper generalized approximation:

Assumption 2. Knowing whether expected votes of two candidates are equal, lower or greater than each other does not give information about any other pair of candidates.

Proposition 5 (Skellam pivotal probs. in plurality voting). i, i ,αi j,T = αi j,T = αj,T and βi j,T = βi j,T = βj,T , s.t.:

t T f S( 1, sjλ, stλ) Y

k K 1 FS( 1, sjλ, skλ)

t T f S(0, sjλ, stλ) Y

k K 1 FS(0, sjλ, skλ) (6)

where f S and FS are Skellam distributions PMF and CDF.

Proof. Given Assumption 2, eq. (2) can be rewritten: αi j,T = Q t T Pr(ni j = ni t 1) Q k K 1 Pr(ni j ni k 1) βi j,T = Q t T Pr(ni j = ni t) Q k K 1 Pr(ni j ni k). Same as in Proposition 4, ni j Pois(sjλ), i, j. Then, by the definition of Skellam random variables, regarding αi j,T we have Pr(ni j ni t = 1) = f S( 1, sjλ, stλ) and similarly Pr(ni j ni k 1)=FS( 1, sjλ, skλ). Analogous for βi j,T . Calculating those is possible because f S is a convolution of two Poisson PMFs (Skellam 1946), and while FS has no closed formula, following Johnson (1959) one can use a step-wise function of the Non-central Chi-Square distribution CDF. See regular Appendix at the end for details.

Later, we will explore through simulations the quality conditions and computational efficiency of this approximation we call Skellam pivotal probabilities vis-a-vis the Possion pivotal probabilities in equation (5).

Convergence Properties Next, we discuss some of the convergence properties of ICV under plurality, beginning with showing that it converges to a Pure Nash Equilibrium (PNE) as electorates become large. It is known that standard plurality CV reaches equilibrium in one-shot non-atomic games (Palfrey 1988; Myerson and Weber 1993), including CV with polls (Fey 1997). Formally, ICV is guaranteed to have converged to stable PNE whenever no elector changes their electoral choice any longer:

Definition 4. PNE in ICV under plurality is an iteration δ > 0 such that: πi,δ =πi,δ +1 = =πi,δ + , i.

However, it can be shown that if no elector changes their electoral choice for two subsequent iterations, that already guarantees none will ever change. Then, even more conveniently, it can be also shown that if the latest vote shares of all candidates remain the same for two subsequent iterations, that already guarantees no elector will change their electoral choice any longer. This comes from the fact that the only element of electors election reward function that can vary across iterations are the pivotal probabilities and those only vary when candidates expected vote shares vary. That is what the next proposition shows:

Proposition 6. sδ h = sδ+1 h , h J iff δ = δ (δ is a PNE).

Proof. Consider what follows i, δ > 0 and h J . If sδ h = sδ+1 h , since N i is fixed and ni h is a function of only N i and sδ h, then also ni,δ h = ni,δ+1 h . Thus, given (2), pivotal probabilities do not change from δ to δ + 1 and because

they are the only that could change in (1), Ei,δ j Ei,δ = Ei,δ+1 j Ei,δ+1 . Which results in πi,δ=πi,δ+1 and then, by the definition of sδ, also in sδ+1 h = sδ+2 h . The same logic follows successively, leading to both sδ h = sδ +1 h = = sδ + h and πi,δ =πi,δ +1 = =πi,δ + .

This is important because, then, proving that ICV results in PNE with large electorates simplifies to proving that there will be two subsequent iterations where candidates vote shares will remain the same. But before we proceed to that, a few details need to be established. Firstly, we will need to impose the (rather innocuous) assumption that, as the electorate size approaches infinity, so do electors eventual guesses about that size (and vice-versa):

Assumption 3. N iff N i , i.

Secondly, we need to formally establish the intuitive fact that, as a candidate s vote share approximates zero, events where it appears tied for 1st become nearly impossible10:

Lemma 5. lim st 0 αi j,T = lim st 0 βi j,T =0, j, t T , K = .

Proof. Rewrite (2) in terms of events ni t >ni k, t T , k K, instead of ni j ni k or ni j > ni k. Then, the lower st, the less likely that ni t > ni k, t T , k K - until it becomes impossible when st =0, in which case αi j,T =βi j,T =0.

Finally, we recall from the CV literature the well known condition that the ratio between the probability of nonleading candidates being pivotal and the probability of leading candidates being pivotal must go to zero as N :

Condition 1. Let 1, , g, , m be the rank of m candidates vote shares, where g N[2,m 1], s.t. s1 = =sg 1 and sg+1 sm 0, with either sg 1 > sg sg+1 or sg 1 sg >sg+1. Then, respectively:

lim N αi h,G/αi r,G = 0 and lim N βi h,G/βi r,G = 0

where r {1, , g 1}, h {g + 1, , m}, G {1, , m} \ {h, r} and G {1, , g} \ {r}.

Palfrey (1988) proved the condition holds when N is constant and Chen and Xia (2011) when it is a random variable, including a Poisson in a Poisson game. For simplicity, both proofs focus on β with |G| = |G | = 1, but the logic is identical for α and extends mathematically trivially to |G| > 1, |G | > 1. Given the condition holds, we can prove both that δ exists in ICV as N , and also how δ is reached:

Proposition 7 (ICV asymptotic convergence). lim N Pr( δ : sδ j = sδ+1 j , j) = 1.

The formal proof is in the regular Appendix at the end. In terms of intuition, it resembles Dhillon and Lockwood (2004) s iterative elimination of dominated strategies - in the sense that deserted voting options due to strategic voting become progressively less appealing up to full abandonment.

10Except in the degenerate circumstance of all candidates having approximately same vote shares near zero.

More specifically, there are four cases to consider. In Case 1, all candidates are tied for 1st. Because then all vote shares are the same, all pivotal probabilities are identical - thus voters simply vote sincerely. If this leads to same vote shares, we say a trivial PNE is reached; otherwise it leads to Case 2, 3, or 4. In Case 2, one candidate is in 1st, all else are tied for 2nd. Again voters will vote sincerely; some because they genuinely prefer the leader, others because probability of being pivotal when voting for any runner-up is identical. This leads to a trivial PNE or to Case 1, 3 or 4.11 In Case 3, two candidates are isolated in the top 2. Condition 1, together with Assumption 3, make it so that as the electorate size approaches infinity, only the top 2 candidates are seen as viable - leading to the abandonment of others. Between the top 2, voters will of course choose sincerely, which guarantees a PNE. In Case 4, multiple (but not all) candidates are tied for 1st. Again from Condition 1 and Assumption 3, as the electorate size approaches infinity trailing candidates are abandoned. This leads to Case 3 or Case 4 with shrank set of viable options (and so on up until it becomes Case 3).

Corollary 1. As N , we have the following convergence bounds. If δ = 0 is Case 1 or 2, 1 δ m 1. If δ = 0 is Case 3, δ = 1. If δ = 0 is Case 4, 2 δ g.

Meir (2018) points out that reproducing the Duverger s Law (Duverger 1963) is a key scientific criterion for a plurality voting model. Usually, plurality Duvergerian equilibrium is defined as an equilibrium where only two candidates have positive votes (Palfrey 1988; Cox 1994). We propose treating that as strong Duvergerian equilibrium:

Definition 5. A Strong Duvergerian Equilibrium (SDE) is a δ : sδ 1 sδ 2 > 0 and sδ h = 0, h J \ {1, 2}.

Just like standard CV games, as electorate size approaches infinity, ICV also converges to SDE:12

Corollary 2. Because as N the prob. of cases 1, 2 or 4 in Proposition 7 happening in δ >0 becomes infinitesimal (Hoffman 1982), then lim N Pr(δ is a SDE) = 1.

Nevertheless, a natural question is how large N has to be for convergence to be guaranteed, since real applications have finite agents. In theory, because a candidate can become more pivotal both when it gains or loses votes, depending on the context - differently from Local-Dominance IV models (Meir, Lev, and Rosenschein 2014; Meir 2015) - in ICV voters can move back to past choices and thus cycles are a possibility. Yet, we will show through simulations that convergence usually results, even with very small electorates. To see why, recall that in (2), in general the lower sj is, the less likely nj > nk, k. Then, in practice, voting for j generally becomes more (less) pivotal as j gains (loses) votes more rapidly than as j looses (gains) votes. In other words, once a candidate starts loosing support, it is hard to recover it - which is intensified the larger the electorate is.

11Note that a cycle between Cases 1 and 2 is not possible. If all electors vote sincerely, that can lead to only one of those cases. 12Except for the uninteresting case of all electors having a same sincerely most-preferred candidate - who always gets 100% votes. Note: we forcefully avoid this (very rare) case in our simulations.

Figure 1: Prop. of simulations converging to Strong (SDE) or to Weak (WDE) Duvergerian Equilibria for a chosen ε.

But such a wasted vote avoidance does not necessarily lead to full abandonment of trailing candidates in finite electorates, thus SDE is not guaranteed. Since Duverger s Law merely states that votes tend to concentrate in 2 candidates, we propose also a weaker Duvergerian Equilibrium concept. Let ρ Q1,m be the effective number13 of candidates ρ=1/ Pm h (sh)2 (Laakso and Taagepera 1979):

Definition 6. A Weak Duvergerian Equilibrium (WDE) is a δ where ρδ 3 ε, for a chosen 0 < ε 1.

Conjecture 1. Let ρδ = 2+x, where x Q[ 1,m 2]. Then N = x 0. Therefore, N = Pr(δ is a WDE) .

While that conjecture cannot be proved easily for finite electorates, it does make intuitive sense. As candidates lose significant vote shares to others, by definition ρ becomes more concentrated. Our simulations confirm the pattern: the greater the electorate, the less likely ρδ diverges much from 2. Therefore, even with finite agents, δ becomes most often at least WDE.

Simulations

We implemented ICV in Python 3.7.3. First, 10,000 simulations were performed using Multinomial pivotal probabilities. Then, their pseudo-random seeds were used to repeat the simulations twice, each time using Poisson or Skellam probabilities - for a total of 30,000 simulations. Initialization Values. In those simulations, model hyperparameters were specified as: λ Uniform(2, 100) and m Uniform(3, 6). Electors candidate utilities were drawn from Beta distributions, with varying parameters: ui Beta(Uniform(0.1, 5.0), Uniform(0.1, 5.0)). The Beta ensures diversity: it can approximate the Uniform, the Gaussian, the Gamma, a Power Law or be bimodal. Hence, initial votes will be diverse across different initial seeds. Convergence. Convergence to an equilibrium was established when no electors altered their chosen candidate for

13This widely used index in Political Science measures concentration. Suppose 3 candidates: the 1st has 50% of votes, the 2nd has 45% and the 3rd has 5%. Then ρ 2.2 effective candidates.

Figure 2: Proportion of simulations that, repeated with same seed using different types of pivotal probabilities, converged to same election winner (black); at least 0.9 correlation of final candidate rankings (red) or final vote counts (gray).

two iterations in a row. All runs converged (in at most 15 iterations, 9th percentile of 5 iterations), except for 63 of 10, 000 runs employing Skellam pivotal probabilities, which resulted in cycles (all < 55 electors, 9th perc. 31 electors). Duvergerian equilibria. Around 85.7% simulations converged to a SDE. Red lines in Figure 1 show nearly all with more than 30 agents resulted in SDE. From blue lines, notice that outcomes not SDE are often at least WDE.14

Outcome similarity. Interestingly, simulations repeated with same starting pseudo-random number generating seed and differing only in types of pivotal probabilities used, generally resulted in same winner and in very similar overall outcomes, when N > 25 (see Figure 2). In fact, as the electorate increases, not knowing electorate sizes makes progressively less of a difference (Poisson or Skellam vs. Multinomial) and the Skellam becomes a very good approximation of the Poisson pivotal probabilities (which is the more important the greater the number of candidates). Runtime. Figure 3 confirms that simulations using Multinomial pivotal probabilities scale much worse, in particular as m increases. But note that the Skellam approximation is just a bit faster than the exact Poisson and both scale similarly. Therefore, the main practical advantage of the former is that it seems to lose numerical precision more slowly, likely because (6) is composed of a few multiplications of infinite sums, while (5) has infinite sums of multiplications.15

Differently from IV models, ICV works through simultaneous optimization updates and is useful with cardinal utilities and large electorates. Differently from CV models, agents achieve convergence through repeated iterations, not abstractly, and without knowledge of preference distributions -

14In their application, Tsang and Larson (2016) show via simulations that if electors see different candidate vote shares according to voter homophily, what we call SDE may be harder to achieve. 15Comparison with recent applications (e.g.Tsang, Salehi-Abari, and Larson 2018) is hard. They only included prob. of breaking two-way ties and only loosely approximated the Skellam.

Figure 3: Lowess lines: log. seconds to convergence with Multinm. (black), Poisson (blue) or Skellam pivotal probs.

knowing only candidates latest vote shares. This way, ICV addresses limitations of most IV and CV models. We have shown that with pivotal probabilities that conform to certain characteristics, convergence in ICV is guaranteed for arbitrarily large electorates. Furthermore, in practice, convergence can usually be achieved even with tiny electorates under weak assumptions. Besides, unless electorates are tiny, ICV with proper pivotal probabilities mostly converges to either having only 2 candidates with positive votes, or at least having votes concentrated in 2 candidates - thus passing the key Duverger s Law test (Meir 2018). ICV can also be efficiently simulated using either Poisson or Skellam pivotal probabilities. However, a theoretical limitation is that, like the Multinomial pivotal probabilities, they also require sophisticated voters. Agents must realize that, under the specified circumstances, their probability of being pivotal is a function of one of those distributions. This is in opposition to lesser sophistication requirements in most IV (see e.g. Meir 2015). Simpler heuristics can and have been proposed. Our hope is that our thorough treatment may serve as a theoretical guide to inform principled heuristics, as well as a benchmark to evaluate them regarding efficiency and outcome similarity. We also have showed characteristics that pivotal probabilities require if heuristics were to aim at guaranteeing convergence and Duvergerian equilibria. Other limitations of present ICV are the costlessness of voting and of strategizing. Exploring ICV with abstention, lazy-voting (Desmedt and Elkind 2010; Elkind et al. 2015) and truth-bias (Meir et al. 2010; Obraztsova, Markakis, and Thompson 2013; Elkind et al. 2015) are logical next steps. Introducing uncertainty about states is also desirable, which has been explored through poll uncertainty in CV (Fey 1997) and in IV (Reijngoud and Endriss 2012; Wilczynski 2019). Lastly, extending ICV to other rulesets seems promising, like SNTV (Cox 1994), Approval and Borda (Myerson and Weber 1993) and Runoff (Bouton and Gratton 2015).

Appendix Proof of Proposition 1

Proof. Recall Assumption 1. Consider first Ai,δ j,T . If i votes for j, then a tie between j and candidates in T is created, so E[ui w|πi,δ = j, Ai,δ j,T ] = (ui j+P

t T ui t)/(|T |+1). If, instead, i abstains, not creating a tie between j and those in T , E[ui w|πi,δ = , Ai,δ j,T ] = (P

t T ui t)/|T |. Now, consider Bi,δ j,T . If i votes for j, breaking the tie and isolat-

ing j in first, E[ui w|πi,δ = j, Bi,δ j,T ] = ui j. If, instead, i abstains, not breaking the tie, E[ui w|πi,δ = , Bi,δ j,T ] =

t T ui t)/(|T |+1). From Lemma 1, Ei,δ j Ei,δ = P T h αi,δ j,T ui j+P

t T ui t |T |+1 + βi,δ j,T ui j i P T h αi,δ j,T

t T ui t |T | +

βi,δ j,T ui j+P

t T ui t |T |+1 i =P T

αi,δ j,T |T | +βi,δ j,T

t T (ui j ui t) |T |+1

Proof of Proposition 5 Proof. To shorten notation, let Λ Qm 0 s.t. Λj = sjλ, j. Using Assumption 5, rewrite (2) as: αi j,T = Q t T Pr(ni t = ni j + 1) Q k K Pr(ni k ni j) βi j,T = Q t T Pr(ni t = ni j) Q k K 1 Pr(ni j ni k) Same as in Proposition 4, ni j Pois(sjλ), i, j. So, focusing on αi j,T , note that Pr(ni t = ni j + 1) = P d=0 f P (d,Λj)f P (d+1,Λt) and Pr(ni k ni j) = P d =0 f P (d ,Λj)FP (d ,Λk). From Skellam (1946) we know f S(x, µ1, µ2) = P d= f P (d + x, µ1)f P (d, µ2). Then: αi j,T = Q

t T f S( 1, Λj, Λt) Q

d =0 f P (d ,Λj)FP (d ,Λk)

Substitute the well known formulae for f P and FP :

t T f S( 1, Λj, Λt) Q

d! Γ(d+1,Λk)

t T f S( 1, Λj, Λt) Q

k K 1 Fχ2(2Λk, 2( 1), 2Λj)

Where Fχ2 is the CDF of the Noncentral Chi-Square distribution. While FS has no closed formula, following Johnson (1959) it can be calculated as a function of Fχ2:

FS(x, µ1, µ2) = Fχ2(2µ2, 2x, 2µ1) if x < 0 1 Fχ2(2µ1, 2(x + 1), 2µ2) if x 0 αi j,T = Q

t T f S( 1, Λj, Λt) Q

k K 1 FS( 1, Λj, Λk)

Analogous for βi j,T . See Online Appendix for details.

Proof of Proposition 7 Proof. Let 1, , g, , m represent the rank of m candidates latest vote shares, with g N[2,m 1]. Case 1: (all tied for 1st) Fix sδ 1 = = sδ m. Then, in δ, αi 1,T = =αi m,T and βi 1,T = =βi m,T , i. Hence, given (1), πi,δ+1 = argmax j J (ui j), i. If that leads to same vector s, δ is a trivial PNE; otherwise it is Case 2, 3 or 4. Case 2: (one in 1st, all else tied for 2nd) Fix sδ 1 > sδ 2 = = sδ m. Then, i, if ui 1 > ui 2 ui m, Ei 1,δ > Ei,δ 2 Ei,δ m regardless of pivotal probabilities; otherwise, note αi 2,T = = αi m,T and βi 2,T = = βi m,T in δ. So, given (1), again πi,δ+1 = argmax j J (ui j), i. Then, if sδ+1 = sδ, δ is a trivial PNE; if not, it is Case 1, 3 or 4. Note that a cycle between Cases 1 and 2 is not possible. All electors voting sincerely can lead to Case 1 or Case 2. Case 3: (2 candidates in the top 2) Fix min(sδ 1, sδ 2) > sδ h, s.t. 3 h m. From Condition 1 and Assumption 3, it follows that as N , given (1), min(Ei,δ 1 , Ei,δ 2 ) > Ei,δ h , i, h, i.e. lim N Pr(πi,δ+1 {1, 2}) = 1, i, hence

lim N sδ+1 h =0, h. From Lemma 5, since either ui 1 ui 2 or

ui 2 ui 1 is positive, lim N Pr(πi,δ+1 =argmax 1,2(ui 1, ui 2))=

1, i, which does not vary, thus ensuring a PNE in δ+1. Case 4: (up to g 1 tied for 1st) fix sδ 1 = = sδ g 1 and sδ g+1 sδ m 0, with either sδ g 1 > sδ g sδ g+1 or sδ g 1 sδ g > sδ g+1, where g +1 h m. Again from Condition 1 and Assumption 3, as N and given (1), min(Ei,δ 1 , , Ei,δ g ) > Ei,δ h , i, h, i.e. lim N Pr(πi,δ+1

{1, , g}) =1, i, hence lim N sδ+1 h = 0, h. Then, from

Lemma 5, as N , δ+1 can be: (i) Case 3; (ii) Case 4 again, with up to g 1 candidates tied for 1st and sδ+1 h =0, h. If sδ+2 = sδ+1 a trivial PNE is reached, otherwise δ+2 is either Case 3 or Case 4 with even less candidates tied for 1st, and so forth until Case 3 is reached. (iii) Case 4 again, with sδ+1 1 = = sδ+1 g > 0, sδ+1 h = 0, h, in which case δ+2 is either (i), (ii) or a trivial PNE.

Counting Possible Pivotal Outcomes Proposition 8. Num. of cases in Vα and Vβ are given by:

Pˆx x=1 Pˆy y=0

( 1)y |K| y

N x(|T | + 1 + y) + d + |K| 1 |K| 1

if |T | + 1 < m

1 N + d mod m = 0 if |T | + 1 = m

where d = 0 and ˆx = N /(|T | + 1) when calculating |Vβ|, d = 1 and ˆx = N /(|T | + 1) when calculating |Vα|, with ˆy = min(|K|, (N x(|T | + 1) + d)/x ) and 1 being the indicator function.

Proof. See Online Appendix.

Details of Algorithm 2 Proposition 9. Poisson pivotal probabilities can be jointly calculated and with no explicit calculation of f P or FP .

Proof. Re-write βi j,T in (5) with infinite summation starting at 1, so all other terms of αi j,T and βi j,T are the same:

f P (d, sjλ)Q

t T f P (d+1, stλ) Q

k K FP (d, skλ)

f P (d + 1, sjλ)Q

t T f P (d+1, stλ) Q

k K FP (d, skλ)

Let µ Q 0. Begin by noting that f P (0, µ) = FP (0, µ) = e µ and, by definition, x N<0, f P (x, µ) = FP (x, µ) = 0. Hence, the joint calculation of both infinite summations is initialized by calculating e shλ, h J , then the infinite summations start at d = 1 and those exponentials are simply updated, up to joint convergence of αi j,T and βi j,T , according to the following: x N 0, since

f P (x, µ) = (µxe µ)

x! , then f P (x + 1, µ) = (µ(x+1)e µ)

x! µ x+1 = f P (x, µ) µ x+1. Similarly, if FP (x, µ) =

e µ P x r=0 µr

r! , then FP (x + 1, µ) = e µ P x+1 r=0 µr

e µ P x r=0 µr

r! + e µ µ(x+1)

(x+1)! = FP (x, µ) + e µ µ(x+1)

Acknowledgments I am thankful for crucial comments and feedback received from Reshef Meir, Edmund Durfee, Walter Mebane and multiple anonymous reviewers, as well as for earlier insights provided by In Song Kim, Kevin Mc Alister and Samuel Baltz. Finally, the research leading to this work was supported by a fellowship from the Michigan Institute for Computational Science and Discovery (MICDE) at the University of Michigan, by the Horowitz Foundation s Irving Louis Howard Award and Joshua Feigenbaum Award, and by Walter Mebane s NSF award SES 1523355.

References Bartholdi, J.; Tovey, C.; and Trick, M. 1989. The computational difficulty of manipulating an election. Social Choice and Welfare, 6(3): 227 241.

Black, J. H. 1978. The Multicandidate Calculus of Voting: Application to Canadian Federal Elections. American Journal of Political Science, 22(3): 609 638.

Bouton, L. 2013. A theory of strategic voting in runoff elections. American Economic Review, 103(4): 1248 1288.

Bouton, L.; and Gratton, G. 2015. Majority runoff elections: Strategic voting and Duverger s hypothesis. Theoretical Economics, 10(2).

Chen, Y.; and Xia, A. 2011. The wasted vote phenomenon with uncertain voter population. Social Choice Welfare, 37(3): 471 492.

Clough, E. 2007. Strategic Voting under Conditions of Uncertainty: A Re-Evaluation of Duverger s Law. British Journal of Political Science, 37(2): 313 332.

Conitzer, V.; Sandholdm, T.; and Lang, J. 2007. When are elections with few candidates hard to manipulate? Journal of the ACM, 54(3).

Conlisk, J. 1996. Why Bounded Rationality? Journal of Economic Literature, 34(2): 669 700.

Cox, G. W. 1994. Strategic Voting Equilibria Under the Single Nontransferable Vote. American Political Science Review, 88(3): 608 621.

Cox, G. W.; and Shugart, M. S. 1996. Strategic Voting Under Proportional Representation. Journal of Law, Economics & Organization, 12(2): 299 324.

Cranor, L. F. 1996. Declared-Strategy Voting: An Instrument for Group Decision-Making. Ph.D. thesis, USA.

Desmedt, Y.; and Elkind, E. 2010. Equilibria of plurality voting with abstentions. In Proceedings of the 11th Conference on Electronic Commerce (ACM-EC), 347 356.

Dhillon, A.; and Lockwood, B. 2004. When are plurality rule voting games dominance-solvable? Games and Economic Behavior, 46: 55 75.

Duverger, M. 1963. Political Parties: Their Organization and Activity in the Modern State. New York: Wiley.

Elkind, E.; Markakis, E.; Obraztsova, S.; and Skowron, P. 2015. Equilibria of Plurality Voting: Lazy and Truth-Biased

Voters. In Proceedings of the 8th Symposium on Algorithmic Game Theory (SAGT), 110 122.

Fabrikant, A.; Jaggard, A. D.; and Schapira, M. 2013. On the Structure of Weakly Acyclic Games. Theory of Computing Systems, 53: 107 122.

Fairstein, R.; Lauz, A.; Meir, R.; and Gal, K. 2019. Modeling People s Voting Behavior with Poll Information. In Proceedings of the 18th International Conference on Autonomous Agets and Multiagent Systems, 1422 1430. Montreal, Canada: International Foundation for Autonomous Agents and Multiagent Systems.

Fey, M. 1997. Stability and Coordination in Duverger s Law: A Formal Model of Preelection Polls and Strategic Voting. American Political Science Review, 91(1): 135 147.

Gibbard, A. 1973. Manipulation of voting schemes: A general result. Econometrica, 41(4): 587 601.

Hoffman, D. T. 1982. A Model for Strategic Voting. SIAM Journal on Applied Mathematics, 42(4): 751 761.

Johnson, N. 1959. On an Extension of the Connexion Between Poisson and χ2 Distributions. Biometrika, 46(3/4): 352 363.

Koolyk, A.; Strangway, T.; Lev, O.; and Rosenschein, J. S. 2017. Convergence and Quality of Iterative Voting Under Non-Scoring Rules. In Proceedings of the 26th International Joint Conference on Artificial Intelligence, 273 279. Melbourne, Australia: International Foundation for Autonomous Agents and Multiagent Systems.

Laakso, M.; and Taagepera, R. 1979. Effective Number of Parties: A Measure with Application to West Europe. Comparative Political Studies, 12(1): 3 27.

Lev, O.; and Rosenschein, J. S. 2012. Convergence of Iterative Voting. In Proceedings of the 11th International Conference on Autonomous Agets and Multiagent System. Valencia, Spain: International Foundation for Autonomous Agents and Multiagent Systems.

Lev, O.; and Rosenschein, J. S. 2016. Convergence of Iterative Scoring Rules. Journal of Artificial Intelligence Research (JAIR), (57): 573 591.

Mc Kelvey, R.; and Ordeshook, P. 1972. Mathematical Applications in Political Science VI, chapter: A general theory of the calculus of voting, 32 79. Charlottesville, USA: The University Press of Virginia.

Mebane, W.; Vasselai, F.; and Baltz, S. 2019. Using Agent Based Models to Simulate Strategic Behavior in Elections. In Polmeth 2019. Boston, MA.

Meir, R. 2015. Plurality Voting under Uncertainty. In Proceedings of the 24h International Joint Conference on Artificial Intelligence, 2103 2109. Buenos Aires, Argentina: Association for the Advancement of Artificial Intelligence.

Meir, R. 2018. Strategic Voting. Cambridge, Massachusetts: Morgan & Claypool Publishers.

Meir, R.; Lev, O.; and Rosenschein, J. S. 2014. A localdominance theory of voting equilibria. In Proceedings of the

15th ACM conference on Economics and Computation, 313 330. Palo Alto, California: ACM conference on Economics and Compu-tation. Meir, R.; Polukarov, M.; Rosenschein, J. S.; and Jennings, N. R. 2010. Convergence to Equilibria in Plurality Voting. In Proceedings of The 24th National Conference on Artificial Intelligence, 823 828. Atlanta, Georgia: International Foundation for Autonomous Agents and Multiagent Systems. Merrill, S. 1981. Strategic decisions under one-stage multicandidate voting systems. Public Choice, 36(1): 115 134. Myatt, D. P. 2007. On the Theory of Strategic Voting. Review of Economic Studies, 74(1): 255 281. Myerson, R. 1998. Population Uncertainty and Poisson games. International Journal of Game Theory, 27(3): 375 392. Myerson, R. 2000. Large Poisson Games. Journal of Economic Theory, 94(1): 7 45. Myerson, R.; and Weber, R. J. 1993. A Theory of Voting Equilibria. American Political Science Review, 87(1): 102 114. Obraztsova, S.; Markakis, E.; and Thompson, D. R. M. 2013. Plurality Voting with Truth-Biased Agents. In Proceedings of the 6th Symposium on Algorithmic Game Theory (SAGT), 26 37. Palfrey, T. 1988. Essays in Contemporary Political Theory, chapter: A Mathematical Proof of Duverger s Law, 51 74. Ann Arbor, MI, USA: University of Michigan Press. Reijngoud, A.; and Endriss, U. 2012. Voter Response to Iterated Poll Information. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems. Valencia, Spain: International Conference on Autonomous Agents and Multiagent Systems. Riker, W.; and Ordeshook, P. 1968. A Theory of the Calculus of Voting. American Political Science Review, 62(1): 25 42. Satterthwaite, M. A. 1975. Strategy-proofness and Arrow s conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of Economic Theory, 10(2): 187 217. Skellam, J. G. 1946. The frequency distribution of the difference between two Poisson variates belonging to different populations. Journal of the Royal Statistical Society, 109(3). Smith, A.; de Mesquita, B. B.; and La Gatta, T. 2016. Group incentives and rational voting. Journal of Theoretical Politics, 29(2). Tsang, A.; and Larson, K. 2016. The Echo Chamber: Strategic Voting and Homophily in Social Networks. In Proceedings of the 15th International Conference on Autonomous Agets and Multiagent Systems, 368 375. Singapore: International Foundation for Autonomous Agents and Multiagent Systems. Tsang, A.; Salehi-Abari, A.; and Larson, K. 2018. Boundedly rational voters in large (r) networks. In Proceedings of the 17th International Conference on Autonomous Agents

and Multi Agent Systems, 301 308. Singapore: International Foundation for Autonomous Agents and Multiagent Systems. Wilczynski, A. 2019. Poll-Confident Voters in Iterative Voting. In Proceedings of The 33rd AAAI Conference on Artificial Intelligence, 2205 2212. Honolulu, Hawaii: Association for the Advancement of Artificial Intelligence. Xia, L. 2021. How Likely Are Large Elections Tied? ar Xiv:2011.03791. Zilberstein, S. 2008. Metareasoning and Bounded Rationality. In Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence. Chicago, US: Association for the Advancement of Artificial Intelligence.