Answer: \(\mathrm{NP}\)-complete and \(\mathrm{W[1]}\)-hard parameterized by \(k\); not FPT unless \(\mathrm{FPT}=\mathrm{W[1]}\).
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximatePESSIMIST is W[1]-hard wrt. k. The proof is via a parameterized reduction from the IN- DEPENDENT SET problem on regular graphs.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), committee size \(k\), a support \(T^+\) of complete rankings with positive binary-rational masses \(\mu_t\) summing to \(1\), and a rational threshold \(q\), does there exist \(S\subseteq C\) with \(|S|=k\) such that \(\sum_{t\in T^+}\mu_t\min_{c\in S}\beta_t(c)\ge q\), where \(\beta_t(c)\) is candidate \(c\)’s Borda score in ranking \(t\)?
Let \(C\) be a set of \(m\ge1\) candidates and let \(k\) be an input integer with \(1\le k\le m\). Types are strict complete rankings of \(C\); \(\beta_t(c)\) denotes the standard unnormalized Borda score of candidate \(c\) in type \(t\).
A society is given by its support: the list \(T^+\) of the \(\tau\) distinct types with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_{t\in T^+}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings. Let \(L\) be the total binary input length; state running times in \(m,\tau,L,k\).
Given a binary-rational threshold \(q\in\mathbb Q\), decide whether there exists a committee \(S\subseteq C\), \(|S|=k\), satisfying \(\sum_{t\in T^+}\mu_t\min_{c\in S}\beta_t(c)\ge q\). Equality is accepted, and no tie-breaking is imposed.
Is this decision problem in \(\mathrm P\) or \(\mathrm{NP}\)-hard? If it is \(\mathrm{NP}\)-hard, is it FPT parameterized by \(k\)?
For finite lists of voters, utilitarian Pessimist is [NP-hard with Borda utilities](https://arxiv.org/pdf/1402.3044), and is [\(\mathrm{W[1]}\)-hard parameterized by \(k\), but polynomial-time solvable for a constant number of voters](https://www.ijcai.org/proceedings/2021/0031.pdf).
No result specifically treating the positive rational-mass support formulation above was located.
The problem is \(\mathrm{NP}\)-complete and \(\mathrm{W[1]}\)-hard parameterized by \(k\). Consequently, it is not FPT parameterized by \(k\) unless \(\mathrm{FPT}=\mathrm{W[1]}\).
The positive rational-mass support formulation inherits the finite-voter hardness through a polynomial-time reduction that merges identical rankings and normalizes their multiplicities. Arbitrary rational masses can be handled directly with exact arithmetic.
Write \(\operatorname{pos}_t(c)\in\{1,\ldots,m\}\) for the position of candidate \(c\) in ranking \(t\). Thus \(\beta_t(c)=m-\operatorname{pos}_t(c)\). Define
\[ F(S)=\sum_{t\in T^+}\mu_t\min_{c\in S}\beta_t(c). \]
We use the following established finite-profile result: given an explicit nonempty list of voters with strict complete rankings, committee size \(k\), and an integer threshold \(h\), deciding whether some committee satisfies
\[ |S|=k,\qquad \sum_{v=1}^{n}\min_{c\in S}\beta_v(c)\ge h \]
is \(\mathrm{NP}\)-hard and \(\mathrm{W[1]}\)-hard parameterized by \(k\). This is utilitarian Pessimist with Borda utilities. The IJCAI paper defines Pessimist using the Borda score of the worst-ranked committee member, recalls its \(\mathrm{NP}\)-hardness, and establishes the parameterized hardness in Theorem 2 through a threshold reduction. These are precisely the scoring convention, committee-size constraint, and weak threshold inequality needed here. [Gupta, Jain, Saurabh, and Talmon, Sections 1.1 and 3](https://www.ijcai.org/proceedings/2021/0031.pdf)
Take a finite-profile instance as above, with \(n\ge1\) voters. Let \(T^+\) contain exactly its distinct rankings. For each \(t\in T^+\), let \(n_t\) be its positive multiplicity. Construct the support instance using the same candidates and committee size, with
\[ \mu_t=\frac{n_t}{n},\qquad q=\frac{h}{n}. \]
This is a valid instance: its rankings are distinct, all masses are positive rationals, and
\[ \sum_{t\in T^+}\mu_t=\frac{\sum_t n_t}{n}=1. \]
For every committee \(S\), grouping identical rankings gives
\[ F(S) =\sum_{t\in T^+}\frac{n_t}{n}\min_{c\in S}\beta_t(c) =\frac1n\sum_{v=1}^{n}\min_{c\in S}\beta_v(c). \]
Since \(n>0\), it follows that
\[ F(S)\ge q \quad\Longleftrightarrow\quad \sum_{v=1}^{n}\min_{c\in S}\beta_v(c)\ge h. \]
Thus the reduction preserves the answer, including equality.
It also has polynomial output size. There are \(\tau\le n\) supported rankings, each mass requires \(O(\log(n+1))\) bits, and the threshold requires \(O(\log(|h|+1)+\log(n+1))\) bits. Grouping the explicit rankings and computing their multiplicities takes polynomial time in the finite-profile input length.
Finally, the output parameter is exactly the input parameter \(k\). Therefore this is both a polynomial many-one reduction and a parameterized reduction. The support problem inherits both hardness results.
We now bound computation directly in the support input length \(L\), without expanding masses into voters.
Write \(\mu_t=a_t/b_t\), where \(a_t,b_t\) are positive integers, and \(q=a_0/b_0\), where \(a_0\) is an integer and \(b_0>0\). Set
\[ D=b_0\prod_{t\in T^+}b_t,\qquad w_t=a_t(D/b_t),\qquad Q=a_0(D/b_0). \]
All these quantities are integers, and
\[ F(S)\ge q \quad\Longleftrightarrow\quad \sum_{t\in T^+}w_t\min_{c\in S}\beta_t(c)\ge Q. \]
The bit length of \(D\) is at most the sum of the denominator bit lengths, hence \(O(L)\). Moreover, \(\sum_t w_t=D\), so the nonnegative integer committee score is at most \((m-1)D\). Its bit length is therefore \(O(L+\log(m+1))\).
For explicit running-time bounds, put
\[ B=L+\lceil\log_2(m+1)\rceil+\lceil\log_2(\tau+1)\rceil+1. \]
Using ordinary quadratic-time integer arithmetic, a conservative bound for preparing the scores and integer weights, checking a certificate \(S\), and comparing its score with \(Q\) is
\[ O\bigl((\tau m+\tau k+m+\tau+1)B^2\bigr). \]
Indeed, the verifier checks that \(S\) contains exactly \(k\) distinct candidates, computes each supported ranking’s minimum over those candidates, and performs the integer comparison above. The certificate needs only \(O(k\log(m+1))\) bits.
This proves membership in \(\mathrm{NP}\). Together with Section 2, it proves \(\mathrm{NP}\)-completeness.
If the support problem had an algorithm running in \(f(k)L^d\), for a computable function \(f\) and constant \(d\) independent of \(k\), composing it with Section 2 would give an FPT algorithm for finite-profile Pessimist. Its \(\mathrm{W[1]}\)-hardness would then imply \(\mathrm{FPT}=\mathrm{W[1]}\).
This is a conditional exclusion of FPT; it does not prove that those complexity classes differ.
Two direct algorithms clarify the tractable boundaries.
Fixed committee size. Enumerating every \(k\)-element committee and evaluating it exactly takes
\[ O\left((\tau m+\tau+1)B^2+ \binom{m}{k}\tau(k+1)B^2\right). \]
This is polynomial for every fixed \(k\), and gives an XP algorithm parameterized by \(k\).
Fixed support size. Enumerate all vectors \(z\in\{0,\ldots,m-1\}^{\tau}\). For each vector, define
\[ A_z=\{c\in C:\beta_t(c)\ge z_t\text{ for every }t\in T^+\}. \]
Accept if some vector satisfies both \(|A_z|\ge k\) and \(\sum_t w_tz_t\ge Q\).
To prove soundness, choose any \(k\) candidates from such an \(A_z\). Each ranking’s minimum is at least its corresponding \(z_t\); since every weight is positive, the committee’s integer score is at least \(Q\).
To prove completeness, take a feasible committee \(S\) and set \(z_t=\min_{c\in S}\beta_t(c)\). This enumerated vector satisfies \(S\subseteq A_z\) and \(\sum_t w_tz_t\ge Q\).
A conservative running-time bound is
\[ O\left((\tau m+\tau+1)B^2+ m^\tau\tau(m+1)B^2\right). \]
Hence the problem is polynomial-time solvable for constant \(\tau\), even with arbitrary binary rational masses.
The boundary cases are also easy: for \(k=1\), maximize the weighted Borda score of a single candidate; for \(k=m\), every ranking’s minimum is \(0\), so the answer is yes exactly when \(q\le0\).
⟨structured verdict parsed — rendered above⟩
The prover’s conclusion is justified: the support formulation is \(\mathrm{NP}\)-complete and \(\mathrm{W[1]}\)-hard parameterized by \(k\), with the stated conditional exclusion of FPT. I found no major or minor mathematical issues.
The definition \(\beta_t(c)=m-\operatorname{pos}_t(c)\) matches standard unnormalized Borda scores, ranging from \(0\) to \(m-1\). Because \(k\ge1\), every committee minimum is defined.
The cited finite-profile result applies to the required objective. The IJCAI paper defines rankings as linear orders, committees as sets of exactly \(k\) candidates, and utilitarian Pessimist as the sum of the Borda scores of the worst-ranked committee members. Theorem 2 states \(\mathrm{W[1]}\)-hardness with respect to \(k\), and its proof sketch explicitly uses an integer target score and acceptance for scores at least that target. The paper also recalls the established \(\mathrm{NP}\)-hardness. Thus the theorem invocation matches the scoring convention and weak threshold inequality; no tie-breaking hypothesis is needed. [Gupta et al., Sections 1.1 and 3](https://www.ijcai.org/proceedings/2021/0031.pdf)
Every distinct ranking receives mass \(n_t/n\), where \(n_t>0\) and \(n\ge1\). Consequently, the constructed masses are positive, the support rankings are distinct, and their masses sum to \(1\).
The displayed identity between the support score and the finite-profile score divided by \(n\) is correct for every committee. Dividing both the objective and threshold by the same positive number preserves both directions of the decision equivalence, including equality.
The output-size estimates are valid: multiplicities and the denominator \(n\) have logarithmic binary length, and there are at most \(n\) distinct rankings. Grouping an explicit list takes polynomial time. The construction keeps \(k\) unchanged and therefore is also a parameterized reduction.
Finding: Both hardness transfers are established.
The common denominator \(D\) is positive and divisible by every denominator used. Hence all \(w_t\) and \(Q\) are integers, and multiplying the threshold inequality by \(D\) is valid even when \(q\) is negative.
The denominator-product bound is correct: its binary length is bounded by the sum of the input denominator lengths. Normalization gives \(\sum_t w_t=D\), so the integer committee score lies between \(0\) and \((m-1)D\). Its claimed binary-length bound follows. The possibly signed integer \(Q\) also has \(O(L)\) bits from its displayed definition.
The certificate length is polynomial. Checking valid candidate identifiers, distinctness, cardinality, ranking minima, and the final integer comparison fits the stated conservative running-time bound using quadratic-time integer arithmetic.
Finding: Membership in \(\mathrm{NP}\) is proved without expanding rational masses into voters. Together with the reduction, this establishes \(\mathrm{NP}\)-completeness.
Composing a hypothetical \(f(k)L^d\) algorithm with the polynomial-size, parameter-preserving reduction gives an FPT algorithm for the cited finite-profile problem. Its \(\mathrm{W[1]}\)-hardness yields the stated implication \(\mathrm{FPT}=\mathrm{W[1]}\).
The prover correctly makes this conclusion conditional and does not assert an unconditional separation.
Enumerating all \(\binom{m}{k}\) committees is exhaustive. Each evaluation uses the already prepared scores and integer weights. The displayed bound covers preprocessing and exact evaluations.
For each fixed \(k\), this is polynomial in the explicit input size. Its dependence on \(m\) also establishes the claimed XP classification.
The domain for \(z\) contains every possible vector of ranking minima, including zero coordinates.
Soundness is valid: any \(k\)-subset of \(A_z\) has coordinatewise minima at least \(z_t\), and positive weights preserve the resulting lower bound.
Completeness is valid: the actual minima of a feasible committee define an enumerated vector, and every committee member belongs to its corresponding \(A_z\).
There are exactly \(m^\tau\) vectors. Testing candidate membership and evaluating the weighted threshold fits the stated bound, which is polynomial for fixed \(\tau\), including arbitrary binary rational masses.
The conclusions for \(k=1\) and \(k=m\) are correct. The latter also covers \(m=1\). Negative thresholds and exact equality are handled by the same integer comparison.
No additional lemma, clarification, or repair is required. The tractable restrictions do not conflict with hardness when both \(k\) and the support size vary.
⟨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.