# plurality_voting_under_uncertainty__dc8f3dcf.pdf

Plurality Voting under Uncertainty

Reshef Meir Harvard University

Understanding the nature of strategic voting is the holy grail of social choice theory, where game-theory, social science and recently computational approaches are all applied in order to model the incentives and behavior of voters. In a recent paper, Meir et al. (2014) made another step in this direction, by suggesting a behavioral game-theoretic model for voters under uncertainty. For a speciﬁc variation of best-response heuristics, they proved initial existence and convergence results in the Plurality voting system. This paper extends the model in multiple directions, considering voters with different uncertainty levels, simultaneous strategic decisions, and a more permissive notion of bestresponse. It is proved that a voting equilibrium exists even in the most general case. Further, any society voting in an iterative setting is guaranteed to converge to an equilibrium. An alternative behavior is analyzed, where voters try to minimize their worst-case regret. As it turns out, the two behaviors coincide in the simple setting of Meir et al. (2014), but not in the general case.

Introduction

Suppose that ALICE, BOB, and CHARLIE run for ofﬁce. A and B are currently leading the polls with 45% and 40%, respectively. Your favorite candidate C is currently trailing behind with 15% (see Fig. 1, left). A game-theorist advice in such a case might be to vote strategically, by supporting your next-preferred candidate (say, B). Indeed, desertion of candidates that seem to lose height on polls in common in the real world, even if they are still perceived as suitable. However, there is no consensus whatsoever regarding how to generalize this straight-forward compromise to an arbitrary situation: should you leave C if he has 25% of the votes? and what if there are three or more candidates that are more popular than your favorite? does the source of the poll matter? and so on. This lack of a conclusive notion for strategic voting is partly due to the fact that there are many ways to describe the information voters have, as well as their beliefs over other voters preferences and actions when casting their

Copyright c 2015, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

vote. Moreover, even for a given belief there may be several different actions that can be justiﬁed as rational. Hence any model of voting behavior and equilibrium must state explicitly its epistemic and behavioral assumptions. A simple starting point would be to apply some standard assumptions from game-theory, for example that voters play a Nash equilibrium of the game induced by their preferences. However, such a prediction turns out to be very uninformative: a single voter can rarely affect the outcome, and thus almost any way the voters vote is a Nash equilibrium (including, for example, when all voters vote for their least preferred candidate). It is therefore natural to consider the role of uncertainty in voters decisions.

Probabilistic and strict uncertainty A classical economic approach is to assume that voters maximize some expected utility, given some prior distribution on other voters preferences and actions (see e.g. the MW model in Related Work). However the assumption that voters have access to an accurate, or even approximate, distribution of this sort seems hard to justify. Furthermore, studies in behavioral psychology show, human decision makers often ignore probabilistic information even when it is given, employing various heuristics instead (Tversky and Kahneman 1974). It is thus unlikely that people are able to represent complex distributions, or to compute and optimize their own expected utility, let alone the equilibria of such games. In a recent effort to reconcile well-founded decision making approaches with a formal game-theoretic analysis, Meir et al. (2014) suggested a model for Plurality voting relying on strict uncertainty and local dominance. Informally, voters beliefs can be described by a single vector of candidates scores. This prospective score vector may be the result of a poll, derived from acquaintance with the other voters, from the outcome of a previous round of voting, etc. Each voter has a single uncertainty level, reﬂecting how sure she is in the correctness of the prospective scores higher uncertainty means the voter considers a larger range of outcomes (score vectors) as possible. In the example introduced above, a voter with an intermediate uncertainty level will consider a tie between A and B as possible, but will reject any outcome where C wins as impossible. Given this uncertain, non-probabilistic view, it is not a-

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015)

priori clear how a voter should act. Meir et al. adopted one of the classic approaches to decision making under strict uncertainty, assuming that a voter i will refrain from voting for a candidate ai that is locally dominated by another candidate a i. Intuitively, a i locally-dominates ai if it is always at least as good, and sometimes strictly better, to vote for a i than for ai (taking into account all outcomes that voter i considers possible). A voting equilibrium is simply a state where no voter votes for a locally-dominated candidate according to her beliefs. Going back to our example, our voter will consider candidate c as locally-dominated by candidate b, and will thus strategize by voting for b. Informally, Meir et al. (2014) proved that if all voters have the same uncertainty level, start by voting truthfully, and play one at a time, then they always converge to a voting equilibrium. In the special case of zero uncertainty, this simply means that the best-response dynamics converges to a Nash equilibrium (which is known from (Meir et al. 2010)). However, these assumptions are rather restrictive. Some voters may be less informed than others, or simply more stubborn (e.g., require even fewer votes to C in order to be convinced he cannot win). Also, there is no reason to believe that voters initially vote for their most preferred candidate, or that only one voter changes her vote after each poll or voting round (see, e.g., (Reijngoud and Endriss 2012)). Meir et al. (2014) showed empirically that convergence occurs even without those assumptions, and conjectured that at least some of the assumptions could be relaxed. However they provided no formal guarantee for such convergence.

