On the Convergence of Iterative Voting: How Restrictive Should Restricted Dynamics Be?

Authors

  • Svetlana Obraztsova National Technical University of Athens
  • Evangelos Markakis Athens University of Economics and Business
  • Maria Polukarov University of Southampton
  • Zinovi Rabinovich Mobileye Vision Technologies Ltd.
  • Nicholas Jennings University of Southampton

DOI:

https://doi.org/10.1609/aaai.v29i1.9331

Abstract

We study convergence properties of iterative voting procedures. Such procedures are defined by a voting rule and a (restricted) iterative process, where at each step one agent can modify his vote towards a better outcome for himself. It is already known that if the iteration dynamics (the manner in which voters are allowed to modify their votes) are unrestricted, then the voting process may not converge. For most common voting rules this may be observed even under the best response dynamics limitation. It is therefore important to investigate whether and which natural restrictions on the dynamics of iterative voting procedures can guarantee convergence. To this end, we provide two general conditions on the dynamics based on iterative myopic improvements, each of which is sufficient for convergence. We then identify several classes of voting rules (including Positional Scoring Rules, Maximin, Copeland and Bucklin), along with their corresponding iterative processes, for which at least one of these conditions hold.

Downloads

Published

2015-02-16

How to Cite

Obraztsova, S., Markakis, E., Polukarov, M., Rabinovich, Z., & Jennings, N. (2015). On the Convergence of Iterative Voting: How Restrictive Should Restricted Dynamics Be?. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1). https://doi.org/10.1609/aaai.v29i1.9331

Issue

Section

AAAI Technical Track: Game Theory and Economic Paradigms