Answer: Polynomial-time solvable with the exact guarantee \(2+\max\{\alpha,t_k\}\).
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThere exists a rule f that for k ∈[m−1], given a moderate-up-to-k preference profile, finds an alternative with metric distortion of at most 2 + max(α, tk). To prove this theorem, we adopt the method used by Gkatzelis et al. [22] to establish the existence of a deterministic rule with a metric distortion of 3. Their approach involves the (p, q)-domination graph, which is a bipartite graph defined for each alternative as follows.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m,\alpha,k\) and a rational distribution \(\mu\) over moderate-up-to-\(k\) ranking-with-intensity ballots, can one compute an alternative \(a\) such that, for every unit-mass electorate \(X\) whose ballot map has pushforward \(\mu\), and every compatible metric \(d\), \(\int_X d(x,a)\,d\lambda(x) \le [2+\max(\alpha,t_k)]\min_{c\in A}\int_X d(x,c)\,d\lambda(x)\), in time polynomial in \(m,\tau,L\)? Here \(t_k\) is the bound defined in Theorem 2.
Let \(A\) contain \(m\ge2\) alternatives, let \(\alpha\in[0,1]\) be a binary rational, and let \(1\le k\le m-1\). A ballot consists of a strict ranking \(\pi\) and a normal or strong mark between each consecutive pair.
A ballot is moderate-up-to-\(k\) when its first \(k\) marks are normal and its next mark is strong; for \(k=m-1\), all marks are normal. Later marks are unrestricted.
A society \(\mu\) is given by its support: the list of its \(\tau\) positive-mass ballot types, each mass a binary rational, summing to \(1\). Here \(\tau\) is the support size, not the number of possible ballots; \(L\) is the total input bit length. Every supported ballot is moderate-up-to-\(k\).
An electorate is any probability space \((X,\lambda)\) with a measurable ballot map having pushforward \(\mu\). Voters and alternatives occupy a metric space, with coincident locations allowed; their induced distances are measurable and have finite social costs.
Compatibility requires, almost everywhere, for consecutive alternatives \(u=\pi(j)\), \(v=\pi(j+1)\): a normal mark means \(\alpha d(x,v)<d(x,u)\le d(x,v)\), and a strong mark means \(d(x,u)\le\alpha d(x,v)\). Equal distances may be ordered arbitrarily subject to these conditions.
Define \(w_1=(1+\alpha)/(1+3\alpha)\), \(t_1=(1-\alpha)/(1+3\alpha)\), and, for \(2\le j\le k\), \(w_j=1-2\alpha/((1-\alpha)t_{j-1}+2w_{j-1}+2\alpha)\), \(t_j=w_j+(1-w_j)t_{j-1}\).
Can a deterministic algorithm, given only \((A,\alpha,k,\mu)\), compute an alternative \(a\) satisfying \(\int_X d(x,a)\,d\lambda(x)\le[2+\max\{\alpha,t_k\}]\min_{c\in A}\int_X d(x,c)\,d\lambda(x)\) for every such electorate and compatible metric, in time polynomial in \(m,\tau,k,L\), or is obtaining this same guarantee NP-hard?
For finite electorates, a polynomial-time deterministic rule achieves this distortion bound ([Abbaszadeh et al.](https://arxiv.org/html/2601.02095v1)). No result addressing exactly the distribution-input problem above was located.
1. Result
The problem is polynomial-time solvable. An algorithm can obtain the exact stated guarantee using at most \(m^2+1\) rational linear programs, each of polynomial size.
The proof uses the finite-electorate existence guarantee supplied in the question, namely [Abbaszadeh et al., Theorem 3.2](https://arxiv.org/html/2601.02095v1#S3.Thmtheorem3.2). It does not require running their algorithm on an exponentially expanded electorate.
Write the supported ballot types as \(\sigma_1,\ldots,\sigma_\tau\), with masses \(p_1,\ldots,p_\tau>0\). Set \(R=2+\max\{\alpha,t_k\}\).
2. Exact representation by conditional mean distances
Introduce variables \(D_{ab}\) for distances between alternatives, and \(h_{ia}\) for the distance from a representative of ballot type \(i\) to alternative \(a\). Use the conventions \(D_{aa}=0\) and \(D_{ab}=D_{ba}\).
Impose nonnegativity and the following inequalities:
For each consecutive pair \(u,v\) in ballot \(\sigma_i\), impose:
Define \(C_a(h)=\sum_{i=1}^{\tau}p_i h_{ia}\).
We prove that these variables exactly represent the social-cost vectors attainable by compatible electorates.
From an arbitrary electorate to these variables.
Let \(X_i\) be the measurable set of voters with ballot \(\sigma_i\). Its mass is \(p_i\). Define
\(\displaystyle h_{ia}=\frac{1}{p_i}\int_{X_i}d(x,a)\,d\lambda(x),\qquad D_{ab}=d(a,b).\)
Every \(h_{ia}\) is finite by the assumed finite social costs. The metric inequalities follow by integrating the pointwise triangle inequalities. For example,
\(\displaystyle D_{ab}\le d(a,x)+d(x,b)\)
gives \(D_{ab}\le h_{ia}+h_{ib}\).
The ballot inequalities also survive averaging, including strict normal inequalities. Indeed, for a normal pair, the integrable function \(d(x,u)-\alpha d(x,v)\) is positive almost everywhere on \(X_i\), so its integral is positive. Consequently, \(h_{iu}>\alpha h_{iv}\).
Finally,
\(\displaystyle C_a(h)=\int_X d(x,a)\,d\lambda(x).\)
From these variables to a finite metric representation.
Suppose the listed inequalities hold. Construct an undirected weighted graph with alternative vertices and one additional vertex \(v_i\) per ballot type:
Give the vertices their shortest-path distances.
These distances preserve every specified alternative distance. To see this, an internal segment \(a,v_i,b\) has length \(h_{ia}+h_{ib}\ge D_{ab}\), so replacing that segment by the alternative edge cannot increase the path length. After all such replacements, the alternative triangle inequalities show that any path from \(a\) to \(b\) has length at least \(D_{ab}\). The direct edge attains this length.
Likewise, a shortest path from \(v_i\) to \(a\) can be chosen without repeated vertices, since edge lengths are nonnegative. If its first alternative is \(b\), replacing its remaining internal type vertices as above shows that its length is at least \(h_{ib}+D_{ba}\). The inequality \(h_{ia}-h_{ib}\le D_{ab}\) then gives
\(\displaystyle h_{ib}+D_{ba}\ge h_{ia}.\)
The direct edge attains \(h_{ia}\).
Thus the resulting distances are exactly \(D_{ab}\) and \(h_{ia}\). Zero distances produce a pseudometric; identifying vertices at zero distance gives a metric space with coincident labeled locations, as permitted in the question.
Put mass \(p_i\) at \(v_i\), with ballot \(\sigma_i\). All compatibility inequalities hold, and the social costs are \(C_a(h)\).
This proves the exact representation.
3. Handling strict inequalities by linear programming
Let \(P\) be the closed polytope obtained from the constraints above by:
Let \(S\subseteq P\) consist of the points where every normal lower inequality is strict.
The upper bounds lose no relevant information: all metric and ballot constraints are homogeneous, so any feasible finite coordinate vector can be scaled into the unit cube. Social-cost comparisons scale by the same positive factor.
We can determine whether \(S\) is empty with one linear program. Add a variable \(0\le\varepsilon\le1\), require
\(\displaystyle h_{iu}-\alpha h_{iv}\ge\varepsilon\)
for every normal pair, and maximize \(\varepsilon\) over \(P\).
Its optimum is positive exactly when \(S\ne\varnothing\). One direction is immediate. For the other, a point of \(S\) has finitely many positive normal gaps; their minimum is positive and supplies a feasible positive \(\varepsilon\).
If the optimum is zero, no compatible electorate exists, by the representation proved above. The algorithm may then return any alternative.
Assume henceforth that \(S\ne\varnothing\), and fix \(z^0\in S\). For any \(z\in P\) and \(0<\delta\le1\), define
\(\displaystyle z^\delta=(1-\delta)z+\delta z^0.\)
Convexity gives \(z^\delta\in P\). Every normal gap at \(z^\delta\) is a convex combination of a nonnegative gap and a strictly positive gap, hence is positive. Therefore \(z^\delta\in S\), and \(z^\delta\to z\).
In particular, every point of \(P\) is a limit of compatible finite metric representations.
4. A uniformly good alternative exists on the whole polytope
Because the masses are rational, choose an integer \(N\) such that every \(Np_i\) is an integer. Form a fixed finite profile containing \(Np_i\) copies of ballot \(\sigma_i\).
This profile satisfies the moderate-up-to-\(k\) hypothesis: every copied ballot is one of the supported ballots, and the all-normal exception is unchanged.
The supplied finite-electorate theorem gives an alternative \(a^\star\), depending only on this fixed profile, whose guarantee holds for every compatible metric.
For each \(z\in S\), realize its coordinates using the metric construction in Section 2 and place all copies of type \(i\) at \(v_i\). This is a compatible finite electorate. Its total cost for alternative \(a\) is \(N C_a(z)\). Hence, for every \(b\in A\),
\(\displaystyle C_{a^\star}(z)\le R C_b(z)\qquad(z\in S).\)
The alternative \(a^\star\) is the same for every \(z\), because the finite rule sees the same profile throughout.
Now fix any \(z\in P\). Apply this inequality to \(z^\delta\in S\) and let \(\delta\) tend to zero. Linearity and continuity of the costs yield
\(\displaystyle C_{a^\star}(z)\le R C_b(z)\qquad(z\in P,\ b\in A).\)
Thus a single alternative satisfies all required comparisons throughout the closed polytope.
The potentially enormous integer \(N\) is used only in this existence proof.
5. The deterministic algorithm and its correctness
Fix a deterministic order of the alternatives. After the strict-feasibility test above, compute, for each ordered pair \(a,b\),
\(\displaystyle M_{ab}=\max_{z\in P}\bigl(C_a(z)-R C_b(z)\bigr).\)
These are bounded rational linear programs. The origin belongs to \(P\), so every \(M_{ab}\) is nonnegative.
Return the first alternative \(a\) for which \(M_{ab}=0\) for every \(b\in A\). Section 4 proves that at least one such alternative exists.
To verify the guarantee, take any compatible measurable electorate. Section 2 supplies coordinates representing its social costs. Scale those coordinates into \(P\). The selected alternative satisfies \(C_a\le R C_b\) there for every \(b\), by the definition of \(M_{ab}\). Scaling back gives
\(\displaystyle \int_X d(x,a)\,d\lambda(x)\le R\int_X d(x,b)\,d\lambda(x)\qquad(b\in A).\)
Taking the minimum over \(b\) proves precisely the requested guarantee. This argument also covers zero optimal social cost.
6. Polynomial bit complexity
It remains to verify that computing \(R\) exactly does not produce exponentially long rational numbers.
Write \(\alpha=p/q\), with integers \(0\le p\le q\) and \(q\ge1\). Define integer triples by
\(\displaystyle W_1=q+p,\qquad T_1=q-p,\qquad Q_1=q+3p,\)
and, for \(j\ge2\), by
\(\displaystyle W_j=(q-p)T_{j-1}+2qW_{j-1},\)
\(\displaystyle T_j=(q+p)T_{j-1}+2qW_{j-1},\)
\(\displaystyle Q_j=(q-p)T_{j-1}+2qW_{j-1}+2pQ_{j-1}.\)
These satisfy \(w_j=W_j/Q_j\) and \(t_j=T_j/Q_j\). For verification, assuming the previous identities, the denominator in the defining recurrence for \(w_j\) is
\(\displaystyle (1-\alpha)t_{j-1}+2w_{j-1}+2\alpha=\frac{Q_j}{qQ_{j-1}}.\)
Therefore
\(\displaystyle w_j=1-\frac{2pQ_{j-1}}{Q_j}=\frac{W_j}{Q_j},\)
and
\(\displaystyle t_j=\frac{W_j+2pT_{j-1}}{Q_j}=\frac{T_j}{Q_j}.\)
All denominators are positive: initially \(W_1,Q_1>0\), and subsequently \(W_j\ge2qW_{j-1}>0\) and \(Q_j\ge W_j\).
If \(B_j=\max\{W_j,T_j,Q_j\}\), the displayed recurrences give \(B_j\le5qB_{j-1}\), while \(B_1\le4q\). Hence these integers have \(O(k(1+\log q))\) bits. Computing \(R\) and comparing \(\alpha\) with \(t_k\) therefore takes polynomial time.
Each linear program has \(O(\tau m+m^2)\) variables and \(O(\tau m^2+m^3)\) constraints. Its rational coefficients have polynomial bit length in \(k,L\). There are at most \(m^2+1\) programs.
We use the standard theorem that rational linear programming admits deterministic exact optimization in time polynomial in its binary encoding length; exactness permits comparison of the optimum with zero. See [Trevisan’s linear-programming notes](https://lucatrevisan.github.io/cs261/lecture05.pdf). All programs here are nonempty and bounded, so their optima exist.
Consequently, the complete algorithm runs in time polynomial in \(m,\tau,k,L\), with the exact distortion bound \(2+\max\{\alpha,t_k\}\).
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The argument establishes a deterministic algorithm with the exact requested guarantee and running time polynomial in \(m,\tau,k,L\). I found no major or minor mathematical issues requiring repair.
The proof’s essential quantifier claim is justified: it obtains one alternative that works for every compatible metric, rather than choosing an alternative separately for each metric.
Arbitrary electorate to coordinates: correct.
Since \(p_i>0\), each conditional mean \(h_{ia}\) is well-defined. Finite social costs and nonnegative distances ensure these means are finite.
All three inequalities involving \(h_{ia},h_{ib},D_{ab}\) follow from the corresponding pointwise triangle inequalities by integration over \(X_i\) and division by \(p_i\). Alternative triangle inequalities hold because \(D_{ab}\) is an actual alternative distance.
The strict normal inequality also survives averaging. An integrable function that is positive almost everywhere on a set of positive measure has strictly positive integral. Thus the claimed implication from pointwise compatibility to \(h_{iu}>\alpha h_{iv}\) is valid. No uniform pointwise margin is needed.
Finally, the supported ballot sets partition the electorate up to a null set, so \(C_a(h)\) equals the original social cost.
Coordinates to metric representation: correct.
The graph construction preserves the specified distances:
The direct edges attain both lower bounds. Consequently, the constructed distances equal all specified coordinates.
Quotienting by zero distance is valid. Keeping voter and alternative labels at their resulting locations is consistent with the task’s explicit permission for coincident locations. Distinct ballot types may have distinct voter labels even when their locations coincide.
The representation is therefore exact at the level needed: attainable social-cost vectors, with shared alternative distances.
Correct.
All compatibility and metric constraints are homogeneous. Every feasible coordinate vector is finite-dimensional with finite entries, so positive scaling places it in the unit cube while preserving strict inequalities and social-cost comparisons.
The strict-feasibility LP is valid. There are finitely many normal inequalities, and a strictly feasible point has a positive minimum gap. Conversely, a positive feasible value of \(\varepsilon\) makes every normal inequality strict.
There is always at least one normal mark per supported ballot because \(k\ge1\). Thus the argument does not encounter an empty family of normal gaps.
If strict feasibility fails, the exact representation proves that no compatible electorate exists. Returning any alternative then satisfies the universal requirement vacuously.
When \(S\) is nonempty, the interpolation argument correctly proves that \(S\) is dense in \(P\). Every non-strict linear constraint survives convex combination, while every normal gap becomes positive because the coefficient of the fixed strictly feasible point is positive.
No assumption that every boundary point itself is compatible is used.
Correct, including the theorem’s hypotheses and quantifiers.
The cited paper’s formal moderate-up-to-\(k\) definition, mandatory compatibility inequalities, recurrence, and Theorem 3.2 match the task. Its definition includes the all-normal case \(k=m-1\). The theorem supplies a rule whose output has the asserted worst-case metric guarantee. [Abbaszadeh et al., Definition 1 and Theorem 3.2](https://arxiv.org/html/2601.02095v1#S3.Thmtheorem3.2)
Rational masses admit a common denominator \(N\), and the resulting finite profile has exactly \(Np_i\) voters of each type. Every copied ballot retains the required moderate-up-to-\(k\) property.
The fixed profile is crucial. The finite rule selects the same \(a^\star\) for every compatible metric realizing that profile. Therefore the proof establishes
\[
\exists a^\star\in A\;\forall z\in S\;\forall b\in A:
C_{a^\star}(z)\le R C_b(z).
\]
It does not interchange an existential and universal quantifier without justification.
The finite total costs are exactly \(N C_a(z)\), so canceling \(N\) is legitimate. Continuity then extends each inequality to all of \(P\), with the same alternative \(a^\star\).
The potentially large \(N\) appears only in the existence argument and does not affect the algorithm’s running time.
Correct.
The polytope \(P\) is nonempty because it contains the origin, and it is bounded by its coordinate bounds. Each objective therefore has an attained finite maximum.
The origin also proves \(M_{ab}\ge0\). Hence \(M_{ab}=0\) is exactly the condition that
\[
C_a(z)\le R C_b(z)
\]
holds throughout \(P\).
Section 4 guarantees an alternative passing every comparison. Choosing the first such alternative in a fixed order makes the algorithm deterministic.
For any compatible electorate, its conditional-mean coordinates scale into \(P\). The selected inequalities therefore hold for its costs after scaling back. Taking the minimum over the finitely many alternatives gives precisely the requested guarantee.
The argument uses inequalities rather than division by the optimal social cost, so zero-cost cases introduce no undefined ratio.
Correct.
The initial integer triple represents the stated values of \(w_1,t_1\). Substitution into the recurrence gives denominator \(Q_j/(qQ_{j-1})\), as claimed.
The identities
\[
Q_j-W_j=2pQ_{j-1},
\qquad
W_j+2pT_{j-1}=T_j
\]
verify both subsequent rational representations.
All triple entries are nonnegative. Moreover, \(W_1,Q_1>0\), \(W_j\ge2qW_{j-1}>0\), and \(Q_j\ge W_j\), so every recurrence denominator is positive throughout the stated parameter range.
The growth estimate \(B_j\le5qB_{j-1}\) is valid, though loose. Together with \(B_1\le4q\), it gives the asserted \(O(k(1+\log q))\) bit bound. Reduction to lowest terms is unnecessary.
The variable and constraint counts are correct. Multiplying mass coefficients by \(R\) preserves polynomial encoding length. The invoked rational LP theorem applies to these nonempty bounded programs and permits exact optimization and exact comparison with zero in polynomial time. [Trevisan’s linear-programming notes, Sections 2.4–2.5](https://lucatrevisan.github.io/cs261/lecture05.pdf)
Thus at most \(m^2+1\) polynomial-size LPs suffice.
The written argument covers \(k=1\), \(k=m-1\), and \(m=2\) without additional steps.
At \(\alpha=1\), normal compatibility is impossible, and the strict-feasibility branch correctly detects this. At \(\alpha=0\), the constraints remain meaningful, and any incompatibility is likewise handled by that branch. The rational recurrence remains defined at both endpoints.
Minimum additional clarification needed: none. The proof resolves the distribution-input problem using the finite-electorate guarantee supplied in the task.
⟨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.