Source-linked AI summary
The Complexity of Membership, Uniqueness, and Counting for Optimal Proportional Approval Voting Committees
Yizhou Ai
TL;DR
PAV's maximizing committees can tie, leaving candidate membership, uniqueness, and the number of optima unresolved before tie-breaking. This paper classifies these optimal-set questions and constructs reductions that encode assignments as committees, establishing completeness results for membership, uniqueness, and counting.
Problem
PAV's maximizing committees can tie, leaving candidate membership, uniqueness, and the number of optima unresolved before tie-breaking.
Source: §1 · p. 1Method
Fixed clause ballots equalize satisfying assignments, while harmonic increments order them with polynomially many voters and unique committee representations preserve counts.
Source: §5 · p. 12, §6 · p. 15Results
Membership and uniqueness are ∆2^P-complete, with uniqueness hardness even for at most two optima; counting is #·OptP-complete under metric reductions, mapping f to f(x)+1 optima.
Source: §4 · p. 11, §6 · pp. 14–15Takeaways & Limitations
These classifications concern the whole maximizing set, including ties hidden by returning one output committee.
Source: §6 · p. 15The #SAT Turing equivalence and #PNP upper bound do not establish #PNP-hardness, and the conditional implication is not an unconditional class separation.
Source: §5 · p. 14
Abstract
from arXiv · showhide
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 $\Delta_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}$.
1 Introduction
PAV can leave several equally scoring committees, making candidate membership, uniqueness, and the size of the optimal set distinct questions. The paper classifies these questions and develops reductions that encode assignments as committees.
1 Introduction
- The paper asks whether a candidate belongs to some or all optimal committees, whether the optimum is unique, and how many optima remain.These properties describe what the ballots determine before tie-breaking.Source: §1 · p. 1
1.1 Our Results
- Both candidate-membership questions are ∆2^P-complete; counting is #·OptP-complete under metric reductions, with each constructed election Ex satisfying #OptimalPAV(Ex) = f(x) + 1.The additive term accommodates source inputs with no feasible witnesses; if the source always has a feasible witness, the construction can preserve its count exactly.Source: §1.1 · p. 2
- Variable-pair committees uniquely represent assignments, while fixed clause voters equalize satisfying assignments and harmonic increments order them using polynomially many voters.A unique-extension encoding preserves the number of source optima.Source: §1.1 · p. 2
1.2 Related Work
- The paper sharpens prior coNP-hardness for uniqueness to ∆2^P-completeness and prior #P-hardness for counting to #·OptP-completeness under metric reductions.Prior work also studied score approximation and algorithms under structural restrictions, which do not by themselves resolve exact ties or optimal-set membership.Source: §1.2 · p. 3
2 Preliminaries
The preliminaries define the approval-election model, PAV scoring, optimal committees, and exact encodings for comparing committee scores.
2 Preliminaries
- An approval election consists of a candidate set, a voter approval profile, and a committee size k; equal approval sets at different positions are distinct voters.All three election components, including k, are part of the input.Source: §2 · p. 4
- PAV uses harmonic utilities, and Opt(E) retains every size-k committee attaining the maximum rather than applying a tie-breaking rule.The optimal set is nonempty because the family of size-k committees is finite and nonempty.Source: §2 · p. 4
- Multiplying PAV scores by D_k = lcm(1, ..., k) gives integer scores computable in polynomial time with polynomial bit lengths.The input profile is represented by an n × m approval matrix, and each committee has a unique m-bit characteristic-vector encoding.Source: §2 · pp. 4–5
3 Complexity of Optimal Membership
Both existential and universal optimal-candidate membership are ∆_2^P-complete. A reduction from LexMax-SAT-Bit encodes satisfying assignments as committees and uses PAV scores to select assignments by a binary objective.
3 Complexity of Optimal Membership
- Binary search with NP queries finds the optimal score, after which NP queries test whether a qualifying committee attains it.For universal membership, the final query tests whether an optimal committee excludes the designated candidate.Source: §3 · p. 5
3.1 Reduction from LexMax-SAT-Bit
- The reduction maps satisfying assignments maximizing J bijectively to optimal committees, with each variable’s true-value candidate recording its assignment bit.The construction’s candidate encoding lets membership of a designated candidate recover the corresponding bit.Source: §3.1 · pp. 6–7
- Clause voters give every satisfied clause a fixed score and penalize violations, while objective rewards vary by less than one and cannot offset a clause violation.Among satisfying assignments, the reward orders committees by J.Source: §3.1 · p. 7
- Harmonic marginal rewards implement the binary objective with polynomially many voters using a Chinese remainder construction.Small-denominator increments and singleton ballots realize the rewards without negative voter counts.Source: §3.1 · pp. 8–9
- A large parameter forces all auxiliary candidates and exactly one candidate per variable pair, making the variable choices determine the committee.This canonical form supports a one-to-one assignment-to-committee correspondence.Source: §3.1 · pp. 9–10
3 Complexity of Optimal Membership
- Both Some-Optimal-PAV-Member and All-Optimal-PAV-Member are ∆_2^P-complete.The upper bounds use polynomially many NP queries, and the reductions establish ∆_2^P-hardness.Source: §3 · p. 5, §3.1 · p. 10
4 Complexity of Uniqueness
The uniqueness problem is Δ₂ᴾ-complete, with hardness persisting even when an instance has at most two optimal committees. The hardness reduction encodes the designated bit through the number of optimal committees.
4 Complexity of Uniqueness
- For the upper bound, uniqueness is decided by negating an NP query asking whether two distinct size-k committees attain the computed optimum score.The optimum score is computed as in the proof of Theorem 3.2.Source: §4 · p. 11
- The reduction adds a variable with one permitted value when the designated bit is one and two when it is zero, leaving that variable outside the objective.When the designated bit is zero, both values satisfy the added constraint and yield the same objective; the construction transfers this distinction to optimal committees.Source: §4 · p. 11
- Uniqueness is Δ₂ᴾ-complete, and hardness holds even when there are at most two optimal committees.The reduction establishes hardness from the satisfiable restriction of LexMax-SAT-Bit.Source: §4 · p. 11
5 Complexity of Counting Optimal Committees
The section proves metric #·OptP-completeness for counting optimal PAV committees, with a reduction producing exactly f(x)+1 committees for each source function f. Its construction preserves multiplicity by distinguishing a unique representative from all source optima, then relates the counting problem to #SAT and #PNP.
5 Complexity of Counting Optimal Committees
- #OptimalPAV is #·OptP-complete under metric reductions, with a polynomial-time construction producing exactly f(x)+1 committees for every f in #·OptP.The reduction subtracts one from the target count to recover f(x).Source: §5 · pp. 11, 13, 14
- When the source witness set is always nonempty, the reduction can preserve its count exactly; otherwise, every PAV instance’s nonempty optimum set prevents a parsimonious reduction from representing zero.The additive one accommodates source inputs with no feasible witnesses.Source: §5 · pp. 11, 13, 14
- The construction adds one optimal witness while preserving every source optimum by uniquely selecting a representative t and leaving the optimal choices of y tied.A separate fallback witness handles inputs with no feasible source witnesses.Source: §5 · pp. 12–13
- Unique-extension formula encodings and designated objective bits yield a bijection from optimal witnesses to optimal committees, with each feasible tuple represented by one satisfying extension.Only objective-output bits receive rewards, so witnesses with equal objective values remain tied.Source: §5 · p. 13
- #OptimalPAV is Turing equivalent to #SAT and belongs to #PNP, with an upper-bound algorithm using #SAT queries after binary search for the optimum score.The final #SAT query counts committees whose score equals the optimum.Source: §5 · p. 14
- If #OptimalPAV belongs to #P, then NP = coNP; the paper does not claim #PNP-hardness or an unconditional separation of counting classes.The #PNP statement is an upper bound, not a hardness result.Source: §5 · p. 14
6 Conclusion
The paper classifies membership in some or all optimal PAV committees, uniqueness, and counting the entire optimal set. Its reductions separate clause satisfaction from objective comparison, while leaving profile restrictions as a direction for further study.
6 Conclusion
- Membership in some or all optimal PAV committees and uniqueness are ΔP_2-complete, while counting optimal committees is #·OptP-complete under metric reductions.The counting reduction adds exactly one to the source count, and these results concern all maximizing committees rather than a single tie-broken output.Source: §6 · pp. 14–15
- Fixed clause ballots give every satisfying assignment the same base score, and harmonic increments order assignments using polynomially many voters while preserving the number of optima.Variable pairs and unique-extension formula encodings give each satisfying assignment a unique committee representation.Source: §6 · p. 15
- The conclusion identifies open questions about whether voter-count or approval-profile restrictions simplify membership, uniqueness, and counting, and how ballot-size limits affect hardness constructions.Existing algorithms use voter-count and profile restrictions [LS26].Source: §6 · p. 15
A Complexity Background
This appendix reviews decision and counting complexity notions used in the paper. It covers oracle classes, witness-counting and optimization classes, and the reductions used to state completeness results.
A Complexity Background
- P, NP, and coNP describe deterministic polynomial-time decision, polynomially verifiable certificates, and complements of NP languages, respectively.An NP oracle answers membership queries, which may be adaptive when later queries depend on earlier answers.Source: A Complexity Background · p. 17
- ΔP_2 uses polynomially many adaptive NP-oracle queries, ΘP_2 uses logarithmically many, and ΣP_2 permits nondeterministic polynomial time with an NP oracle.The appendix also introduces #P as counting accepting paths and #·OptP as counting paths attaining a maximum objective.Source: A Complexity Background · pp. 17–18
- The appendix distinguishes deterministic polynomial-time computation with an NP oracle, exact #P-oracle computation, and counting paths that themselves may query an NP oracle.These correspond respectively to FPNP, FP#P, and #PNP.Source: A Complexity Background · p. 18
- A metric reduction computes a source function from one target-function value and the original input, whereas a parsimonious reduction preserves the count exactly.Completeness requires hardness from every function in the class as well as membership; the reduction notion is specified in each statement.Source: A Complexity Background · p. 18