Research goals The main purpose of this work is to close this gap, and to prove equilibrium existence and convergence under conditions that are as broad as possible. While we adopt the model of Meir et al. at large, we study a non-atomic variation of it, where the effect of any single voter is negligible. This simpliﬁes the model, and allows us to prove stronger results. We modify the distance function used to determine the possible ranges of candidates scores, to one that is better justiﬁed by psychological studies (for details see Footnote 4). In addition, we are interested whether the behavioral assumptions can be weakened, or, alternatively, be replaced with a more nuanced way to select among several undominated candidates. To that end, we deﬁne a variation of the model where voters are aiming to minimize their worst-case regret over all states they believe possible, and compare this behavior to voting under local dominance.

Our contribution

Our main result is proving that voters with local dominance behavior always converge to an equilibrium. This holds for any population of voters with different preferences and uncertainty levels, for any initial voting proﬁle, and for any order of moves (including moves of arbitrary subsets of voters, and suboptimal moves). We then turn to study voters minimizing worst-case regret. When voters have the same uncertainty level and start from the truthful proﬁle, we show that regret minimization

coincides with local dominance. However if these requirements are relaxed then the behaviors may signiﬁcantly differ, and even the existence of equilibrium is not guaranteed. Due to space constraints, some of the proofs were omitted, and are available in the full version of this paper.1 In the full version we also show that all of our results hold in the ﬁnite case, for voters that move one-at-a-time.

The Formal Model Basic notations Where possible, we follow the notations and deﬁnitions of (Meir, Lev, and Rosenschein 2014). We denote [x] = {1, 2, . . . , x} for all x N. For a ﬁnite set A, Δ(A) denotes the set of all probability distributions over A (all non-negative vectors of size |A| that sum to 1). The set of candidates is denoted by M, where m = |M|. Let Q = π(M) be the set of all strict orders (permutations) over M. We encode all the information on a voter, including her preferences, in her type,2 where the set of all types is denoted by V. Speciﬁcally, a voter of type v V has preferences Qv Q, where Qv(a) [m] is the rank of candidate a M (lower is better), and qv = Q 1 v (1) is her most-preferred candidate. We denote a v b if Qv(a) < Qv(b). There is no ﬁnite set of voters. Rather, a preference proﬁle Q Δ(Q) is a distribution over preferences, specifying the fraction of voters with each preference order. A population V Δ(V) is a distribution over types, that is, a preference proﬁle aggregated with any additional information speciﬁed by voters types (e.g., their beliefs and behaviors). Under the Plurality rule, every voter selects a single candidate. A given action proﬁle should specify how many voters of each type vote for every candidate. Formally, an action proﬁle (also called state) a is a reﬁnement of V, where a(v, c) R+ denotes the fraction of voters of type v who vote for c M. Intuitively, the winner under state a is the candidate c getting at most votes, i.e., maximizing v a(v, c). Our next deﬁnitions are intended to enable easier notations and analysis. We treat the voter set as if it is partitioned to subsets whose size is ϵ, for some arbitrarily small ϵ > 0.3 We denote by I the collection of these 1/ϵ sets, and refer to an arbitrary voter in the set i I as voter i. W.l.o.g. all voters in set i I are indistinguishable: they have the same type vi and the same action ai in any proﬁle a (otherwise we just further split set i to smaller uniform subsets).

Score vectors and tie-breaking The outcome of the Plurality rule in state a, denoted f(a) M, only depends on the total number of votes for each candidate. We thus deﬁne the score vector sa induced by action proﬁle a. That is, sa(c) = |{i I : ai = c}|ϵ =

v V a(v, c). We will use a and sa interchangeably, sometimes omitting the subscript a. We denote by S = Rm + the set of all score vectors. We

1http://arxiv.org/abs/1411.4949 2We later extend the deﬁnition of a type to also include the belief structure and behavior of the voter. 3This is not a restrictive assumption. We further discuss its implications in the full version.

