Answer: A deterministic algorithm always outputs \(W\in F\) with \(R(W)\le 5\) in time polynomial in \(m,\tau,L\).
Theorem 3.16 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe distortion of Algorithm 2 for minimum total social cost is at most 5, and this bound is tight.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(F\), a rational mass distribution \(\mu\) over reported rankings, and public ordinal comparisons of candidate distances, output a candidate \(W\) whose robust distortion over all compatible mass measures \(\lambda\) on complete latent metric types with report marginal \(\mu\) is at most \(5\): \(\sup_{\lambda}\frac{\int d_u(W)\,d\lambda(u)}{\min_{Y\in F}\int d_u(Y)\,d\lambda(u)}\le 5\).
Let \(F\) be a nonempty set of \(m\) candidates. A society is given by its support: a list of \(\tau\) reported strict total rankings, each with positive binary rational mass \(\mu(\sigma)\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible rankings; \(L\) is the total input bit length.
For each candidate \(X\), the public input also gives a total ranking of \(F\setminus\{X\}\) by distance from \(X\). These rankings specify weak distance comparisons, with equal distances broken arbitrarily; numerical candidate distances are unknown.
A complete latent type is \(u=(\sigma,(d_u(X))_{X\in F})\), with finite nonnegative real distances satisfying \(d_u(X)\le d_u(Y)\) whenever \(X\) precedes \(Y\) in \(\sigma\). A compatible world uses one common metric on the distinct candidates and voter locations, realizes these distances and all public comparisons, and carries a Borel probability measure \(\lambda\) on latent types with report marginal \(\mu\) and finite expected distances. Voters may coincide with candidates, and each report may split over arbitrarily many latent types. Inputs are promised to admit a compatible world.
Define \(C_\lambda(X)=\int d_u(X)\,d\lambda(u)\) and \(R(W)=\sup_\lambda C_\lambda(W)/\min_{Y\in F}C_\lambda(Y)\), where the supremum ranges over compatible worlds. Interpret a zero-over-zero ratio as \(1\), and a positive-over-zero ratio as \(+\infty\).
Can a deterministic algorithm always output \(W\in F\) with \(R(W)\le5\) in time polynomial in \(m,\tau,L\), or is achieving this distortion guarantee NP-hard?
For finite electorates, a deterministic polynomial-time rule using voter rankings and candidate distance rankings achieves total-cost distortion at most \(5\); this bound is tight for that rule. [Anshelevich–Zhu](https://arxiv.org/html/1805.03103)
A related continuum model assigns ranking masses to finitely many latent locations and studies distortion with small-group deliberation; its information model differs from the one above. [Goel–Goyal–Munagala](https://arxiv.org/html/2502.01380v2)
A deterministic polynomial-time algorithm always finds a candidate \(W\) with \(R(W)\le 5\).
The algorithm below implements the comparison principle behind [Anshelevich–Zhu’s Algorithm 2 and Theorem 3.16](https://arxiv.org/html/1805.03103#S3.SS2.SSS2). We prove its guarantee directly for the measure-valued model, including arbitrary splitting of each report.
The case \(m=1\) is immediate: return the sole candidate, whose distortion is \(1\) under the stated conventions. Assume henceforth that \(m\ge 2\).
For distinct candidates \(A,B\), define the reported preference mass
\[ q(A,B)=\sum_{\sigma:\,A\text{ precedes }B\text{ in }\sigma}\mu(\sigma). \]
Strict total reports imply \(q(A,B)+q(B,A)=1\). Say that \(A\) weakly defeats \(B\) when \(q(A,B)\ge \tfrac12\). At least one candidate weakly defeats the other in every pair.
Next, construct a directed graph \(Q\) whose vertices are unordered candidate pairs. Write \(e(A,B)=\{A,B\}\). Whenever \(A\) precedes \(B\) in the public distance ranking from \(X\), insert the arc
\[ e(X,A)\longrightarrow e(X,B). \]
Let \(e\preceq f\) mean that \(f\) is reachable from \(e\), allowing a path of length zero.
In any compatible world, write \(D(A,B)\) for the common candidate distance and \(D(e(A,B))=D(A,B)\). Every arc of \(Q\) represents a valid weak inequality. Therefore transitivity gives
\[ e\preceq f\quad\Longrightarrow\quad D(e)\le D(f) \]
in every compatible world. Reachability also handles cycles of weak comparisons automatically.
Construct a directed graph \(G\) on the candidates. For distinct \(W,Y\), include \(W\longrightarrow Y\) exactly when there exists \(P\ne Y\) satisfying
\[ q(P,Y)\ge \tfrac12 \qquad\text{and}\qquad e(Y,W)\preceq e(Y,P). \]
Allow \(P=W\). Thus, whenever \(W\) weakly defeats \(Y\), the edge \(W\longrightarrow Y\) exists by reflexivity of reachability. Consequently, \(G\) has at least one directed edge between every distinct pair.
Return the first candidate in the input order that has an outgoing edge to every other candidate. We next prove that such a candidate exists.
Suppose, for contradiction, that no candidate has outgoing edges to all others.
Define a graph \(H\) containing precisely the edges \(A\longrightarrow B\) of \(G\) whose reverse edge is absent from \(G\).
Every vertex \(Y\) has positive indegree in \(H\): by assumption some edge \(Y\longrightarrow Z\) is absent from \(G\), while the pairwise property of \(G\) ensures that \(Z\longrightarrow Y\) is present.
A finite directed graph with positive indegree at every vertex contains a directed cycle: repeatedly follow an incoming edge until a vertex repeats. Choose a simple cycle
\[ X_0\longrightarrow X_1\longrightarrow\cdots \longrightarrow X_{k-1}\longrightarrow X_0. \]
Here \(k\ge 3\), since \(H\) has no loops or oppositely directed edge pairs. All subscripts below are interpreted modulo \(k\).
Every edge \(A\longrightarrow B\) in \(H\) is a weak defeat. Indeed, if \(q(A,B)<\tfrac12\), then \(q(B,A)>\tfrac12\), so the reverse edge would belong to \(G\), contradicting its absence.
Set \(e_i=e(X_i,X_{i+1})\). The incoming cycle edge shows that \(X_{i-1}\) weakly defeats \(X_i\). Since \(X_{i+1}\longrightarrow X_i\) is absent from \(G\), the algorithm’s edge condition, with \(P=X_{i-1}\), implies
\[ e_i\not\preceq e_{i-1}. \]
Both pairs share \(X_i\). Its public total ranking therefore supplies one of the comparisons \(e_i\preceq e_{i-1}\) or \(e_{i-1}\preceq e_i\). The former is excluded, so
\[ e_{i-1}\preceq e_i \]
for every \(i\). These comparisons form a cycle of reachability relations. Following that cycle gives \(e_i\preceq e_{i-1}\), a contradiction.
Hence the algorithm always returns a candidate.
Fix an arbitrary compatible world, with measure \(\lambda\). Let \(W\longrightarrow Y\) be an edge of \(G\), and choose its witness \(P\).
Let \(S\) be the set of latent types whose report places \(P\) before \(Y\). This is a Borel set determined by the report coordinate. The report marginal gives
\[ \lambda(S)=q(P,Y)\ge \tfrac12. \]
For every \(u\in S\), ranking consistency and the metric triangle inequality imply
\[ D(P,Y)\le d_u(P)+d_u(Y)\le 2d_u(Y). \]
Nonnegativity then yields
\[ C_\lambda(Y) \ge \int_S d_u(Y)\,d\lambda(u) \ge \frac{\lambda(S)}2D(P,Y) \ge \frac14D(P,Y). \]
The public-comparison condition for the edge guarantees
\[ D(Y,W)\le D(Y,P). \]
Finally, the metric triangle inequality holds for every latent type:
\[ d_u(W)\le d_u(Y)+D(Y,W). \]
Integrating, using total mass \(1\) and finite expected distances, gives
\[ C_\lambda(W) \le C_\lambda(Y)+D(Y,W) \le C_\lambda(Y)+D(Y,P) \le 5C_\lambda(Y). \]
This argument uses the report marginal only to determine \(\lambda(S)\). It therefore applies regardless of how each report splits across latent types.
The returned candidate \(W\) has an edge to every distinct \(Y\). Together with the trivial inequality for \(Y=W\), the preceding result proves
\[ C_\lambda(W)\le 5C_\lambda(Y) \]
for every candidate \(Y\) and every compatible world.
Because the candidate set is finite, its minimum cost is attained. If that minimum is positive, the desired ratio is at most \(5\). If it is zero, the displayed inequality forces \(C_\lambda(W)=0\), so the stipulated ratio is \(1\).
The same input-dependent candidate works in every compatible world. Taking the supremum proves \(R(W)\le 5\).
There are \(\binom m2\) vertices in \(Q\). It suffices to insert comparisons between consecutive entries of each public ranking: paths imply all other comparisons. Thus \(Q\) has \(O(m^2)\) arcs. Its transitive closure can be computed in \(O(m^6)\) Boolean operations. Testing all triples defining \(G\) takes \(O(m^3)\) further operations.
The majority masses can be computed without expanding the electorate. Write the input masses as \(\mu(\sigma)=a_\sigma/b_\sigma\), and let
\[ B=\prod_\sigma b_\sigma, \qquad n_\sigma=a_\sigma(B/b_\sigma). \]
The bit length of \(B\) is \(O(L)\). Moreover, the positive integers \(n_\sigma\) sum to \(B\), because the masses sum to \(1\). Every majority comparison can therefore be performed exactly by testing
\[ 2\sum_{\sigma:\,A\text{ precedes }B}n_\sigma\ge B. \]
There are \(O(\tau m^2)\) such additions, involving integers of \(O(L)\) bits. All preprocessing and graph computations consequently take time polynomial in \(m,\tau,L\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. Its algorithm uses only the supplied rankings and rational masses, always returns a candidate, and proves the required bound uniformly over all compatible worlds. I found no major or minor mathematical issues.
The case \(m=1\) is handled correctly, including zero cost: the stipulated ratio is always \(1\).
For distinct candidates, strict total reports imply
\(q(A,B)+q(B,A)=1\). Thus at least one direction is a weak majority defeat, including exact ties.
The graph \(Q\) correctly represents the public weak distance comparisons. Unordered pair vertices respect metric symmetry, and every directed path implies the corresponding weak inequality in every compatible world. Cycles cause no problem: reachability is a preorder, and the proof does not incorrectly assume antisymmetry or strict distance comparisons.
The edge condition is well-defined: \(W\ne Y\) and \(P\ne Y\) ensure that both pair vertices exist.
Allowing \(P=W\) correctly ensures that every weak majority defeat produces an edge, by reflexive reachability. Consequently, every distinct candidate pair has at least one directed edge in \(G\).
Selecting the first qualifying candidate in input order makes the algorithm deterministic.
The contradiction argument is valid at every step:
The contradiction establishes the claimed existence. It also accommodates arbitrarily broken distance ties.
The measure argument is rigorous. The set \(S\) is measurable because it is determined by the finite report coordinate, and the report marginal gives \(\lambda(S)=q(P,Y)\).
For each realized type in \(S\), ranking consistency and the common metric give
\(D(P,Y)\le d_u(P)+d_u(Y)\le 2d_u(Y)\).
Nonnegativity and \(\lambda(S)\ge \tfrac12\) then correctly yield
\(C_\lambda(Y)\ge D(P,Y)/4\).
The edge certificate gives \(D(Y,W)\le D(Y,P)\). Integrating
\(d_u(W)\le d_u(Y)+D(Y,W)\)
is legitimate because expected distances are finite and \(\lambda\) has total mass \(1\). Combining the inequalities yields
\(C_\lambda(W)\le 5C_\lambda(Y)\), with the constant checked correctly.
The proof makes no finite-support assumption about latent types. Arbitrary splitting of reports is covered by the marginal identity alone.
The cited [Anshelevich–Zhu paper](https://arxiv.org/html/1805.03103#S3.SS2.SSS2) contains the corresponding finite-electorate comparison principle and total-cost bound. The submission independently proves what it needs for this model; it does not rely on an unstated continuum extension of that theorem.
The returned candidate satisfies the cost inequality against every distinct candidate; against itself, it follows from nonnegativity.
The minimum exists because \(F\) is finite. For a positive minimum, division gives the required ratio. For a zero minimum, the inequality forces the returned candidate’s cost to be zero, so the specified zero-over-zero convention gives ratio \(1\).
The quantifier order is correct: the algorithm selects one candidate from the public input, and that same candidate satisfies the bound in every compatible world. Taking the supremum therefore preserves the bound.
The complexity claims are correct:
No electorate expansion is required.
The output fully establishes the deterministic polynomial-time guarantee requested in USER_TASK. No additional lemma, clarification, or repair is needed.
⟨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.