Answer: For \(\lambda(j)=1\) throughout, both variants are in \(\mathsf{P}\). For every other fixed admissible \(\lambda\), the exact variant is \(\mathsf{NP}\)-hard and \(\mathsf{coNP}\)-hard, and the greedy variant is \(\mathsf{NP}\)-complete.
Theorem 3.3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateConsider a Thiele rule $\RRR$ associated with the OWA $\lambda$. If $\lambda(i)=1$ for all $i \in{\mathbb N}^+$, then the problem $\RRR$-\RCE is polynomial-time solvable. Otherwise, it is \coNP-hard and \coWone-hard when parameterized by $k$. These hardness results hold for all fixed $\ell \in [k-s]$ where $s \in \NN^+$ is the smallest number such that $\lambda(s+1) < 1$, and even if $\Dist(E, E')=1$.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a candidate set \(C\), committee size \(k\), distance bound \(\ell\), a Thiele rule with OWA function \(\lambda\), and a binary-rational distribution \(\mu\) over pairs of nonempty ballots \((A,B)\), define the stage marginals \(\mu^0_A=\sum_B\mu_{A,B}\) and \(\mu^1_B=\sum_A\mu_{A,B}\). Given a size-\(k\) committee \(S\) maximizing the stage-0 score, does there exist a size-\(k\) committee \(S'\) maximizing the stage-1 score \(F_\lambda(\mu^1,S')=\sum_B\mu^1_B\sum_{j=1}^{|S'\cap B|}\lambda(j)\) with \(k-|S\cap S'|\le\ell\)? For the greedy variant, replace score maximizers with committees obtainable by greedy marginal-score choices, allowing any tie resolution.
Let \(C\) be a candidate set with \(m\geq1\), let \(1\leq k\leq m\), and let \(0\leq\ell\leq k\) be integers. Committees are size-\(k\) subsets of \(C\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. Here types are pairs \((A,B)\) of nonempty approval ballots contained in \(C\), and \(\sum_{A,B}\mu_{A,B}=1\). The support size \(\tau\) counts listed pairs, not possible types.
For each fixed polynomial-time computable OWA function \(\lambda:\mathbb N^+\to\mathbb Q\cap[0,1]\), require \(\lambda(1)=1\) and \(\lambda(j+1)\leq\lambda(j)\).
Define \(\mu^0_A=\sum_B\mu_{A,B}\), \(\mu^1_B=\sum_A\mu_{A,B}\), and \(F_\lambda(\nu,T)=\sum_D\nu_D\sum_{j=1}^{|T\cap D|}\lambda(j)\), with an empty inner sum equal to zero.
An exact winning committee maximizes \(F_\lambda\) over size-\(k\) subsets. A greedy winning committee is obtainable from the empty set by repeatedly adding an unselected candidate maximizing the score increment, for \(k\) steps; every resolution of ties is allowed.
For either variant, the input includes a committee \(S\) promised to win for \(\mu^0\) under that variant. Decide whether some committee \(S'\) winning for \(\mu^1\) under the same variant satisfies \(k-|S\cap S'|\leq\ell\).
Let \(L\) be the total binary input length; state running times in \(m,\tau,L,k,\ell\).
For each fixed admissible \(\lambda\), is this decision problem in \(\mathsf P\) or \(\mathsf{NP}\)-hard, separately for the exact and greedy variants?
For finite electorates, the exact problem is polynomial-time solvable for Approval Voting, where \(\lambda(j)=1\) throughout, and otherwise is \(\mathsf{coNP}\)-hard and \(\mathsf{coW[1]}\)-hard parameterized by \(k\).
The finite-electorate greedy problem is polynomial-time solvable for Approval Voting and \(\mathsf{NP}\)-hard for every other admissible OWA function. These results do not explicitly classify the rational-mass formulation.
For every fixed admissible \(\lambda\), the rational-mass problem has the following classification under polynomial-time many-one reductions:
| OWA function | Exact variant | Greedy variant |
|---|---|---|
| \(\lambda(j)=1\) for every \(j\) | \(\mathsf{P}\) | \(\mathsf{P}\) |
| Any other admissible \(\lambda\) | \(\mathsf{NP}\)-hard and \(\mathsf{coNP}\)-hard | \(\mathsf{NP}\)-complete |
The exact variant’s \(\mathsf{NP}\)-hardness requires an additional argument: it does not follow merely from the supplied finite-electorate \(\mathsf{coNP}\)-hardness result. Section 4 gives a direct reduction.
These are classifications with \(k\) and \(\ell\) included in the input. Some restrictions are easy: \(\ell=k\) always gives a yes-instance, as does \(k=m\). Moreover, whenever \(\lambda(j)=1\) for every \(j\leq k\), both variants coincide with Approval Voting.
Write the support as \((A_i,B_i,\mu_i)\), for \(i\in\{1,\ldots,\tau\}\). Directly from the definition of the marginal,
\( F_\lambda(\mu^1,T) =\sum_{i=1}^{\tau}\mu_i\sum_{j=1}^{|T\cap B_i|}\lambda(j). \)
Thus all computations can use the listed pairs directly; aggregation of identical second-stage ballots is optional.
To check the arithmetic bounds, write \(\mu_i=p_i/q_i\) and \(\lambda(j)=a_j/d_j\), with positive denominators. Define
\( Q=\prod_{i=1}^{\tau}q_i,\qquad D=\prod_{j=1}^{k}d_j,\qquad w_i=p_iQ/q_i,\qquad v_j=a_jD/d_j. \)
Every committee score has the integer representation
\( QD\,F_\lambda(\mu^1,T) =\sum_{i=1}^{\tau}w_i\sum_{j=1}^{|T\cap B_i|}v_j. \)
The bit length of \(Q\) is bounded by the input length. Since \(\lambda\) is fixed and polynomial-time computable, the total encoding length of its first \(k\) values is polynomial in \(k\). Also, \(0\leq F_\lambda(\mu^1,T)\leq k\). Consequently, all score and marginal comparisons have polynomial bit complexity in \(L+k\).
Below, \(P_\lambda(L+k)\) denotes a fixed polynomial large enough to cover these arithmetic costs and the computation of \(\lambda(1),\ldots,\lambda(k)\).
Consider a finite electorate of \(n\) voters, whose two ballots are \((A_i,B_i)\). For each distinct pair \((A,B)\), let \(n_{A,B}\) be its multiplicity and output the positive mass
\( \mu_{A,B}=n_{A,B}/n. \)
There are at most \(n\) listed pairs, and each mass has encoding length \(O(\log n)\). This transformation is polynomial-time in the explicit finite-electorate input.
For every committee, its rational-mass score equals its finite-electorate score divided by \(n\). The same identity holds for every greedy marginal increment. Therefore:
Hence the supplied finite-electorate hardness results transfer to rational masses. In particular, this proves greedy \(\mathsf{NP}\)-hardness and exact \(\mathsf{coNP}\)-hardness for every non-AV function. The quoted results appear as Theorem 3.3 and Corollary 4.3 of [Zech, Boehmer, Elkind, and Teh, *Multiwinner Temporal Voting with Aversion to Change*](https://arxiv.org/html/2408.11017v1).
The supplied exact \(\mathsf{coW[1]}\)-hardness also transfers, because the transformation leaves \(k\) unchanged.
Suppose \(\lambda(j)=1\) throughout. Define each candidate’s second-stage approval mass by
\( a(c)=\sum_{i:c\in B_i}\mu_i. \)
Then
\( F_\lambda(\mu^1,T)=\sum_{c\in T}a(c). \)
The greedy marginal of \(c\) is always \(a(c)\), independent of previously selected candidates. Thus the exact and greedy winning committees coincide.
Let \(b\) be the \(k\)-th largest approval mass, and define
\( H=\{c:a(c)>b\},\qquad E=\{c:a(c)=b\}. \)
Every winning committee contains all of \(H\), exactly \(k-|H|\) candidates from \(E\), and no other candidates. Indeed, violating this description permits replacing a selected candidate by an unselected candidate with strictly greater approval mass.
The largest overlap with \(S\) among winning committees is therefore
\( r_{\max} =|H\cap S|+\min\{k-|H|,\ |E\cap S|\}. \)
This bound is attainable: choose as many members of \(E\cap S\) as the remaining capacity permits, and then fill any remaining positions from \(E\setminus S\).
The answer is yes precisely when
\( r_{\max}\geq k-\ell. \)
Using a common denominator for the masses, schoolbook integer arithmetic, and sorting, a valid bit-operation bound is
\( O\!\left( L+(m\tau+m\log(m+1)+\tau+k)(L+1)^2 \right). \)
The algorithm uses the listed support; it never expands masses into voters.
A certificate is an ordered list of distinct candidates \(c_1,\ldots,c_k\). Put \(U_0=\varnothing\) and \(U_t=\{c_1,\ldots,c_t\}\).
At step \(t\), the marginal of an unselected candidate \(c\) is
\( \Delta(c\mid U_{t-1}) =\sum_{i:c\in B_i}\mu_i\lambda(|U_{t-1}\cap B_i|+1). \)
Check that \(c_t\) has maximum marginal among all unselected candidates, permitting equality. Finally, check \(|U_k\cap S|\geq k-\ell\).
These checks take
\( O\!\left(km\tau P_\lambda(L+k)\right) \)
time. Acceptance is equivalent to a greedy winning committee satisfying the distance bound. Combined with the transfer lemma, this proves \(\mathsf{NP}\)-completeness for every non-AV greedy rule.
Enumerate all \(\binom{m}{k}\) committees. Evaluate each score, and retain the largest overlap with \(S\) among committees achieving the largest score. This gives the bound
\( O\!\left( \left[m\tau+\tau k\binom{m}{k}\right]P_\lambda(L+k) \right). \)
In particular, the exact problem is fixed-parameter tractable in \(m\) and belongs to \(\mathsf{XP}\) parameterized by \(k\).
It also belongs to \(\mathsf{P}^{\mathsf{NP}}\): binary-search the optimal integer-scaled score using an oracle for the existence of a committee meeting a score threshold, then ask whether a committee achieves that optimum and the required overlap. The search takes polynomially many queries because the scaled scores have polynomial bit length.
The number of size-\(k\) committees within distance \(\ell\) of \(S\) is
\( N_\ell =\sum_{r=0}^{\min\{\ell,m-k\}} \binom{k}{r}\binom{m-k}{r}. \)
For each such committee \(T\), test whether it is greedy-obtainable by dynamic programming over subsets of \(T\). Mark \(\varnothing\) reachable. From a reachable \(U\subsetneq T\), mark \(U\cup\{c\}\) reachable for every \(c\in T\setminus U\) whose marginal is maximal among all of \(C\setminus U\).
This dynamic program is correct because all future marginals depend on the selected set \(U\), rather than its selection order. Its transitions are exactly the permitted greedy additions. Thus \(T\) is obtainable if and only if its full-set state is reachable.
The resulting running time is
\( O\!\left( \left[m\tau+N_\ell 2^k m\tau\right]P_\lambda(L+k) \right). \)
Alternatively, applying the same dynamic program to all subsets of \(C\) of size at most \(k\) gives
\( O\!\left( m\tau \sum_{i=0}^{k-1}\binom{m}{i} \,P_\lambda(L+k) \right). \)
These bounds again depend on the listed support size \(\tau\), rather than the number of possible ballot pairs.
Fix an admissible function \(\lambda\) that is not AV. Let \(s\geq1\) be the smallest index satisfying
\( \lambda(s+1)<1. \)
By monotonicity and minimality,
\( \lambda(1)=\cdots=\lambda(s)=1,\qquad \delta:=1-\lambda(s+1)>0. \)
Both \(s\) and \(\delta\) are constants associated with the fixed rule.
We reduce from Independent Set. Its input is a simple graph \(G=(V,E_G)\), with \(n=|V|\), and a target \(\kappa\) satisfying \(1\leq\kappa\leq n\). Restricting to these bounds retains \(\mathsf{NP}\)-hardness, since instances outside them are trivial.
Add a new vertex \(p\), isolated from \(V\), and put
\( X=V\cup\{p\},\qquad r=\kappa+1. \)
Let \(D\) be a disjoint set of \(r\) dummy vertices. Construct a graph \(H\) on \(X\cup D\) with:
Write \(h=|X\cup D|\).
Finally, add a disjoint set \(F\) of \(s-1\) padding candidates. The election’s candidate set and committee size are
\( C=X\cup D\cup F,\qquad k=r+s-1=\kappa+s. \)
Choose any \(\kappa\)-element subset \(R\subseteq V\), and supply
\( S=F\cup\{p\}\cup R,\qquad \ell=r-1=\kappa. \)
Thus \(S\) has the required size \(k\).
First specify unnormalized integer ballot weights:
Every weight in the second group is positive because \(\deg_H(v)\leq h-1\). Let \(W\) be the total weight of these two groups, and put \(M=W+1\).
Let \(Z=W+(s-1)M\) be the total weight. For each weighted second-stage ballot \(B\) of weight \(w\), output the type
\( (A,B)=(S,B),\qquad \mu_{S,B}=w/Z. \)
All ballots are nonempty, all listed masses are positive, and their sum is \(1\). If any types coincide, combine their weights.
Every first-stage ballot is \(S\). Hence for every size-\(k\) committee \(T\),
\( F_\lambda(\mu^0,T) =\sum_{j=1}^{|T\cap S|}\lambda(j) \leq\sum_{j=1}^{k}\lambda(j) =F_\lambda(\mu^0,S), \)
because all weights \(\lambda(j)\) are nonnegative. The promised first-stage optimality of \(S\) is therefore satisfied.
Multiplying second-stage scores by \(Z\) does not change their maximizers. We henceforth use these unnormalized scores.
Suppose a size-\(k\) committee \(T\) omits \(f\in F\). Since \(k>|F|\), it contains some candidate \(x\notin F\). Replace \(x\) by \(f\).
The singleton ballot \(\{f\}\) increases the score by exactly \(M\). The other padding singleton ballots have unchanged scores.
For each of the first two ballot groups, replacing one candidate by another changes its approval count by at most one. Its score can consequently decrease by at most its weight, because every marginal weight lies in \([0,1]\). The total loss from those groups is at most \(W\).
The replacement therefore increases the score by at least
\( M-W=1>0. \)
Thus an exact winner cannot omit any member of \(F\). For \(s=1\), this assertion is vacuous.
Consider a committee \(F\cup T\), where \(T\subseteq X\cup D\) and \(|T|=r\).
Every ballot in the first two groups receives a constant contribution \(s-1\) from \(F\). Beyond this:
Therefore an edge ballot’s contribution beyond padding is
\( |T\cap\{u,v\}|-\delta\,\mathbf{1}[\{u,v\}\subseteq T]. \)
The weighted linear contribution of each selected vertex \(v\) is
\( \deg_H(v)+(h-\deg_H(v))=h. \)
Let \(e_H(T)\) denote the number of edges induced by \(T\) in \(H\). Adding all contributions gives
\( \operatorname{score}(F\cup T) =(s-1)W+(s-1)M+rh-\delta e_H(T). \)
The first three terms are independent of \(T\). Since \(\delta>0\), maximizing the score is equivalent to minimizing \(e_H(T)\).
The dummy set \(D\) has size \(r\) and induces no edges. Together with Section 4.3, this proves the exact characterization:
The second-stage exact winning committees are precisely \(F\cup T\), where \(T\) is an independent set of size \(r\) in \(H\).
Because every vertex of \(X\) is adjacent to every vertex of \(D\), an independent set of size \(r\geq2\) cannot meet both sets. Consequently, a size-\(r\) independent set in \(H\) is either \(D\) or lies entirely in \(X\).
If \(G\) has an independent set \(I\subseteq V\) of size \(\kappa\), then \(I\cup\{p\}\) is an independent set of size \(r\) in \(X\). Thus
\( S'=F\cup I\cup\{p\} \)
is an exact winner. It shares at least \(F\cup\{p\}\) with \(S\), so
\( k-|S\cap S'| \leq k-s =\kappa =\ell. \)
The constructed instance is therefore a yes-instance.
Conversely, suppose \(G\) has no independent set of size \(\kappa\). Then \(X\) has no independent set of size \(\kappa+1\): deleting \(p\), if present, from such a set would leave at least \(\kappa\) independent vertices of \(G\).
The only size-\(r\) independent set in \(H\) is consequently \(D\), so the unique second-stage exact winner is \(F\cup D\). Its overlap with \(S\) is exactly \(F\), and hence
\( k-|S\cap(F\cup D)| =k-(s-1) =r =\kappa+1 >\ell. \)
The constructed instance is a no-instance. This proves both directions of the reduction.
For fixed \(\lambda\), \(s\) is constant. The construction has
\( m=n+\kappa+s+1=O_\lambda(n),\qquad \tau=O_\lambda(n^2). \)
Furthermore,
\( W=|E(H)|+\sum_v(h-\deg_H(v)) =h^2-|E(H)| \leq h^2. \)
Thus \(M\) and \(Z\) have \(O_\lambda(\log(n+1))\) bits, as do every mass numerator and denominator. Ballots and the whole support have polynomial encoding length. The reduction is therefore polynomial-time.
This completes the missing \(\mathsf{NP}\)-hardness proof for every non-AV exact rule. It also preserves the parameter up to the fixed additive constant \(s\), since \(k=\kappa+s\).
Binary rational masses preserve the finite-electorate hardness results, and their scores admit polynomial-bit exact comparisons. Approval Voting remains polynomial-time solvable for both variants. For every other admissible OWA function, the exact variant is \(\mathsf{NP}\)-hard by the direct reduction above, and the greedy variant is \(\mathsf{NP}\)-complete.
⟨structured verdict parsed — rendered above⟩
The prover resolves the requested classification. The direct reduction for the exact variant is correct, and the algorithms and hardness transfer are valid. I found no major or minor mathematical issues.
All complexity statements below concern the promised inputs specified in USER_TASK.
The marginal-score identity is correct: summing over listed pairs counts each second-stage ballot with precisely its marginal mass. Duplicate second-stage ballots need not be aggregated.
The integer scaling is also correct. Each denominator \(q_i\) divides \(Q\), each denominator \(d_j\) divides \(D\), and therefore \(w_i\) and \(v_j\) are integers. The stated identity
\[
QD\,F_\lambda(\mu^1,T)
=\sum_i w_i\sum_{j=1}^{|T\cap B_i|}v_j
\]
holds exactly.
The bit-length argument is sufficient:
Thus the claimed polynomial-time exact comparisons are justified.
The transformation replaces the multiplicity of each ballot pair by its multiplicity divided by the total number of voters. It has polynomial output size for an explicitly listed finite electorate.
Every committee score and every greedy marginal is multiplied by the same positive factor \(1/n\). This preserves exact maximizers, all greedy ties, the first-stage winning promise, and the distance condition. It also preserves \(k\), so the parameterized hardness transfer is valid.
The cited results have the required hypotheses: rational, polynomial-time computable, normalized, nonincreasing OWA functions; nonempty ballots; and greedy outcomes allowing all tie resolutions. Theorem 3.3 and Corollary 4.3 give the asserted finite-electorate hardness for non-AV rules. Their restrictions on the allowed distance do not obstruct hardness when that distance is an input parameter. [Cited paper](https://arxiv.org/html/2408.11017v1)
The prover correctly distinguishes this transfer from the additional argument needed to establish exact-variant \(\mathsf{NP}\)-hardness.
For AV, the score is the sum of selected candidates’ approval masses, and each greedy marginal is independent of previously selected candidates. Hence exact and greedy winners coincide.
The threshold characterization using \(H\) and \(E\) is correct. There are fewer than \(k\) candidates strictly above the threshold, and sufficiently many candidates at the threshold to fill the remaining positions. Every committee with the specified composition maximizes the additive score; any other composition admits a strictly improving exchange.
The overlap bound
\[
r_{\max}=|H\cap S|+\min\{k-|H|,\ |E\cap S|\}
\]
is both an upper bound and attainable. Accordingly, the decision criterion is correct.
The stated bit-operation bound covers common-denominator arithmetic, approval-mass accumulation, sorting, and overlap computation. No voter expansion is required.
Greedy membership. The certificate explicitly supplies a selection order. The marginal formula is correct, and checking against every unselected candidate verifies exactly the permitted greedy transitions, including ties. The final overlap check establishes the requested condition. Certificate length and verification time are polynomial, so the \(\mathsf{NP}\)-membership claim is valid.
Exact enumeration. Enumerating all size-\(k\) committees and maximizing overlap among maximum-score committees solves the problem. The stated bound accommodates score evaluation and overlap computation. The resulting \(\mathsf{FPT}\) claim for \(m\) and \(\mathsf{XP}\) claim for \(k\) follow.
Exact oracle upper bound. Existence of a committee meeting an integer-scaled score threshold has an \(\mathsf{NP}\) certificate. Polynomial bit length permits polynomially many binary-search queries. The final query adds the overlap constraint at the computed optimum. Thus membership in \(\mathsf{P}^{\mathsf{NP}}\) is justified.
Greedy enumeration. The formula for \(N_\ell\) correctly counts committees formed by removing and replacing the same number of members of \(S\). Its summation limits cover all feasible replacements.
The subset dynamic program is correct: marginals depend only on the selected set, and its transitions are precisely globally maximizing greedy additions. Reachability therefore characterizes greedy obtainability. Both stated enumeration bounds are valid with the polynomial factor chosen as described.
Fixed-rule constants. Non-AV and monotonicity imply a finite first drop below \(1\). Thus \(s\) exists, the first \(s\) weights equal \(1\), and \(\delta>0\). Both are constants for the fixed rule.
Candidate construction. The sets are disjoint as specified. Since \(\kappa\leq n\), the choice of \(R\) exists. The committee \(S\) has size \(k=\kappa+s\), and \(\ell=\kappa\) satisfies the required input bounds.
Masses and promise. Every vertex-ballot weight is positive because the graph is simple. All ballots are nonempty, \(Z>0\), and normalization produces positive rational masses summing to \(1\). Every first-stage ballot equals \(S\); nonnegative OWA weights therefore make \(S\) an exact winner, even when some later weights vanish.
Forced padding. A committee omitting a padding candidate contains a nonpadding candidate available for replacement. The replacement gains \(M\) from the corresponding singleton ballot. Each other weighted ballot can lose at most its weight, so total loss is at most \(W\). The strict improvement \(M-W=1\) proves that every winner contains all padding candidates. The empty-padding case is explicitly covered.
Score formula. With all padding selected, an edge ballot’s remaining contribution is its selected-endpoint count minus \(\delta\) when both endpoints are selected. Vertex-ballot weights make the total linear contribution of each selected vertex exactly \(h\). The padding constants are counted correctly, yielding
\[
(s-1)W+(s-1)M+rh-\delta e_H(T).
\]
Since \(D\) is an independent size-\(r\) set, the minimum induced-edge count is zero. The characterization of winners as padded independent size-\(r\) sets follows.
Reduction equivalence. Complete adjacency between \(X\) and \(D\) prevents any independent set from meeting both. An independent size-\(\kappa\) set in \(G\), together with \(p\), gives a winner satisfying the distance bound. Conversely, absence of such a set prevents any independent size-\(\kappa+1\) set in \(X\). The unique winner is then \(F\cup D\), whose distance from \(S\) is \(\kappa+1>\ell\). Both directions are correct.
Encoding. The candidate count is correct, the support is quadratic for fixed \(\lambda\), and the identity \(W=h^2-|E(H)|\) follows from the degree sum. All weights and denominators have logarithmic bit length in \(n+1\). The reduction is polynomial-time and respects the promise.
The classification stands: AV is polynomial-time solvable in both variants; every other fixed admissible rule gives an exact problem that is both \(\mathsf{NP}\)-hard and \(\mathsf{coNP}\)-hard, and a greedy problem that is \(\mathsf{NP}\)-complete.
The stated easy restrictions are also correct. No additional clarification or mathematical repair is needed. The status label below records the established non-AV hardness; the AV exception is separately proved.
⟨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.