also sometimes refer to score vectors as states, although s may not be attained from an actual action proﬁle. E.g., it is possible that c M s(c) = 1. Note that we may only use the aggregate scores s in a context where voters identiﬁers are not important. Every score vector s implicitly contains an arbitrary tiebreaker Q+ s Q. The winner f(s) is the candidate c M whose score s(c) is maximal. If there is more than one candidate with maximal score, we break ties according to Q+ s . Formally, f(s) = argminc argmax s(c ) Q+ s (c). Note that the outcome is well deﬁned even for score vectors that are not derived from valid action proﬁles.

Dynamics and equilibria We describe the behavior of a voter of type v V by a response function gv : M S 2M \ . That is, a mapping from the current state (only taking into account aggregate scores) and current action, to a subset of actions. Together, Qv and gv completely deﬁne the type v. For an identiﬁed voter i I, we write gi(s) instead of gvi(ai, s). We also write gi(a) as a shorthand for gi(sa). Intuitively, this means that a voter i I may choose any action in gi(a).

Deﬁnition 1. A voting equilibrium for population V is a state a, where gi(a) = {ai} for all i I.

For example, if gi is the best-response function (gi(a) = {c M : c maximizes the utility of i in a} for all i), then a voting equilibria coincides with the Nash equilibria of the game. We emphasize that classic results on existence of equilibria in nonatomic games (e.g., (Schmeidler 1973)) do not apply, since even if we assign cardinal utilities to voters, those would be highly discontinuous in the action proﬁle. Note that we do not assume that voters with the same type, or even the same identiﬁer, are coordinated. Even in cases where an equilibrium exists, players may or may not reach one, depending on their initial state and the order in which they play. We are therefore interested in sufﬁcient conditions under which the game is acyclic, i.e. there are no ﬁnite cycles of moves by groups of any size.

Uncertainty and Strategic Voting The most important part of the model is of course the way we deﬁne the behavior, which is the response function gi. This behavior depends on voters preferences, and also on their beliefs about the current state. We assume voters derive their beliefs using a distance-based strict uncertainty model, following (Meir, Lev, and Rosenschein 2014).

Distance-based uncertainty Suppose we have some distance measure for score vectors, denoted by δ : S S R+. For any s, let S(s, x) = {s : δ(s, s ) x} be the set of vectors that are at distance at most x from s. A distance function δ is candidate-wise if it can be written as δ(s, s ) = maxc M ˆδ(s(c), s (c)) for some monotone function ˆδ (meaning that for a ﬁxed s, ˆδ(s, s ) is nondecreasing in |s s |). Thus s S(s, x) if only if the score of every candidate in s is sufﬁciently close to its score in s, see Fig. 1.

s(A) = 0.45

s(C) = 0.15

Figure 1: On the left ﬁgure we see a given state s, which can be thought of as the result of a poll, or of the current voting round. On the right we depict the set of possible states S(s, r) for r = 0.15. Any s is a possible state as long as the score of each candidate is in the marked range. The dashed line marks the threshold above which a candidate is considered a possible winner.

In (Meir, Lev, and Rosenschein 2014), several metrics have been suggested for the function δ, including various ℓd norms. Among those the multiplicative distance (where ˆδ(s, s ) = max{s /s, s/s } 1) and the ℓ metric (where ˆδ(s, s ) = |s s |) are candidate-wise. While all of our results apply for any candidate-wise distance (see full version), for concreteness we assume throughout the paper the multiplicative distance. Note that the multiplicative distance is independent of the amount of voters, i.e. δ(s, s ) = δ(αs, αs ) for all α > 0. This is consistent with ﬁndings on how people perceive uncertainty over numerical values (Kahneman and Tversky 1974; Tversky and Kahneman 1974).4

The intensity of probabilistic uncertainty is typically captured by some variance. The intensity of the agent s uncertainty in our non-probabilistic model is captured by the uncertainty parameter rv R+, which is part of the agent s type. Given a proﬁle a, voter i I believes that the actual state may be any s S(sa, ri), where ri = rvi. A voter facing strict uncertainty may use various heuristics when selecting a strategy. In this work we follow two standard approaches: avoiding dominated strategies (Aumann 1999), and minimizing worst-case regret (Savage 1951; Hyaﬁl and Boutilier 2004).

