Strategic Behavior is Bliss: Iterative Voting Improves Social Welfare
Year: 2022

Abstract:
Recent work in iterative voting has defined the additive dynamic price of anarchy (ADPoA) as the difference in social welfare between the truthful and worst-case equilibrium profiles resulting from repeated strategic manipulations. While iterative plurality has been shown to only return alternatives with at most one less initial votes than the truthful winner, it is less understood how agents’ welfare changes in equilibrium. To this end, we differentiate agents’ utility from their manipulation mechanism and determine iterative plurality’s ADPoA in the worstand average-cases. We first prove that the worst-case ADPoA is linear in the number of agents. To overcome this negative result, we study the average-case ADPoA and prove that equilibrium winners have a constant order welfare advantage over the truthful winner in expectation. Our positive results illustrate the prospect for social welfare to increase due to strategic manipulation.

heading: 1 Introduction
text: Voting is one of the most popular methods for a group of agents to make a collective decision based on their preferences. Whether a decision is for a high-stakes presidential election or a routine luncheon, agents submit their preferences and a voting rule is applied to select a winning alternative.
One critical flaw of voting is its susceptibility to strategic manipulations. That is, agents may have an incentive to misreport their preferences (i.e. votes) to obtain a more favorable outcome. Unfortunately, manipulation is inevitable under any non-dictatorial single-round voting systems when there are three or more alternatives, as recognized by the celebrated Gibbard-Satterthwaite theorem [Gibbard, 1973, Satterthwaite, 1975]. Consequently, decades of research sought to deter manipulation, especially by high computational barriers [Bartholdi et al., 1989, Faliszewski et al., 2010, Faliszewski and Procaccia, 2010]; see [Conitzer and Walsh, 2016] for a recent survey of the field.
While there is a large body of literature on manipulation of single-round voting systems, sequential and iterative voting procedures are less understood. Indeed, these procedures occur in a variety of applications, such as Doodle or presidential election polls, where people finalize their votes after previewing others’ responses [Meir et al., 2010, Desmedt and Elkind, 2010, Xia and Conitzer, 2010, Reijngoud and Endriss, 2012, Zou et al., 2015]. Our key question is:
What is the effect of strategic behavior in sequential and iterative voting?
A series of work initiated by Meir et al. [2010] characterizes the dynamics and equilibria of iterative voting, where agents sequentially and myopically improve their reported preferences based on other agents’ reports [Reyhani and Wilson, 2012, Lev and Rosenschein, 2012, Brânzei et al., 2013, Grandi et al., 2013, Obraztsova et al., 2013, Meir et al., 2014, Rabinovich et al., 2015, Obraztsova et al.,
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
2015, Endriss et al., 2016, Meir, 2016, Tsang and Larson, 2016, Koolyk et al., 2017]. While the convergence of iterative voting has been investigated for many commonly studied voting rules, the effect of strategic behavior, in terms of aggregate social welfare, remains largely unclear.
A notable exception is Brânzei et al. [2013]’s work that introduced and characterized the additive dynamic price of anarchy (ADPoA) of iterative voting with respect to the plurality, veto, and Borda social choice functions. The (additive) DPoA measures the social welfare (difference) ratio between the truthful winner and an iterative policy’s equilibrium winners when an adversary minimizes aggregate social welfare by controlling both the order in which agents make their strategic manipulations and agents’ truthful preferences altogether. In particular, Brânzei et al. [2013] proved that under iterative plurality, the number of agents whose top preference is an equilibrium winner is at most one less than that of the truthful plurality winner. Therefore, strategic behavior does not have a significant negative impact on the social welfare measured by the sum plurality score of the winner. Nevertheless, it is unclear whether this observation holds for other notions of social welfare.

