Answer: —
Theorem 5 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateLet A be an algorithm which on input a ranking profile with n agents and m alternatives, and integers k and q with 1 ⩽k/2 < q ⩽k < m, runs in time polynomial in m and n and returns a set P of (polynomially many) k-sized committees of alternatives with the following property: For every distance function d, there is a committee C ∈P such that SCq(C|d) < (1 + 2/e + ε) · SCq(O|d), where O is a committee of minimum social cost according to d, and ε is a positive constant. Then, P = NP. Extensions and Open Problems In this work, we extended the metric distortion framework to multiwinner voting.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given alternatives \(A\), types \(T\) with complete rankings \(\succ_t\), rational masses \(\mu_t\ge0\) summing to \(1\), and \(k/2<q\le k<m\), where each type has a common hidden distance row \(\delta(t,\cdot)\), determine whether a polynomial-time algorithm can output a polynomial-size shortlist \(P\) of \(k\)-committees such that, for every ranking-consistent pseudometric satisfying \(\delta(t,a)\le\delta(t,b)+\delta(t',b)+\delta(t',a)\), \(\min_{C\in P}\sum_t\mu_t c_{t,q}(C\mid\delta)<\left(1+\frac{2}{e}+\varepsilon\right)\min_{|O|=k}\sum_t\mu_t c_{t,q}(O\mid\delta)\), in time polynomial in \(m\), \(\tau=|T|\), and the encoding length of \(\mu\).
Let \(A\) contain \(m\) alternatives, and let integers \(k,q\) satisfy \(1\le k/2<q\le k<m\).
A society is given by its support: a list \(T\) of \(\tau\) types with positive binary rational masses \(\mu_t\) summing to \(1\), each with a strict complete ranking \(\succ_t\) of \(A\). Here \(\tau\) is the support size, not the number of possible rankings; let \(L\) be the total input bit length.
An admissible hidden distance array \(\delta:T\times A\to\mathbb R_{\ge0}\) has one common row per type and satisfies \(a\succ_t b\Rightarrow\delta(t,a)\le\delta(t,b)\) and \(\delta(t,a)\le\delta(t,b)+\delta(t',b)+\delta(t',a)\) for every \(t,t'\in T\) and \(a,b\in A\). Distance ties may be broken arbitrarily in the supplied rankings.
A committee is a subset \(C\subseteq A\) of size \(k\). Define \(c_{t,q}(C\mid\delta)\) as the distance to its \(q\)-th alternative in ranking \(\succ_t\), and \(\operatorname{SC}_\mu(C\mid\delta)=\sum_{t\in T}\mu_t c_{t,q}(C\mid\delta)\).
For a fixed constant \(\varepsilon>0\), the required output is a nonempty shortlist \(P\) of committees, chosen using only the rankings, masses, \(k\), and \(q\), such that every admissible \(\delta\) satisfies
\(\min_{C\in P}\operatorname{SC}_\mu(C\mid\delta)<(1+2/e+\varepsilon)\min_{O\subseteq A:\,|O|=k}\operatorname{SC}_\mu(O\mid\delta)\).
Does a deterministic algorithm produce such a shortlist with size and running time polynomial in \(m,\tau,L\), for each fixed \(\varepsilon>0\), or is achieving this approximation guarantee NP-hard?
For finite lists of agents, the stated hardness result says that polynomial-time construction of a polynomial-size shortlist with this guarantee implies \(\mathrm P=\mathrm{NP}\). In the same finite-agent model, the shortlist consisting of each agent’s top-\(k\) committee guarantees approximation factor \(3\).
Taking the finite-agent hardness assertion in the question as a premise, the intended weighted-support problem is NP-hard in the stated sense: a polynomial-time algorithm producing a polynomial-size shortlist would imply \(\mathrm P=\mathrm{NP}\). The transfer requires averaging distances within each ranking type; simply identifying agents would not justify it.
There are two qualifications. Literally, the strict inequality is impossible for the admissible array \(\delta\equiv0\). I therefore address the intended approximation requirement when the optimal cost is positive, with zero-cost instances requiring a zero-cost committee.
Also, the published finite-agent theorem uses \(1+2/e-\varepsilon\), whereas the question supplies \(1+2/e+\varepsilon\). Below I prove the transfer, distinguish its conditional consequence from the published result, and establish a polynomial-time guarantee for sufficiently large \(\varepsilon\).
Let a finite profile have agents \(N=\{1,\ldots,n\}\). Partition its agents into nonempty classes \(N_t\) according to their identical supplied rankings. Set \(n_t=|N_t|\) and \(\mu_t=n_t/n\).
For any admissible finite-agent distance array \(d\), define
\(\displaystyle \bar\delta(t,a)=\frac1{n_t}\sum_{i\in N_t}d(i,a).\)
I claim that \(\bar\delta\) is admissible for the compressed profile.
Nonnegativity is preserved by averaging. If \(a\succ_t b\), every agent \(i\in N_t\) satisfies \(d(i,a)\le d(i,b)\), so \(\bar\delta(t,a)\le\bar\delta(t,b)\).
For the quadrilateral inequality, fix types \(t,s\) and alternatives \(a,b\). For every pair \(i\in N_t\), \(j\in N_s\),
\(d(i,a)\le d(i,b)+d(j,b)+d(j,a).\)
Averaging over all \(n_tn_s\) pairs gives
\(\bar\delta(t,a)\le\bar\delta(t,b)+\bar\delta(s,b)+\bar\delta(s,a).\)
Thus \(\bar\delta\) satisfies every required constraint.
Now fix any committee \(C\). Let \(a_t(C)\) be its alternative in position \(q\) under ranking \(\succ_t\). This alternative is the same for every agent in \(N_t\), even when their distance rows differ. Consequently,
\(\displaystyle \operatorname{SC}_\mu(C\mid\bar\delta) =\sum_t\frac{n_t}{n}\bar\delta(t,a_t(C)) =\frac1n\sum_{i\in N}c_{i,q}(C\mid d). \)
This identity holds simultaneously for every committee. Therefore it also preserves the optimal committee cost and the minimum cost attained by any fixed shortlist, up to the common factor \(1/n\).
Suppose a deterministic support-model algorithm constructs a polynomial-size shortlist with approximation factor \(R\).
Given an explicitly listed finite-agent profile, compress it as above and run that algorithm. This transformation is polynomial-time: \(\tau\le n\), and each mass \(n_t/n\), represented by binary-encoded numerator and denominator, has bit length \(O(\log n)\). Hence the compressed input length is polynomial in the original input length.
The output depends only on the compressed rankings and masses. For each admissible finite-agent array \(d\), its averaged array \(\bar\delta\) is admissible, so the support-model guarantee applies. By the cost identity, the resulting shortlist satisfies
\(\displaystyle \min_{C\in P}\sum_{i\in N}c_{i,q}(C\mid d) < R\min_{|O|=k}\sum_{i\in N}c_{i,q}(O\mid d), \)
whenever the optimal cost is positive. Zero-cost recovery transfers by the same identity.
Thus a polynomial-time support-model construction yields a polynomial-time finite-agent construction with exactly the same approximation factor. The condition \(1\le k/2<q\le k<m\) is unchanged.
Conditional conclusion. If the finite-agent hardness assertion supplied in the question holds at \(R=1+2/e+\varepsilon\), then such a support-model algorithm implies \(\mathrm P=\mathrm{NP}\). Requiring one common distance row per type does not evade that assertion.
The following bound also identifies a limitation of the supplied hardness assertion.
Write \(c_t(C)=c_{t,q}(C\mid\delta)\). First, committee costs satisfy
\(c_t(X)\le c_t(Y)+c_s(Y)+c_s(X).\)
To prove this, let \(B_u(C)\) denote the first \(q\) alternatives of \(C\) under ranking \(\succ_u\).
Because \(2q>k\), choose \(a\in B_t(Y)\cap B_s(Y)\). Also choose \(b\in B_s(X)\) whose position under \(\succ_t\), restricted to \(X\), is at least \(q\). Such a \(b\) exists because these two subsets of \(X\) have sizes \(q\) and \(k-q+1\), whose sum exceeds \(k\). The ranking constraints and quadrilateral inequality give
\(c_t(X)\le\delta(t,b)\le\delta(t,a)+\delta(s,a)+\delta(s,b)\le c_t(Y)+c_s(Y)+c_s(X).\)
Let \(C_s\) be type \(s\)’s top-\(k\) committee, and let \(O\) be optimal. Since \(C_s\) contains type \(s\)’s globally first \(q\) alternatives,
\(c_s(C_s)\le c_s(O).\)
For \(t\ne s\), the preceding inequality therefore gives
\(c_t(C_s)\le c_t(O)+2c_s(O).\)
For \(t=s\), use the stronger bound \(c_s(C_s)\le c_s(O)\). Summing with masses yields
\(\displaystyle \operatorname{SC}_\mu(C_s) \le \operatorname{SC}_\mu(O)+2c_s(O)-2\mu_s c_s(O). \)
Average this inequality over \(s\), with weights \(\mu_s\). Since the minimum is no greater than this weighted average,
\(\displaystyle \min_s\operatorname{SC}_\mu(C_s) \le 3\operatorname{SC}_\mu(O)-2\sum_s\mu_s^2c_s(O). \)
Define \(\mu_{\min}=\min_s\mu_s>0\). Because \(\mu_s^2\ge\mu_{\min}\mu_s\),
\(\displaystyle \min_s\operatorname{SC}_\mu(C_s) \le (3-2\mu_{\min})\operatorname{SC}_\mu(O). \)
The shortlist \(P=\{C_s:s\in T\}\) is nonempty, has at most \(\tau\) committees, and is constructible in polynomial time. Its guarantee is strictly below \(3\) whenever the optimum is positive, and it recovers zero optimal cost.
In particular, it satisfies the requested positive-optimum guarantee whenever
\(\varepsilon\ge 2-2/e.\)
Thus the supplied hardness assertion cannot apply to every positive \(\varepsilon\), unless \(\mathrm P=\mathrm{NP}\).
The published finite-agent result is Theorem 5 of Caragiannis, Shah, and Voudouris, and its factor is \(1+2/e-\varepsilon\). It does not establish hardness at the larger factor requested here. [The Metric Distortion of Multiwinner Voting](https://repository.essex.ac.uk/33648/1/1-s2.0-S0004370222001424-main.pdf)
Accordingly:
⟨structured verdict parsed — rendered above⟩
The compression argument and weighted top-\(k\) bound are correct. Under the finite-agent hardness premise explicitly supplied in USER_TASK, the compression argument establishes the claimed hardness consequence for the intended weighted-support problem. The published theorem cited by the prover supports a smaller approximation threshold; the prover correctly distinguishes that theorem from the supplied premise.
There are minor qualifications concerning the zero-cost convention and the precise statement of the cited theorem. I found no false mathematical step in the arguments presented.
The prover correctly identifies that the literal requirement fails for \(\delta\equiv0\): both sides of the required strict inequality are zero.
Its explicit convention—strict approximation when the optimum is positive, and recovery of zero optimal cost otherwise—is a natural interpretation of the intended approximation question. Under the verification discipline specified in the prompt, this is a minor issue, rather than grounds for rejecting the substantive argument.
The convention nevertheless changes the literal specification. Every subsequent guarantee must be understood with that qualification.
The partition into classes of identical supplied rankings is well defined. Each class is nonempty, so \(n_t>0\), and the masses \(\mu_t=n_t/n\) are positive rationals summing to one.
The admissibility checks are valid:
The last calculation also covers \(t=s\); it does not require distinct types or distinct agents.
Finding: This lemma is correct for the stated array constraints. It also applies to finite-agent arrays arising from a pseudometric, since those arrays satisfy the quadrilateral inequalities used here.
For any fixed committee \(C\), the alternative \(a_t(C)\) is determined by the supplied ranking. Consequently, it is identical for all agents in \(N_t\).
Distance ties cause no problem: the supplied strict ranking fixes the selected alternative, and its distance still equals the relevant order-statistic value because the ranking is distance consistent.
The displayed identity
\[
\operatorname{SC}_\mu(C\mid\bar\delta)
=\frac1n\sum_{i\in N}c_{i,q}(C\mid d)
\]
is correct.
The averaging construction does not depend on \(C\). Thus the identity holds simultaneously for every committee, justifying its application to both the optimal committee cost and the minimum over a fixed shortlist.
Finding: No quantifier exchange or optimization gap occurs here.
The compression has polynomial input size:
Accordingly, a running-time and shortlist-size bound polynomial in \(m,\tau,L\) becomes polynomial in the original explicit finite-agent input length.
For each admissible finite-agent array \(d\), the constructed \(\bar\delta\) is admissible. The support-model guarantee therefore applies separately to every such \(d\), using the same output shortlist. Multiplying the cost identity by the positive number \(n\) preserves the strict inequality.
Zero-cost recovery transfers by the same identity, provided that this recovery is part of the adopted approximation convention.
Finding: The reduction establishes precisely the claimed implication. Requiring a common row within each type does not obstruct this direction of transfer. Expanding arbitrary binary rational masses into agents is unnecessary.
USER_TASK supplies the finite-agent hardness assertion as a premise. Therefore, requiring an independent proof of that premise would impose an additional assignment. The prover’s final admission that it does not independently settle the larger threshold does not invalidate the conditional resolution requested under that premise.
The intersection arguments are correct:
\[ q+(k-q+1)=k+1>k. \]
For the selected \(a,b\), every inequality in the displayed chain follows from the supplied ranking constraints or the quadrilateral inequality.
This reasoning includes \(q=k\), equal types, and distance ties.
Finding: The committee inequality is proved correctly.
The inequality \(c_s(C_s)\le c_s(O)\) follows from the top-\(k\) committee containing type \(s\)’s globally first \(q\) alternatives.
For \(t\ne s\), the committee inequality gives the stated bound. Using the stronger inequality for \(t=s\), the weighted sum is correctly calculated as
\[
\operatorname{SC}_\mu(C_s)
\le \operatorname{SC}_\mu(O)+2(1-\mu_s)c_s(O).
\]
Averaging over \(s\) with weights \(\mu_s\) gives
\[
\min_s\operatorname{SC}_\mu(C_s)
\le 3\operatorname{SC}_\mu(O)-2\sum_s\mu_s^2c_s(O).
\]
The subsequent use of \(\mu_s^2\ge\mu_{\min}\mu_s\) is valid because all masses and costs are nonnegative.
The bound remains valid when \(\tau=1\). When the optimum is zero, it ensures zero-cost recovery. When the optimum is positive, \(\mu_{\min}>0\) makes the approximation factor strictly smaller than \(3\).
Finally, the threshold calculation is correct:
\[
1+2/e+\varepsilon\ge3
\quad\Longleftrightarrow\quad
\varepsilon\ge2-2/e.
\]
The strict improvement below \(3\) handles equality at this boundary.
Finding: The polynomial-time upper bound and its stated range are correct. No uniform lower bound on \(\mu_{\min}\) is needed.
The cited Theorem 5 concerns polynomial-time construction of polynomially many committees for explicit finite-agent profiles, with the same parameter restriction, and its threshold is \(1+2/e-\varepsilon\). The prover correctly reports the sign and correctly declines to apply that theorem at \(1+2/e+\varepsilon\). [Theorem 5 in the cited paper](https://repository.essex.ac.uk/33648/1/1-s2.0-S0004370222001424-main.pdf)
Minor issue: The theorem’s complete hypotheses are not stated explicitly in the write-up, particularly its pseudometric model. The minimum clarification is to state the precise theorem and explain that its finite-agent distance arrays satisfy the inequalities used by the compression lemma.
The conditional hardness conclusion and the large-\(\varepsilon\) algorithm are not a formal contradiction: together with a hardness premise covering that range, they would imply \(\mathrm P=\mathrm{NP}\). The prover correctly states this qualification.
The write-up should explicitly label its conclusion as applying to the positive-optimum/zero-recovery convention, and give the complete statement of the published theorem when discussing that separate result. No repair to the compression or weighted-bound arguments is required.
⟨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.