Modeling Voters in Multi-Winner Approval Voting

Jaelle Scheuerman, Jason L. Harman, Nicholas Mattei, K. Brent VenableAAAI 2021 · DOI

In the field of Computational Social Choice (COMSOC), researchers often model voters as either perfectly sincere or perfectly rational strategic actors. However, real-world human behavior is frequently constrained by cognitive bandwidth, leading voters to rely on mental shortcuts or heuristics. This paper, originally presented at AAAI-21, bridges the gap between theoretical voting models and actual human behavior in the context of multi-winner approval voting.

The Challenge of Multi-Winner Complexity

Most voting research focuses on Single-Winner Plurality. This study tackles Multi-Winner Approval Voting (AV), where voters can approve any number of candidates, and the top $k$ candidates are elected. While finding an optimal strategic vote is mathematically possible in some AV settings, the number of possible ballots grows exponentially with the number of candidates. For a human voter, evaluating every possible subset of candidates is computationally implausible.

Previous models like "Attainability-Utility" (AU) successfully modeled the trade-off between a candidate's utility (personal preference) and their attainability (likelihood of winning) in single-winner elections. However, the standard AU model fails in multi-winner settings because it still requires evaluating entire candidate subsets, which often leads to predicting "complete" ballots (voting for everyone liked) more often than humans actually do.

The Attainability-Utility with Threshold (AUT) Model

To better reflect human decision-making, the authors propose the Attainability-Utility with Threshold (AUT) heuristic. This model assumes that humans evaluate candidates individually rather than in groups.

  1. Individual Scoring: For each candidate, a score is calculated based on their utility and attainability.
  2. The Threshold: A voter approves a candidate only if their individual score exceeds a specific threshold ($\tau$).
  3. Cognitive Plausibility: This approach aligns with "adaptive toolbox" theories in psychology, suggesting humans use simple rules to match environmental constraints rather than performing complex global optimizations.
The attainability function models the probability of a candidate winning based on their current vote share and election uncertainty (beta).

The attainability component of the model, as shown above, uses a sigmoid function to represent how a candidate's perceived chance of winning changes with their current vote share. The parameter $\beta$ represents the level of uncertainty in the election.

Experimental Methodology

The researchers collected a behavioral dataset from 104 participants on Amazon Mechanical Turk. Participants played a voting game with real monetary stakes, choosing ballots for 5-candidate election scenarios. The study manipulated the number of winners ($k = 1, 2, \text{ or } 3$) and the level of uncertainty (the number of ballots yet to be cast).

AUT was compared against four baselines:

  • Optimal: Maximizing expected utility.
  • Complete: Voting for all candidates with positive utility.
  • Take $k$ Best: Voting for the top $k$ preferred candidates.
  • Standard AU: The original subset-based model.

Key Results and Performance

The results demonstrated that humans are strategic but suboptimal; they attempt to manipulate their votes for better payouts but rarely find the mathematically "optimal" ballot. The AUT model significantly outperformed all other models in predicting these human choices.

Comparison of prediction accuracy across different models for 1, 2, and 3-winner scenarios.

As illustrated in the performance data, AUT achieved a mean prediction accuracy of approximately 58% to 68%. Notably, while other models saw their accuracy decline as the number of winners ($k$) increased, AUT remained consistently strong. In the 3-winner condition, AUT was 80.7% more accurate than the standard AU model and significantly better than the "Take $k$ Best" strategy commonly assumed in simpler heuristic models.

Conclusion

The success of the AUT model suggests that human voters in multi-winner elections focus on individual candidate viability rather than complex subset combinations. Future work aims to explore these heuristics in larger candidate pools and higher-stakes environments, potentially leading to hybrid machine learning models that use cognitively plausible features to predict voter behavior with even higher precision.

Summary updated

BibTeX
@inproceedings{scheuerman2021modeling,
  author = {Jaelle Scheuerman and Jason L. Harman and Nicholas Mattei and K. Brent Venable},
  title = {{Modeling Voters in Multi-Winner Approval Voting}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i6.16716},
}
Figure