Complexity of finding and counting best voting committees explained
The Complexity of Membership, Uniqueness, and Counting for Optimal Proportional Approval Voting Committees
Computer Science and Game Theory
Summary
This study looks at how hard it is to find the best groups (committees) in a voting system called Proportional Approval Voting, which tries to fairly represent voters by maximizing a special score. The authors explore if a certain candidate is in some or all best groups, whether there’s only one best group, and how many best groups there might be. They show that answering these questions is very complex and connected to other tough problems in computer science. They also show that counting all best groups is as hard as some of the hardest counting problems known.
Proportional Approval Votingcommittee selectionharmonic utilitiescomputational complexityΔ2P-completenesscounting complexityoptimal committeesNP vs coNPsatisfiability problem (SAT)#P-completeness
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}$.