Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.
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.

Other comments:
- 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.
- 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.
- 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.
- 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.
- 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.
- typo in footnote 1: "i[f] one exists"
limitations_and_societal_impact: I was satisfied with how limitations and social impact were discussed.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.

Comments:

*. 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?  

*. 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.

*. 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?
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_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This study deals with the issue of strategic manipulations in sequential and interactive votings, and assesses how agents' welfare changes when in equilibrium.

main_review: The manuscript is hard to read which penalizes the work; many sections need rephrasing to help the reader to appreciate the work.
For instance in the abstract it is stated:
"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?

Please carefully proofread the document to fix typos, grammar issues, and expressivity issues for instance:
"Therefore, the positive result by Braˆnzei
55 et al. [2013] does not extend to utility functions beyond plurality utility."  as utilities you mean the other two voting rules (veto, Borda)? 

Please 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.

The conclusive remarks could be more insightful connecting the findings of the study to real life scenarios.
limitations_and_societal_impact: The authors clearly state the limitations of their work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 

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.

Speaking 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.)

I 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?

Minor comments:

176: applied to break it
176: suggest saying that Lemma 1 and Theorem 2 appear later in the text
Footnote 1: if one exists
255: results combine
limitations_and_societal_impact: Yes.
review_title: null

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)