heading: 1.1 Our Contributions
text: We address the key question discussed above in the iterative voting framework, first proposed by Meir et al. [2010], by characterizing Brânzei et al. [2013]’s ADPoA under plurality dynamics and rank-based utility functions that differ from the iteration method. Given m ≥ 3 alternatives, a ranked-based utility function is characterized by a utility vector ~u such that each agent receives ui utility if their i-th ranked alternative wins, although this alternative may differ for each agent. We study iterative plurality due to its simplicity and popularity in practice. Moreover, our results absolve the need for the mechanism’s center to know ~u exactly, thus conserving agents’ privacy. Still, we assume this is constant for all agents.
Our first main result (Theorem 1) states that, unfortunately, for any fixed m ≥ 3 and utility vector ~u, the ADPoA is Θ(n) for n agents. Therefore, the positive result achieved by Brânzei et al. [2013] is not upheld if ~u differs from plurality utility under the iterative plurality mechanism.
To overcome this negative worst-case result, we introduce the notion of expected additive dynamic price of anarchy (EADPoA), which presumes agents’ truthful preferences to be generated from a probability distribution. Our second main result (Theorem 2) is positive and surprises us: for any fixed m ≥ 3 and utility vector ~u, the EADPoA is −Ω(1) when agents’ preferences are i.i.d. uniformly at random, known as Impartial Culture (IC) in social choice. In particular, our result suggests that strategic behavior is bliss because iterative voting helps agents choose an alternative with higher expected social welfare, regardless of the order of agents’ strategic manipulations.
Techniques. We compute the EADPoA by partitioning the (randomly generated) profiles according to their potential winners – the alternatives that can be made to win by incrementing their plurality scores by at most one. Conditioned on profiles with two potential winners, we show that iterative plurality returns the alternative that beats the other in a head-to-head competition (Lemma 1). This type of “self selection” improves the expected social welfare over truthful plurality winner by Ω(1) (Lemma 2). When there are three or more potential winners, we further show that the expected welfare loss is o(1) (Lemmas 3 and 4). Since the likelihood of k-way ties is exponentially small (in fact, Θ ( n− k−1 2 ) [Xia, 2021]), the overall social welfare is improved in expectation. We provide an
experimental justification of our second main result in Appendix B.

heading: 1.2 Related Work and Discussions
text: Sequential and iterative voting. Since iterative voting’s inception in 2010, many researchers have studied its convergence properties under differing assumptions and iteration protocols. Meir et al. [2010] first established the convergence of iterative plurality with deterministic tie-breaking from any initial preference profile or with randomized tie-breaking from the truthful profile. However, this result appears quite sensitive to its assumptions, since the authors found counter-examples when allowing agents to manipulate simultaneously, using better- instead of best-replies, or weighing agents’ votes unequally. Lev and Rosenschein [2012] and Reyhani and Wilson [2012] independently showed that no other scoring rule besides veto necessarily converges, while Koolyk et al. [2017] demonstrated the same for common non-scoring rules, such as Maximin, Copeland, and Bucklin.
Similarly, Obraztsova et al. [2013, 2015] and Rabinovich et al. [2015] each analyze the conditions for Nash equilibrium for iterative voting rules and their truth-biased or lazy voting counterparts [Thompson et al., 2013]. Rabinovich et al. [2015] conclude that determining whether a given profile is a reachable Nash equilibrium is NP-complete.
Most iterative voting rules require agents to have full information about each others’ votes in order to compute their best-responses. To relax this strong assumption, Reijngoud and Endriss [2012] and Endriss et al. [2016], inspired by Chopra et al. [2004], introduce communication graphs and poll information functions that restricts the amount information each agent receives and better respects voter privacy. The researchers subsequently provide susceptibility, immunity, and convergence results according to different voting rules. Tsang and Larson [2016] use these concepts to simulate iterative plurality on a social network and allow agents to infer their best-responses based on their neighbors’ reports. The authors demonstrate how correlating agents’ preferences affects the PoA and DPoA of strategic outcomes.
Sequential but non-iterative voting games have also been investigated in the literature. Desmedt and Elkind [2010] characterized the subgame perfect Nash equilibrium of a voting game where agents vote sequentially and are allowed to abstain from voting. Xia and Conitzer [2010] characterized the subgame perfect Nash equilibrium of a similar voting game where agents are not allowed to abstain, and proved that the equilibrium winner is highly unfavorable in the worst case, which can be viewed as an ordinal PoA. Our paper focuses on iterative voting setting proposed by Meir et al. [2010] and therefore differs from these works.
Best-response mechanisms. A separate line of research from iterative voting has studied the convergence and acyclicity properties of best-response mechanisms. Monderer and Shapley [1996] first introduced the finite improvement property applied to games with agents that sequentially change their actions. Apt and Simon [2015] and Fabrikant et al. [2010] subsequently characterized betterresponse dynamics in weakly acyclic games, which encapsulate potential and dominance-solvable games, and demonstrate bounds on finding their Nash equilibrium. The relationship between iterative voting and best-response mechanisms was explored by Meir et al. [2014] and Meir [2016], who fully characterized the acyclicity and local dominance properties of iterative voting rules.
Implications of our main results. Our results provide completeness and explanatory power to the empirical studies of Grandi et al. [2013] and Tsang and Larson [2016]. The former work shows an increase in additive social welfare using the Borda welfare vector due to plurality dynamics when agents have restricted manipulations and independent or correlated preferences [Berg, 1985]. The latter work shows a similar gain when agents have single-peaked preferences, are embedded on a social network, and make their manipulations based on estimates of their neighbors’ reports. Put together, iterative voting provides a social welfare benefit that serves as an additional defense of strategic manipulation to those presented by Dowding and Hees [2008]. We believe our results will benefit a further study of non-strategyproof mechanisms in other social choice domains, such multi-issue voting [Bowman et al., 2014, Grandi et al., 2020].

