Answer: \(\alpha(0)=1\), while \(\alpha(\eta)=+\infty\) for every \(0<\eta<1/3\). At \(\eta=0\), deterministic polynomial-time algorithms achieve every fixed factor \(1+\varepsilon\); factor \(1\) is achievable iff \(\mathrm P=\mathrm{NP}\). At positive \(\eta\), no algorithm can achieve a finite uniform guarantee.
Theorem 4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThere is a tournament graph corresponding to a preference profile for which the Byzan- tine nodes may change the edge weights such that the median of the resulting preference profile is a k k−2-approximation of the optimal median, where k = n/t. For t close to n/3, this gives a 3- approximation.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\), rational \(\eta\in[0,1/3)\), and an observed rational distribution \(\rho\) over rankings \(\mathcal R=S_m\), listed on its \(\tau\)-type support, define \(\mathcal H_\eta(\rho)=\{\mu\in\Delta(\mathcal R):\exists\nu\in\Delta(\mathcal R),\ \rho=(1-\eta)\mu+\eta\nu\}\) and \(U=\{(a,b):\exists\mu\in\mathcal H_\eta(\rho)\text{ with }\mu(\{p:a\succ_p b\})=1\}\). Decide whether \(U\) is acyclic; if not, return a directed-cycle certificate. If it is, return a ranking \(q\) respecting every pair in \(U\) that minimizes \(\sup_{\mu\in\mathcal H_\eta(\rho)}D(q,\mu)/\operatorname{OPT}(\mu)\), along with a worst-case compatible \(\mu\), where \(D(q,\mu)=\sum_p\mu_p\tau(q,p)\), \(\operatorname{OPT}(\mu)=\min_sD(s,\mu)\), and a zero denominator gives ratio \(1\) when \(D=0\) and \(+\infty\) otherwise.
Let \(m\ge3\), let \(\mathcal R=S_m\) consist of strict rankings, and let rational \(\eta\in[0,1/3)\) be given.
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational. Here \(\tau\) is the support size, not the number of possible types. The observed society \(\rho\) has total mass \(1\); let \(L\) be the total input bit length.
Write \(\Delta(\mathcal R)\) for all probability distributions on \(\mathcal R\), allowing real masses, and define \(\mathcal H_\eta(\rho)=\{\mu\in\Delta(\mathcal R):\exists\nu\in\Delta(\mathcal R),\ \rho=(1-\eta)\mu+\eta\nu\}\).
Define \(U=\{(a,b):a\ne b,\ \exists\mu\in\mathcal H_\eta(\rho),\ \mu(\{p:a\succ_p b\})=1\}\).
Using Kendall's \(\tau\) distance, set \(D(q,\mu)=\sum_{p\in\mathcal R}\mu_p\tau(q,p)\), \(\operatorname{OPT}(\mu)=\min_{s\in\mathcal R}D(s,\mu)\), and \(R(q)=\sup_{\mu\in\mathcal H_\eta(\rho)}D(q,\mu)/\operatorname{OPT}(\mu)\).
A zero denominator gives ratio \(1\) when the numerator is zero and \(+\infty\) otherwise. Any tied choice of ranking is permitted, but the procedure must be deterministic.
If \(U\) is cyclic, return a directed cycle; otherwise return a ranking \(q\) respecting every pair in \(U\), together with a compatible \(\mu\) attaining \(R(q)\).
What is the sharp uniform approximation guarantee \(\alpha(\eta)\) for \(R(q)\) over all inputs with acyclic \(U\)? Which guarantees can deterministic algorithms achieve in time polynomial in \(m,\tau,L\)?
For finite electorates with \(n\) voters and \(0<t<n/3\) Byzantine voters, an indistinguishability lower bound is \(n/(n-2t)\); a matching distributed guarantee is reported, using exact Kemeny medians as a subroutine. [Melnyk, Wang and Wattenhofer](https://disco.ethz.ch/courses/hs19/distsys/lnotes/byzantine%20preferential%20voting%20paper.pdf).
For ranking distributions, breakdown bounds under total variation perturbations are known, addressing displacement of median rankings rather than the compatible-society ratio above. [Goibert et al.](https://proceedings.mlr.press/v202/goibert23a/goibert23a.pdf). No result settling this precise approximation task was located.
The sharp uniform guarantee for the task as stated is
\(\alpha(0)=1\), and \(\alpha(\eta)=+\infty\) for every \(0<\eta<1/3\).
Here “uniform” means independent of \(m,\tau,L\). For every fixed positive \(\eta\), there are societies with acyclic \(U\) that force a unique output ranking and whose robust ratio grows without bound as \(m\) grows. Their support size stays fixed.
Consequently, no algorithm, regardless of running time, can achieve a finite uniform guarantee when \(\eta>0\). At \(\eta=0\), deterministic polynomial-time algorithms achieve \(1+\varepsilon\) for every fixed \(\varepsilon>0\); achieving \(1\) in polynomial time is equivalent to \(\mathrm P=\mathrm{NP}\).
An exact rational distribution attaining the requested supremum always exists for a ranking respecting \(U\). Thus the negative result is not an issue of nonattainment.
Write the observed support as \(p_1,\ldots,p_\tau\), with masses \(r_1,\ldots,r_\tau\). Introduce the unnormalized retained masses \(x_i=(1-\eta)\mu_{p_i}\).
Compatibility is equivalent to
\[ \mathcal P=\left\{x\in\mathbb R^\tau:0\le x_i\le r_i,\ \sum_{i=1}^{\tau}x_i=1-\eta\right\}. \]
Indeed, compatibility forces \(\mu\) to have no mass outside the observed support and gives these inequalities. Conversely, for \(\eta>0\), define \(\mu_{p_i}=x_i/(1-\eta)\) and \(\nu_{p_i}=(r_i-x_i)/\eta\). These are probability distributions satisfying the required decomposition. For \(\eta=0\), the conditions force \(x=r\) and \(\mu=\rho\).
For distinct candidates \(a,b\), let \(w_{ab}=\rho(\{p:a\succ_p b\})\). A compatible distribution can be unanimous on \(a\succ b\) exactly when the capacity on that event is sufficient to retain mass \(1-\eta\). Therefore,
\[ (a,b)\in U\quad\Longleftrightarrow\quad w_{ab}\ge 1-\eta. \]
Computing these quantities takes polynomial time in \(m,\tau,L\). Standard deterministic graph search then either returns a directed cycle or constructs a topological ordering of \(U\).
Fix \(0<\eta<1/3\). Choose a power of two \(k\) satisfying \(k\eta\ge 1-\eta\). This \(k\) remains fixed throughout the construction.
For any integer \(m\ge 2k\), use candidates \(1,\ldots,m\), and define
\[ q_0=(1,2,\ldots,m),\qquad s_0=(m,m-1,\ldots,1). \]
For each \(r\in\{0,\ldots,k-1\}\), partition the increasing list \(1,\ldots,m\) into consecutive blocks by cutting after every \(i<m\) satisfying \(i\equiv r\pmod{k}\).
Every block has size at most \(k\). Define \(p_r\) by reversing the order of the blocks while keeping the candidates within each block in increasing order.
Two properties follow directly:
Choose a dyadic rational \(h\) such that
\[ \eta<h\le \eta+\frac{1-\eta}{m^2}. \]
Such a number exists by density of dyadic rationals. Set
\[ \rho=h\delta_{q_0}+\frac{1-h}{k}\sum_{r=0}^{k-1}\delta_{p_r}. \]
Because \(k\) is a power of two, every observed mass is dyadic. For \(m\ge 2k\), the displayed rankings are distinct, so \(\tau=k+1\).
For every \(a<b\), the mass at \(q_0\) implies \(w_{ab}\ge h>\eta\). Hence \(w_{ba}<1-\eta\), so no backward pair \((b,a)\) belongs to \(U\).
For every adjacent pair,
\[ w_{i,i+1}=1-\frac{1-h}{k} \ge 1-\frac{1-\eta}{k} \ge 1-\eta. \]
Thus \(U\) contains the entire chain
\[ 1\succ 2\succ\cdots\succ m. \]
All its edges point forward in \(q_0\), so \(U\) is acyclic. Since it contains this chain, its only respecting ranking is \(q_0\).
Let \(M=\binom m2\), \(B_r=\tau(s_0,p_r)\), and \(B=k^{-1}\sum_r B_r\).
If a block has size \(b\le k\), it contributes \(\binom b2\le b(k-1)/2\) disagreements with \(s_0\). Summing over the blocks gives
\[ B_r\le \frac{m(k-1)}2,\qquad B\le \frac{m(k-1)}2. \]
Since \(q_0\) and \(s_0\) orient every pair oppositely,
\[ \tau(q_0,p_r)=M-B_r. \]
Now remove mass \(\eta\) entirely from the observed atom \(q_0\). Writing \(e=h-\eta>0\), the resulting compatible distribution is
\[ \mu=\frac{e}{1-\eta}\delta_{q_0} +\frac{1-h}{k(1-\eta)}\sum_{r=0}^{k-1}\delta_{p_r}. \]
The decomposition uses \(\nu=\delta_{q_0}\). Direct calculation yields
\[ D(q_0,\mu)=\frac{(1-h)(M-B)}{1-\eta}, \]
and
\[ D(s_0,\mu)=\frac{eM+(1-h)B}{1-\eta}. \]
Because \(\operatorname{OPT}(\mu)\le D(s_0,\mu)\),
\[ R(q_0)\ge \frac{(1-h)(M-B)}{eM+(1-h)B}. \]
The bounds on \(h,e,B\) give
\[ R(q_0)\ge \frac{(1-1/m^2)m(m-k)}{1+(k-1)m}. \]
For \(m\ge 2k\), we have \(1-1/m^2\ge 1/2\), \(m-k\ge m/2\), and \(1+(k-1)m\le km\). Consequently,
\[ R(q_0)\ge \frac{m}{4k}. \]
This tends to infinity. Every admissible procedure must output \(q_0\), so the construction proves \(\alpha(\eta)=+\infty\) for every fixed positive \(\eta\).
The proof uses neither a cyclic \(U\) nor a zero denominator.
Let \(q\) respect an acyclic \(U\).
Suppose some compatible distribution is \(\delta_p\). By the capped-simplex characterization, \(\rho_p\ge 1-\eta\). Every comparison in \(p\) then belongs to \(U\), forcing \(q=p\).
For every compatible \(\mu\),
\[ \mu_p\ge \frac{\rho_p-\eta}{1-\eta} \ge \frac{1-2\eta}{1-\eta}>\frac12. \]
For any \(s\ne p\), the triangle inequality gives
\[ D(s,\mu)-D(p,\mu) \ge (2\mu_p-1)\tau(s,p)>0. \]
Thus \(p\) is the unique Kemeny median of every compatible distribution. All relevant ratios equal \(1\), including under the prescribed zero-denominator convention. Hence \(R(q)=1\), attained, for example, by \(\mu=\rho\).
Otherwise, \(\operatorname{OPT}(\mu)>0\) throughout the compact compatible polytope. Since it is the minimum of finitely many continuous linear functions, it is continuous and has a strictly positive minimum there.
For each ranking \(s\), define \(A(x)=\sum_i x_i\tau(q,p_i)\) and \(B_s(x)=\sum_i x_i\tau(s,p_i)\). Then
\[ R(q)=\max_{s\in S_m}\max_{x\in\mathcal P}\frac{A(x)}{B_s(x)}. \]
Each denominator is positive. A linear-fractional function with positive denominator attains its maximum at a vertex: if \(x=\sum_j\lambda_jv_j\), then
\[ \frac{A(x)}{B_s(x)} = \frac{\sum_j\lambda_jB_s(v_j)\,[A(v_j)/B_s(v_j)]} {\sum_j\lambda_jB_s(v_j)}, \]
which is a weighted average of its vertex values.
Every vertex of \(\mathcal P\) is rational; at most one coordinate lies strictly between its lower and upper bounds. Therefore a rational compatible \(\mu\) attaining \(R(q)\) exists, with encoding length polynomial in the input length.
A deterministic exact procedure can enumerate the vertices and rankings, evaluate all ratios, and return a maximizing witness. It can also minimize \(R(q)\) over rankings respecting \(U\). This establishes an exact procedure with exponential running time; it does not assert polynomial-time adversarial-witness search.
When \(\eta=0\), the compatible set is \(\{\rho\}\). Choosing an exact Kemeny median gives \(R(q)=1\).
It remains to check the requirement to respect \(U\).
Suppose every supported ranking puts \(a\) above \(b\), but \(q\) puts \(b\) above \(a\). Exchange the positions of \(a,b\).
The contribution of \(\{a,b\}\) decreases by \(1\). For each candidate \(c\) positioned between them, the combined contribution of \(\{a,c\},\{b,c\}\) decreases by
\[ 2\rho(\{p:a\succ_p c\succ_p b\})\ge 0. \]
To verify this, the possible orders in a supported ranking are \(c\succ a\succ b\), \(a\succ c\succ b\), and \(a\succ b\succ c\); their decreases are respectively \(0,2,0\). All other pair contributions remain unchanged.
Hence the exchange strictly decreases \(D(q,\rho)\). Every exact Kemeny median therefore respects \(U\), proving \(\alpha(0)=1\).
The weighted tournament PTAS of Kenyon-Mathieu and Schudy can be derandomized and gives a \(1+\varepsilon\) approximation for every fixed \(\varepsilon>0\). Its hypotheses hold here: take the pair weight \(w_{ab}=\rho(a\succ b)\), so \(w_{ab}\ge0\) and \(w_{ab}+w_{ba}=1\). These weights are computable using polynomial-time rational arithmetic from the support representation. [Kenyon-Mathieu and Schudy, Theorem 1](https://eccc.weizmann.ac.il/report/2006/144/download).
Apply the unanimity repair above whenever necessary, deterministically choosing the first violated pair. Each exchange decreases the normalized cost by at least \(1\), while the initial cost is at most \(\binom m2\). Thus at most \(\binom m2\) exchanges occur. The approximation guarantee is preserved, and the required maximizing witness is simply \(\mu=\rho\).
Achieving exactly \(1\) would compute an exact Kemeny median. That problem is NP-hard even for four equally weighted rankings, which are valid dyadic inputs here. [Dwork et al., Appendix B](https://archives.iw3c2.org/www10/cdrom/papers/577/). Conversely, if \(\mathrm P=\mathrm{NP}\), polynomial-time decision and search recover an exact median.
Thus the finite uniform guarantees are classified as follows:
| Contamination | Sharp unrestricted-time guarantee | Deterministic polynomial-time guarantees |
|---|---|---|
| \(\eta=0\) | \(1\) | Every fixed \(1+\varepsilon\); exactly \(1\) iff \(\mathrm P=\mathrm{NP}\) |
| \(0<\eta<1/3\) | \(+\infty\) | No finite uniform guarantee |
The factor \(1/(1-2\eta)\) does hold if one may output an exact Kemeny median \(q\) of \(\rho\) without imposing the comparisons in \(U\).
Indeed, for any compatible decomposition and any Kemeny median \(s\) of \(\mu\), observed optimality and the triangle inequality imply
\[ (1-\eta)\bigl(D(q,\mu)-D(s,\mu)\bigr) \le \eta\,\tau(q,s) \le \eta\bigl(D(q,\mu)+D(s,\mu)\bigr). \]
Therefore \((1-2\eta)D(q,\mu)\le D(s,\mu)\), with the zero-denominator convention also respected.
The present task additionally demands validity simultaneously for every compatible society. Its high-support comparisons can force a long chain even though their individual unanimity witnesses differ. Section 2 proves that this requirement precludes a finite uniform ratio. The reported distributed bound therefore cannot supply the requested guarantee under this precise observation model and output condition. [Melnyk, Wang and Wattenhofer](https://disco.ethz.ch/courses/hs19/distsys/lnotes/byzantine%20preferential%20voting%20paper.pdf).
⟨structured verdict parsed — rendered above⟩
The output resolves the requested uniform approximation question. The unboundedness construction, supremum-attainment argument, and uncontaminated-case guarantees are correct. I found no major or minor mathematical issues.
The computational conclusion concerns finite uniform approximation factors. The output does not establish polynomial-time maximizing-witness search for positive contamination, and explicitly avoids claiming that result.
The retained-mass polytope is correct. Since \(1-\eta>0\), the decomposition forces \(\mu\) to vanish outside the observed support and imposes \(0\le x_i\le r_i\), with total retained mass \(1-\eta\). Conversely, the displayed definitions of \(\mu\) and \(\nu\) give probability distributions when \(\eta>0\). The separate treatment of \(\eta=0\) correctly avoids division by zero.
The equivalence \((a,b)\in U\Longleftrightarrow w_{ab}\ge1-\eta\) is valid: unanimity requires all retained mass to lie in the indicated event, whose available capacity is \(w_{ab}\). Fractional retention is permitted, so sufficient capacity also suffices.
Computing these capacities, detecting a directed cycle, and obtaining a deterministic topological ordering all take polynomial time in the specified support representation.
The choice of a power of two \(k\) with \(k\eta\ge1-\eta\) is possible for every fixed positive \(\eta\). Its independence from \(m\) is essential and is stated correctly.
The partition construction has the claimed properties:
Thus exactly one \(p_r\) reverses any given adjacent pair, and \(p_r\) disagrees with \(s_0\) precisely within blocks.
For \(m\ge2k\), each residue class occurs among the possible cut positions. Consequently, the \(p_r\) are distinct from each other and from \(q_0\). The claimed support size \(k+1\) is correct.
The interval prescribed for \(h\) is nonempty and contains a dyadic rational strictly larger than \(\eta\). Its upper endpoint is below \(1\), so all observed masses are positive. Division by the power of two \(k\) preserves dyadic rationality.
For every \(a<b\), the atom at \(q_0\) gives \(w_{ab}\ge h>\eta\). Hence \(w_{ba}=1-w_{ab}<1-\eta\), excluding every backward edge from \(U\).
The adjacent-pair calculation is exact: \(w_{i,i+1}=1-(1-h)/k\). The subsequent inequalities follow from \(h>\eta\) and \(k\eta\ge1-\eta\).
Therefore \(U\) contains the complete adjacent chain and has no backward edges. It is acyclic, and every ranking respecting it must equal \(q_0\). The construction satisfies the task’s admissibility condition; it does not obtain its lower bound through a cyclic instance.
Removing mass \(\eta\) from \(q_0\) is permitted because \(h>\eta\). The proposed \(\mu\) is compatible, with contaminating distribution \(\nu=\delta_{q_0}\).
The block disagreement estimate \(B_r\le m(k-1)/2\) is correct. The complement identity \(\tau(q_0,p_r)=M-B_r\) follows because \(q_0\) and \(s_0\) orient every candidate pair oppositely. Both displayed cost formulas consequently check out.
Using \(\operatorname{OPT}(\mu)\le D(s_0,\mu)\) gives the lower bound in the correct direction. The constants in the next estimate also check out. In particular:
These bounds yield the displayed fraction, and the restrictions \(m\ge2k\) yield \(R(q_0)\ge m/(4k)\).
The witness has positive mass on multiple distinct rankings, so its optimal cost is positive. The divergence therefore does not rely on the zero-denominator convention.
Because the forced ranking is unique and \(k\) remains fixed as \(m\) grows, this establishes the absence of any finite uniform guarantee for every fixed positive \(\eta\), regardless of computational resources.
The point-mass case is handled correctly. Compatibility of \(\delta_p\) implies \(\rho_p\ge1-\eta\), placing every comparison of \(p\) in \(U\) and forcing \(q=p\).
The lower bound on \(\mu_p\) follows from the total available mass outside \(p\). Since \(\eta<1/3\), it exceeds \(1/2\). The triangle-inequality estimate then establishes that \(p\) is the unique median of every compatible distribution. The conclusion \(R(q)=1\), including compatible point masses, respects the prescribed convention.
In the remaining case, zero optimal cost would require a point mass, since Kendall distance vanishes only between identical rankings. Thus optimal cost is positive everywhere on the compact compatible polytope. Continuity gives a positive minimum.
The conversion to a maximum over rankings and retained-mass vectors is valid. The displayed weighted-average identity correctly proves that each positive-denominator linear-fractional objective has a vertex maximizer.
The vertex description and rationality claim are correct. At most one coordinate can lie strictly between its bounds; its value is determined by the rational sum constraint. The resulting witness has polynomial encoding length. Exhaustive deterministic enumeration therefore provides the claimed exact procedure, without implying polynomial running time.
When \(\eta=0\), compatibility reduces to \(\mu=\rho\). An exact median achieves ratio \(1\), including when optimal cost is zero.
The swap calculation is correct. Under unanimous preference for \(a\) over \(b\), the three possible relative orders involving an intermediate candidate contribute decreases \(0,2,0\). The pair \(\{a,b\}\) contributes a decrease of \(1\), and all other pair contributions remain unchanged.
Hence every violating swap strictly decreases cost, proving that exact medians respect \(U\). The same calculation supports the polynomial repair procedure: each swap decreases cost by at least \(1\), the initial cost is at most \(\binom m2\), and repair preserves an existing approximation guarantee.
The cited PTAS theorem applies. Its weighted-tournament hypotheses require nonnegative weights with pairwise sums bounded between a fixed positive constant and \(1\); here those sums equal \(1\). The source explicitly supplies derandomization, so fixed-\(\varepsilon\) deterministic polynomial time is supported. Rational weight computation and arithmetic are compatible with the input representation. [Kenyon-Mathieu and Schudy, Theorem 1](https://eccc.weizmann.ac.il/report/2006/144/download).
The cited hardness result covers four equally weighted full rankings. Such profiles fit the support representation; repeated rankings, if present, can be combined into dyadic masses. Since exact medians respect unanimous comparisons, the output constraint does not invalidate this hardness application. The converse under \(\mathrm P=\mathrm{NP}\) uses polynomially verifiable ranking certificates and rational costs of polynomial encoding length. [Dwork et al., Appendix B](https://archives.iw3c2.org/www10/cdrom/papers/577/).
Thus the claimed deterministic guarantees at \(\eta=0\) are justified: every fixed factor \(1+\varepsilon\), and exact factor \(1\) precisely if \(\mathrm P=\mathrm{NP}\).
The final inequalities follow from observed optimality and the triangle inequality in the stated directions. They establish the factor \(1/(1-2\eta)\) when choosing an observed median without the additional \(U\)-respecting restriction. If the compatible optimal cost is zero, the same inequality forces the numerator to vanish.
This does not conflict with the construction: the construction forces a ranking through comparisons whose unanimity witnesses can differ. The output correctly distinguishes that requirement from unconstrained observed-median selection.
No repair or additional mathematical clarification is needed. The exact continuous optimization problem has an NP-hard uncontaminated subcase; the positive-contamination conclusion establishes unbounded uniform approximation ratios, rather than a separate computational-hardness classification for each fixed positive \(\eta\).
⟨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.