Voting committee membership and counting problems proven computationally hard
The Complexity of Membership, Uniqueness, and Counting for Optimal Proportional Approval Voting Committees
Computer Science and Game Theory
Summary
This paper looks at a special voting system called Proportional Approval Voting where groups select committees to represent people fairly. The authors study how hard it is to figure out which candidates can be on these winning committees, if the best committee is unique, and how many best committees there are. They prove these questions are very difficult from a computer science perspective, as hard as some classic logic problems. This means some tasks about these voting results require a lot of computer resources and can't be simplified easily.
What this means in practice
- •For voting system designers: Assess the computational feasibility of determining committee membership and uniqueness in proportional voting systems.
- •For complexity analysts: Use the hardness results to guide resource allocation when implementing proportional voting algorithms or counting solutions.
A theory result. No direct application yet.
Authors
Yizhou Ai
Abstract
Proportional Approval Voting (PAV) chooses committees that maximize a sum of harmonic utilities. We study the set of maximizing committees: whether a candidate belongs to some or all of them, whether the optimum is unique, and how many optima exist. When the committee size is part of the input, the three decision problems are $Δ_2^\mathrm{P}$-complete. Uniqueness remains hard for instances with at most two optimal committees. Counting optimal committees is $\#\!\cdot\!\mathrm{OptP}$-complete under metric reductions: every function $f$ in this class reduces to an election with exactly $f(x)+1$ optimal committees. The reductions encode satisfying assignments directly as committees and use harmonic marginal rewards to realize binary objectives with polynomially many voters. Each satisfying assignment has a unique committee representation, and fixed clause ballots give these representations the same clause score. We also prove Turing equivalence with $\#\mathrm{SAT}$ and show that membership of the counting problem in $\#\mathrm{P}$ would imply $\\mathrm{NP}=\mathrm{coNP}$.