heading: 2 Preliminaries
text: Basic setting. Let A = [m] , {1, . . . ,m} denote the set of m ≥ 3 alternatives and n ∈ N denote the number of agents. We denote by L(A) the set of all strict linear orders over A and use Rj ∈ L(A), j ≤ n to represent agents’ preference rankings. Preferences are aggregated into profiles P = (R1, . . . , Rn), and we use top(Rj) ∈ A to denote agent j’s top preferred alternative. For any pair of alternatives a, b ∈ A, we use P [a b] to denote the number of agents that prefer a to b in P .
Integer positional scoring rules. An (integer) positional scoring rule r~s is characterized by an integer scoring vector ~s = (s1, . . . , sm) ∈ Zm≥0 with s1 ≥ s2 ≥ · · · ≥ sm ≥ 0 and s1 > sm. For example, plurality uses the vector ~splu = (1, 0, . . . , 0), veto uses (1, . . . , 1, 0), and Borda uses (m− 1,m− 2, . . . , 0). In this work we focus on the plurality rule rplu = r~splu and define the score of a ∈ A according to profile P as sP (a) = ∑ R∈P 1{top(R) = a}. We use the resolute function rplu(P ) = arg maxa∈A sP (a) to select a single winning alternative, breaking ties lexicographically and favoring that with the smallest index. Assume r = rplu unless stated otherwise.
Rank-based utility and additive social welfare. We assume that agents have additive utilities characterized by a rank-based utility vector ~u = (u1, . . . , um) ∈ Rm≥0 with u1 ≥ . . . ≥ um ≥ 0 and u1 > um. Like the scoring rule, each agent j gets ~u(Rj , a) = ui utility for the alternative a ∈ A ranked ith in Rj . Unlike prior work, however, we do not presume that ~u is the same as the scoring vector ~s. We define the additive social welfare of a according to P as SW~u(P, a) = ∑n j=1 ~u(Rj , a).
Iterative plurality voting. Given agents’ truthful preferences P , we consider an iterative process of profiles (P t)t≥0 that describe agents’ reported preferences (i.e. votes) (Rt1, . . . , R t n)t≥0 over time. For each round t, one agent j is chosen by a scheduler φ to make a myopic improvement step, denoted by Rtj
j−→ R′j , to their report. This step is called a better-response if j prefers the new outcome r(R′j , R t −j) to the prior one r(R t j , R t −j), whereas it is a best-response (BR) if, additionally, j could not have achieved a more preferred outcome than manipulating to R′j from P t. 1
Following Brânzei et al. [2013], we limit our discussion to strategic manipulations beginning from the truthful profile P 0 = P . This guarantees that all improvement steps R′j
j−→ R′′j from profile P ′ to P ′′ are best-responses that change the iterative winner: r(P ′) 6= top(R′j) ∧ r(P ′′) = top(R′′j ). 2 As a result, any sequence of BR steps converges inO(nm) rounds [Reyhani and Wilson, 2012]. The profiles {P ∗} with no further improvement steps are therefore Nash equilibrium (NE) with respect to P . We define EW(P ) as the set of equilibrium winning alternatives corresponding to all NE reachable from P via some BR sequence. That is,
EW(P ) = {r(P ∗) : ∃ a BR sequence from P leading to the NE profile P ∗}
Lastly, we’ll define the set of potential winning alternatives of any profile P as those who could become a winner if their plurality score were to increment by one, including the current winner. That is, some agent could make these alternatives win by taking a BR step that increases their plurality score, if the agent’s ranking permits. Following [Rabinovich et al., 2015], we have:
PW(P ) = { a ∈ A : { sP (a) = sP (r(P ))− 1, a is ordered before r(P ) sP (a) = sP (r(P )), a is ordered after r(P ) } ∪ {r(P )}
where the ordering is lexicographical for tie-breaking. Reyhani and Wilson [2012] proved that the potential winning set is monotonic in t: ∀t ≥ 0, PW(P t+1) ⊆ PW(P t), which implies EW(P ) ⊆ PW(P 0). As a result, iterative plurality voting acts like a sequential tie-breaking mechanism whose outcome follows from the scheduler φ. The following example demonstrates this section’s concepts. Example 1. Let n = 9, m = 3, and consider the truthful profile P defined with R1 = R2 = R3 = [1 3 2], R4 = R5 = [2 3 1], R6 = [2 1 3], and R7 = R8 = R9 = [3 2 1]. We observe from the plurality scores (sP (1), sP (2), sP (3)) = (3, 3, 3) that r(P ) = 1 and PW (P ) = {1, 2, 3}, representing a three-way tie. Next, Figure 1 describes the five BR sequences from P :
We therefore conclude EW(P ) = {2, 3}. Moreover, consider the utility vector ~u = (u1, u2, u3). Then the social welfare for each alternative is (SW~u(P, 1), SW~u(P, 2), SW~u(P, 3)) = (3u1 + 1u2 + 5u3, 3u1 + 3u2 + 3u3, 3u1 + 5u2 + 1u3). 2
1Note that φ must select a BR step if one exists [Apt and Simon, 2015]. 2These are characterized as Type 1 or direct best replies in the literature [Meir, 2016]. Conversely, Type 3 best-responses (r(P ′) = top(R′j) ∧ r(P ′′) = top(R′′j )) do not occur in improvement sequences from the truthful profile. Note that no BR step is of Type 2 (r(P ′) = top(R′j) ∧ r(P ′′) 6= top(R′′j )).

heading: 3 Additive Dynamic PoA under General Utility Vectors
text: How bad are equilibrium outcomes, given that strategic manipulations inevitably occur by the Gibbard-Satterthwaite theorem [Gibbard, 1973, Satterthwaite, 1975]? Brânzei et al. [2013] sought to answer this question by defining the additive dynamic price of anarchy (ADPoA) as the adversarial loss – the difference in welfare between the truthful winner r(P ) and its worst-case equilibrium winner in EW(P ) – according to the worst-case P . To motivate this concept, consider users of a website that can regularly log in and update their preferences for an election. Then the ADPoA bounds the welfare loss if a virtual assistant can recommend when users should make their changes.
Brânzei et al. originally defined the ADPoA for a given positional scoring rule r~s and an additive social welfare function respecting ~u = ~s. In this case, the ADPoA of plurality was found to be 1, while the (multiplicative) DPoA of veto is Ω(m) and Borda is Ω(n) form ≥ 4 [Brânzei et al., 2013]. Although these results answer the authors’ question and appear optimistic for plurality, they suggest more about the iteration mechanism than agents’ collective welfare. For example, an ADPoA for plurality of 1 means that for any truthful profile, the difference in initial plurality scores of any equilibrium winner is at most one less that of the truthful winner. However, when we relax the utility vector ~u to differ from ~s, we find in Theorem 1 that the ADPoA is quite poor at Θ(n).
First we recall Brânzei et al.’s definition of ADPoA using our notation and explicitly define the adversarial loss D+ for a particular truthful profile P before proceeding to our first main result. Definition 1 (Additive Dynamic Price of Anarchy (ADPoA) [Brânzei et al., 2013]). Given a positional scoring rule r~s, utility vector ~u = (u1, . . . , um) over m ≥ 3 alternatives, and truthful profile P , the adversarial loss starting from P is defined as
D+r~s,~u(P ) = SW~u(P, r~s(P ))−mina∈EW(P ) SW~u(P, a)
The additive dynamic price of anarchy (ADPoA) of r~s and ~u under n agents is defined as
ADPoA(r~s, ~u, n) = maxP∈L(A)n D + r~s,~u (P )
We will use ADPoA and D+ to denote ADPoA(rplu, ~u, n) and D+rplu,~u when the context is clear. 3 For example, we saw in Example 1 that r(P ) = 1 and EW (P ) = {2, 3}. Then
D+(P ) = max{ SW~u(P, 1)− SW~u(P, 2), SW~u(P, 1)− SW~u(P, 3) } = max{ (3u1 + 1u2 + 5u3)− (3u1 + 3u2 + 3u3) ,
(3u1 + 1u2 + 5u3)− (3u1 + 5u2 + 1u3) } = −2(u2 − u3) ≤ 0
Therefore the social welfare of both equilibrium winners is at least that of the truthful winner. In Theorem 2 below we’ll see this conclusion hold in expectation. For the worst case profile P , however, the following theorem proves that this is not the case – rather, the worst-case equilibrium winner of P has a social welfare linearly worse than the truthful winner. Theorem 1. Fix m ≥ 3 and utility vector ~u = (u1, . . . , um). Then ADPoA(rplu, ~u, n) is Θ(n). Specifically, ∀n > 2m,
(u2 − um) ( n m − 2 ) ≤ ADPoA(rplu, ~u, n) ≤ nu1
Proof. The ADPoA is trivially upper bounded by the maximum social welfare attainable by any truthful profile P . For example, if P is defined withRj = (1, 2, . . . ,m) ∀j ≤ n, then ∀P̃ ∈ L(A)n,
D+(P̃ ) = SW~u(P̃, r(P̃ ))−mina∈EW(P̃ ) SW~u(P̃, a) ≤ SW~u(P̃, r(P̃ )) ≤ SW~u(P, r(P )) = nu1
To lower bound ADPoA, we will construct a profile P with a two-way tie between alternatives 1, 2 ∈ A such that D+(P ) = (u2 − um) ( n m − 2 ) . This implies the desired lower bound of
ADPoA = maxP̃∈L(A)n D +(P̃ ) ≥ D+(P ) = (u2 − um) ( n m − 2 )
3The superscript ‘+’ denotes an additive measure instead of multiplicative in the classical definition of PoA.
Fix m ≥ 3 and let n > 2m be even. We denote by k = arg mink̃∈[2,m−1](uk̃ − uk̃+1) the position in ~u with the minimal difference in adjacent coordinates. Let α = 1m (n + m − 2) and β = (α− 1)(m− 2), such that n = 2α+β. We will then construct P as follows, with α agents that prefer 1 first and 2 last, α agents that prefer 2 first and 1 second, (β2 − 1) agents that prefer 1 second and 2 last, and (β2 + 1) agents that prefer 2 in their ranking’s k-th position and 1 in their ranking’s (k + 1)-th position. We can see here that sP (1) = sP (2) = α, and ∀c > 2, sP (c) = α − 1, thus guaranteeing the two-way tie. Therefore r(P ) = 1 and P [2 1] = α + β2 + 1 > α + β 2 − 1 = P [1 2]. This implies EW(P ) = {2} by the following lemma.
Lemma 1. Let m ≥ 2 and a, b ∈ A such that a is ordered before b in tie-breaking. Suppose PW(P ) = {a, b} for some truthful profile P . Then EW(P ) = {a} if P [a b] ≥ P [b a]; otherwise EW(P ) = {b}.
The lemma’s proof can be found in Appendix A.1. As a result,
D+(P ) = SW~u(P, 1)− SW~u(P, 2) = α(u2 − um) + ( β 2 − 1 ) (u2 − um)− ( β 2 + 1 ) (uk − uk+1)
≥ (u2 − um)(α− 2) = (u2 − um) ( n−m− 2
m
) ≥ (u2 − um) ( n m − 2 )
where the first inequality holds because (uk − uk+1) ≤ (u2 − um).

heading: 4 Expected Additive DPoA
text: In this section we extend Brânzei et al.’s ADPoA notion to account for the average-case adversarial loss for a positional scoring rule r~s, rather than only the studying worst-case. This expected additive dynamic price of anarchy (EADPoA) bounds the adversarial loss of strategic manipulation according to more typical distributions of agents’ rankings. Here we distribute profiles i.i.d. uniformly over L(A)n, known as the Impartial Culture distribution πn = ICn. Definition 2 (Expected Additive DPoA (EADPoA)). Given a positional scoring rule r~s, a utility vector ~u over m ≥ 3 alternatives, n agents, and a distribution πn over L(A)n for agents’ preferences, the expected additive dynamic price of anarchy is defined as follows:
EADPoA(r~s, ~u, n, πn) = EP∼πn [ D+r~s,~u(P ) ] Like before, we will use EADPoA and D+ to denote EADPoA(rplu, ~u, n, ICn) and D+rplu,~u respectively. We similarly fix a rank-based utility vector ~u that may differ from the scoring rule ~s, but we will not presume in the following theorem that this is known by the iterative plurality mechanism. In the subsequent proof, we will also drop the subscript “P ∼ ICn” to simplify notation when the context is clear. Theorem 2. Fix m ≥ 3 and utility vector ~u = (u1, . . . , um). For any n ∈ N we have
EADPoA(rplu, ~u, n, ICn) = −Ω(1)
Proof. The key idea is to partition L(A)n according to each profile’s potential winner set. More precisely, for every W ⊆ A with W 6= ∅, we define:
PoA(W ) = Pr(PW(P ) = W )× E[D+(P ) | PW(P ) = W ]
By the law of total expectation, then EADPoA = E[D+(P )] = ∑m
α=1 ∑ W⊆A:|W |=α PoA(W ) (1)
where α denotes the number of potential winners in P . It is straightforward to see that when α = 1, any profile P with |PW(P )| = 1 is already a NE, which implies D+(P ) = 0. The rest of the proof proceeds as follows. For any n ∈ N we will show in Lemma 2 that for ∀W ⊆ A with |W | = 2
PoA(W ) = −Ω(1). We will then demonstrate that PoA(W ) = o(1) ∀W ⊆ A with |W | = 3 (Lemma 3) and |W | ≥ 4 (if m ≥ 4; Lemma 4). Recalling that m is fixed, the total number of subsets of A is viewed as a constant. Finally, these results combine to conclude
EADPoA = 0︸︷︷︸ α=1 −Ω(1)︸︷︷︸ α=2 + o(1)︸︷︷︸ α≥3 = −Ω(1)
Profiles with two tied alternatives drive the EADPoA negative because of the self-selecting property of Lemma 1. For example, consider a truthful P with PW(P ) = {a, b} and r(P ) = a. When more agents prefer the non-truthful winner b in this setting, iterative plurality makes this correction by changing the winner to b and increases agents’ social welfare on average. When more agents prefer the truthful winner a, rather, iterative plurality doesn’t change this outcome and the adversarial loss remains zero. Without a sufficient counter-balance to the former α = 2 case by any of the α ≥ 3 cases, the adversarial loss overall remains negative in expectation.
The remainder of this section is devoted to detailing the proof behind the α = 2 case (Lemma 2). We declare the α = 3 case without proof (Lemma 3) and briefly prove the α ≥ 4 case (Lemma 4). Lemma 2 (α = 2). Given m ≥ 3 and a utility vector ~u, for any W ⊆ A with |W | = 2 and any n ∈ N, we have PoA(W ) = −Ω(1).
Proof. Without loss of generality let W = {1, 2} and suppose u2 > um. There are two possible cases of PW(P ) = {1, 2}: either sP (1) = sP (2) or sP (1) + 1 = sP (2), which we’ll denote by E1 and E2 respectively. This suggests PoA(W ) = Pr(E1)×E[D+(P ) | E1]+Pr(E2)×E[D+(P ) | E2]. We’ll focus on the first case where alternatives 1 and 2 are tied, since the latter’s proof is similar.
We believe this proof is challenging due to the dependence in agents’ rankings once we condition on profiles that satisfy two-way ties (i.e. E1). As a result, standard approximation techniques that assume independence, such as the Berry-Esseen inequality, no longer apply and may also be too coarse to support our claim. Instead, we will use a Bayesian network to further condition agents’ rankings based on two properties: the top ranked-alternative and which of the two tied alternatives the agents prefer. Once we guarantee agents’ rankings’ conditional independence, we can identify the expected utility they gain for each alternative and then compute E[D+(P ) | E1] efficiently. At a high level, there are two conditions for a profile P to satisfy E1 and have non-zero adversarial loss. First, the profile must indeed be a two-way tie. This is represented in Step 1 below by identifying each agent j’s top-ranked alternative tj ∈ A and conditioning D+(P ) on a specific vector of top-ranked alternatives ~t ∈ T2 ⊆ An, a set corresponding to all profiles satisfying E1. Second, by Lemma 1, the profile should satisfy P [2 1] ≥ P [1 2]. This is represented in Step 1 by identifying an indicator zj ∈ {1, 2} to suggest whether 1 j 2 or 2 j 1 respectively. We further condition D+(P ) on a specific vector ~z ∈ Z~t,k, a set corresponding to all profiles in E1 with k = P [2 1] ≥ P [1 2] = n − k. Once we condition D+(P ) to satisfy these two conditions, we identify the expected difference in welfare between the alternatives Etj ,zj for each agent j conditioned on tj , zj in Step 2, which follows from the Impartial Culture assumption. Finally, we compute D+(P ) by summing over all profiles satisfying the above two conditions and solve in Step 3, making use of Stirling’s approximation.
More precisely, for any j ≤ n, we represent agent j’s ranking distribution (i.i.d. uniform over L(A)) by a Bayesian network of three random variables (see Figure 2). First, Tj ∈ A represents j’s top-ranked alternative and follows a uniform distribution. Second, Zj ∈ {1, 2} indicates whether (1 j 2) or (2 j 1) conditioned on Tj , and has probability {0.5, 0.5} if Tj /∈ {1, 2}. Third, Qj follows the uniform distribution over linear orders that uphold both Tj and Zj . It is not hard to verify that (unconditional) Qj follows the uniform distribution over L(A), which implies that ~Q = (Q1, . . . , Qn) follows the same distribution as P .
Step 1: Identify profiles that satisfy E1. Let T2 ⊆ [m]n denote the set of top-ranked alternative vectors ~t = (t1, . . . , tn) such that alternatives 1 and 2 have the maximum plurality score. Then E1 holds for ~Q if and only if ~T takes a value in T2.
T2 = { ~t ∈ [m]n : ∀3 ≤ i ≤ m, |{j : tj = 1}| = |{j : tj = 2}| > |{j : tj = i}| }
Conditioned on agents’ top-ranked alternatives being ~t ∈ T2, we have by Lemma 1 that D+( ~Q) is non-zero if and only if ~Q[2 1] > ~Q[1 2]. Let Id1(~t) = {j ≤ n : tj = 1}, Id2(~t) = {j ≤ n : tj = 2}, and Id3(~t) = {j ≤ n : tj /∈ {1, 2}} be the respective set of first-, second-, and third-party agents for ~t. Since ~t ∈ T2 implies |Id1(~t)| = |Id2(~t)|, there must be more third-party agents that prefer 2 1 than those that prefer 1 2. For every d |Id3(~t)|+12 e ≤ k ≤ |Id3(~t)|, we thus define Z~t,k ⊆ {1, 2}n as the set of all vectors ~z where the number of 2’s in Id3(~t) is exactly k.
Z~t,k = {~z ∈ {1, 2} n : ∀j ∈ Id1(~t) ∪ Id2(~t), zj = tj , and |{j ∈ Id3(~t) : zj = (2 1)}| = k}
By the law of total expectation and noting the independence of ~Q’s components, we have
Pr(E1)× E[D+(P ) | E1] = ∑ ~t∈T |Id3(~t)|∑ k=d |Id3(~t)|+12 e ∑ ~z∈Z~t,k Pr(~T = ~t, ~Z = ~z) n∑ j=1 Etj ,zj (2)
where Etj ,zj = E~Qj [~u(Qj , 1) − ~u(Qj , 2) | Tj = tj , Zj = zj ] is the expected difference in welfare between alternatives 1 and 2 for an agent j with Tj = tj and Zj = zj .
Step 2: Compute expected welfare difference per agent. We note that Etj ,zj only depends on the values of tj and zj , but not j. The cases for (tj = zj = 1) and (tj = zj = 2) negate each other with E1,1 + E2,2 = 0. If tj /∈ {1, 2} and zj = 1, then Etj ,1 = η > 0 because u2 > um. Similarly, it follows that if tj /∈ {1, 2} and zj = 2, then Etj ,2 = −η. Therefore Equation (2) becomes∑
~t∈T |Id3(~t)|∑ k=d |Id3(~t)|+12 e ∑ ~z∈Z~t,k Pr(~T = ~t, ~Z = ~z)× (|Id3(~t)| − 2k)η (3)
where we’ve inserted ∑n j=1Etj ,zj = |Id1(~t)|E1,1 + |Id2(~t)|E2,2 − kη + (|Id3(~t)| − k)η.
Step 3: Simplify and solve. Note that Id3(~T ) is equivalent to the sum of n i.i.d. binary random variables, each of which is 1 with probability m−2m ≥ 1 3 . By Hoeffding’s inequality, with exponentially small probability we have Id3(~T ) < 16n. Therefore, we can focus on the Id3(~T ) ≥ 1 6n case in (3), which, by denoting β = |Id3(~t)| for ease of notation, becomes:
≤ e−Ω(n) + ∑
~t∈T2:β≥ 16n β∑ k=d β+12 e ∑ ~z∈Z~t,k Pr(~T = ~t, ~Z = ~z)× (β − 2k)η
= e−Ω(n) − η ∑
~t∈T2:β≥ 16n
( 1
2
)β (⌈ β + 1
2
⌉)( β⌈ β+1
2 ⌉) (4) = e−Ω(n) − η
∑ ~t∈T2:β≥ 16n Pr(~T = ~t)×Θ( √ n) (5)
= e−Ω(n) − ηPr ( ~T ∈ T2, Id3(~T ) ≥ 1
6 n
) ×Θ( √ n) ≤ −Ω(1) (6)
where Equation (4) follows from Claim 1 (see Appendix A.3) and Equation (5) follows from Stirling’s approximation (see Appendix A.4). We get Equation (6) since Pr(~T ∈ T2) is equivalent to the probability of two-way ties under plurality w.r.t. IC, which is known to be Θ(n−1/2) [Gillett, 1977]. This concludes Lemma 2, and a more full proof can be found in Appendix A.2.
Lemma 3 (α = 3). Given m ≥ 3 and a utility vector ~u, for any W ⊆ A with |W | = 3 and any n ∈ N, we have PoA(W ) = o(1).
We defer the proof of Lemma 3 to Appendix A.5.
Lemma 4 (α ≥ 4). Given m ≥ 4 and a utility vector ~u, for any W ⊆ A with |W | ≥ 4 and any n ∈ N, we have PoA(W ) = o(1).
Proof. The lemma follows after noticing the following. Firstly, we note that Pr(PW(P ) = W ) = Θ(n−1.5) following a similar proof using the polyhedron representation as described in the proof of Lemma 3 (see Appendix A.5). Second, for any profile P , D+(P ) = O(n).

heading: 5 Conclusions and Future Work
text: This paper studies the effects of strategic behavior in iterative plurality voting in terms of its adversarial loss – the difference in social welfare between the truthful winner and the worst-case equilibrium winning alternative. Our results naturally extend those of Brânzei et al. [2013] by utilizing rank-based utility functions whose utility vector ~u differs from the iterative positional scoring rule r~s. We prove that iterative plurality has an adversarial loss linear in the number of agents in the worst case (Theorem 1). By distributing agents’ preferences according to the impartial culture, we overcome this negative result and prove a constant order improvement in social welfare regardless of the order of agents’ repeated strategic manipulations (Theorem 2). Even through our main result only works for IC, we are not aware of previous theoretical work on the expected performance of iterative voting under any distribution. Generalizing this study to other dynamics, utility functions, and families of distributions are interesting and important directions for future work.
For example, many iterative voting rules do not necessarily converge, but all games with bestresponse dynamics have cycles or steady-state equilibrium over agents’ joint pure-strategy action space L(A)n [Young, 1993, Meir, 2016]. Such games may instead be characterized by the worstcase ratio (or difference) between the social welfare of the game’s truthful outcome and the average welfare of a stationary distribution over each cycle – known as the price of sinking [Goemans et al., 2005]. Bounding the welfare in each cycle could plausibly extend the DPoA, left for future work.
A second branch of future work could compare the iterative voting equilibrium winners’ social welfare to that of the optimal winner, rather than the truthful outcome – known as the price of stability [Anshelevich et al., 2004, Tsang and Larson, 2016]. This is related to work in distortion which modifies agents’ utility functions to be normalized [Procaccia and Rosenschein, 2006, Caragiannis and Procaccia, 2011] or embedded in a metric space [Anshelevich et al., 2018].
A third branch of future work could generalize the choice of agents’ ranking distribution from IC, for example using smoothed analysis [Xia, 2020]. Determining the robustness of our theoretical results to other preference distributions, especially to those based on real-world data, would provide further insight into the effects of strategic manipulation on electoral outcomes. It would be interesting to see whether a greater proportion of i.i.d. preference distributions yield EADPoA results similar or dissimilar to that of IC.

heading: Acknowledgements
text: We thank anonymous reviewers for helpful comments. This work is supported by NSF #1453542, ONR #N00014-17-1-2621, and a giftfund from Google. J. Kavner acknowledges Abigail Jacobs for helpful discussions during the earliest stage of this work.

Review summaries:
The authors study the welfare of Nash equilibria reached via best-response dynamics from the truthful profile. For worst-case profiles, these equilibria can have linearly less welfare than the truthful outcome. Assuming impartial culture, however, the expected welfare of these equilibria is higher than the welfare for the truthful outcome, assuming rank-based utilities.

This paper studies iterative voting in which agents' utility vector could be different from the scoring vector. The authors show that PoA bounds is linear in the number of agents. Surprisingly, in an i.i.d. environment, the equilibrium winners have a constant order welfare advantage over the truthful winner.