4For example, the studies show that if the average number of girls born daily in a hospital is s, then people believe that the probability that on a given day the number is within [(1 r)s, (1+r)s] is ﬁxed and does not depend on s. Kahneman and Tversky highlight that this reasoning stands in contrast to the scientiﬁc truth in this case, where the range r is proportional to 1/ s. In our case we can think of the score of a candidate as the limit of a Poisson variable (rather than Binomial in the hospital example), and thus the range [s/(1 + r), s(1 + r)] is more appropriate.

Voter inﬂuence In the nonatomic case, every voter has negligible inﬂuence, yet they still prefer some actions over others. How does the outcome change when a voter votes for some candidate c? To solve this discrepancy, we assume that a voter considers herself as pivotal only if she happens to break an exact tie. Formally, we deﬁne f(s, c) = c if c has maximal score in s (overriding the default tie-breaker Q+ s ), and f(s, c) = f(s) otherwise.

Local dominance The ﬁrst approach we consider follows (Conitzer, Walsh, and Xia 2011; Meir, Lev, and Rosenschein 2014), where voting dynamics is determined by local dominance relations. Consider a particular voter i = vi, ai . Let S = S(s, ri). We say that action ai S-beats bi if there is at least one s S s.t. f(s , ai) i f(s , bi). That is where i strictly prefers f(s , ai) over f(s , bi). Action ai S-dominates bi if (I) ai S-beats bi; and (II) bi does not S-beat ai. We next deﬁne the response function that strategic voters apply under the local dominance behavioral model. Consider a voter i, where vi = Qi, ri .

Deﬁnition 2 (Strategic move under local dominance (LD)). Let D M be the set of candidates that S(a, ri)- dominate ai, and that are not S(a, ri)-dominated. If D = then gi(a) = {ai}. Otherwise:

For a weak LD voter, gi(a) = D. For a strict LD voter, gi(a) = argmind D Qi(d).

In other words, a strict LD voter votes the most preferred candidate that locally-dominates her current choice (if such exists). The deﬁnition of a weak LD voter is much more permissive, and does not restrict the voter to select the most preferred candidate in D. A higher value of ri may either indicate that the voter is less informed, or simply that she requires stronger evidence that a move will be beneﬁcial, a tendency we can interpret as stronger loss aversion (Kahneman, Knetsch, and Thaler 1991). The following observation is immediate from Deﬁnitions 1 and 2.

Proposition 1. Let V be a population of LD voters. A proﬁle a is a voting equilibrium iff i I, ! a i M, such that a i S(a, ri)-dominates ai. I.e., if no voter votes for a locally dominated candidate.

Convergence with LD Voters We say that candidate c is a possible winner for i in state s if there is a possible state where c wins. Formally, Wi(s) = {c M : s S(s, ri) s.t. f(s , c) = c}. Also denote W0(s) = {c M : f(s, c) = c} = Wi(s) for ri = 0, and Wi(s) = Wi(sa). It is easy to see that under the multiplicative distance c Wi(s) iff s(c) (1 + ri) 2s(f(s)), and that similar thresholds exist for other metrics, see (Meir, Lev, and Rosenschein 2014) and the full version of this paper. The next key lemma, however, holds only for candidate-wise distances, which means that the possible scores of the different candidates are calculated independently (it is the only place in the paper where the candidate-wise assumption is used).

Lemma 2. Every pair of possible winners are tied for victory in some possible state. Formally, for every b, c Wi(s), there is s S(s, ri) s.t. b, c W0(s ).

Proof. Consider some b, c Wi(s). Let the score of all candidates except b, c be s (a) = s(a)/(1 + ri), and set s (b) = s (c) = min{s(b), s(c)}(1+ri). Then s S(s, ri), and s (b) = s (c) s (a) for all a M.

In the example depicted in Fig. 1, A is a possible winner for any r. B is a possible winner for voters for which 0.4(1+ ri) 0.45/(1 + ri), which means ri 0.06. Only voters whose uncertainty ri is above 0.73 consider C as a possible winner, as otherwise 0.15(1 + ri) < 0.45/(1 + ri). We denote by ai i a i valid local dominance steps where a i gi(a) and a i = ai. The next two lemmas characterize such LD moves. Lemma 3. Consider an LD move ai i a i. Then either (a) ai / Wi(s); or (b) ai i b for all b Wi(s); or (c) ri = 0, {ai, a i} W0(s) and a i i ai.

