Answer: Polynomial-time computable in \(m,\tau,L\), with \(D_\mu(S_\mu)\le 1+\sqrt2\) for every promised input.
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet $f$ be the voting rule that, for any election instance $\instance = (\voters, \candidates, k, \succ)$, selects a committee of size two according to Algorithm~\ref{alg:2-winner-voting-rule} (the $2$-Winner Polar Comparison Rule). Assume that voters and candidates lie on a line metric, and let $d$ be any metric consistent with~$\succ$. Then, under the utilitarian additive social cost, \[ \dist(f(\succ), \instance; d) \le 1+\sqrt{2}. \] In particular, the distortion of $f$ satisfies \[ \dist(f) \le 1+\sqrt{2}.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) candidates, \(k=2\), and a rational distribution \(\mu\) over complete rankings with a common line realization, compute the mass version \(S_\mu\) of the Polar Comparison Rule using pairwise masses \(\mu(a\succ b)\). For every compatible candidate placement \(y\) and unit-mass voter-location measure \(\nu\) whose ranking marginal is \(\mu\), require \(\sup_{(y,\nu)\models\mu}\frac{\int \sum_{a\in S_\mu}|z-y_a|\,d\nu(t,z)}{\min_{S\in\binom{C}{2}}\int \sum_{a\in S}|z-y_a|\,d\nu(t,z)}\le 1+\sqrt{2}\).
Let \(C=[m]\), with \(m\ge 2\), and fix committee size \(k=2\). A society is given by its support: the list of the \(\tau\) strict complete rankings with positive mass, each mass a binary rational; masses sum to \(1\). Here \(\tau\) is the support size, not the number of possible rankings, and \(L\) is the total input bit length.
A compatible realization consists of distinct candidate locations \(y_a\in\mathbb R\) and a probability measure \(\nu\) on ranking–location pairs \((t,z)\), with ranking marginal \(\mu\), finite first moment, and \(|z-y_a|<|z-y_b|\) whenever \(a\succ_t b\), almost surely. Existence of such a realization is promised; locations are not supplied.
Write \(p_{ab}=\sum_{t:a\succ_t b}\mu(t)\). To fix ordinal choices, select the lexicographically least candidate sequence admitting a compatible realization in that left-to-right order. Orient majority arcs by \(p_{ab}>1/2\), breaking equal-mass ties toward the earlier candidate in this sequence; let the majority order be the lexicographically least Hamiltonian path of this tournament.
Define the mass Polar Comparison Rule as follows. Let \(a,b\) be the first two candidates in the majority order, and remove every candidate \(e\) for which \(p_{e'e}=1\) for some \(e'\notin\{e,a\}\). Among the remaining candidates strictly opposite \(b\) across \(a\) in the selected candidate sequence, let \(c\) be the nearest to \(a\) in that sequence. Set \(S_\mu=\{a,b\}\) if \(c\) does not exist, or \(p_{cb}\le 1/(1+\sqrt2)\), or \(p_{ba}\ge 1/(1+\sqrt2)\); otherwise set \(S_\mu=\{a,c\}\).
For a compatible realization define \(\operatorname{SC}_\nu(S;y)=\int\sum_{a\in S}|z-y_a|\,d\nu(t,z)\) and \(D_\mu(S)=\sup_{(y,\nu)\models\mu}\operatorname{SC}_\nu(S;y)/\min_{T\in\binom C2}\operatorname{SC}_\nu(T;y)\).
Can the mass Polar Comparison Rule be computed in time polynomial in \(m,\tau,L\) while guaranteeing \(D_\mu(S_\mu)\le 1+\sqrt2\) for every promised input, or does either requirement fail?
For finite electorates, the Polar Comparison Rule guarantees utilitarian additive distortion at most \(1+\sqrt2\); this bound is tight for deterministic two-winner rules when \(m\ge4\). [Verified discrete results](https://arxiv.org/pdf/2411.13720). No result settling exactly the distributional problem above was located.
Both requirements hold. The mass Polar Comparison Rule is computable in time polynomial in \(m,\tau,L\), and every promised input satisfies \(D_\mu(S_\mu)\le 1+\sqrt2\).
The proof requires two separate arguments: an exact polynomial algorithm for the prescribed candidate order, and a transfer of the finite-electorate distortion theorem to arbitrary compatible probability measures.
Fix distinct candidate locations \(y\). For a ranking \(t\), define its location region by
\(\displaystyle I_t(y)=\{z\in\mathbb R: |z-y_a|<|z-y_b|\text{ whenever }a\succ_t b\}.\)
For distinct locations, each pairwise inequality defines an open half-line whose boundary is the corresponding candidate midpoint. Thus \(I_t(y)\) is an open interval, possibly unbounded or empty.
A candidate order admits a compatible realization of \(\mu\) if and only if it admits a Euclidean embedding with one voter for each supported ranking:
The latter measure has finite support and therefore finite first moment. Consequently, candidate-order feasibility depends only on the supported rankings, not on their positive masses.
Call a candidate order a *single-peaked axis* if every initial segment of every supported ranking is consecutive in that order. Every realizable candidate order is such an axis: candidates closer than a given distance to a voter form an interval on the line.
We use the following structural part of Knoblauch’s Euclidean-recognition algorithm.
Known structural result. For a Euclidean-realizable finite profile of strict complete rankings, one can compute in polynomial time a subset \(B\subseteq C\) and an order \(\pi_B\) such that:
These are the properties established in Step 3 and Lemma 2 of [Knoblauch’s working paper](https://media.economics.uconn.edu/working/2008-52.pdf).
Its hypotheses hold here by Section 1. The algorithm uses the \(\tau\) supported rankings as its finite profile.
The following extension lemma supplies the additional fact needed for our lexicographic requirement.
A candidate order \(\sigma\) is realizable if and only if:
Proof. Necessity follows from the preceding observations and the structural result.
For sufficiency, first suppose \(B\ne\varnothing\). Start with an embedding of the restricted profile on \(B\), reflected if necessary to match \(\sigma|_B\). Use one voter location \(z_t\) for each original supported ranking.
Candidates in \(U\) have the same relative ranking in every vote. Insert them in that unanimous preference order, from best to worst, always following their positions in \(\sigma\).
Consider an insertion of \(u\). Among the candidates already present, let \(P\) consist of those unanimously preferred to \(u\), and let \(Q\) consist of those unanimously worse than \(u\). These sets partition the present candidates because \(u\) is unanimously comparable with every candidate.
Suppose first that \(P\ne\varnothing\). In the restriction of \(\sigma\) to the present candidates and \(u\), both \(P\) and \(P\cup\{u\}\) are initial ranking segments. Hence both are consecutive. Thus \(u\) is immediately outside \(P\), on one specified side, and every candidate in \(Q\) lies outside the interval occupied by \(P\).
Keep \(P\) and all voters fixed. Translate every member of \(Q\) to the left of \(P\) leftward by \(H\), and every member to the right rightward by \(H\).
This preserves the current rankings:
Choose a location \(w\) for \(u\), outside \(P\) on its specified side, sufficiently far away that every voter prefers every member of \(P\) to \(u\). Then choose \(H\) sufficiently large that every voter prefers \(u\) to every member of \(Q\), and \(u\) lies before the translated \(Q\) candidates on its side. This realizes all required comparisons and the prescribed order.
If \(P=\varnothing\), then \(u\) is universally best among the current candidates. Choose a point \(h\) in the gap prescribed for \(u\) by \(\sigma\). Translate the candidates to its left by \(-H\), and those to its right by \(H\). Cross-side midpoints remain unchanged. Within either side, the rankings are unanimously monotone toward \(h\), because the axis is single-peaked with common top candidate \(u\). For sufficiently large \(H\), all voters lie between the two sides, those within-side rankings hold, and every voter prefers a new candidate at \(h\) to every translated candidate.
These insertions finish the construction.
If \(B=\varnothing\), unanimous comparability means all rankings coincide. Place their best candidate and all voters at zero. Insert subsequent candidates on their prescribed sides, choosing each new distance sufficiently large. The same nonempty-\(P\) insertion argument applies, with \(Q\) empty. This realizes every single-peaked axis. \(\square\)
For each supported ranking and each initial segment, impose the requirement that its candidate set be consecutive. There are \(\tau m\) such sets, with total explicit size polynomial in \(\tau,m\).
The [Booth–Lueker PQ-tree theorem](https://www.cs.uoi.gr/~loukas/courses/grad/Algorithmic_Graph_Theory/index.files/Booth-Lueker-PQtrees.pdf) gives a polynomial algorithm constructing a tree whose frontiers are exactly the permutations satisfying these consecutivity constraints. At a P-node its children may be permuted arbitrarily; at a Q-node their listed order may be reversed.
By Lemma 1, we must find the least frontier whose restriction to \(B\) is \(\pi_B\), and separately the least whose restriction is its reversal.
Here is an explicit polynomial procedure for either prescribed core order.
For every node, its descendant \(B\)-leaves must be consecutive in the prescribed core order, since all its descendant leaves form one block in a frontier. Reject a node if this condition fails. Process the tree from leaves upward.
The greedy P-node step is exact. Its available child blocks have distinct first candidates, and selecting any available block leaves a feasible ordering of the remaining blocks. Therefore the smallest available first candidate determines the lexicographically best next block. Internal child choices are independent once their core subsequences are fixed.
Induction proves that each node returns its least feasible frontier. All operations are polynomial. Taking the smaller root frontier from the two core orientations gives exactly the least realizable candidate sequence required by the question. If \(B=\varnothing\), run the unconstrained version once.
Compute all \(p_{ab}\) directly from the support using exact rational arithmetic.
The tournament specified in the question is transitive. To prove this, take an embedding in the selected candidate order with one voter point per supported ranking. Clear the rational mass denominators, obtaining a finite electorate for this argument.
Let \(z_*\) be its lower median voter location. For candidates with \(y_a<y_b\), write \(h=(y_a+y_b)/2\). Strict compatibility excludes voters at \(h\). The tournament directs \(a\) toward \(b\) precisely when at least half the electorate lies to the left of \(h\), including equality because \(a\) occurs earlier on the axis. This is equivalent to \(z_*<h\).
Thus the tournament is exactly the strict distance ranking of the lower median voter. It is transitive and has a unique Hamiltonian path. Its lexicographically least Hamiltonian path therefore requires only sorting or topological ordering.
After this, the domination test and the search for \(c\) are direct polynomial scans.
The irrational threshold also presents no computational difficulty. Since \(1/(1+\sqrt2)=\sqrt2-1\), for a nonnegative rational \(r=u/v\), with \(v>0\),
\(\displaystyle r\le\frac1{1+\sqrt2}\quad\Longleftrightarrow\quad (u+v)^2\le 2v^2.\)
The corresponding greater-than-or-equal comparison is obtained by reversing the inequality.
A common denominator has bit length at most the sum of the input denominator lengths. Hence all rational sums and integer comparisons have polynomial bit complexity. The whole rule is therefore computable in time polynomial in \(m,\tau,L\).
Before transferring the distortion bound, we verify that the selected axis does not cause a mismatch with the geometric Polar Comparison Rule in another compatible embedding.
Let \(a,b\) be the first two majority candidates, and let \(R\) be the surviving candidates other than \(a\).
The candidate \(a\) survives: a unanimous dominator would have a majority arc toward \(a\), contradicting its first position in the transitive tournament. Also \(b\in R\): any unanimous dominator other than \(a\) would precede \(b\).
Any two distinct members of \(R\) are not unanimously comparable; otherwise one would remove the other. Therefore, if \(|R|\ge2\), every member of \(R\) belongs to \(B\).
Every tied-majority pair likewise belongs to \(B\), since a candidate outside \(B\) is unanimously comparable with every candidate. Reflect any compatible embedding, if necessary, so that its order on \(B\) agrees with the selected axis. Reflection preserves all costs. All majority ties then point toward the geometrically left candidate.
The surviving order also agrees:
Consequently, in every compatible finite embedding, after the harmless reflection, our majority choices and geometric choice of \(c\) coincide with Algorithm 3 of the cited paper.
We may therefore apply its finite-electorate theorem: for strict complete rankings and distinct candidate locations on the line, that two-winner Polar Comparison Rule has utilitarian additive distortion at most \(1+\sqrt2\). The domination exclusion and both threshold branches are exactly those in this question after normalizing voter counts. See [Algorithm 3 and Theorem 1](https://arxiv.org/pdf/2411.13720).
Fix an arbitrary compatible realization \((y,\nu)\). Define
\(\displaystyle F_a=\int |z-y_a|\,d\nu(t,z).\)
Every \(F_a\) is finite by the first-moment assumption.
There exists a compatible finite atomic measure with the same ranking marginal and exactly the same \(F_a\) for every candidate.
Proof. Order the candidate locations and partition the line into the \(m+1\) intervals cut by those locations, assigning each boundary consistently to an adjacent interval.
For each supported ranking \(t\), restrict its conditional location distribution to each partition cell of positive mass. Replace that restriction by one atom at its conditional mean.
Every function \(z\mapsto |z-y_a|\) is affine on each cell. Thus conditional averaging preserves its integral.
The new atom remains in \(I_t(y)\): that set is an open interval, and the mean of an integrable random variable lying almost surely strictly between its finite endpoints also lies strictly between them. Therefore every atom remains strictly compatible.
There are at most \(\tau(m+1)\) atoms. Their masses preserve the ranking marginal and every candidate’s cost. \(\square\)
Denote these atoms by \((t,z_{tj})\), with masses \(\alpha_{tj}>0\). They satisfy \(\sum_j\alpha_{tj}=\mu(t)\).
Choose a positive integer \(Q\) with \(Q\mu(t)\) integral for every supported ranking. For each positive integer \(N\), approximate the atom masses by multiples of \(1/(NQ)\), preserving each ranking’s total exactly. Explicitly, round down all but the last atom count within each ranking, and assign the remaining count to its last atom.
The resulting counts \(n_{tj}^{(N)}\) are nonnegative integers satisfying
\(\displaystyle \sum_j n_{tj}^{(N)}=NQ\mu(t),\qquad \frac{n_{tj}^{(N)}}{NQ}\longrightarrow\alpha_{tj}.\)
Place that many voters at each \(z_{tj}\). This gives a compatible finite electorate with exactly the original normalized ranking masses. Hence it selects exactly \(S_\mu\): its support, candidate-order feasibility, majority comparisons, domination tests, and thresholds are unchanged.
Let \(\nu_N\) be its normalized empirical measure. Because the atom locations are fixed and finite in number,
\(\displaystyle \operatorname{SC}_{\nu_N}(T;y)\longrightarrow\operatorname{SC}_{\nu}(T;y)\)
for every committee \(T\). There are finitely many two-candidate committees, so their minimum costs converge as well.
The finite theorem gives, for every \(N\),
\(\displaystyle \operatorname{SC}_{\nu_N}(S_\mu;y)\le(1+\sqrt2)\min_{T\in\binom C2}\operatorname{SC}_{\nu_N}(T;y).\)
Passing to the limit proves the same inequality for \(\nu\).
Finally, its denominator is positive. For distinct candidates \(r,s\), the triangle inequality gives
\(\displaystyle \operatorname{SC}_{\nu}(\{r,s\};y)\ge |y_r-y_s|>0.\)
Taking the minimum over finitely many pairs preserves positivity. Dividing and then taking the supremum over all compatible realizations establishes \(D_\mu(S_\mu)\le1+\sqrt2\).
The potentially enormous finite electorates appear only in the proof of the bound; the polynomial algorithm never constructs them.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The argument establishes both polynomial-time computation of the prescribed rule and the bound \(D_\mu(S_\mu)\le 1+\sqrt2\). I found no major or minor mathematical gaps.
The external results cited in the proof have the required scope. The checks below concern the submitted argument; they do not supply an alternative proof.
The description of \(I_t(y)\) is correct. With distinct candidate locations, each strict distance comparison imposes an open half-line constraint. Their intersection is an open interval, possibly empty or unbounded.
Both directions of the claimed equivalence are justified:
Thus the feasible candidate orders depend only on the support. No assumption about the sizes or denominators of the positive masses enters this equivalence.
The single-peaked-axis condition is necessary: an initial ranking segment consists of the candidates inside an appropriate distance interval around the voter. This also holds for every restriction used later in the proof.
Finding: correct.
The cited structural result matches the source. Knoblauch’s Step 3 fixes the order of the restricted core \(B\) up to reversal, and Lemma 2 gives unanimous comparability of candidates outside that core with every other candidate. The full support profile is Euclidean-realizable by Section 1, so the required hypothesis holds. The source’s procedure computes the relevant sets and order in polynomial time. [Knoblauch’s working paper](https://media.economics.uconn.edu/working/2008-52.pdf)
The necessity direction of Lemma 1 follows from these properties and the initial-segment condition.
The sufficiency construction withstands the following checks.
Unanimous comparability makes \(P\) and \(Q\) a genuine partition of the candidates already present. For every restricted ranking, \(P\) and \(P\cup\{u\}\) are initial segments. Their consecutivity therefore places \(u\) directly outside the block \(P\), with \(Q\) outside that block.
The stated translation preserves all existing comparisons:
There are finitely many voter points and candidates. Thus the successive choices of \(w\) and \(H\) can satisfy all the stated strict inequalities simultaneously. Taking \(H\) after choosing \(w\) also ensures the prescribed candidate order and distinctness.
Here \(u\) is first in every restricted ranking. The single-peaked-axis condition consequently forces the stated monotone preferences on each side of its prescribed gap.
Opposite-side comparisons are preserved by unchanged midpoints. For sufficiently large \(H\), all finitely many voter points lie between the translated sides, the within-side preferences agree with those required, and the new candidate is strictly preferred to every existing candidate. The argument also covers an exterior gap or an empty side.
When \(B=\varnothing\), unanimous comparability forces all supported rankings to coincide. The submitted construction starts with their common first candidate and inserts subsequent candidates at sufficiently large distances on the sides prescribed by the axis. Its use of the nonempty-\(P\) case is valid.
Finding: Lemma 1 is established as written.
The initial-segment constraints number at most \(\tau m\), and their total explicit size is polynomial in \(m,\tau\).
The cited PQ-tree result provides exactly the required representation of permutations satisfying these consecutivity constraints, with independent permutations at P-nodes and reversals at Q-nodes. Its reduction algorithm has polynomial running time in the explicit constraint size. [Booth–Lueker paper](https://www.cs.uoi.gr/~loukas/courses/grad/Algorithmic_Graph_Theory/index.files/Booth-Lueker-PQtrees.pdf)
The additional optimization procedure is valid:
The bottom-up induction therefore returns the least feasible frontier for each core orientation. Lemma 1 justifies taking the smaller of those two frontiers as the least realizable candidate sequence. The unconstrained empty-core case is handled explicitly.
Finding: the prescribed candidate sequence is computable in polynomial time.
The lower-median argument correctly handles both odd and even electorates.
For \(y_a<y_b\), strict compatibility excludes voter points at their midpoint \(h\). The arc points from \(a\) to \(b\) exactly when at least half the electorate lies left of \(h\), because an equal split is resolved toward the earlier candidate. This is equivalent to the lower median lying strictly left of \(h\).
Thus every tournament comparison agrees with the lower median voter’s strict distance ranking. The tournament is transitive, and its Hamiltonian path is unique. Sorting or topological ordering computes precisely the majority order specified in the task.
The threshold computation is correct for \(u\ge0\) and \(v>0\):
\[ \frac uv\le\sqrt2-1 \quad\Longleftrightarrow\quad (u+v)^2\le2v^2. \]
Both sides being squared are nonnegative, so squaring introduces no extraneous cases. Reversing the inequality correctly handles the other threshold comparison.
The rational arithmetic claim also holds: a product of the input denominators has bit length bounded by their total bit length. Rational summation, exact unanimity and majority tests, and the integer-square comparisons therefore have polynomial bit complexity.
Finding: the remaining rule computations are polynomial in \(m,\tau,L\).
The ordinal-convention check is sufficient.
Neither \(a\) nor \(b\) can be removed: a relevant unanimous dominator would precede the candidate in the transitive majority order.
Two distinct members of \(R\) cannot be unanimously comparable, since their unanimous comparison would remove the worse member. Consequently, when \(|R|\ge2\), every member of \(R\) belongs to the core. Every tied-majority pair also belongs to the core, because unanimous comparability is incompatible with a half-mass comparison.
Reflecting an embedding aligns its core orientation with the selected sequence. This aligns all majority ties.
For the surviving candidates, the proof properly separates the substantive cases:
Algorithm 3 has exactly the submitted domination exclusion and threshold branches. The source also breaks majority ties toward the geometrically left candidate. Theorem 1 gives the claimed utilitarian additive bound for compatible finite line embeddings with distinct candidate locations; its scope includes even electorates. Thus the application after reflection is justified. [Algorithm 3, Lemma 3, and Theorem 1](https://arxiv.org/pdf/2411.13720)
Finding: the finite theorem applies to the submitted rule’s output in every compatible finite embedding.
Lemma 2 is valid.
Finite first moment makes every conditional mean used in the compression finite. Each candidate-distance function is affine on a cell cut out by the candidate locations, including whichever adjacent cell receives a boundary point. Replacing a positive-mass restriction by its conditional mean therefore preserves all candidate costs.
The mean remains inside the ranking’s open interval: the submitted strict-endpoint argument applies to each finite endpoint, while an unbounded endpoint imposes no restriction. Compatibility and the ranking marginal are therefore preserved. The atom count is at most \(\tau(m+1)\).
The subsequent integer approximation also checks out:
Although some atoms can disappear for small \(N\), each ranking retains its positive total mass. Thus the ranking support and every ordinal choice defining \(S_\mu\) remain unchanged.
Because the atom locations are fixed and finite in number, all committee costs converge. The minimum also converges because there are finitely many committees. Passing to the limit in the finite-theorem inequality is justified.
Finally, for every candidate pair,
\[ \operatorname{SC}_\nu(\{r,s\};y)\ge |y_r-y_s|>0. \]
Distinctness and finiteness of the candidate set make the minimum denominator positive. Division and the supremum over compatible realizations are therefore valid.
Finding: the distortion bound is established for every promised input. The large finite electorates are used only for the transfer argument and do not affect the computational bound.
None. No repair or additional mathematical lemma 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.