Convergence and Quality of Iterative Voting Under Non-Scoring Rules
A. Koolyk, O. Lev, J. Rosenschein
AAMAS 2016
Abstract
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.
Remarks: Short paper, later published in IJCAI-2017
Experiments: