Answer: Polynomial-time solvable for \(m=3\), with rational output support size \(\tau\leq\min\{s,12\}\).
Theorem 7 — class: algorithmic
Given a finite set \(T\subseteq V_3\) of complete canonical cardinal valuation types, compute or approximate \(\rho_{J^\star}(T)=\inf_{\mu\in\Delta(T)}\frac{\sum_{t\in T}\mu_t\sum_{c\in C}p^{J^\star}_c(\mu)u_t(c)}{\max_{c\in C}\sum_{t\in T}\mu_tu_t(c)}\), where \(J^\star=c_1U^1+c_2U^2\) and \(p^{J^\star}_c(\mu)=c_1\sum_{t:c\in\operatorname{Top}_1(t)}\mu_t+\frac{c_2}{2}\sum_{t:c\in\operatorname{Top}_2(t)}\mu_t\); return a certified worst-case mass vector and ratio bound.
Let \(C=\{A,B,C\}\), with \(m=3\). The input is a nonempty catalogue \(T\) of \(s\) distinct complete valuation types, each explicitly given by binary rational utilities \(u_t:C\to[0,1]\), injective and satisfying \(\min_c u_t(c)=0\) and \(\max_c u_t(c)=1\).
A society is given by its support: the list of its \(\tau\) types with positive mass, each mass a binary rational. Here \(\tau\) means support size, not the number of possible types; masses sum to \(1\). Optimization permits any support contained in \(T\), including omission of catalogue types.
Fix \(c_1=77066611/157737759\) and \(c_2=80671148/157737759\). The rule \(U^q\) samples a type according to its mass and then uniformly selects one of its \(q\) highest-valued candidates; set \(J^\star=c_1U^1+c_2U^2\). Strict valuations make \(\operatorname{Top}_q(t)\) unambiguous.
For \(\mu\in\Delta(T)\), put \(w_c(\mu)=\sum_t\mu_tu_t(c)\), \(p_c(\mu)=c_1\sum_{t:c\in\operatorname{Top}_1(t)}\mu_t+(c_2/2)\sum_{t:c\in\operatorname{Top}_2(t)}\mu_t\), and \(R(\mu)=\sum_cp_c(\mu)w_c(\mu)/\max_cw_c(\mu)\). Define \(\rho(T)=\inf_{\mu\in\Delta(T)}R(\mu)\), allowing real masses in this infimum.
Given binary rational \(0<\varepsilon<1\), the approximation problem requests a rational society \(\widehat\mu\) and rational lower bound \(b\) with \(b\leq\rho(T)\leq R(\widehat\mu)\leq b+\varepsilon\). Let \(L\) be the total input bit length.
Can this certified additive approximation of \(\rho(T)\) be computed in time polynomial in \(m,s,\tau,L,\log(1/\varepsilon)\), or is it NP-hard?
For discrete societies, \(J^\star\) has worst-case welfare ratio strictly greater than \(0.610\) for every positive number of voters. The analysis also treats real frequencies of twelve limiting valuation types; no complexity classification for the arbitrary rational catalogue problem above was located. [Verified source](https://arisfilosratsikas.com/papers/range_voting.pdf).
The certified additive approximation is polynomial-time solvable for the stated case \(m=3\). The algorithm returns a rational society supported on at most \(\min\{s,12\}\) catalogue types, together with a rational lower bound satisfying the requested inequalities.
The proof has two ingredients: an exact reduction to twelve types, and an exact threshold algorithm for quadratic optimization in constant dimension.
For a type \(t\), define its election-probability vector by
\(v_t(c)=c_1\mathbf 1_{\{c\in\operatorname{Top}_1(t)\}}+\frac{c_2}{2}\mathbf 1_{\{c\in\operatorname{Top}_2(t)\}}.\)
Since \(c_1+c_2=1\), every \(v_t\) is a probability vector. Consequently, so is \(p(\mu)=\sum_t\mu_tv_t\).
Write \(W(\mu)=\max_c w_c(\mu)\) and \(N(\mu)=\sum_c p_c(\mu)w_c(\mu)\). Normalization of each valuation gives
\(\sum_c w_c(\mu)=\sum_t\mu_t\sum_c u_t(c)\geq 1,\)
and therefore \(W(\mu)\geq 1/3\). Moreover, \(0\leq N(\mu)\leq W(\mu)\), because \(p(\mu)\) is a probability vector. Thus
\(0\leq R(\mu)\leq 1.\)
The denominator is bounded away from zero, so \(R\) is continuous on the compact simplex \(\Delta(T)\). In particular, the defining infimum is attained:
\(\rho(T)=\min_{\mu\in\Delta(T)}R(\mu).\)
There are six strict rankings of three candidates. Fix one such ranking, written \(a\succ b\succ d\). Every type having this ranking has utilities
\(u_t(a)=1,\qquad u_t(b)=x_t,\qquad u_t(d)=0,\qquad 0<x_t<1.\)
Its election-probability vector depends only on the ranking:
\(v_t(a)=c_1+c_2/2,\qquad v_t(b)=c_2/2,\qquad v_t(d)=0.\)
For each nonempty ranking class, retain types attaining its smallest and largest middle utilities. If these coincide, retain just one type. Let \(T'\subseteq T\) be the retained catalogue. Then \(|T'|\leq\min\{s,12\}\).
To prove that this reduction is exact, consider a ranking class whose extrema are \(x_-\lt x_+\). For any type in that class, set
\(\lambda_t=\frac{x_+-x_t}{x_+-x_-}.\)
Then \(0\leq\lambda_t\leq1\), and
\(u_t=\lambda_tu_-+(1-\lambda_t)u_+,\qquad v_t=\lambda_tv_-+(1-\lambda_t)v_+.\)
The first identity follows coordinatewise from the utilities above. The second follows because all three probability vectors are identical.
Replacing mass \(\mu_t\) by masses \(\mu_t\lambda_t\) and \(\mu_t(1-\lambda_t)\) on the two retained types therefore preserves both \(w(\mu)\) and \(p(\mu)\). Applying this replacement to every omitted type preserves \(R(\mu)\). A singleton ranking class requires no replacement.
Conversely, every society on \(T'\) is admissible on \(T\). Hence
\(\rho(T')=\rho(T).\)
All retained types are actual members of the input catalogue, with their original strict valuations.
We need the following elementary algorithmic lemma.
Lemma. Fix a positive integer \(n\). Given rational coefficients of a quadratic polynomial
\(f(x)=x^{\mathsf T}Hx+h^{\mathsf T}x+\gamma,\qquad H=H^{\mathsf T},\)
one can compute its exact minimum on
\(\Delta_n=\{x\in\mathbb R^n:x_i\geq0,\ \sum_i x_i=1\}\)
and a rational minimizer in time polynomial in the coefficient bit length. No definiteness assumption on \(H\) is required.
Proof. Enumerate every nonempty subset \(S\subseteq\{1,\ldots,n\}\). On the corresponding face, set coordinates outside \(S\) to zero and write the remaining coordinates as \(y\).
Choose \(j\in S\). Consider the rational linear system
\(\sum_{\ell\in S}y_\ell=1,\)
\(2\sum_{\ell\in S}(H_{i\ell}-H_{j\ell})y_\ell+h_i-h_j=0\qquad(i\in S\setminus\{j\}),\)
together with \(y_\ell\geq0\). Its equations say precisely that all gradient coordinates indexed by \(S\) are equal.
If this system is feasible, obtain one rational feasible point and evaluate \(f\) there. Return the smallest value among all points obtained.
We first justify the feasible-point computation. The solution set is a bounded rational polyhedron, being contained in a simplex. Every nonempty bounded polyhedron has a vertex: successively minimizing its coordinates produces nested nonempty compact faces, ending in a singleton.
At a vertex, the equality rows together with the active inequalities span the whole coordinate space. Otherwise, a nonzero direction annihilating all these rows would permit sufficiently small perturbations in both directions, contradicting extremality. Here the active inequalities are coordinate equations \(y_\ell=0\). Thus enumerating subsets of coordinates to set to zero, solving the resulting full-rank systems, and checking all equations and inequalities finds a rational feasible point whenever one exists.
Next, all solutions of the stationarity equations on a given face have the same objective value. Indeed, let \(y,z\) be two such solutions and put \(d=z-y\). Their coordinate sums agree, so \(\mathbf 1^{\mathsf T}d=0\). Their gradients are constant across \(S\), giving
\(d^{\mathsf T}\nabla f(y)=0,\qquad d^{\mathsf T}(\nabla f(z)-\nabla f(y))=0.\)
Since the gradient difference is \(2H_{SS}d\), we obtain \(d^{\mathsf T}H_{SS}d=0\). The quadratic expansion therefore gives
\(f(z)-f(y)=d^{\mathsf T}\nabla f(y)+d^{\mathsf T}H_{SS}d=0.\)
Finally, let \(x^\star\) be a global minimizer and let \(S\) be its positive support. It lies in the relative interior of that simplex face. For each \(i,j\in S\), sufficiently small perturbations along \(e_i-e_j\) are feasible in both directions. Differentiating at the minimum shows that the corresponding gradient coordinates agree. Thus \(x^\star\) satisfies the stationarity system for \(S\).
The rational point selected for this system has the same objective value as \(x^\star\). Every other selected point is feasible, so the smallest selected value is exactly the global minimum.
For fixed \(n\), both subset enumerations have constant size. All systems have constant dimension. Exact Gaussian elimination and rational comparisons have polynomial bit complexity; determinant formulas also show that the produced rational points have polynomial bit length. This proves the lemma. \(\square\)
Index the reduced catalogue by \(1,\ldots,n\), where \(n\leq12\), and let \(x\in\Delta_n\) denote its masses.
Define rational matrices \(U,V\), with three rows and \(n\) columns, by
\(U_{ci}=u_i(c),\qquad V_{ci}=v_i(c).\)
Then
\(w(x)=Ux,\qquad p(x)=Vx,\qquad N(x)=x^{\mathsf T}Hx,\)
where
\(H=\frac12(V^{\mathsf T}U+U^{\mathsf T}V).\)
For a rational threshold \(r\in[0,1]\), define three quadratic polynomials
\(q_{c,r}(x)=N(x)-r\,w_c(x).\)
Because \(r\geq0\),
\(N(x)-r\max_cw_c(x)=\min_c q_{c,r}(x).\)
Since \(W(x)>0\), it follows that
\(\rho(T)\leq r\quad\Longleftrightarrow\quad \min_{c\in C}\min_{x\in\Delta_n}q_{c,r}(x)\leq0.\)
Apply the lemma to each of these three rational quadratic polynomials. This decides the threshold question exactly in polynomial time.
Moreover, whenever the answer is affirmative, the algorithm supplies a rational \(x\) and a candidate \(c\) satisfying \(q_{c,r}(x)\leq0\). Consequently,
\(N(x)\leq r\,w_c(x)\leq r\,W(x),\)
so \(R(x)\leq r\). The threshold test therefore returns a rational society witnessing its affirmative answer.
Initialize rational endpoints \(\ell=0\) and \(u=1\). Choose any pure society as the current witness \(\widehat\mu\). The bounds established above give
\(\ell\leq\rho(T)\leq R(\widehat\mu)\leq u.\)
At each iteration, test \(r=(\ell+u)/2\).
Both updates preserve
\(\ell\leq\rho(T)\leq R(\widehat\mu)\leq u.\)
After \(K=\lceil\log_2(1/\varepsilon)\rceil\) iterations, the interval length satisfies \(u-\ell=2^{-K}\leq\varepsilon\). Output \(b=\ell\) and the stored society. Then
\(b\leq\rho(T)\leq R(\widehat\mu)\leq u\leq b+\varepsilon,\)
exactly as required.
Grouping the catalogue and finding its extrema takes polynomial time in \(s\) and \(L\). Each threshold computation has dimension at most twelve and coefficient bit length polynomial in \(L+K\). There are \(K\) threshold computations. The total running time and output bit length are therefore polynomial in \(s,L,\log(1/\varepsilon)\), with output support size \(\tau\leq\min\{s,12\}\).
This settles the stated fixed-\(m=3\) problem. The supplied discrete-society welfare guarantee is established separately by Theorem 7 of [Filos-Ratsikas and Miltersen](https://arisfilosratsikas.com/papers/range_voting.pdf).
⟨structured verdict parsed — rendered above⟩
The prover establishes the requested certified additive approximation in polynomial time for the stated fixed case \(m=3\). The argument is correct and self-contained. I found no major or minor mathematical gaps.
The polynomial bound depends on fixing \(m=3\): the reduced optimization dimension is at most twelve. The prover explicitly restricts its conclusion accordingly.
The constants satisfy
\[
77066611+80671148=157737759,
\]
so \(c_1+c_2=1\), and both constants are positive.
For each type, the probabilities assigned by \(U^1\) sum to one, as do those assigned by \(U^2\). Consequently, \(v_t\) and their mass-weighted average \(p(\mu)\) are probability vectors.
Every normalized valuation has a coordinate equal to one and all coordinates nonnegative. Thus the stated inequality \(\sum_c w_c(\mu)\geq1\) is valid, implying \(W(\mu)\geq1/3\). Since \(N(\mu)\) is a convex combination of the welfare coordinates,
\[
0\leq N(\mu)\leq W(\mu).
\]
The bounds \(0\leq R(\mu)\leq1\) follow.
Both numerator and denominator are continuous, and the denominator is uniformly positive. The catalogue is finite and nonempty, so its simplex is nonempty and compact. The attainment claim follows correctly.
Assessment: Correct, including boundary societies with zero masses.
Injectivity and normalization imply that a type with ranking \(a\succ b\succ d\) has utilities \(1,x_t,0\), with \(0<x_t<1\). There are exactly six possible rankings.
Each nonempty ranking class is finite, so its minimum and maximum middle utilities are attained by actual catalogue types. Retaining these gives at most twelve types.
When the extrema differ, the stated coefficient
\[
\lambda_t=\frac{x_+-x_t}{x_+-x_-}
\]
belongs to \([0,1]\). The utility-vector interpolation is correct coordinatewise. The election-probability vectors are identical within the ranking class, so their interpolation identity is also correct.
The replacement preserves nonnegative masses and their total, and preserves both aggregate vectors \(w\) and \(p\). Hence it preserves the ratio. This applies to real masses as required by the optimization domain.
If the extrema coincide, every type in the ranking class has the same complete valuation. Since catalogue types are distinct, this class contains only one type; no division by zero or omitted replacement arises.
Every reduced-catalogue society is admissible for the original catalogue, establishing the reverse inclusion of attainable ratios.
Assessment: The equality \(\rho(T')=\rho(T)\) is proved exactly. No limiting or non-strict types are introduced.
The lemma is valid without a definiteness assumption.
Face enumeration. Every possible positive support is enumerated. On a selected face, the displayed equations express equality of all gradient coordinates on that face, together with the simplex equation.
Feasible-point computation. The feasible set is a closed bounded rational polyhedron. The successive-coordinate minimization argument correctly establishes that any nonempty such set has a vertex. At a vertex, the equality rows and active coordinate inequalities must span the coordinate space: otherwise a nonzero annihilating direction permits feasible perturbations in both directions.
Accordingly, enumeration of coordinate zero constraints and exact solution of full-rank systems finds a rational feasible point whenever one exists. Checking all original equations and inequalities excludes invalid candidates.
Equality of stationary values. For two solutions \(y,z\) of the same face system, \(d=z-y\) has coordinate sum zero. Therefore its scalar product with either constant-coordinate gradient is zero. The calculation
\[
\nabla f(z)-\nabla f(y)=2H_{SS}d
\]
and the quadratic expansion are correct, including the factor of two. They establish that all solutions of that stationarity system have the same objective value.
Capture of a global minimum. A global minimizer exists by compactness. Its positive support places it in the relative interior of the corresponding simplex face, where the stated bidirectional perturbations are feasible. The gradient equalities therefore hold. The rational point selected for this face has exactly the global minimum value.
Other selected points need not be local minima, but all are feasible. Their inclusion cannot produce a value below the global minimum.
Complexity and edge cases. Both enumerations have constant size for fixed dimension. Exact linear algebra, evaluations, and comparisons have polynomial bit complexity. Constant-dimensional determinant bounds justify polynomial output bit length. Singleton faces are covered: their gradient equations are vacuous and their simplex equation fixes the point.
Assessment: Correct and sufficiently justified.
The matrix identity
\[
N(x)=x^{\mathsf T}\frac{V^{\mathsf T}U+U^{\mathsf T}V}{2}x
\]
is correct: symmetrization preserves the scalar quadratic form.
For \(r\geq0\), subtracting \(r\) times the largest welfare coordinate gives the smallest of the three displayed quadratic expressions. The sign restriction is essential and is explicitly satisfied.
Together with attainment and \(W(x)>0\), this proves the stated threshold equivalence. Each quadratic is rational and has dimension at most twelve, so the lemma applies.
An affirmative test supplies a rational feasible point satisfying
\[
N(x)\leq r\,w_c(x)\leq r\,W(x),
\]
and hence \(R(x)\leq r\). The selected candidate need not maximize welfare; the second inequality remains valid because \(r\geq0\).
Assessment: Correct, including equality at the threshold and the endpoint \(r=0\).
The initial interval and any pure society satisfy the claimed invariant.
An affirmative threshold result updates the upper endpoint and supplies the necessary witness. A negative result implies \(\rho(T)>r\), so updating the lower endpoint is valid while retaining the existing witness.
After the stated number of iterations, the interval width is at most \(\varepsilon\). The final inequalities therefore establish exactly the requested certificate:
\[
b\leq\rho(T)\leq R(\widehat\mu)\leq b+\varepsilon.
\]
All masses returned by the threshold algorithm are rational. Zero coordinates can be omitted in the support representation; the remaining masses are positive and sum to one. The support bound is consequently valid.
Threshold bit lengths grow polynomially with the input length and iteration count. There are only three constant-dimensional quadratic minimizations per iteration. Thus the total running time and output length have the claimed polynomial bounds.
Assessment: Correct. The argument provides both a rational upper witness and a valid rational lower bound.
The proof addresses the arbitrary rational catalogue in USER_TASK, allows omitted catalogue types, and optimizes over real masses. It does not impose a support-size restriction absent from the task.
The final reference to the discrete welfare guarantee is accurate: Theorem 7 states the guarantee for the supplied coefficients and every positive voter count in the three-candidate setting. That theorem is background and is not needed for the complexity argument. [Verified paper](https://arisfilosratsikas.com/papers/range_voting.pdf)
No additional clarification or repair 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.