Proof. Suppose that ai, b Wi(a), and ai i b (i.e., (a) and (b) are violated). Assume ﬁrst that a i / W0(s). By Lemma 2 there is a state s S(s, ri) where ai, b have maximal score (possibly with other candidates), strictly above a i. W.l.o.g. Q+ s (b) < Q+ s (ai), as the tie-breaker does not affect the distance. Thus f(s , ai) = ai, f(s , a i) = b. Since ai i b, then we have that ai S(a, ri)-beats a i. The remaining case is where a i W0(s) and ai i a i. Then in the state s where ai, a i are tied it is better to vote for ai. In either case we get that a i / D, which is a contradiction.

Lemma 4. Consider an LD move ai i a i. Then 1. a i Wi(s), and there is some c Wi(s) s.t. a i i c. 2. For a strict LD move, a i = argminc Wi(a) Qi(c). 3. If ai / Wi(s), then |gi(s)| = 1. Part 1 is the only thing we need for our later convergence results, and its proof is immediate: Consider a i = argminc Wi(a) Qi(c). Clearly a i locally dominates any candidate not in Wi(a), thus a i Wi(s). If there is only one possible winner, no action dominates any other action.

Beyond the fact that the above lemmas are required for our main result, they show that a strict LD move boils down to a simple heuristics: vote for the most preferred candidate among those whose score is above the threshold. For a weak LD move, any candidate above the threshold except the least preferred can be selected.

Existence of equilibrium and convergence Suppose that voters start at some arbitrary state a0, and play repeatedly. We get a sequence of states a0, a1, . . . where in every iteration some arbitrary subset of voters may change their vote. That is, for any t N and any i I, either at+1 i gi(at), or at+1 i = at i. Our primary result states that voters always converge in the nonatomic model.5

5We assume strict preference orders for consistency with most of the social-choice literature. However we note that the theorem

Theorem 5. Any sequence of weak LD moves is ﬁnite.

Proof. We only need to show that no valid sequence may contain a cycle. Assume, toward a contradiction, that there is a cyclic path (at)T t=0, and denote by R M all candidates that are part of the cycle. Let s be the lowest score of any candidate in R during the cycle, w.l.o.g. candidate a R at time t . Thus s = st (a ) st(c) for all c R for every time t T. Consider the next step where some voters join a (w.l.o.g. at step t ), and pick an arbitrary voter j I s.t. a = at +1 j = at j . Thus at step t there is a move aj j a

where aj = at+1 j R. By Lemma 4, a is a possible winner for voter j, i.e., a Wj(st ). Since st (c) st (a ) for all c R, we have R Wj(at ), and in particular aj Wj(at ). By Lemma 3, either aj is the least-preferred candidate for j in Wj(st ) (Cases I and II below), or the third category of the lemma holds. We treat the latter case separately (Case III), so assume aj is indeed the least-preferred in Wj(st ). Since R Wj(at ), aj is the least-preferred in R as well. There must be some step t in the cycle where a voter of type vj moves to aj (w.l.o.g. voter j). So in st , aj is preferred by j to some other possible winner z by Lemma 4. Since aj is the least-preferred in R, and aj j z, we have that z Wj(st )\R. Denote the (ﬁxed) score of z by s(z). Case I: s(z) s . Consider again step t . Since s(z) s , we have z Wj(st ). Since aj is the least preferred possible winner in t , we have that z j aj, which is a contradiction. Case II: s(z) < s . Denote d = at j , and consider the

step d j aj at time t . Since d R then st (d) s > s(z), and thus d Wj(st ). By Lemma 3 (category (b) or (c)), we have that aj j d. This is a contradiction since aj is the least-preferred in R. Case III: The remaining case is when there is b Wj(st ) s.t. aj j b. Then by Lemma 3, a W0(st ). However since a has minimal score, this means that R W0(st ), i.e., all candidates in the cycle have the same score s at time t . Then all of R must have the same score at every time t, since if the score of some candidates goes up, the score of others must go down below the minimum s . This means that all of the moves in the cycle fall under categories (b) or (c) of Lemma 3. Thus voters only vote for more preferred candidates, which contradicts a cycle.

One can argue that the uncertainty level of a voter may not remain the same throughout the game. For example, there may be less uncertainty as the game advances. We note that Theorem 5 holds even if Wj(st ) and Wj(st ) are obtained via different values of rj. The above theorem proves convergence under very broad conditions, but does not provide much intuition as to what

applies also under weak preferences. Indeed, introducing indifference in the preference relation only eliminate LD moves, and therefore never creates a cycle.

