Convergence in Multi-Issue Iterative Voting under Uncertainty

Joshua Kavner, Reshef Meir, Francesca Rossi, Lirong XiaIJCAI 2023 · DOI

TL;DR

This paper explores how groups make decisions when faced with multiple choices simultaneously, and agents can change their minds iteratively. They find that while simple voting can lead to frustrating cycles, introducing uncertainty about others' preferences can surprisingly guarantee convergence to a stable outcome, especially for binary choices.

What Problem Does This Paper Address?

Imagine a committee needing to decide on several things at once – like choosing a project, a budget, and a team lead. If everyone just votes once, the outcome might not reflect anyone's true preferences well, leading to paradoxes. A more dynamic approach is iterative voting, where agents can update their votes based on what others are doing. However, in multi-issue scenarios, even this iterative process can get stuck in endless loops where no stable decision is ever reached. This paper tackles the question of when and how multi-issue iterative voting does converge to a stable outcome, particularly when agents aren't entirely sure about everyone else's preferences.

Methods

The authors build upon existing models of iterative voting (IV) and local dominance theory. They introduce a novel model that synthesizes simultaneous multi-issue voting with local dominance, allowing agents to update their votes based on possible sets of vote profiles. They explore two main "dynamics" or ways agents update their votes:

  • Best Response (BR): Agents update their vote to the best possible outcome given what they believe others are voting for. This is done without uncertainty.
  • Local Dominance Improvement (LDI): Agents update their vote if they believe it could lead to a weakly better outcome for all possible scenarios they consider, and strictly better for at least one. This dynamic explicitly incorporates uncertainty.

To ensure convergence, they propose two refinements:

  1. O-legal preferences: Agents' preferences over candidates for an issue are only dependent on the outcomes of prior issues in a predefined order.
  2. Alternating Uncertainty: Agents strategically adjust their uncertainty levels, focusing more on the current issue they are voting on and less on others.

Datasets

Not discussed in the paper. The authors rely on simulated experiments with randomly generated preference profiles.

Key Insights and Ideas

  • Uncertainty as a Stabilizer: Counter-intuitively, uncertainty about other agents' preferences can guarantee convergence in multi-issue voting, whereas perfect information can lead to cycles. This is because uncertainty limits the number of "improvement steps" an agent might consider, preventing them from getting stuck in loops.
  • Interdependence is the Culprit: Cycles in voting arise from agents' preferences being interdependent across issues. If changing your vote on one issue significantly alters your preference for another, you can get stuck.
  • Order Matters (for Convergence): For binary issues, imposing an order on the issues and ensuring agents' preferences respect this order (O-legal preferences) is sufficient to guarantee convergence. This is because it breaks the problematic interdependencies.
  • Binary Issues are Key: The convergence guarantees found in this paper primarily apply to binary (two-option) issues. Multi-candidate issues remain more challenging and can still lead to cycles even with the proposed refinements.

Key Results

  • BR Dynamics Can Cycle: Even without uncertainty, iterative voting with best-response dynamics can fail to converge for multi-issue scenarios, as demonstrated by an example.
  • LDI Dynamics Can Also Cycle (Theoretically): Without specific refinements, LDI dynamics (with uncertainty) can also fail to converge for multi-issue scenarios, though uncertainty generally reduces the likelihood of cycles.
  • Refinements Guarantee Convergence: For binary issues, both O-legal preferences and alternating uncertainty dynamics are shown to be sufficient to guarantee convergence for LDI dynamics.
  • Empirical Evidence: Experiments show that as uncertainty increases, the percentage of non-converging (cycling) vote profiles drops dramatically, approaching zero. This suggests that in practice, uncertainty makes convergence almost guaranteed.
  • Improved Welfare: The study suggests that iterative voting, especially with uncertainty, can improve the social welfare of outcomes compared to simple truthful voting, potentially mitigating multiple-election paradoxes.

Limitations and Future Work

  • Multi-Candidate Issues: The convergence guarantees do not extend to multi-candidate issues, which remain a significant challenge.
  • Preference Distributions: The empirical study used a specific, impartial culture preference distribution. Future work could explore more realistic distributions and welfare functions.
  • Privacy and Information Revelation: While IV offers some privacy, agents implicitly reveal information through their improvement steps. Understanding and potentially mitigating this is an open direction.
  • Axiomatic Properties: Further research is needed to detail the axiomatic properties of multi-issue IV rules, especially how they relate to decision rules used for individual issues.

Summary updated

BibTeX
@inproceedings{kavner2023convergence,
  author = {Joshua Kavner and Reshef Meir and Francesca Rossi and Lirong Xia},
  title = {{Convergence in Multi-Issue Iterative Voting under Uncertainty}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/310},
}
Figure