Answer: \(\mathrm{NP}\)-complete
Theorem 3.7 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe decision variant of proxy selection is NP-hard, even for majority agreement and a single dRep.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) proposals, an explicit finite support \(\Theta\) of consistent types \(\theta=(v,\widehat v)\in\{0,1\}^m\times\{0,1,\bot\}^m\), rational masses \(\mu_\theta\ge0\) with \(\sum_{\theta\in\Theta}\mu_\theta=1\), and \(q\in[0,1]\), decide whether some ballot \(t\in\{0,1\}^m\) makes the Approval Voting winner \(w_\mu(t)\), formed by majority-agreement attraction \(d(\theta,t)=|\{j\in R_\theta:t_j\ne\widehat v_j\}|\le\lfloor |R_\theta|/2\rfloor\) with \(R_\theta=\{j:\widehat v_j\ne\bot\}\), satisfy \(U_\mu(w_\mu(t))\ge q\), where attracted mass votes \(t\), unattracted mass contributes its revealed approvals, \(U_\mu(j)=\sum_{\theta\in\Theta}\mu_\theta v_{\theta,j}\), and ties favor larger \(U_\mu\).
Given a finite candidate set \(C\), each type \(\theta=(v_\theta,\widehat v_\theta)\) has intrinsic approvals \(v_\theta\in\{0,1\}^{C}\) and revealed approvals \(\widehat v_\theta\in\{0,1,\bot\}^{C}\), where \(\widehat v_\theta(c)\ne\bot\) implies \(\widehat v_\theta(c)=v_\theta(c)\). Let \(R_\theta=\{c:\widehat v_\theta(c)\ne\bot\}\), and let rational masses \(\mu_\theta\ge0\) sum to \(1\).
For an advertised ballot \(t\in\{0,1\}^{C}\), type \(\theta\) delegates iff \(d_\theta(t):=|\{c\in R_\theta:t(c)\ne\widehat v_\theta(c)\}|\le\lfloor |R_\theta|/2\rfloor\). Its mass then casts \(t\); otherwise it casts its revealed ballot, with \(\bot\) contributing no approval. Let \(S_\mu^t(c)\) be the resulting mass-weighted approval score, \(I_\mu(c)=\sum_\theta\mu_\theta v_\theta(c)\), and let \(w_\mu(t)\) maximize \(S_\mu^t\), breaking score ties in favor of larger \(I_\mu\).
Target. Is deciding whether some \(t\) satisfies \(I_\mu(w_\mu(t))\ge q\) in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
Nearest known results. The corresponding finite-voter decision problem is \(\mathrm{NP}\)-hard, even with majority agreement and one dRep. No result for this exact rational-mass formulation is assumed.
Under the stated explicit rational encoding, the decision problem is \(\mathrm{NP}\)-complete. In particular, it is \(\mathrm{NP}\)-hard even for instances obtained by aggregating finite electorates satisfying the supplied majority-agreement and one-dRep restrictions.
Consider a finite electorate \(N=\{1,\ldots,n\}\). Voter \(i\) has type \(\theta_i=(v_i,\widehat v_i)\). For an advertised ballot \(t\), define the ballot actually cast by voter \(i\) as
\[ a_i^t(c)= \begin{cases} t(c),&\text{if }d_{\theta_i}(t)\leq \lfloor |R_{\theta_i}|/2\rfloor,\\ 1,&\text{if }d_{\theta_i}(t)>\lfloor |R_{\theta_i}|/2\rfloor \text{ and }\widehat v_i(c)=1,\\ 0,&\text{otherwise.} \end{cases} \]
Thus unrevealed coordinates contribute zero when the voter does not delegate. Let
\[ A_N^t(c)=\sum_{i=1}^n a_i^t(c) \quad\text{and}\quad J_N(c)=\sum_{i=1}^n v_i(c). \]
For every distinct type \(\theta\), let
\[ m_\theta=\bigl|\{i\in N:\theta_i=\theta\}\bigr|, \qquad \mu_\theta=\frac{m_\theta}{n}. \]
These masses are nonnegative rationals and satisfy \(\sum_\theta\mu_\theta=1\).
Because delegation depends only on \(\theta\) and \(t\), all voters of the same type make the same delegation decision and cast the same ballot. Consequently, for every \(t\) and \(c\),
\[ S_\mu^t(c) =\sum_\theta\frac{m_\theta}{n}a_\theta^t(c) =\frac{1}{n}\sum_{i=1}^n a_i^t(c) =\frac{A_N^t(c)}{n}, \]
and similarly
\[ I_\mu(c) =\sum_\theta\frac{m_\theta}{n}v_\theta(c) =\frac{J_N(c)}{n}. \]
It follows that, for any candidates \(c,c'\),
\[ S_\mu^t(c)>S_\mu^t(c') \quad\Longleftrightarrow\quad A_N^t(c)>A_N^t(c'), \]
and, when their approval scores are equal,
\[ I_\mu(c)>I_\mu(c') \quad\Longleftrightarrow\quad J_N(c)>J_N(c'). \]
Therefore aggregation preserves the entire lexicographic winner comparison: first by cast approval score and then by intrinsic approval score.
If several candidates remain tied after both comparisons, they have the same intrinsic score. Hence the truth of \(I_\mu(w_\mu(t))\geq q\) is independent of any unspecified residual tie-breaking.
Use the supplied premise that the corresponding finite-voter decision problem is \(\mathrm{NP}\)-hard. Given such an instance with \(n\) voters and an integer intrinsic-score threshold \(Q\):
By the aggregation lemma, for every advertised ballot \(t\), the finite and rational-mass instances select exactly the same winner set under the stated two-stage tie-breaking. Moreover,
\[ J_N(w(t))\geq Q \quad\Longleftrightarrow\quad \frac{J_N(w(t))}{n}\geq\frac{Q}{n} \quad\Longleftrightarrow\quad I_\mu(w_\mu(t))\geq q. \]
Thus the finite instance is a yes-instance if and only if the constructed rational-mass instance is a yes-instance.
The reduction is polynomial-time. There are at most \(n\) distinct types, and every mass \(m_\theta/n\) and the threshold \(Q/n\) have binary encoding length polynomial in the finite instance size. Aggregation changes neither the majority-agreement rule nor the use of a single advertised representative ballot. Hence the supplied restricted hardness transfers as well.
This proves \(\mathrm{NP}\)-hardness.
A certificate is an advertised ballot \(t\in\{0,1\}^{C}\), whose length is \(|C|\).
For each type, one can compute \(d_\theta(t)\) and its delegation decision in \(O(|C|)\) time. One then computes every \(S_\mu^t(c)\) and \(I_\mu(c)\) using exact rational arithmetic, determines the maximum cast score, and among its maximizers determines the maximum intrinsic score.
The bit length of all intermediate rational sums is polynomial in the total input encoding length: one may, for example, clear all input denominators using their product, whose binary length is at most the sum of their binary lengths. Comparing the resulting integer-weighted scores and the rational threshold is therefore polynomial-time.
Hence the problem belongs to \(\mathrm{NP}\).
The exact rational-mass formulation is \(\mathrm{NP}\)-complete. The reason hardness survives is that this model permits exact normalized representations of arbitrary finite electorates; aggregation introduces no fractional behavioral choice because every type either delegates its entire mass or none of it.
⟨structured verdict parsed — rendered above⟩
The prover correctly transfers the supplied finite-voter NP-hardness result to the rational-mass formulation by aggregating identical voter types. The reduction preserves delegation decisions, cast approval scores, intrinsic scores, winner comparisons, and the threshold condition. The membership-in-\(\mathrm{NP}\) argument is also valid under explicit binary rational encoding.
No substantive gap or incorrect step was found.
The definition of \(a_i^t(c)\) accurately reproduces the stated voting rule:
The delegation condition uses exactly \(d_{\theta_i}(t)\leq\lfloor |R_{\theta_i}|/2\rfloor\).
For each distinct type, the construction sets \(\mu_\theta=m_\theta/n\). These masses are nonnegative and sum to \(1\). Their binary encodings have polynomial length.
Identical voters have identical intrinsic and revealed ballots, so they necessarily make the same delegation decision for every \(t\). Aggregating them therefore loses no behavior relevant to the objective.
The equalities
\[ S_\mu^t(c)=\frac{A_N^t(c)}{n} \]
and
\[ I_\mu(c)=\frac{J_N(c)}{n} \]
are correct. Multiplication by the common positive factor \(1/n\) preserves both strict comparisons and equalities. Thus the primary cast-score comparison and secondary intrinsic-score comparison are preserved exactly.
If candidates remain tied after both score comparisons, they have equal intrinsic scores. Therefore every permitted residual choice has the same value of \(I_\mu\), and the truth of the threshold predicate is independent of unspecified residual tie-breaking. This observation is correct.
Setting \(q=Q/n\) gives
\[ J_N(w(t))\geq Q \quad\Longleftrightarrow\quad I_\mu(w_\mu(t))\geq q. \]
Together with preservation of winner comparisons, this establishes equivalence for every advertised ballot \(t\), and hence equivalence of the existential decision problems.
The prover explicitly relies on the finite-voter NP-hardness supplied in the task, so no unsupported external hardness theorem is introduced.
There are at most \(n\) resulting types. Each fraction \(m_\theta/n\) and \(Q/n\) has polynomial binary length. Grouping identical explicitly represented voter types can be performed in polynomial time. Hence the reduction is polynomial-time.
The aggregation does not alter the individual majority-agreement delegation rule or introduce additional advertised ballots, so the stated restricted hardness transfers.
An advertised ballot \(t\) is a certificate of length \(|C|\). Given \(t\), all delegation decisions, candidate scores, and tie-breaking comparisons can be computed in polynomial time.
The exact-arithmetic justification is sound: clearing denominators using their product produces integers whose binary lengths are bounded by the sum of the input denominator lengths, hence polynomial in the explicit input size. Rational comparison with \(q\) is consequently polynomial-time.
The reduction proves \(\mathrm{NP}\)-hardness, while certificate verification proves membership in \(\mathrm{NP}\). Therefore the claimed \(\mathrm{NP}\)-completeness result follows.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.