Strategic Behavior is Bliss: Iterative Voting Improves Social Welfare
Authors: Joshua Kavner
Lirong Xia
Venue: NeurIPS 2021 Poster (2021)
Keywords: computational social choice
iterative voting
best-response dynamics
price of anarchy

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 worst- and 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. 

Strategic Behavior is Bliss: Iterative Voting Improves Social Welfare
Joshua Kavner
Lirong Xia Department of Computer Science Rensselaer Polytechnic Institute Troy, NY 12180 xialirong@gmail.comm com
Department of Computer Science Rensselaer Polytechnic Institute Troy, NY 12180 Navnej@rpi.er edu
Abstract
Recent work in iterative voting has defined the additive dynamic price anarchy (ADPoA) as the difference in social welfare between the truthful and worst-case equilibrium profiles resulting from repeated strategic manipulations. While iter- ative plurality has been shown only return alternatives with most less initial votes than the truthful winner, it is less understood how agents' welfare changes in equilibrium. To this end, differentiate agents' utility from their nipulation mechanism and determine iterative plurality's ADPoA in the worst- and average-cases. We first prove that the worst-case ADPoA 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 strategic manipulation.
Introduction
Voting is one of the most popular methods for a group of agents make a collective decision based on their preferences. Whether decision is for high-stakes presidential election or routine luncheon, agents submit their preferences and voting rule applied to select winning alternative.
One critical flaw of voting is its susceptibility to strategic manipulations. That is, agents may have incentive misreport their preferences (i.e. votes) obtain more favorable outcome. Un- fortunately, manipulation is inevitable under any non-dictatorial single-round voting systems when there are three or more alternatives, as recognized by the celebrated Gibbard-S Slbbard-Sattertwwall theo- rem [Gibbard, 1973, Satterthwaite, 1975]. Consequently, decades of research sought to deter ma- nipulation, especially by high computational barriers [Bartholdi al., 1989, Faliszewski al., 2010, Faliszewski and Procaccia, 2010]; see [Conitzer and Walsh, 2016] for recent survey of the field.
While there is large body of literature manipulation of single-round voting systems, sequential and iterative voting procedures are less understood. Indeed, these procedures occur in a variety of applications, such Doodle 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 al., 2015]. Our key question is:
What is the effect of strategic behavior in sequential and iterative voting?
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, Brânzei et al., 2013, Grandi al., 2013, Obraztsova et al., 2013, Meir al., 2014, Rabinovich et al., 2015, Obraztsova al.,
35th Conference on Neural Information Processing Systems (NcurIPS 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 Bránzei al. [2013]'s work that introduced and characterized the addi- tive 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 's equilibrium winners when an adversary min- imizes aggregate social welfare by controlling both the order in which agents make their strategic manipulations and agents' truthful preferences altogether. In particular, Brâ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.
1.1 Our Contributions
We address the key question discussed above in the iterative voting framework, first proposed by Meir et al. [2010], by characterizing Brånzei et al. [2013]'s ADPoA under plurality dynamics and rank-bused utility functions that differ from the iteration method. Given m 2 3 alternatives, a ranked-based utility function is characterized by a utility vector ūī such that each agent receives u, 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 ab- solve the need for the mechanism's 's center to know こ 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 2 3 and utility vector ū,, the ADPoA is ((n) for n agents. Therefore, the positive result achieved by Brânzei et al. [2013] is not upheld if e 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 generated from a probability distribution. Our second main result (Theorem 2) is positive and surprises us: for any fixed m 2 3 and utility vector iž, the EADPoA is (11 when agents' preferences are i.i.d. uni- formly 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 accord- ing to their potential winners- - the alternatives that can be made to win by incrementing their plural- ity 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 head-to sond-to-heat head competition (Lemma 1). This type of "self selection" " improves the expected social welfare over truthful plurality winner by 2(1) (Lemma 2). When there three 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="=') [Xia, 2021]), the overall social welfare is improved in expectation. We provide an experimental justification of our second main result in Appendix B.
1.2 Related Work and Discussions
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- he-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- -eunter-examplss when allowing agents to manipulate simultaneously, using better- instead of best-replies, or weighing agents' votes unequally. Lev and Rosenschein 2211] 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 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 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 re- sults according to different voting rules. Tsang and Larson [2016] use these concepts to simulate iterative plurality on 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 abstain from voting. Xia and Conitzer [2010] characterized the subgame perfect Nash equilibrium of 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 con- vergence 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 better- response dynamics in weakly acyclic games, which encapsulate potential and dominance-solvee games, and demonstrate bounds on finding their Nash equilibrium. The relationship between itera- tive 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 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 similar gain when agents have single-peaked preferences, are embedded on 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- -onsstrategyproff mechanisms in other social choice domains, such multi-issue voting [Bowman et al., 2014, Grandi et al., 2020].
2 Preliminaries
Basic setting. Let A = [m] A {l..... m) denote the set of m 2 3 alternatives and n E N denote the number of agents. We denote by L(A) the set of all strict linear orders over A and use R2 E [(A).j j < n to represent agents' preference rankings. Preferences are aggregated into profiles P [R...... ...., R,), and we use top( It,) E A to denote agent j's top preferred alternative. For any pair of alternatives a, b E A, we use Pla > b] to denote the number of agents that prefer a to in P.
Integer positional scoring rules. An (integer) positional scoring rule Fry is characterized by an integer scoring vector ğ (si...., E 2mh with 81 2 $2 2 2 8m 2 0 and $1 > Sm- For example, plurality uses the vector Sptu = (1, . ... 0), veto uses (1, (1...., 1, 0). and Borda uses (m 1, m 2,..., 0). In this work we focus on the plurality rule Tptu Trp... and define the score of a E A according to profile P as sp(a)= = ΣREP 1 [rop(()) = a}. We use the resolute function Tyua( (P= = arg max.c_ (a) to select a single winning alternative, breaking ties lexicographically and favoring that with the smallest index. Assume Tplu unless stated otherwise.
3

---

Rank-based utility and additive social welfare. We assume that agents have additive utilities characterized by a
utility vector i7 = (WI,..., .,. Um E 2 with di 2 ... um - 0 and u1 > Um- Like the scoring rule, each agent j gets R a) = uN utility for the alternative E A ranked 7t in Ry. Unlike prior work, however, we do not presume that is the same as the scoring vector g. We define the additive social welfare of according to P as SW SWa(P.a) = شド= ū RRy a).
Iterative plurality voting. Given agents' truthful preferences P. we consider an iterative process of profiles (P*))20 that describe agents' reported preferences (i.e. votes) (Ri...., R,, R2) over time. For each round 6, one agent j is chosen by a scheduler & to make a myopic improvement step, denoted by R2 2 R'.. to their report. This step is called a better-response if prefers the new outcome r( R R( to the prior one r rRRj, R'y)). whereas it is a best-response (BR) if, additionally, j could not have achieved more preferred outcome than manipulating to It', from Pt.
Following Brânzei al. [2013], we limit our discussion strategic manipulations beginning from the truthful profile pD P. This guarantees that all improvement steps R2; 4 R2 from profile pr pd are best-responses that change the iterative winner: r(P') + top(Rt)) r(P") top to)(R As result, any sequence of BR steps converges in (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( as the set of equilibrium winning alternatives corresponding to all NE reachable from P via some BR sequence. That is,
EW(P) (r(P") F BR sequence from P leading 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 BR step that increases their plurality score, if the agent's ranking permits. Following [Rabinovich et al., 2015], we have:
PW(P) = {a a
(p((a) = sr(r(P) - 1, a is ordered before r r(P) (p((a)= = sr (r(()))
a is ordered after r r(P) } u (r(P))
where the ordering is lexicographical for tie- fie-breaking. Reyhani and Wilson [2012] proved that the potential winning set is monotonic in t: Vt 2 O. PW(pt+1) S. (WP)), which implies EW(P) S PW(P"). As result, iterative plurality voting acts like a sequential tie-breaking mechanism whose outcome follows from the scheduler é. The following example demonstrates this section's 's concepts.
Example 1. Let
9,
3, and consider the truthful profile P defined with R2 R2 = R3
[1 > 3 > 2). R1 = Rs = [2 > 3 > 11. Rs = [2 > 1> 3). and R7 = Rs Rg = [3 > 2 > 1l. We observe from the plurality scores (1p(1), sp(s))2)))))))))
sp s3)) = (3, 3.33 that r(P) and PW (P)
{1, 3),, representing three-way tie. Next, Figure 1 describes the five BR sequences from P:
6 (11132(1)333)1)
5 (1133(3)
(111(3)22333/3)
5
6
(1112[3)2333)33
(11123[11333)1)
(111(3]31333/3)
(111222333)(1)
(111222(2]33)22)
8
(1112223[2]3)2}
(11122233(2])2)
Figure 1:
Five BR sequences in Example The tuples denote agents' reported top alternatives; the winner appears in curly brackets; arrows denote which agent makes each BR step and the updated report is emphasized.
We therefore conclude EW(P) = 32.3). Moreover, consider the utility vector ī = (uj, u2, Uz). Then the social welfare for each alternative is (SWa(P,1) SWa(P. 2), SWa(P,3) (3u1 +1u + 5w3, 3u1 + 3uz + 3u3, 3uy + 5uz + lua).
'Note that ó must select BR step if one exists [Apt and Simon, 2015].
"These are characterized as Type or direct best replies in the literature [Meir, 2016J. Conversely, Type 3 best-responses (r(P") top RR)) A r(P") = top( (R )) do not occur in improvement sequences from the truthful profile. Note that no BR step is of Type 2 (r(P") top((t)) A r(P") A top(H?)).

---

3 Additive Dynamic PoA under General Utility Vectors
How bad are equilibrium outcomes, given that strategic manipulations inevitably occur by the Gibbard-Satte Satterthwaite theorem [Gibbard, 1973, Satterthwaite, 1975]? Bränzei et al. [2013] sought to answer this question by defining the additive dynamic price of anarchy (ADPoA) as the adversar- ial loss the difference in welfare between the truthful winner r(P) and its worst-case equilibrium winner in EW according to the worst-case P. To motivate this concept, consider users of a website that regularly log in and update their preferences for election. 'Thn the ADPoA bounds the welfare loss a virtual assistant can recommend when users should make their changes.
Brânzei et al. originally defined the ADPoA for a given positional scoring rule rş and additive social welfare function respecting = 8. In this case, the ADPoA of plurality was found to 1, while the (multiplicatiie) DPoA of veto is (m() and Borda is (nx) for m 4 [Brâ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, ADPoA for plurality of means that for any truthful profile, the difference in initial plurality scores of any equilibrium winner is most utility vector ie to differ from 8, we find in Theorem that the ADPoA is quite poor at (n)).
less that of the truthful winner. However, when we relax the
First we recall Brâ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) [Brânzei et al., 2013]). Given positional scoring rule тæ, utility vector य = (u1...., Mm)) over m 2 3 alternatives, and truthful profile P. the adversarial loss starting from P is defined
D (P) SWa(P, (rr(())))))))) millaeE(PP) SWa(P,a)
The additive dynamic price of anarchy (ADPoA) r and i under agents defined as ADPoA(Ts: U. n)) maXpe D* (P)
We will use ADPoA and D to denote ADPoA(rplu: ū. n) and D Tptu, when the context is clear." For example, we saw in Example that r(P) = and CW(P) = 3). Then
D+ = max SWa(P, 1) SWa( SWa( SWa(P,3)
max{ (3u) + lu2 + 5ug) (3m) + 3u2 + 3ua)
(3u1 + luz + 5ug) (3u1 + 5u2 + 1us)
2 u3) < 0
Therefore the social welfare of both equilibrium winners is at least that of the truthful winner. In Theorem below we'll see this conclusion hold in expectation. For the worst case profile P. how- ever, 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 2 and utility vector ī (uI,...,u.,, Then ADPoA(T ā. is (n)). Specifically, Vn >> 2m,
ni (2 < ADPoA(Tppus n) S nui m
(u2 - Um)
Proof. The ADPoA is trivially upper bounded by the maximum social welfare attainable by any truthful profile P. For example, if is defined with R2 (1, .m) Vj n, then VP L(A)",
D+(P)= = sw a r())) min SW P. a) s swa(P, & SWa(P, = nu1
To lower bound ADPoA, we will construct a profile P with a two-way tie between alternatives 1,2 E AA such that D* PP) (w2 Wmm) (m - 2). This implies the desired lower bound of
ADPoA max PEC(A)) D+ (P) Z D+ (u2 un))
(m
"Te superscript '+' denotes additive measure instead of multiplicative in the classical definition of PoA.
5

---

Fix m 2 3 and let n > 2m be even. We denote by k arg - (4g - 4/11) the position in with the minimal difference adjacent coordinates. Let a = 1 (n + m 2) and 3 (m 2), such that 2a + 8. We will then construct P as follows, with agents that prefer first and 2 last, a agents that prefer first and 1 second, (3 1) agents that prefer 1 second and 2 last, and ( + 1) agents that prefer 2 in their ranking's s k-th position and in their ranking's s (k 1)-th position. We can see here that sp(1) sp(2) = a. and Vc > 2, sp(c)
1, thus
guaranteeing the two-way tie. Therefore r r(P)
and P(2 > 1] a +1
P[1 > 2]. This implies (W( = {2) by the following lemma.
Lemma 1. Let m 2 and a, b A such that a is ordered before b in tie tie-breaking. Suppose PW(P) = {a, b) for some truthful profile P. Then EW(P) = {a} if Pla > bj 2 Plb > a); otherwise EW(P) {b}.
The lemma's ' proof can be found in Appendix A.I. As a result,
D (P) = SW a (P.1) SWa(P,2
2-- - (u2 - um) -
= a(u2 - um) + (2
+1 (ux - uk+1)
2
2 (u2 - Um )m - 2) = (U2 um) (n (n- m
(m- -
2 (u2 - -u
m
m
where the first inequality holds because (ug uk+ 1 E (u2 mm)
Expected Additive DPoA
In this section we extend Brânzei et al.' ADPoA notion to account for the average-case adversarial loss for positional scoring rule rg, 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 C(A)", known as the Impartial Culture distribution T. IC".
Definition 2 (Expected Additive DPoA (EADPoA)). Given positional scoring rule rs. a utility vector 7 over m 2 3 alternatives, n agents, and distribution Tn over [(A)" for agents' prefer- ences, the expected additive dynamic price of anarchy is defined as follows:
FADPoA(rs, U. U, m.) Ep DD [P=
Like before, we will use EADPoA and D* to denote EADPoA(rpla ił, n, IC") and D+ "p respec- tively. We similarly fix rank-based utility vector 7 that may differ from the scoring rule 5, but we will not presume the following theorem that this is known by the iterative plurality mechanism. In the subsequent proof, we will also drop the subscript "P IC"h to simplify notation when the context is clear.
Theorem 2. Fix m and utility vector ã (uI,..., Unn) For any n E N we have
EADPoA(Tptus Ut n, 1C -Q((1)
Proof. The key idea is to partition L(A)" according to each profile's potential winner set. More precisely, for every W A with W A 0, define:
PoA(W) Pr(PW W) E (P) PW(P) W]
By the law of total expectation, then
EADPoA = EDD -"'I EWCAIWEF PoA(W)
(1)
where a denotes the number of potential winners in P. it straightforward to see that when = 1. any profile with PW(P) = 1 is already a NE, which implies D (P)( = 0. The rest of the proof proceeds as follows. For any e N will show in Lemma 2 that for VW A with [W]

---

C A with |W| = 3 (Lemma 3) and [W] 2 (if m 2 4: Lemma 4). Recalling that m is fixed, the total number of subsets of A is viewed as constant. Finally, these results combine to conclude
(o)(W) = -9(1). We will then demonstrate that (o)(W) = o(1 vW
EADPoA
2(1 (1 (1(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 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 a = 2 case by any of the a 2 3 cases, the adversarial loss overall remains negative in expectation.
The remainder of this section is devoted to detailing the proof behind the a = 2 case (Lemma 2). We declare the 3 case without proof (Lemma 3) and briefly prove the 2 4 case (Lemma 4). Lemma 2 (a = 2). Given m 2 3 and a utility vector ū, for any W S A with [W| = 2 and any n E N. we have (W)(WW) = (1)).
Proof. Without loss of generality let W = {1,2} and suppose U2 Um There are two possible cases of PW( = 2]: either (1) = s2( or (1(1) + == ====ppp 82(2), which we'll llll denote by & and &g respectively. This suggests PoA(W)- = Pr(E)) E D
Pr(E)) B D (P) Ez].
We'll focus on the first case where alternatives 1 and 2 are tied, since the latter's 's proof is similar.
We believe this proof is challenging due the dependence in agents' rankings once we condition on profiles that satisfy two-way ties (i.e. &. As 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 Bayesian network to further condition agents' rankings based on two properties: the top ranked-alleernative 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 (P) | E efficiently.
At a high level, there are two conditions for a profile P to satisfy ε and have non-zero adversarial loss. First, the profile must indeed be a two-way tie. This is represented in Step I below by iden- tifying each agent j's top-ranked alternative ij E AA and conditioning D+(P) on a specific vector of top-ranked alternatives E To S. AA" a set corresponding to all profiles satisfying &, Second, by Lemma 1, the profile should satisfy P(2 > 1] 2 P > 2]. This is represented Step by identifying an indicator 2j E {1,2] to suggest whether > 2 or 2 >- respectively. We fur- ther condition D+ (P) on a specific vector 5 E Σr,, a set corresponding to all profiles in E, with
k = P(2 > 1] 2 P[1 > 2] n k. Once we condition D+ to satisfy these two condi- tions, identify the expected difference in welfare between the alternatives Ea,,,, for each agent j conditioned on 44. 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. represent agent j's ranking distribution (i.i.d. uniform over ((A)) by a Bayesian network of three random variables (see Figure 2). First, T3 E A represents j's top-ranked alternative and follows uniform distribution. Second, Z, {1, 2} indicates whether (1 >5 2) or (2 >, 1) conditioned on Tj. and has probability {0.5, 0.5} if T & {1,2). Third, 2j follows the uniform distribution over linear orders that uphold both T; and Zy. It is not hard to verify that (unconditional) Q, follows the uniform distribution over ((A), which implies that
Q (Q1, (Q1...., Qu.) follows the same distribution P.
Step 1: Identify profiles that satisfy En Let T2 S. [m]] denote the set of top-ranked alternative vectors i' = (t....., tn)) such that alternatives and have the maximum plurality score. Then E holds for Q if and only if T takes a value in Tz.
To {i'E [m]" v3 < i S m, 10 1g = 1) 10: :, = 23 10: = 0]
7

---

T₁
T2
T
Z
Z
Z
Q₂
Figure 2: Bayesian network representation of P as Z, and @ for the a 2 case.
Conditioned on agents' top-ranked alternatives being & E T2, have by Lemma 1 that (Q) is non-zero if and only if Q[2 > 1] > Q[1 > 2]. Let Id (8) = (i S n 12 = 1), Idg(() = (i S n: I, = =2], and ld)(2) = [j S n: : 1 & [1,2)} be the respective set of first-, second,, and third-party agents for Since f E To implies [Id (t) = [ld2(t), there must be more third-party agents that prefer 2 > than those that prefer
2. For every [ k [Id) we thus define 2G, S [1,2]" as the set of all vectors 2 where the number of 2's in Idg (f) is exactly k.
2
ir = {i [1,2}" .jj E Id1 (f) (d), 2j tj, and {j E Ids 2j (2 - 1) = k}
By the law of total expectation and noting the independence of Q's components, have
[d)
Pr(Ei) R
D+ (P) &i] = Σ
Σ
P, 2) Σ Fagas
TET km (0,00 SE
where E,y,=; E i7( Ri(Q,,1 1) ūi) 2) T = 1, Zj =25] is the expected difference in welfare between alternatives and 2 for an agent with T, = and Z₁ 2z.
Compute expected welfare difference per agent. We note that Fay only depends on 1) and (1, = 2j negate each other with Σ + E.. = 0. If t $ {1, 2} and žj = 1, then Et, = > 0 because > Um Similarly, it follows that tj & [1,2] and 2j = 2, then E,,, = -7. Therefore Equation (2) becomes
Step 2:
the values of tú and 2j. but not j. The cases for (tj 2j
(d)
Σ
Σ
Pr(T F, 7 2) x ([Ids(f) 2k)r
(3)
TET k= My SE2E,
where we've inserted Σj=1 Ein,e [t) + (dd(t)](22 kn (Idd((t) k)n.
Step 3: Simplify and solve. Note that Idg(T) is equivalent to the sum of i.i.d. binary random
variables, each of which is with probability m- N 1.4 By Hoeffding's s inequality, with exponen-
m
tially small probability we have Idx(T') < nn. Therefore, we can focus the Id, I case in (3), which, by denoting [fd for ease of notation, becomes:
Se Se-
Σ
Σ
P x) (B 2k)n
=
TeT2:02 in
k= |= 1111 BEZT,
1 3
(1&
11+11 1
1)
8
-((m)
n
Σ
2
8+1
(4)
fn
= (((m)
Σ
Pr(T = 1) x O(V
(5)
i pm
1 " x x((V) - -2(1)
=c- -(nn - Pr
T Idg
(6)
8

---

where Equation (4) follows from Claim 1 (see Appendix A.3) and Equation (5) follows from Stir- ling's approximation (see Appendix A.4). We get Equation (6) since Pr(T' E T2) is equivalent to the probability of two-way ties under plurality w.r.t. IC, which is known to be (n22/2) [Gillett, 1977]. This concludes Lemma 2, and a more full proof can be found in Appendix A.2.
3). Given m 3 and a utility vector for any W C A with [ 3 and any Lemma 3 (a-
N. we have PoA(WW) o(1).
We defer the proof of Lemma to Appendix A.5.
Lemma 4 (a 2 4). Given m 2 4 and a utility vector iz for any W S A with [W] 2 4 and any n E N, we have (o)(W)) = o(1).
Proof. The lemma follows after noticing the following. Firstly, we note that Pr(PW(() W)
(n (1)) following 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) = (n))
5
Conclusions and Future Work
This paper studies the effects of strategic behavior in iterative plurality voting in terms of its adver- sarial loss the difference in social welfare between the truthful winner and the worst-case equi- librium winning alternative. Our results naturally extend those of Brânzei et al. [2013] by utilizing rank-based utility functions whose utility vector i7 differs from the iterative positional scoring rule rs. 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 the impartial culture, 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 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 best- response dynamics have cycles or steady-state equilibrium over agents' joint pure-strategy action space ((A))" [Young, 1993, Meir, 2016]. Such games may instead be characterized by the worst- case 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 the price of sinking [Goemans 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 wel- fare 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 metric space [Anshelevich et al., 2018].
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 greater proportion of i.i.d. preference distributions yield EADPoA results similar or dissimilar to that of IC.
Acknowledgements
We thank anonymous reviewers for helpful comments. This work is supported by NSF #1453542, ONR #N000114-7-1-2621,, and a giftfund from Google. J. Kavner acknowledges Abigail Jacobs for helpful discussions during the earliest stage of this work.

---

References
Elliot Anshelevich, Anirban Dasgupta, Jon Kleinberg. Êva Tardos, Tom Wexler, and Tim Roughgar- den. The price of stability for network design with fair cost allocation. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 295-304, 2004.
Elliot Anshelevich, Onkar Bhardwaj, Edith Elkind, John Postl, and Piotr Skowron. Approximating Optimal Social Choice under Metric Preferences. Artificial Intelligence, 264(27-51), 2018.
Krzysztof R Apt and Sunil Simon. A classification of weakly acyclic games. Theory and Decision, 78(4):501-524, 2015.
John Bartholdi, III, Craig Tovey, and Michael Trick. The computational difficulty of manipulating an election. Social Choice and Welfare, 6(3):227-241, 1989.
Sven Berg. Paradox of voting under an urn model: The effect of homogeneity. Public Choice, 47 (2)3777-387, 1985.
Clark Bowman, Jonathan K Hodge, and Ada Yu. The potential of iterative voting to solve the separability problem in referendum elections. Theory and decision, 77(1):111-24,, 2014.
Simina Brânzei, loannis Caragiannis, Jamie Morgenstern, and Ariel D. Procaccia. How bad is selfish voting? In Proceedings of the 27th AAAI Conference on Artificial Intelligence, pages 138-144, 2013.
Ioannis Caragiannis and Ariel D. Procaccia. Voting almost maximizes social welfare despite limited communication. Artificial Intelligence, 1755611665-1667, 2011.
Samir Chopra, Eric Pacuit, and Rohit Parikh. Knowledge-theoretie properties of strategic voting. In European Workshop on Logics in Artificial Intelligence, pages 18-30. Springer, 2004.
Vincent Conitzer and Toby Walsh. Barriers Manipulation Voting. Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel Procaccia, editors, Handbook of Computational Social Choice, chapter Cambridge University Press, 2016.
Yvo Desmedt and Edith Elkind. Equilibria of plurality voting with abstentions. In Proceedings of the 11th ACM conference on Electronic commerce, pages 347-356, 2010.
Keith Dowding and Martin Hees. In praise of manipulation. British Journal of Political Science, 38: 1 15, 01 2008. doi: 10. 10.1007/5000712330 22300000XX.22
Ulle Endriss, Svetlana Obraztsova, Maria Polukarov, and Jeffrey S. Rosenschein. Strategic voting with incomplete information. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI' 16, page 236-242. AAAI Press, 2016.
Alex Fabrikant, Aaron Jaggard, and Michael Schapira. On the structure of weakly acyelic games. In Spyros Kontogiannis, Elias Koutsoupias, and Paul G. Spirakis, editors, Algorithmic Game Theory, pages 126-137, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg.
Piotr Faliszewski and Ariel D. Procaccia. Al's manipulation: Are winning? Al Magazine, 31(4):53-64, 2010.
Piotr Faliszewski, Edith Hemaspaandra, and Lane A. Hemaspaandra. Using complexity to protect elections. Communications of the ACM, 53:74-82, 2010.
Allan Gibbard. Manipulation of voting schemes: A general result. Econometrica, 41:587-601, 1973.
Raphael Gillett. Collective Indecision. Behavioral Science, 22(6):383-390, 1977.
M. Goemans, Vahab Mirrokni, and Vetta. Sink equilibria and convergence. In 46th Annual IEEE Symposium on Foundations of Computer Science (55), pages 142-151, 11 2005.
10

---

Umberto Grandi, Andrea Loreggia, Francesca Rossi, Kristen Brent Venable, and Toby Walsh. Re- stricted manipulation in iterative voting: Condorcet efficiency and borda score. In International Conference on Algorithmic Decision Theory, pages 181-192. Springer, 2013.
Umberto Grandi, Jéröme Lang, Ali Ozkes, and Stéphane Airiau. Voting behavior in one-shot and iterative multiple referenda. Available at SSRN, 2020.
Aaron Koolyk, Tyrone Strangway, Omer Lev, and Jeffrey S. Rosenschein. Convergence and quality of iterative voting under non son-sccning rules. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17, pages 273-279, 2017.
Omer Lev and Jeffrey S Rosenschein. Convergence of iterative voting. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems- Volume pages 611 618, 2012.
Reshef Meir. Strong and weak acyclicity in iterative voting. In Martin Gairing and Rahul Savani, editors, Algorithmic Game Theory, pages 182-194, Berlin, Heidelberg, 2016. Springer Berlin Heidelherg.
Reshef Meir, Maria Polukarov, Jeffrey S. Rosenschein, and Nicholas R. Jennings. Convergence to Equilibria Plurality Voting. Proceedings of the National Conference on Artificial Intelligence (AAAI), pages 823 828, Atlanta, GA, USA, 2010.
Reshef Meir, Omer Lev, and Jeffrey S. Rosenschein. Local-Dominance Theory of Voting Equilib- ria. In Proceedings of the 15th ACM Conference on Electronic Commerce, pages 313-330, Palo Alto, CA, USA, 2014.
Dov Monderer and Lloyd S. Shapley. Potential games. Games and Economic Behavior, 14(1): 124-143, 1996.
Svetlana Obraztsova, Evangelos Markakis, and David R. M. Thompson. Plurality voting with truth- biased agents. In Berthold Vöcking, editor, Algorithmic Game Theory, pages 26-37, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.
Svetlana Obraztsova, Evangelos Markakis, Maria Polukarov, Zinovi Rabinovich, and Nicholas R. Jennings. On the convergence of iterative voting: How restrictive should restricted dynamics be? In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, AAAI'15, page 993-999, 2015.
Ariel Procaccia and Jeffrey S. Rosenschein. The distortion of cardinal preferences in voting. In Proceedings of the 10th International Conference Cooperative Information Agents, CIA'06, page 317-331, Berlin, Heidelberg, 2006. Springer-Verlag.
Zinovi Rabinovich, Svetlana Obraztsova, Omer Lev, Evangelos Markakis, and Jeffrey Rosenschein. Analysis of equilibria in iterative voting schemes. Proceedings of the 29th AAAI Conference on Artificial Intelligence. AAAI Press, 2015.
Annemieke Reijngoud and Ulle Endriss. Voter response to iterated poll information. In Proceedings of the Eleventh International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), volume 1, pages 635-644, 06 2012.
Reyhaneh Reyhani and Mark C. Wilson. Best reply dynamics for scoring rules. In Proceedings of the 20th European Conference on Artificial Intelligence, ECAI' page 672-677, NLD, 2012. IOS Press.
Mark Satterthwaite. Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of Economic Theory, 10: 187-217, 1975.
David R.M. Thompson, Omer Lev, Kevin Leyton-Brown and Jeffrey Rosenschein. Empirical analy- sis of plurality election equílibria, In Proceedings of the Thirteenth International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pages 391-398, Paris, France, 2013.

---

Alan Tsang and Kate Larson. The echo chamber: Strategic voting and homophily in social networks. In Proceedings of the 2016 International Conference on Autonomous Agents and Multiagent Sys- tems, AAMAS 16, page 368-375, 2016.
Lirong Xia. The Smoothed Possibility of Social Choice. In Proceedings of NeurlPS, 2020.
Lirong Xia. How Likely Are Large Elections Tied? In Proceedings of the 22nd ACM Conference on Economics and Computation, Budapest, Hungary, 2021.
Lirong Xia and Vincent Conitzer. Stackelberg voting games: Computational aspects and paradoxes. In Proceedings of the National Conference on Artificial Intelligence (AAAI), pages 921-926, At- lanta, GA, USA, 2010.
H Peyton Young. The Evolution of Conventions. Econometrica, 61(1):57-84, January 1993.
James Zou, Reshef Meir, and David Parkes. Strategic voting behavior in doodle polls. In Proceed- ings of the 18th ACM Conference on Computer Supported Cooperative Work Social Computing. CSCW '1, page 464 472, New York, NY, USA, 2015.
12


Reviews:
[{"review_id": "klJK600jPwZ", "reviewer": "Reviewer_xnBa", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is well-written, clear, and easy to follow. It is very interesting to see that in theory, when agents' utility vector could be different from the scoring vector, strategic behavior can help improve social welfare when agents are i.i.d.. However, the setting, in which agents' utility vector could be different from the scoring vector, needs further motivations and justifications; and the reviewer is curious about the social welfare performance under strategic behavior against optimal benchmark instead of the truthful benchmark.\n\nComments:\n\n*. There is little motivation on when and why agents' utility vector could be different from the scoring vector. If the agents' utility vector is public, then it is unclear why the voting mechanism does not use the agents' utility vector as the scoring vector. The reviewer guesses one possible motivation is that agents' utility vector is unknown. It seems that Theorem 2 works even when the utility vector is unknown. Could you confirm?  \n\n*. When the agents' utility vector is unknown, is it possible to design a truthful voting mechanism to achieve optimal social welfare? If not, what is the best approximation one can achieve? These might be interesting questions to consider if they are not solved in the literature.\n\n*. Theorem 1 looks a bit strange as it has no requirement on n, the number of voters. When n < 2m, the lower bound could be negative?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "*. The comparison is against the benchmark under truthful bidding, which is generally different from the optimal benchmark when the utility vector is different from the scoring vector. Therefore, it is possible to see improvement under strategic behavior against the truthful benchmark. It would be better to highlight this fact in the fact somewhere. Is there any result regarding the approximation under strategic behavior against the optimal benchmark?", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "chkfy0Dl_yi", "reviewer": "Reviewer_kFVz", "summary": "The authors study strategic voting in the context of iterative plurality voting, in which voters may update their plurality votes over multiple rounds of voting. They study the additive dynamic price of anarchy (ADPoA), and show that in the worst-case, ADPoA can be linear in the number of agents, but for the case of impartial culture, equilibrium winners actually have a constant order advantage over the truthful winner, which is an instance of social welfare benefit due to strategic manipulation. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I found this paper to be well-written and interesting -- I haven't seen many results that demonstrate that (in some settings) strategic manipulation can result in a strict increase in overall social welfare. The first theoretical result, which shows that the ADPoA can be linear in the number of agents in the worst case, was not too surprising and used relatively standard techniques, but is still a nice result that shows considerable separation from the second impartial culture result.\n\nSpeaking of that result, I would have liked to see a bit more intuition given about why this unintuitive result arises. Is it because there isn't much imbalance in impartial cultures, and allowing people to perturb their votes a bit will naturally help? I found the proof, which cases on the cardinality of W, a bit lacking in intuition here. (All I got is that the gain whenever there are two potential winners offsets the small losses whenever there are more than two potential winners.)\n\nI also think this paper would benefit from a simulation section in which the authors could explore a range of randomized / average-case settings with mixtures that are not just uniform (impartial culture). It would be very interesting to see how robust the theoretical result for impartial culture is as the culture becomes less impartial (i.e., more imbalanced). Is the degradation in benefit smooth in some other parameter? Does strategic behavior also help when the process is simulated on (approximately) real-world data?\n\nMinor comments:\n\n176: applied to break it\n176: suggest saying that Lemma 1 and Theorem 2 appear later in the text\nFootnote 1: if one exists\n255: results combine", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "YEqdiJ3sbzA", "reviewer": "Reviewer_TFbu", "summary": "This study deals with the issue of strategic manipulations in sequential and interactive votings, and assesses how agents' welfare changes when in equilibrium.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The manuscript is hard to read which penalizes the work; many sections need rephrasing to help the reader to appreciate the work.\nFor instance in the abstract it is stated:\n\"We first negatively demonstrate that the worst-case ADPoA is linear in the number of agents.\" ->  what negatively demostrate mean here? that there is negative linear relationship?\n\nPlease carefully proofread the document to fix typos, grammar issues, and expressivity issues for instance:\n\"Therefore, the positive result by Braˆnzei\n55 et al. [2013] does not extend to utility functions beyond plurality utility.\"  as utilities you mean the other two voting rules (veto, Borda)? \n\nPlease also consider reorganizing the manuscript so that the reader has all the necessary background to follow the narrative. For instance in the theoretical background, implications, limitations and techniques could be mentioned after the literature review.\n\nThe conclusive remarks could be more insightful connecting the findings of the study to real life scenarios.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors clearly state the limitations of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "XrfP6cHKq_", "reviewer": "Reviewer_YQpz", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I enjoyed reading the paper: Iterative voting seems like an important setting that we should understand better. I'm not familiar enough with prior work to know how surprising the results are, but I found the contrast between the worst-case bound (which fills in a natural gap in Branzei et al.'s analysis) and the impartial-culture bound neat. The overall presentation is clear, even though I had trouble following the proofs of Lemma 2 & 3 (I give some feedback on specifics of the presentation below). While best-responses for plurality naturally have a very restricted structure, the proofs seem to have nontrivial technical ideas.\n\nOther comments:\n- It seems like Lemma 2 includes quite clever ideas, which the reader should take away from the paper (given that the proofs are in the body). What I dearly missed while reading was a roadmap of the proof that would more clearly connect to the steps 1-4 (I found the titles of these steps rather uninformative). In line 283, it was not clear to me that the entries of the vectors were the first-ranked alternatives. Step 2 of the proof introduces multiple variables (especially the curly-Z_t,k) without giving intuitive explanations for them; this makes the proof very notationally dense and harder to follow than necessary.\n- I did not quite get where the authors were going in lines 80-84. Clearly, the cost of strategic behavior is not equally distributed among agents; agents whose top-ranked alternative is the plurality winner can only lose and agents who rank the plurality winner last can only win. When the authors propose quasi-linear utilities, do they suggest to compensate election losers with money? That's an interesting suggestion, but definitely departs from the motivating scenarios and opens the gates for more elaborate manipulation. In short: I'm interested in hearing what the authors suggest here, but I don't see it yet based on their description.\n- The paragraph \"Implications and limitations of the main results\" in Section 1.2 was hard to appreciate before seeing the content of the paper itself. To me, these points would have more naturally into a discussion at the end.\n- I was quite confused by how Lemmas 2-4 are stated and proved within the proof of Theorem 2. Instead, I would recommend ending the proof at line 255, which, with some forward-referencing to the lemmas, essentially already concludes the argument.\n- lines 215/216 make for a really awkward transition into Thm. 1, given that they refer to Thm. 2, and given that Thm. 1 talks about cases that the example does not generalize to well.\n- typo in footnote 1: \"i[f] one exists\"", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I was satisfied with how limitations and social impact were discussed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Thank you for your submission. The reviewers reached a consensus that this paper is well-written and presents interesting results. Please follow the reviewers' suggestions to improve the paper in the next revision.
Decision: Accept (Poster)