Social Welfare Maximization in Approval-Based Committee Voting under Uncertainty

Haris Aziz, Yuhang Guo, Venkateswara Rao Kagita, Baharak Rastegari, Mashbat Suzuki

Abstract

Approval-based committee (ABC) voting is a fundamental mechanism for collective decision-making, yet it traditionally assumes perfect information regarding voter preferences. This paper investigates ABC voting under uncertainty, where voter approvals are probabilistic. We define several uncertainty models—Joint Probability, Lottery, and Candidate Probability—and analyze the computational complexity of identifying committees that maximize social welfare. Our results map the complexity landscape for determining if a committee is possibly or necessarily optimal, as well as the challenge of finding the most likely optimal committee.

Introduction

In standard Approval-Based Committee (ABC) voting, voters approve a subset of candidates, and a committee of fixed size $k$ is selected to maximize utilitarian social welfare (the total number of approvals). This model is widely applicable, from corporate board elections to recommendation systems. However, real-world scenarios often involve uncertainty: preferences might be estimated from noisy data, or "voters" might represent groups with internal disagreements.

This paper addresses the algorithmic challenges of maximizing social welfare when only probabilistic information about voter approvals is available. We explore how to define "best" in this context and whether such committees can be found efficiently.

Uncertainty Models and Problem Hierarchy

The authors formalize four models of uncertainty to capture different levels of dependency and granularity:

  1. Joint Probability: A full distribution over all possible voting profiles.
  2. Lottery Model: Each voter independently follows a distribution over sets of candidates they might approve.
  3. Candidate Probability: Each voter-candidate pair has an independent probability of approval.
  4. Three-Valued Approval (3VA): A simplified candidate model where approvals are known (1), disapproved (0), or unknown (0.5).

To navigate these models, the paper defines several decision and search problems. These include IsPossSWM (is a committee possibly a social welfare maximizer?), IsNecSWM (is it necessarily one?), and MaxSWM (finding the committee most likely to be optimal). The relationships between these problems are illustrated in the hierarchy below.

Hierarchy of probabilistic social welfare maximization problems.

Computational Complexity Landscape

The core contribution of this work is a comprehensive classification of the computational complexity of these problems across the different uncertainty models.

Summary of complexity results for social welfare maximization under uncertainty.

Key findings include:

  • The Lottery Model's Hardness: While the Candidate Probability model often allows for polynomial-time solutions, the Lottery model is significantly more difficult. For instance, IsPossSWM is NP-complete in the Lottery model but in P for others.
  • Necessity vs. Possibility: Checking if a committee is always the best (IsNecSWM) is generally easier (solvable in P) than checking if it might be the best (IsPossSWM) in the Lottery model.
  • The Difficulty of MaxSWM: Finding the committee with the highest probability of being the social welfare maximizer (MaxSWM) is NP-hard for both Joint and Lottery models. Its complexity in the Candidate Probability model remains an intriguing open question.

Key Insights

Expectation vs. Probability

A significant conceptual finding is that a committee maximizing expected social welfare is not necessarily the one with the highest probability of being the social welfare maximizer. The authors demonstrate this with a counterexample involving 3 voters and 4 candidates, showing that these two intuitive objectives can diverge.

Robustness and Algorithms

The authors developed a novel dynamic programming (DP) approach to compute the exact probability distribution of social welfare (SW-Dist) in $O(n \cdot m \cdot k)$ time for the Lottery and Candidate models. In the 3VA model, they show that maximizing expected social welfare provides a $(1/2, 1/2)$-robustness guarantee, though this does not generalize to the Candidate Probability model.

Conclusion

This research provides a rigorous foundation for committee voting under uncertainty. By mapping the complexity of various social welfare objectives, it identifies which problems are tractable and which require approximation. Future work will focus on closing the complexity gap for MaxSWM in the candidate model and extending these results to more complex satisfaction functions beyond utilitarian social welfare.

Summary updated

BibTeX
@inproceedings{aziz2026social,
  author = {Haris Aziz and Yuhang Guo and Venkateswara Rao Kagita and Baharak Rastegari and Mashbat Suzuki},
  title = {{Social Welfare Maximization in Approval-Based Committee Voting under Uncertainty}},
  booktitle = {AAMAS},
  year = {2026},
  url = {https://openreview.net/forum?id=Q36dwX7iXw},
}
Figure