happens along the converging path. Our next result shows that when all voters have the same uncertainty level, convergence is much more structured. Our result extends a similar result in (Meir, Lev, and Rosenschein 2014) for the ﬁnite model, but note that in our model convergence is guaranteed even when subsets of voters move simultaneously. Conveniently, when all voters has the same uncertainty r, at any state at there is just one agreed set of possible winners, denoted by W t = W(at). We say that a move ai i a i is an opportunity move if a i i ai, and otherwise it is a compromise move.

Proposition 6. Consider any non-atomic Plurality voting game with weak LD moves, where all voters have the same uncertainty level r. If a0 is the truthful state, then for all t: (A) W t+1 W t; (B) the score of the winner is nondecreasing; (C) there are only compromise moves; and (D) any at i is either the most preferred candidate for i in W t, or it is not in W t.

The proposition still holds if the uncertainty level r decreases over time.

Regret Minimization

The local dominance approach is appropriate to describe voters who are reluctant to change their vote, unless they know it cannot hurt them, a behavior that is consistent with loss aversion. A different approach to decision making under strict uncertainty is minimization of worst case regret, explained by risk aversion (Bell 1982). Intuitively, such a voter wants to avoid situations where she could have gained much, but failed to vote for the right candidate. On one hand, regret minimization is simpler than local dominance since it does not depend on the current vote. Thus we can write gv(s), Wv(s) rather than gi(s), Wi(s). On the other hand, regret may depend on cardinal utilities, rather than ordinal preferences. A cardinal utility scale is a generic function u : M R, meaning that u(a) = u(b) for all a = b. A cardinal utility scale u ﬁts order Q π(M), if u(a) > u(b) whenever Q(a) < Q(b). We thus augment the deﬁnition of a type v with a cardinal utility scale uv that ﬁts Qv. Formally, the regret of a type v voter for voting b in state s is REGv(s , b) = maxc M u(f(s , c)) u(f(s , b)). Note that REGv(s , b) 0. The worst case regret (WCR) of a type v voter for voting b in s is WCRv(s, b) = maxs S(s,rv) REGv(s , b).

Deﬁnition 3 (Strategic move under regret minimization). A WCR voter of type v in proﬁle a votes for a candidate b minimizing WCRv(sa, b).

We ﬁrst characterize WCR moves. Under a candidatewise distance, we can effectively ignore the cardinal utility scale, as only the preference order affects the vote.

Lemma 7. Either |Wv(s)| = 1 (in which case all regrets are 0); or the unique candidate minimizing WCRv(s, c) is a = argminc Wv(s) Qi(c).

Local dominance vs. Regret minimization From Lemmas 4 and 7, we get that regret provides a partial justiﬁcation for strict LD moves.

Corollary 8. Let ai i a i be a strict LD move in state s, then a i is the WCR response of type vi, i.e., the unique candidate c minimizing WCRvi(s, c).

Thus this mean that the WCR dynamics and the strict LD dynamics coincide? The answer is no, since the entailment is only in one direction: any strict LD move is also a WCR move, but there may be an WCR move ai i a i even when ai is not locally dominated. This may occur for example when both of ai, a i are possible winners. Thus under the WCR dynamics voters have less tendency to stay where they are, and therefore cycles are more likely to form. It is an open question whether cycles exist when all voters have the same r, yet if we add a restriction on the initial state then convergence is guaranteed.

Proposition 9. Consider any non-atomic Plurality voting game, where all voters have the same uncertainty level r. If a0 is the truthful state (and |Wr(a0)| 2), then for every time t and any i I, the WCR move and the strict LD move of i coincide. In particular, the WCR dynamics converges to an equilibrium.

Proof. Consider any voter i I. By property (D) of Proposition 6, we have that either at i / Wr(st), or at i is the best possible winner. In the ﬁrst case, by Lemma 4, there is a strict LD move, and by Corollary 8, this move coincides with the WCR move. In the latter case, there is no LD move for i (so at+1 i = at i under LD), and by Lemma 7, at i minimizes worst case regret (so at+1 i = at i under WCR). Finally, since the LD dynamics converges, we get that under the conditions of the proposition (same r, truthful initial state), WCR converges as well.

Diverse population For the local dominance dynamics, Theorem 5 shows that any game is acyclic. Since under regret minimization voters are more likely to have a strategic move, it is also more likely that cycles emerge, and even the existence of an equilibrium is not guaranteed.

