Answer: \(\mathrm{NP}\text{-complete}\)
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor every sequential Thiele rule except AV, it is NP-hard to decide whether a voter can benefit from abstention.
statement extracted from the paper’s text layer; consult the paper for the exact wording
For a fixed sequential Thiele rule \(R\) other than AV, given candidates \(C\), committee size \(k\), rational approval-type masses \(\mu\), a distinguished type \(t^\star\), and rational \(0 < \beta \le \mu_{t^\star}\), let \(\mu^- = \mu - \beta e_{t^\star}\). Decide whether the set of committees \(F_R(\mu^-)\) selected under all tie-breakings is strictly Kelly-preferred by type \(t^\star\) to \(F_R(\mu)\).
Given a finite candidate set \(C\), committee size \(k\), explicit nonempty approval types \(T\subseteq 2^C\setminus\{\varnothing\}\), rational masses \((\mu_t)_{t\in T}\) summing to \(1\), sequential PAV starts with \(S=\varnothing\) and repeatedly adds any candidate maximizing \(\Delta_\mu(c\mid S)=\sum_{t\in T}\mu_t\bigl(H_{|t\cap(S\cup\{c\})|}-H_{|t\cap S|}\bigr)\), where \(H_0=0\) and \(H_j=\sum_{r=1}^j1/r\). All tie choices are allowed.
Target. Is it polynomial-time solvable, or NP-hard, to decide whether some size-\(k\) committee obtainable by this process contains at least \(s\) candidates approved by a distinguished type \(t^\star\), i.e. satisfies \(|W\cap t^\star|\ge s\)?
Nearest known results. For finite unweighted approval profiles, deciding whether a given voter approves at least \(s\) candidates in some sequential-PAV winning committee is NP-complete. No continuous-mass result is stated here.
The decision problem is \(\mathrm{NP}\)-complete. In particular, allowing rational masses over explicitly listed approval types preserves the known hardness for finite unweighted approval profiles exactly; no approximation or limiting argument is needed.
Let \(S\subseteq C\) and \(c\in C\setminus S\). For every type \(t\in T\),
\[ H_{|t\cap(S\cup\{c\})|}-H_{|t\cap S|} = \begin{cases} \dfrac{1}{|t\cap S|+1},&c\in t,\\[4pt] 0,&c\notin t. \end{cases} \]
Therefore
\[ \Delta_\mu(c\mid S) = \sum_{\substack{t\in T\\c\in t}} \frac{\mu_t}{|t\cap S|+1}. \]
This form will be used both for verification and for the reduction.
A certificate is an ordered sequence of distinct candidates
\[ (c_1,\ldots,c_k). \]
For \(j\in\{1,\ldots,k\}\), let
\[ S_{j-1}=\{c_1,\ldots,c_{j-1}\}. \]
The verifier checks that, for every \(j\) and every \(d\in C\setminus S_{j-1}\),
\[ \Delta_\mu(c_j\mid S_{j-1}) \geq \Delta_\mu(d\mid S_{j-1}). \]
This is precisely the condition that \(c_j\) is an allowed tie choice at step \(j\). The verifier then checks
\[ |S_k\cap t^\star|\geq s. \]
It remains to justify that the marginal comparisons can be performed in polynomial time.
Write each input mass as \(\mu_t=p_t/q_t\). Every term in a marginal has the form
\[ \frac{p_t}{q_t(|t\cap S|+1)}. \]
The additional factor \(|t\cap S|+1\) is at most \(|C|+1\). A common denominator obtained by multiplying the denominators of at most \(|T|\) terms has bit length at most the sum of their bit lengths, namely polynomial in the input size. Hence every marginal can be computed and compared exactly using polynomially many operations on polynomial-bit integers.
There are at most \(k|C|\) relevant marginal comparisons. Thus the certificate is verifiable in polynomial time, proving that the problem belongs to \(\mathrm{NP}\).
Use the supplied known result:
Given a finite unweighted approval profile, a committee size \(k\), a distinguished voter, and a threshold \(s\), deciding whether some sequential-PAV winning committee contains at least \(s\) candidates approved by that voter is \(\mathrm{NP}\)-complete.
Consider such an instance. Let the voters be indexed by \(i\in\{1,\ldots,n\}\), let \(A_i\subseteq C\) be voter \(i\)'s approval set, and let \(i^\star\) be the distinguished voter.
Assume first that \(A_{i^\star}\neq\varnothing\). Let
\[ V^+=\{i:A_i\neq\varnothing\}, \qquad N=|V^+|. \]
Because \(A_{i^\star}\neq\varnothing\), we have \(N\geq1\).
For every distinct nonempty approval set \(t\) occurring in the profile, define
\[ n_t=|\{i:A_i=t\}|. \]
Construct the rational-mass instance by setting
\[ T=\{A_i:i\in V^+\}, \qquad \mu_t=\frac{n_t}{N}, \qquad t^\star=A_{i^\star}. \]
Repeated approval sets occur only once in \(T\). Their multiplicities are encoded in the masses. Every mass is positive, and
\[ \sum_{t\in T}\mu_t = \frac{1}{N}\sum_{t\in T}n_t = 1. \]
Let \(\Delta_V(c\mid S)\) denote the ordinary unweighted sequential-PAV marginal in the original profile. For every state \(S\subseteq C\) and every \(c\in C\setminus S\),
\[ \begin{aligned} \Delta_\mu(c\mid S) &= \sum_{t\in T} \frac{n_t}{N} \left( H_{|t\cap(S\cup\{c\})|} - H_{|t\cap S|} \right)\\ &= \frac{1}{N} \sum_{i\in V^+} \left( H_{|A_i\cap(S\cup\{c\})|} - H_{|A_i\cap S|} \right). \end{aligned} \]
A voter with \(A_i=\varnothing\) contributes zero to every marginal. Consequently,
\[ \Delta_\mu(c\mid S)=\frac{1}{N}\Delta_V(c\mid S). \]
The factor \(1/N\) is positive and independent of \(c\). Hence, for all remaining candidates \(c,d\),
\[ \Delta_\mu(c\mid S)\geq\Delta_\mu(d\mid S) \quad\Longleftrightarrow\quad \Delta_V(c\mid S)\geq\Delta_V(d\mid S). \]
Thus the maximizing candidates, including all ties, are identical at every state \(S\).
Induction on the number of selection steps now shows that an ordered candidate sequence is permitted in the original unweighted instance if and only if it is permitted in the rational-mass instance. Therefore the two instances have exactly the same obtainable size-\(k\) committees.
Moreover,
\[ |W\cap t^\star| = |W\cap A_{i^\star}|, \]
so the distinguished-voter condition is also preserved exactly. It is immaterial if other voters share \(A_{i^\star}\), because the target condition depends only on the distinguished approval set, not on the identity or mass of the corresponding type.
If \(A_{i^\star}=\varnothing\), then every committee \(W\) satisfies
\[ |W\cap A_{i^\star}|=0. \]
Such an instance is therefore decidable immediately from whether a size-\(k\) sequential-PAV outcome exists and whether \(0\geq s\). For standard well-formed instances with \(0\leq k\leq|C|\), an outcome always exists.
These trivial cases can be mapped to fixed valid yes- and no-instances of the rational-mass problem. For example:
Hence the requirement that all explicitly represented types be nonempty does not obstruct the reduction.
The distinct approval types can be obtained by grouping equal approval ballots. There are at most \(n\) such types, and every mass \(n_t/N\) has polynomial encoding length. The construction is therefore a polynomial-time many-one reduction.
The problem is \(\mathrm{NP}\)-hard by this reduction and belongs to \(\mathrm{NP}\) by Section 2. Therefore it is \(\mathrm{NP}\)-complete. In particular, it is not polynomial-time solvable unless \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover correctly establishes NP-completeness by exactly encoding multiplicities of identical unweighted ballots as rational masses. The normalization scales every marginal by the same positive factor, so all maximizing candidates and ties are preserved at every state. No approximation or continuity argument is used.
The proof has only a minor edge-case omission concerning encodings with \(k>|C|\).
For \(c\notin S\), if \(c\in t\), adding \(c\) increases \(|t\cap S|\) by exactly one, so the harmonic-score increment is
\[ \frac{1}{|t\cap S|+1}. \]
If \(c\notin t\), the increment is zero. The resulting formula for \(\Delta_\mu(c\mid S)\) is correct.
An ordered sequence of distinct candidates correctly records all tie choices. Comparing its selected candidate with every remaining candidate at each step is exactly the condition for the sequence to be obtainable.
The exact-arithmetic argument is sound:
There is a minor encoding edge case. The claimed bound of at most \(k|C|\) comparisons is polynomial only after observing that a yes-instance must have \(k\leq |C|\), or after specifying that the verifier first rejects \(k>|C|\). If \(k\) is binary encoded and unrestricted, the written runtime statement alone is not sufficient. This is a routine clarification and does not affect the substantive NP-membership argument.
Grouping identical nonempty ballots and assigning mass \(\mu_t=n_t/N\) is valid:
The construction meets the target input format.
The displayed identity
\[ \Delta_\mu(c\mid S)=\frac{1}{N}\Delta_V(c\mid S) \]
is correct. Empty-ballot voters contribute zero, while grouping identical nonempty ballots reproduces their multiplicities exactly.
Because \(N\geq1\), multiplication by \(1/N\) preserves all strict comparisons and equalities. Thus it preserves the complete set of maximizers, including ties, at every state. The stated induction therefore establishes equality of all permitted ordered sequences and all obtainable size-\(k\) committees.
The distinguished-voter objective is also preserved because \(t^\star=A_{i^\star}\). Other voters having the same approval set does not change the set-intersection condition.
When \(A_{i^\star}=\varnothing\), the target count is always zero. Under the standard condition \(0\leq k\leq |C|\), an outcome exists, so the source answer is determined by whether \(0\geq s\). Branching to fixed yes- and no-instances is a valid polynomial-time reduction.
The proposed fixed no-instance is indeed negative: the initial marginals are \(1/3\) for \(a\) and \(2/3\) for \(b\), so \(b\) is uniquely selected.
The write-up should explicitly state how malformed or unrestricted instances with \(k>|C|\) are treated. The natural convention is that no size-\(k\) outcome exists, but the user task did not explicitly impose \(k\leq|C|\).
The reduction is exact, polynomial in size, and preserves both every sequential tie choice and the distinguished-type objective. Combined with the valid NP-membership argument, it establishes NP-completeness. The only identified defect is a routine input-domain clarification.
⟨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.