2016/06/19 by Reshef Meir, Maria Polukarov, Jeffrey S. Rosenschein +1
Computer Science · Decision Sciences · Economics, Econometrics and Finance · Mathematics · #Auction Theory and Applications #Computer science #Game Theory and Applications #Game Theory and Voting Systems #Mathematical economics #Mathematics #Political science #Voting #cs.GT #cs.MA
paper · pdf · doi:10.1016/j.artint.2017.08.002
some of the results appeared in preliminary versions of this paper: Convergence to Equilibrium of Plurality Voting, Meir et al., AAAI 2010; Strong and Weak Acyclicity in Iterative Voting, Meir, COMSOC 2016
arxiv created 2016/06/19 · openalex created_date 2016/07/22 · openalex publication_date 2017/08/24 · arxiv updated 2018/08/13 · openalex updated_date 2026/08/05
We consider iterative voting models and position them within the general framework of acyclic games and game forms. More specifically, we classify convergence results based on the underlying assumptions on the agent scheduler (the order of players) and the action scheduler (which better-reply is played). Our main technical result is providing a complete picture of conditions for acyclicity in several variations of Plurality voting. In particular, we show that (a) under the traditional lexicographic tie-breaking, the game converges for any order of players under a weak restriction on voters' actions; and (b) Plurality with randomized tie-breaking is not guaranteed to converge under arbitrary agent schedulers, but from any initial state there is some path of better-replies to a Nash equilibrium. We thus show a first separation between restricted-acyclicity and weak-acyclicity of game forms, thereby settling an open question from [Kukushkin, IJGT 2011]. In addition, we refute another conjecture regarding strongly-acyclic voting rules.