Proposition 10. There is a voting game where no voting equilibrium exists under WCR dynamics.

Discussion and Related Work We highlight some of the ideas and results in the paper, and how they compare with existing literature.

Uncertainty and regret Voting behavior based on regret minimization was considered by Ferejohn and Fiorina (1974). However their model (like probability-based models) heavily relies on voters having cardinal utilities. Also, they take an extreme approach where voters do not use any available information, and thus all states are considered possible. Another regret-based model was suggested in (Merrill 1982), which also ignores any available information. Merrill shows that under the Plurality rule uncertain

voters should be truthful, which stands in sharp contrast to behavior observed in the real world. One of the most prominent models for voting under (probabilistic) uncertainty was suggested by Myerson and Weber (1993), where voters preferences are sampled from a known prior distribution. An equilibrium according to the MW model is a mapping from preferences to a distribution over votes, such that each voter maximizes her expected utility w.r.t. this distribution. Myerson and Weber prove via a ﬁxed-point argument that an equilibrium always exists for every positional scoring rule, and in particular for Plurality. We see our regret minimization model as a nonprobabilistic variation of the MW model. Speciﬁcally, in the MW model the voter considers the probability of each tie to conclude her expected utility. In our WCR model the voter focuses on the most signiﬁcant possible tie, which greatly facilitates the decision making process. Some voting experiments suggest that human voting behavior is consistent with regret minimization (Blais et al. 1995; Krueger and Acevedo 2008), though voters may not see themselves as such. We should note that these studies have limited relevance to our work since they concern the decision whether to vote (voter turnout), rather than the strategic decision what to vote. Thus more experimentation is required to test the validity of such models. A related approach is iterated regret minimization (Halpern and Pass 2012), which was recently applied to voting (Emery and Wilson 2014). This approach assumes that voters know exactly both the preferences and the decision making process of the other voters, whereas both of these assumptions are avoided in the models we studied.

Local Dominance Concepts that are similar or equivalent to local dominance have been recently introduced in the voting literature, notably Π-manipulation (Conitzer, Walsh, and Xia 2011; Reijngoud and Endriss 2012) and de re manipulation (van Ditmarsch, Lang, and Safﬁdine 2012). However these papers did not consider distance metrics and did not present any results on equilibrium existence or convergence. For further background, we refer the reader to (Meir, Lev, and Rosenschein 2014), which surveyed many gametheoretic models of voting equilibrium, in particular w.r.t. various approaches to uncertainty, dominance, and iterative voting procedures. In addition, Meir et al. showed via extensive simulations that the equilibria reached by LD voters (especially with diverse uncertainty levels) reproduce patterns observed in the real world. In particular, in equilibrium most voters vote for only two prominent candidates, a phenomenon known as Duverger s Law (Duverger 1954). Consider the assumption made in (Meir, Lev, and Rosenschein 2014), that among all candidates dominating her current action, a voter will always select the one that is most preferred. Our paper tackles this assumption in two ways. First, we show that it is not required for convergence, and can thus be relaxed (among the other restrictions we relax). Second, we show that this assumption can be justiﬁed on the grounds that it minimizes the worst case regret of the voter.

Implications for general games A recent result on memoryless dynamics in atomic games, suggests that in any game with more than one pure equilibrium, cycles must occur if arbitrary groups of agents can move simultaneously (Jaggard, Schapira, and Wright 2011). Our result shows that this is no longer true in nonatomic games, and in fact there is a large class of games where convergence is guaranteed despite the existence of multiple equilibria.

Conclusion and Future Directions We showed that in the Plurality voting system, voters who avoid locally-dominated candidates will always converge to an equilibrium, and that this result is robust to the uncertainty levels in the populations, the initial state, and the order in which voters or groups of voters play. In ﬁnite games without uncertainty, it is known that convergence must occur in polynomial time in the number of voters and candidates. The speed of convergence in nonatomic games is not easily deﬁned. For example voters can just move in smaller and smaller masses in an inﬁnite (acyclic) path. However one can ask if there is a bound on the maximal number of times a single voter can move. For example under the conditions of Prop. 6, any voter can move at most m 1 times, so we can say that convergence is fast. Our general convergence proof does not provide a bound of such sort, but we believe it is an interesting open question for future research. We conjecture that no agent should move more than a polynomial (in m) number of times until convergence occurs.

