Answer: For every fixed \(0<\varepsilon<1\), achieving a \(\tau^{1-\varepsilon}\)-approximation is NP-hard; no algorithm polynomial in \(m,\tau,L\) achieves this guarantee unless \(\mathrm{P}=\mathrm{NP}\).
Corollary 16 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor Γ ∈{ΓW , ΓB, ΓM , ΓC, Γsp, Γscv, Γgs}, Γ-VDEL−cannot be approximated within n1−ϵ unless P = NP. Finally, we characterize the parameterized complexity of Γ-VDEL−.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\) and a rational mass distribution \(\mu\) over supported complete rankings \(T\), choose retained masses \(0\leq \nu_t\leq\mu_t\) to maximize \(\sum_{t\in T}\nu_t\), subject to this condition: for every candidate mapping \(\xi\) and every \(\Phi\in\Gamma_{\rm sp}\), at least one condition \(\phi\in\Phi\) has zero retained mass, \(\sum_{t\in T:t\models_\xi\phi}\nu_t=0\).
Let \(C\) be a nonempty candidate set of size \(m\). A society is given by its support: a list \(T\) of \(\tau\) distinct strict complete rankings, each with positive binary rational mass \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings; \(L\) is the total input bit length.
Define \(\Gamma_{\rm sp}=\{\Phi_\alpha,\Phi_W\}\), with \(\Phi_\alpha=\{(a>b>c)\land(d>b),(c>b>a)\land(d>b)\}\) and \(\Phi_W=\{(a>c)\land(b>c),(a>b)\land(c>b),(b>a)\land(c>a)\}\).
For each configuration, \(\xi\) ranges over injective mappings from its variables into \(C\); \(t\models_\xi\phi\) means that ranking \(t\) satisfies the comparisons after substitution by \(\xi\).
Choose real retained masses \(0\leq\nu_t\leq\mu_t\), without renormalization, maximizing \(M(\nu)=\sum_{t\in T}\nu_t\), subject to: for every \(\Phi\in\Gamma_{\rm sp}\) and every \(\xi\), some \(\phi\in\Phi\) satisfies \(\sum_{t\in T:t\models_\xi\phi}\nu_t=0\). Let \(\mathrm{OPT}\) be the maximum retained mass.
For each fixed \(0<\varepsilon<1\), does this problem admit a polynomial-time \(\tau^{1-\varepsilon}\)-approximation, or is achieving this factor NP-hard? The guarantee is \(M(\nu)\geq\mathrm{OPT}/\tau^{1-\varepsilon}\); state running times in \(m,\tau,L\), and \(\varepsilon\) when variable.
For a finite list of \(n\) voters, maximizing the number retained while obtaining single-peaked preferences cannot be approximated within \(n^{1-\varepsilon}\), for any fixed \(0<\varepsilon<1\), unless \(\mathrm{P}=\mathrm{NP}\). [Elkind and Lackner](https://ojs.aaai.org/index.php/AAAI/article/download/8823/8682)
No result settling this precise rational-mass approximation question was located in the literature search.
For every fixed \(0<\varepsilon<1\), achieving a \(\tau^{1-\varepsilon}\)-approximation is NP-hard. Consequently, no algorithm polynomial in \(m,\tau,L\) has the stated guarantee unless \(\mathrm{P}=\mathrm{NP}\).
The proof transfers the given voter-retention hardness theorem by combining identical rankings. Interpret binary rational masses as rational numbers whose numerators and denominators are encoded in binary.
For a retained-mass vector \(\nu\), define \(S(\nu)=\{t\in T:\nu_t>0\}\).
Since all retained masses are nonnegative, for every condition \(\phi\) and injective mapping \(\xi\),
\(\displaystyle \sum_{t:t\models_\xi\phi}\nu_t=0 \quad\Longleftrightarrow\quad \text{no }t\in S(\nu)\text{ satisfies }\phi\text{ under }\xi.\)
Thus feasibility depends only on \(S(\nu)\).
In particular, define \(\widehat{\nu}_t=\mu_t\) for \(t\in S(\nu)\), and \(\widehat{\nu}_t=0\) otherwise. Then \(\widehat{\nu}\) is feasible whenever \(\nu\) is feasible, and \(M(\widehat{\nu})\geq M(\nu)\). Therefore
\(\displaystyle \mathrm{OPT}=\max_{\substack{S\subseteq T\\S\text{ feasible}}}\sum_{t\in S}\mu_t.\)
This proves that fractional retention provides no advantage: an optimum retains each ranking either at its full mass or at zero mass. It also proves that an approximation algorithm’s output can be converted to such a solution without decreasing its value.
For completeness, these feasible subsets are exactly the single-peaked profiles. The forbidden-configuration characterization uses \(\Phi_\alpha\) and \(\Phi_W\), precisely as given in the question. For a fixed injective mapping, the two conditions of \(\Phi_\alpha\) cannot hold in the same ranking because they impose opposite orders on \(a,b,c\); the three conditions of \(\Phi_W\) specify three different worst candidates. Hence, if every condition has a witness, those witnesses are distinct rankings. This establishes equivalence between the zero-mass constraints and absence of the forbidden configurations. The characterization and voter-retention hardness are stated in [Elkind and Lackner, Section 3 and Corollary 16](https://ojs.aaai.org/index.php/AAAI/article/download/8823/8682).
Although the paper permits arbitrary mappings in its configuration definition, this does not change the equivalence. In \(\Phi_W\), identifying any two variables makes at least one condition impossible. In \(\Phi_\alpha\), identifying two of \(a,b,c\) contradicts their strict chain; setting \(d=b\) makes both conditions impossible, setting \(d=a\) makes the second impossible, and setting \(d=c\) makes the first impossible. Thus a complete configuration occurrence necessarily uses an injective mapping.
Consider an instance of the finite-voter problem with \(n\geq1\) voters. Let \(T\) be its set of distinct rankings, and let \(k_t\) be the number of voters having ranking \(t\). Construct the rational-mass instance with
\(\displaystyle \mu_t=\frac{k_t}{n}.\)
All masses are positive, their sum is one, and \(\tau=|T|\leq n\).
Let \(K^*\) be the maximum number of voters that can be retained while obtaining a single-peaked profile. We claim that
\(\displaystyle \mathrm{OPT}=\frac{K^*}{n}.\)
To prove this, take any feasible ranking subset \(S\subseteq T\). Retaining every voter whose ranking belongs to \(S\) gives a single-peaked profile with \(\sum_{t\in S}k_t=n\sum_{t\in S}\mu_t\) voters. Therefore \(K^*\geq n\,\mathrm{OPT}\).
Conversely, take an optimal retained voter list and let \(S\) be its distinct rankings. Its feasibility depends only on those rankings. Adding every omitted voter whose ranking is already in \(S\) preserves single-peakedness: the same axis still works for every voter. Consequently, the optimal voter count equals \(\sum_{t\in S}k_t\), and \(S\) gives a mass solution of value \(K^*/n\). Hence \(\mathrm{OPT}\geq K^*/n\), proving the claim.
Fix \(0<\varepsilon<1\). Suppose an algorithm polynomial in \(m,\tau,L\) returns a feasible \(\nu\) satisfying
\(\displaystyle M(\nu)\geq\frac{\mathrm{OPT}}{\tau^{1-\varepsilon}}.\)
Apply it to the compressed instance and retain all original voters whose ranking belongs to \(S(\nu)\). By Section 1, this voter list is single-peaked. Its size \(K\) satisfies
\(\displaystyle K=\sum_{t\in S(\nu)}k_t =nM(\widehat{\nu}) \geq nM(\nu) \geq\frac{n\,\mathrm{OPT}}{\tau^{1-\varepsilon}} =\frac{K^*}{\tau^{1-\varepsilon}} \geq\frac{K^*}{n^{1-\varepsilon}}.\)
The last inequality uses \(\tau\leq n\) and \(1-\varepsilon>0\).
We have therefore obtained a polynomial-time \(n^{1-\varepsilon}\)-approximation for the finite-voter problem. This contradicts the hardness theorem supplied in the question unless \(\mathrm{P}=\mathrm{NP}\).
No assumption that the original voters have distinct rankings is needed.
Label candidates by integers. Sorting the explicit voter list and counting multiplicities requires \(O(nm\log(n+1))\) candidate comparisons, together with polynomial-time binary arithmetic. The compressed instance has encoding length
\(\displaystyle L=O\!\left(\tau m\log(m+1)+\tau\log(n+1)\right).\)
Indeed, each ranking is stored explicitly, and each mass has numerator and denominator at most \(n\). Thus construction, invocation of the hypothetical approximation algorithm, and reconstruction of the retained voter list all take polynomial time in the original explicit input length.
The hardness holds separately for every fixed \(\varepsilon\). It therefore also excludes a uniform algorithm polynomial in \(m,\tau,L,1/\varepsilon\), or running in \(f(\varepsilon)\operatorname{poly}(m,\tau,L)\) with finite \(f(\varepsilon)\), unless \(\mathrm{P}=\mathrm{NP}\).
For comparison, retaining a ranking of maximum mass gives a \(\tau\)-approximation in polynomial time: a singleton is feasible, its mass is at least \(1/\tau\), and \(\mathrm{OPT}\leq1\). Exact optimization is possible in \(2^\tau\operatorname{poly}(m,\tau,L)\) time by enumerating ranking subsets. Each subset’s feasibility can be checked in \(O(\tau m^4)\) comparison operations by enumerating the injective mappings and checking condition witnesses; rational objective comparisons require only polynomial-time arithmetic in \(L\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned question correctly. The compression preserves the optimum, and the approximation guarantee transfers in the required direction. No major or minor mathematical issues were found.
The zero-sum equivalence is correct: a finite sum of nonnegative retained masses is zero exactly when every summand is zero. Consequently, replacing each positive retained mass by its full available mass preserves every constraint.
The replacement also respects the bounds \(0\leq\nu_t\leq\mu_t\) and cannot decrease the objective. Thus the stated optimization over feasible subsets is justified, and fractional retention gives no improvement over full retention of selected rankings.
The cited paper defines exactly the two configurations in the task and states that their absence characterizes single-peaked preferences. Its configuration definition requires distinct witnessing votes and permits arbitrary candidate mappings. These are the two potential mismatches, and the prover addresses both. See [Elkind and Lackner, Section 3](https://ojs.aaai.org/index.php/AAAI/article/download/8823/8682).
For an injective mapping, the two alpha conditions are mutually inconsistent within one ranking. The three worst-diverse conditions are likewise pairwise inconsistent: each makes a different candidate worst among the same three. Therefore witnesses for all conditions must be distinct rankings, satisfying the paper’s distinct-vote requirement.
The collision analysis is exhaustive. Identifying any two variables in the worst-diverse configuration makes a required strict comparison impossible. For the alpha configuration, collisions within \(a,b,c\) invalidate the strict chains; the remaining possibilities are precisely \(d=a\), \(d=b\), and \(d=c\), each invalidating at least one required condition. Hence noninjective mappings cannot create additional complete occurrences.
The constructed masses \(k_t/n\) are positive rational numbers, sum to one, and satisfy \(\tau\leq n\).
Both inequalities establishing \(\mathrm{OPT}=K^*/n\) are valid. A feasible ranking subset yields a feasible voter list by including every copy of its rankings. Conversely, adding omitted copies of an already retained ranking preserves the same single-peaked axis. If an optimal voter list omitted such copies, adding them would contradict optimality. Thus its count equals the sum of the corresponding multiplicities.
No assumption of distinct original votes is used.
Every step in the displayed bound for \(K\) follows from the preceding arguments: reconstruction counts full multiplicities, saturation cannot decrease retained mass, the hypothetical algorithm supplies its guarantee, and optimum preservation supplies the equality involving \(K^*\).
The final inequality has the correct direction because \(\tau\leq n\) and \(1-\varepsilon>0\). The resulting voter-retention algorithm therefore has the forbidden \(n^{1-\varepsilon}\) guarantee.
Corollary 16 explicitly includes the single-peaked configuration family and gives the cited voter-retention inapproximability. Its problem is maximizing surviving voters, matching the reduction’s objective. See [Elkind and Lackner, Section 8](https://ojs.aaai.org/index.php/AAAI/article/download/8823/8682).
Sorting explicit rankings and counting their multiplicities uses the stated number of candidate comparisons. Binary arithmetic contributes only polynomial overhead.
Each constructed mass has numerator and denominator at most \(n\), so the compressed encoding bound is valid. In particular, the reduction creates no exponentially long rational numbers. Construction, invocation, and reconstruction are polynomial in the original explicit input length.
Hardness for every fixed \(\varepsilon\) also excludes both stated uniform running-time forms: fixing any admissible \(\varepsilon\) makes its parameter-dependent contribution constant.
A singleton cannot witness either complete forbidden configuration, so retaining a maximum-mass ranking is feasible. Its mass is at least \(1/\tau\), and \(\mathrm{OPT}\leq1\), giving the claimed \(\tau\)-approximation.
Subset enumeration and the stated configuration checks give the claimed exponential exact running time. Exact rational objective comparisons have polynomial bit complexity in \(L\).
The empty retained subset is feasible. When there are too few candidates for a configuration’s injective mapping, that family contributes no constraints. These cases, including \(m=1\) and \(\tau=1\), cause no failure in the argument.
No additional clarification is needed to verify the conclusion.
⟨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.