Convergence and Quality of Iterative Voting Under Non-Scoring Rules

Convergence and Quality of Iterative Voting Under Non-Scoring Rules

Aaron Koolyk, Tyrone Strangway, Omer Lev, Jeffrey S. Rosenschein

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 273-279. https://doi.org/10.24963/ijcai.2017/39

Iterative voting is a social choice mechanism that assumes all voters are strategic, and allows voters to change their stated preferences as the vote progresses until an equilibrium is reached (at which point no player wishes to change their vote). Previous research established that this process converges to an equilibrium for the plurality and veto voting methods and for no other scoring rule. We consider iterative voting for non-scoring rules, examining the major ones, and show that none of them converge when assuming (as most research has so far) that voters pursue a best response strategy. We investigate other potential voter strategies, with a more heuristic flavor (since for most of these voting rules, calculating the best response is NP-hard); we show that they also do not converge. We then conduct an empirical analysis of the iterative voting winners for these non-scoring rules, and compare the winner quality of various strategies.
Keywords:
Agent-based and Multi-agent Systems: Noncooperative Games
Agent-based and Multi-agent Systems: Social Choice Theory