The ultimate test for any scientiﬁc theory is in the accuracy of its predictions. An advantage of the theory studied in this paper is that it is possible to test its epistemic assumptions (distance-based uncertainty) and behavioral assumptions (local dominance/WCR minimization) almost independently. We intend to check whether empirical and experimental evidence (e.g. from (Van der Straeten et al. 2010)) support the theory, and if so, what can we say about actual uncertainty levels in real populations.

While the deﬁnition of weak LD voters naturally extends to many other voting rules (as do the deﬁnitions in (Conitzer, Walsh, and Xia 2011; Reijngoud and Endriss 2012; van Ditmarsch, Lang, and Safﬁdine 2012)), the action space in most rules contains all permutations of M, and there may be many actions that dominate a particular action. Thus the mere definitions are not very instructive as to how a voter would act. We hope the (local) worst-case regret minimization approach will be useful in deﬁning reasonable voting behaviors under uncertainty for other voting rules. Finally, distance based uncertainty may prove useful in other games where there is a natural metric over action proﬁles.

Acknowledgments The author would like to thank Omer Lev, David Parkes and Maria Polukarov for insightful discussions and for commenting on drafts of this paper, and Harvard CRCS for the support. Some of the future directions and clariﬁcations were pointed out by anonymous referees.

Aumann, R. J. 1999. Interactive epistemology i: knowledge. International Journal of Game Theory 28(3):263 300. Bell, D. E. 1982. Regret in decision making under uncertainty. Operations research 30(5):961 981. Blais, A.; Young, R.; Fleury, C.; and Lapp, M. 1995. Do people vote on the basis of minimax regret? Political Research Quarterly 48(4):827 836. Conitzer, V.; Walsh, T.; and Xia, L. 2011. Dominating manipulations in voting with partial information. In AAAI 11, 638 643. Duverger, M. 1954. Political Parties: Their Organization and Activity in the Modern State. New York: John Wiley. Y. Emery, M., and Wilson, M. C. 2014. Iterated regret minimization in voting games. In COMSOC 14. Ferejohn, J. A., and Fiorina, M. P. 1974. The paradox of not voting: A decision theoretic analysis. The American political science review 525 536. Halpern, J. Y., and Pass, R. 2012. Iterated regret minimization: A new solution concept. Games and Economic Behavior 74(1):184 207. Hyaﬁl, N., and Boutilier, C. 2004. Regret minimizing equilibria and mechanisms for games with strict type uncertainty. In UAI 04, 268 277. Jaggard, A. D.; Schapira, M.; and Wright, R. N. 2011. Distributed computing with adaptive heuristics. In ITCS 11. Kahneman, D., and Tversky, A. 1974. Subjective probability: A judgment of representativeness. In The Concept of Probability in Psychological Experiments. Springer. 25 48. Kahneman, D.; Knetsch, J. L.; and Thaler, R. H. 1991. Anomalies: The endowment effect, loss aversion, and status quo bias. The journal of economic perspectives 193 206. Krueger, J. I., and Acevedo, M. 2008. A game-theoretic view of voting. Journal of Social Issues 64(3):467 485. Meir, R.; Polukarov, M.; Rosenschein, J. S.; and Jennings, N. R. 2010. Convergence to equilibria in plurality voting. In AAAI 10, 823 828. Meir, R.; Lev, O.; and Rosenschein, J. S. 2014. A local-dominance theory of voting equilibria. In ACM-EC 14, 313 330. Merrill, S. 1982. Strategic voting in multicandidate elections under uncertainty and under risk. In Power, voting, and voting power. Springer. 179 187. Myerson, R. B., and Weber, R. J. 1993. A theory of voting equilibria. The American Political Science Review 87(1):102 114. Reijngoud, A., and Endriss, U. 2012. Voter response to iterated poll information. In AAMAS 12, 635 644. Savage, L. J. 1951. The theory of statistical decision. Journal of the American Statistical association 46(253):55 67. Schmeidler, D. 1973. Equilibrium points of nonatomic games. Journal of Statistical Physics 7(4):295 300. Tversky, A., and Kahneman, D. 1974. Judgment under uncertainty: Heuristics and biases. science 185(4157):1124 1131. Van der Straeten, K.; Laslier, J.-F.; Sauger, N.; and Blais, A. 2010. Strategic, sincere, and heuristic voting under four election rules: an experimental study. Social Choice and Welfare 35(3):435 472. van Ditmarsch, H.; Lang, J.; and Safﬁdine, A. 2012. Strategic voting and the logic of knowledge. In AAMAS 12, 1247 1248.