Answer: \(\mathrm{NP}\)-complete
Proposition 3 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateFor all x ∈Rn, and all α, β ∈Rn + two weighting vectors having decreasing components we have: gα,β(x) = min τ∈Π n X i=1 (ατ(i) x+ i −βτ(i) x− i ) (6) with Π the set of permutations on {1, .., n}.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite candidate set \(C\), supported voter types \(t\) with rational masses \(\mu_t\) summing to \(1\) and grade vectors \(v^t\), a committee size \(k\), and rational rank measures \(\nu^\pm=a_0^\pm\delta_0+a^\pm(q)\,dq\) with nonnegative nonincreasing step densities, choose \(S\subseteq C\), \(|S|=k\), maximizing \(G(S)=\int_{[0,1]}Q_S^+(q)\,d\nu^+(q)-\int_{[0,1]}Q_S^-(q)\,d\nu^-(q)\), where \(u_t(S)=\sum_{c\in S}v_c^t\), and \(Q_S^+\) and \(Q_S^-\) are the ascending quantile of \(\max(u_t(S),0)\) and descending quantile of \(\max(-u_t(S),0)\) under \(\mu\).
A society is given by its support: the list of the \(\tau\ge1\) types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types.
There are \(m\ge1\) candidates \(C\), an input integer grade bound \(T\ge1\), grades \(v_c^t\in\{-T,\ldots,T\}\), and a committee size \(1\le k\le m\). Committees are subsets \(S\subseteq C\) with \(|S|=k\), and \(u_t(S)=\sum_{c\in S}v_c^t\).
The input rank measures are \(\nu^\pm=a_0^\pm\delta_0+a^\pm(q)\,dq\), where \(\delta_0\) is the unit point mass at zero, \(a_0^\pm\) are nonnegative binary rationals, and \(a^\pm\) are nonnegative nonincreasing step functions with explicitly listed binary-rational breakpoints and heights; their total masses need not equal \(1\).
Let \(Q_S^+\) be the ascending quantile of \(\max(u_t(S),0)\) under \(\mu\), and \(Q_S^-\) the descending quantile of \(\max(-u_t(S),0)\). Set \(Q_S^+(0)=\min_t\max(u_t(S),0)\) and \(Q_S^-(0)=\max_t\max(-u_t(S),0)\); other quantile boundary choices do not affect the integrals.
Define \(G(S)=\int_{[0,1]}Q_S^+(q)\,d\nu^+(q)-\int_{[0,1]}Q_S^-(q)\,d\nu^-(q)\). Let \(r\) count the density steps and \(L\) be the total binary input length; state running times in \(m,\tau,L,k,T,r\).
Given also a binary-rational threshold \(B\), is deciding whether some committee satisfies \(G(S)\ge B\) in P, or is it NP-hard?
For discrete biOWA with nonnegative nonincreasing weight vectors, the aggregate has a shared-permutation minimum representation and an assignment LP for evaluating a fixed utility vector. Discrete committee optimization is NP-hard and polynomial-time for fixed \(k\). [Martin–Perny (2019)](https://www.ijcai.org/proceedings/2019/0252.pdf)
No complexity classification for exactly the supported-mass problem above was located in the search.
The decision problem is \(\mathrm{NP}\)-complete. This remains true with \(T=1\), grades in \(\{0,1\}\), no atoms at zero, and at most three density steps across the two rank measures.
There are polynomial-time algorithms for fixed \(k\), and for jointly fixed \(\tau\) and \(T\). Fixing \(\tau\) alone is insufficient: the problem is already \(\mathrm{NP}\)-complete for \(\tau=2\) when \(T\) is binary encoded.
All claims below concern the explicitly listed support; no enumeration of other possible types is required.
Fix a committee \(S\), and choose a permutation \(\pi\) such that
\(\ u_{\pi(1)}(S)\le\cdots\le u_{\pi(\tau)}(S)\).
Define
\(p_i=\max(u_{\pi(i)}(S),0),\qquad n_i=\max(-u_{\pi(i)}(S),0),\)
\(s_0=0,\qquad s_i=\sum_{j=1}^{i}\mu_{\pi(j)},\qquad A^\pm(x)=\int_0^x a^\pm(q)\,dq.\)
Then \(p_i\) is nondecreasing, while \(n_i\) is nonincreasing. Consequently, except at interval endpoints, both relevant quantiles use the same mass intervals:
\(Q_S^+(q)=p_i,\qquad Q_S^-(q)=n_i\qquad\text{for }s_{i-1}<q<s_i.\)
Ties cause no difficulty: exchanging equal quantile values between adjacent intervals does not change either integral. The specified values at zero give the exact formula
\(G(S)=a_0^+p_1-a_0^-n_1+\sum_{i=1}^{\tau}\left[p_i\bigl(A^+(s_i)-A^+(s_{i-1})\bigr)-n_i\bigl(A^-(s_i)-A^-(s_{i-1})\bigr)\right].\)
Computing the utilities takes \(O(k\tau)\) integer additions. Sorting takes \(O(\tau\log(\tau+1))\) comparisons. Once the density breakpoints are ordered, sweeping them together with the cumulative masses computes all integral contributions in \(O(\tau+r)\) rational operations. Ordering the density lists, if necessary, costs \(O(r\log(r+1))\) comparisons once.
These operations have polynomial bit complexity. To see this explicitly, let \(D\) be the product of the denominators of all rational input entries. Its binary length is \(O(L)\). Each cumulative mass and each density breakpoint has denominator dividing the corresponding part of \(D\). Multiplying an interval length by a density height uses denominators from those two groups, so every term in the displayed formula has denominator dividing \(D\). The atom terms and \(B\) also have denominators dividing \(D\).
Moreover, \(|u_t(S)|\le kT\), and every density height and atom coefficient is bounded by \(2^{O(L)}\). Thus the reduced numerators and denominators needed for evaluation have \(O(L+\log(kT+1))=O(L)\) bits. Exact comparison with \(B\) is therefore polynomial time.
In particular, evaluation takes
\(O\!\left(k\tau+\tau\log(\tau+1)+\tau+r\right)\operatorname{poly}(L)\)
bit time after preprocessing costing
\(O\!\left(L+r\log(r+1)\right)\operatorname{poly}(L)\).
The polynomial factors here and below are independent of the numerical value of \(T\).
A certificate lists the \(k\) distinct candidates. Its validity and objective threshold can be checked by this algorithm. Hence the decision problem belongs to \(\mathrm{NP}\).
We reduce from Vertex Cover: given a finite simple graph \(H=(V,E)\) and an integer \(h\), decide whether some subset of at most \(h\) vertices meets every edge. This is a classical \(\mathrm{NP}\)-complete problem. [Karp (1972), Main Theorem, Node Cover](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf)
We may restrict to \(E\ne\varnothing\) and \(1\le h\le |V|\). The excluded cases are immediately decidable and can be replaced by fixed yes or no instances satisfying these restrictions.
Set \(C=V\), \(m=|V|\), \(k=h\), and \(T=1\). For each edge \(e\), introduce one type, with grades
\(v_c^e=\mathbf{1}_{\{c\in e\}}.\)
Because the graph is simple, different edges give different grade vectors. The support therefore has exactly \(\tau=|E|\) types. For every committee,
\(u_e(S)=|S\cap e|\in\{0,1,2\}.\)
We now construct positive dyadic masses and an atom-free measure that evaluates the minimum utility. Put
\(d=\max\{1,\lceil\log_2\tau\rceil\},\qquad \varepsilon=2^{-d}.\)
Enumerate the types and assign
\(\mu_i=\varepsilon\quad(1\le i<\tau),\qquad \mu_\tau=1-(\tau-1)\varepsilon.\)
These masses sum to \(1\). Since \(\tau\varepsilon\le1\), every mass is at least \(\varepsilon>0\).
Take \(a_0^+=a_0^-=0\), \(a^-=0\), and let \(a^+\) have height \(\varepsilon^{-1}\) on \([0,\varepsilon)\) and height \(0\) on \([\varepsilon,1]\). This density is nonnegative and nonincreasing. Its integral is \(1\), and the total number of density steps across both signs is at most three.
For any committee, the set of types attaining \(\min_e u_e(S)\) has mass at least \(\varepsilon\). All utilities are nonnegative. Therefore
\(Q_S^+(q)=\min_e u_e(S)\qquad\text{for }0<q<\varepsilon.\)
There are no atoms, so endpoint choices are irrelevant, and
\(G(S)=\varepsilon^{-1}\int_0^\varepsilon Q_S^+(q)\,dq=\min_e u_e(S).\)
Choose \(B=1\). It follows that
\(G(S)\ge1\quad\Longleftrightarrow\quad |S\cap e|\ge1\text{ for every }e\in E.\)
Thus a size-\(h\) committee meets the threshold exactly when it is a size-\(h\) vertex cover. A cover of size at most \(h\) can be enlarged to size exactly \(h\), because \(h\le |V|\); adding vertices preserves coverage. This proves both directions of the reduction.
The grade table has \(m\tau\) entries. Each mass, breakpoint, and density height uses \(O(\log(\tau+1))\) bits. The construction therefore has polynomial size and can be written in
\(O(m\tau+\tau\log(\tau+1)+\log(m+1))\) bit operations.
Together with Section 1, this proves \(\mathrm{NP}\)-completeness under the stated restrictions.
Enumerate all \(\binom{m}{k}\) committees and evaluate each exactly. Including preprocessing, the running time is
\(O\!\left(L+r\log(r+1)+\binom{m}{k}\bigl[k\tau+\tau\log(\tau+1)+\tau+r\bigr]\right)\operatorname{poly}(L).\)
Since \(\binom{m}{k}\le m^k\), this is polynomial time for each fixed \(k\), including arbitrary binary-encoded \(T\).
Write \(v_c=(v_c^1,\ldots,v_c^\tau)\). Every utility vector obtainable using at most \(k\) candidates lies in
\(\mathcal Z=\{-kT,\ldots,kT\}^{\tau},\qquad N=|\mathcal Z|=(2kT+1)^\tau.\)
Number the candidates \(1,\ldots,m\). Let \(D_i(j,z)\) mean that some \(j\)-element subset of the first \(i\) candidates has utility vector \(z\). Initialize \(D_0(0,0)\) to true and every other entry to false. Use
\(D_i(j,z)=D_{i-1}(j,z)\ \lor\ \bigl(j\ge1\text{ and }D_{i-1}(j-1,z-v_i)\bigr),\)
with entries outside the allowed ranges interpreted as false.
The recurrence is exact: every subset either excludes candidate \(i\), or includes it and leaves a subset with one fewer candidate and utility vector \(z-v_i\). Induction on \(i\) proves the stated meaning of every entry.
Finally, evaluate \(G(z)\) for each vector with \(D_m(k,z)\) true and compare with \(B\). Equal utility vectors necessarily give equal objectives.
The running time is
\(O\!\left(L+r\log(r+1)+N\bigl[mk\tau+\tau\log(\tau+1)+\tau+r\bigr]\right)\operatorname{poly}(L).\)
The dynamic-programming tables use \(O((k+1)N)\) Boolean entries when only consecutive layers are retained. This algorithm is polynomial for jointly fixed \(\tau,T\), and pseudopolynomial in \(T\) for fixed \(\tau\).
For completeness, we give a reduction showing why the preceding dependence on \(T\) matters.
Use Partition: given positive binary integers \(a_1,\ldots,a_n\), ask whether some subset sums to \(A/2\), where \(A=\sum_i a_i\). This problem is \(\mathrm{NP}\)-complete. [Karp (1972), Main Theorem, Partition](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf)
Create \(n\) item candidates with two-type grade vectors
\(v_i=(na_i,\ A-na_i),\)
and \(n\) additional candidates, each with vector \((0,A)\). Set
\(m=2n,\qquad k=n,\qquad \tau=2,\qquad T=\max\{n\max_i a_i,A\}.\)
Every grade lies in \(\{-T,\ldots,T\}\). Give both types mass \(1/2\). Use no atoms, zero negative density, and a positive density of height \(2\) on \([0,1/2)\) and height \(0\) thereafter. These rank measures are fixed, independent of the Partition instance.
For any committee, let \(I\) be its chosen item candidates and put \(s=\sum_{i\in I}a_i\). Because exactly \(n\) candidates are selected,
\(u_1(S)=ns,\qquad u_2(S)=nA-ns.\)
Both totals are nonnegative, since \(0\le s\le A\). The prescribed masses and density give
\(G(S)=\min\{ns,nA-ns\}.\)
With \(B=nA/2\),
\(G(S)\ge B\quad\Longleftrightarrow\quad s=A/2.\)
Every subset \(I\) can be extended to an \(n\)-candidate committee using the additional candidates. Thus the equivalence holds in both directions. All output numbers have polynomial binary length, completing the reduction.
Consequently, even with exactly two supported types and fixed atom-free rank measures, the problem is \(\mathrm{NP}\)-complete when \(T\) is binary encoded.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output establishes that the specified supported-mass decision problem is \(\mathrm{NP}\)-complete. Both reductions are valid, exact evaluation has polynomial bit complexity, and the stated algorithms for bounded parameters are correct. I found no major or minor mathematical issues.
Sorting the signed utilities in ascending order makes \(p_i=\max(u_{\pi(i)}(S),0)\) nondecreasing and \(n_i=\max(-u_{\pi(i)}(S),0)\) nonincreasing. Consequently, the ascending positive quantile and descending negative quantile occupy the same cumulative-mass intervals, as asserted. This remains valid when utilities have mixed signs: clipping creates additional ties but preserves the required orders.
The formula for \(G(S)\) correctly integrates each constant quantile value over its mass interval. Its atom contributions are also correct: \(p_1\) is the minimum positive-part utility, and \(n_1\) is the maximum negative-part utility. Thus the formula respects the task’s special definitions at zero. Other interval endpoints carry no density mass, so their boundary conventions do not affect the result.
Tied signed utilities have identical positive and negative parts, making their ordering immaterial. The case \(\tau=1\) also fits the formula without modification.
The operation counts are valid. Computing utilities requires \(O(k\tau)\) additions; sorting requires \(O(\tau\log(\tau+1))\) comparisons; merging the cumulative-mass intervals with the density steps requires \(O(\tau+r)\) rational operations.
The denominator argument is sound. An interval length uses denominators from masses and breakpoints, while its density multiplier uses a separate input denominator. The product \(D\) includes all these factors, so each reduced contribution has denominator dividing \(D\). Integer utility multipliers introduce no additional denominators. Summing the contributions therefore preserves the claimed denominator bound.
The numerator bounds are also sufficient: utilities have magnitude at most \(kT\), coefficients have polynomial binary length, and the number of contributions is bounded by the explicit input size. Exact arithmetic and comparison with \(B\) therefore have polynomial bit complexity. The displayed evaluation and preprocessing bounds are justified.
A certificate containing \(k\) distinct candidate indices has polynomial length. Its validity and threshold condition can be checked by the stated evaluation algorithm. Membership in \(\mathrm{NP}\) follows.
The invoked theorem is the standard \(\mathrm{NP}\)-completeness of deciding whether a graph has a vertex cover of size at most a given bound. This matches the Node Cover problem in [Karp’s Main Theorem](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf). Restricting to nonempty edge sets and \(1\le h\le |V|\) removes only immediately decidable cases, as the output explains.
The construction satisfies the target’s input requirements. Candidates correspond to vertices; edge types have grades in \(\{0,1\}\); \(T=1\); and \(k=h\) is admissible. Distinct edges in a simple graph have distinct incidence vectors, so the support contains exactly \(|E|\) types.
The mass calculation is correct. With \(\varepsilon=2^{-d}\), one has \(\tau\varepsilon\le1\), hence \(\mu_\tau=1-(\tau-1)\varepsilon\ge\varepsilon>0\). All masses are dyadic and sum to one. When \(\tau=1\), the sole mass is one and the same argument remains valid.
The positive density is nonnegative and nonincreasing, has integral one, and uses two constant pieces. The zero negative density uses at most one further piece. Both atom coefficients vanish, so the stated restriction of at most three density steps is satisfied.
Every minimum-utility type has mass at least \(\varepsilon\). Therefore the ascending positive quantile equals the minimum utility throughout the open interval \((0,\varepsilon)\). Since all utilities are nonnegative, the identity \(G(S)=\min_e u_e(S)\) follows exactly.
With \(B=1\), meeting the threshold is equivalent to covering every edge. The conversion from “at most \(h\)” to “exactly \(h\)” is justified by \(h\le |V|\), and adding vertices preserves coverage. Both directions of the reduction hold.
The grade table and rational coefficients have polynomial output size. Their stated construction-time bound is consistent with writing the explicit table and dyadic encodings. Combined with membership in \(\mathrm{NP}\), this establishes the principal classification and its claimed restrictions.
Enumerating all \(\binom{m}{k}\) committees is exhaustive. Applying the exact evaluator to each committee yields the displayed running-time bound, with density preprocessing performed once.
The inequality \(\binom{m}{k}\le m^k\) gives polynomial time for every fixed \(k\). Binary encoding of \(T\) causes no difficulty because evaluation depends polynomially on its bit length.
Every utility coordinate of a subset with at most \(k\) candidates lies between \(-kT\) and \(kT\). Thus the stated state space contains every relevant partial utility vector.
The initialization is correct. The recurrence correctly separates subsets that exclude candidate \(i\) from those that include it. Reading exclusively from the preceding candidate layer prevents repeated selection of a candidate.
Interpreting out-of-range entries as false is valid: no subset of an allowed cardinality can have a coordinate outside the stated bounds. Consequently, this truncation cannot discard a relevant reachable state.
Evaluating reachable states with cardinality exactly \(k\) is sufficient because \(G\) depends only on the utility vector and the fixed masses and rank measures.
There are \(N=(2kT+1)^\tau\) utility states. The stated time bound accounts for the candidate layers, cardinalities, coordinate operations, and final evaluations. Retaining two consecutive layers gives the claimed \(O((k+1)N)\) Boolean-entry bound.
For jointly fixed \(\tau,T\), the running time is polynomial because \(k\le m\). For fixed \(\tau\), the dependence on the numerical value of \(T\) is pseudopolynomial, as stated.
The invoked source problem is the standard \(\mathrm{NP}\)-complete Partition problem on positive binary integers, listed in [Karp’s Main Theorem](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf). The reduction uses this formulation directly.
All candidate grades satisfy the chosen bound \(T=\max\{n\max_i a_i,A\}\), including potentially negative coordinates \(A-na_i\). Also, \(m=2n\) and \(k=n\) satisfy the committee-size restriction.
The two supported types are distinct: every additional candidate has grade zero for the first type and grade \(A>0\) for the second. Both masses are positive and sum to one. Repeated additional candidate vectors are permitted because committees select distinct candidates, not distinct grade vectors.
For any committee, the identities \(u_1(S)=ns\) and \(u_2(S)=nA-ns\) correctly account for all \(n\) selected candidates. Since \(0\le s\le A\), both utilities are nonnegative despite possible negative individual grades.
The fixed density and equal masses yield \(G(S)=\min\{ns,nA-ns\}\). Its comparison with \(B=nA/2\) is equivalent to \(s=A/2\). This also handles odd \(A\): the rational threshold is admissible, and no integer subset sum can equal \(A/2\).
Every item subset can be padded to a size-\(n\) committee using the \(n\) additional candidates. Conversely, every threshold-satisfying committee supplies a partition subset through its selected items. Output size and construction time are polynomial in the source bit length.
Required feedback: No repair or additional mathematical clarification is needed. The general hardness result and all supplementary parameter claims are established.
⟨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.