Convergence in Multi-Issue Iterative Voting under Uncertainty

Convergence in Multi-Issue Iterative Voting under Uncertainty

Joshua Kavner, Reshef Meir, Francesca Rossi, Lirong Xia

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence
Main Track. Pages 2783-2791. https://doi.org/10.24963/ijcai.2023/310

We study strategic behavior in iterative plurality voting for multiple issues under uncertainty. We introduce a model synthesizing simultaneous multi-issue voting with local dominance theory, in which agents repeatedly update their votes based on sets of vote profiles they deem possible, and determine its convergence properties. After demonstrating that local dominance improvement dynamics may fail to converge, we present two sufficient model refinements that guarantee convergence from any initial vote profile for binary issues: constraining agents to have O-legal preferences, where issues are ordered by importance, and endowing agents with less uncertainty about issues they are modifying than others. Our empirical studies demonstrate that while cycles are common for agents without uncertainty, introducing uncertainty makes convergence almost guaranteed in practice.
Keywords:
Game Theory and Economic Paradigms: GTEP: Computational social choice