| paper | d4-conf-wine-2018-0017 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
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. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
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.
A batch robust Kemeny problem over ranking types: the observed distribution is a mixture of honest mass \((1-\eta)\mu\) and Byzantine mass \(\eta\nu\); choose a ranking minimizing its worst-case Kemeny approximation ratio over compatible honest societies, while detecting when robust Pareto validity forces a cycle.
The mirror covers Theorem 4's Byzantine Kemeny approximation lower bound and the Section 5 objective of approximating the honest Kemeny median. It leaves out Theorem 6's distributed protocol guarantees, Theorem 3's agreement protocol, and the axiomatic results.
The strongest mirror I believe in is robust continuous Kemeny consensus. Let \(\mathcal R=S_m\) be the strict rankings of the \(m\) candidates. A type is a ranking \(p\in\mathcal R\); the population is large, with many agents sharing each of a relatively small number \(\tau\) of ranking types. A concrete setting is the paper’s distributed model-aggregation application: many validators rank the same finite set of labels, and repeated model or deployment templates produce repeated rankings. A fraction \(\eta<1/3\) of the population is Byzantine and can report arbitrary rankings.
The honest population has an unknown distribution \(\mu\) over \(\mathcal R\), and the faulty population has a distribution \(\nu\). The observed report distribution is
\[
\rho=(1-\eta)\mu+\eta\nu.
\]
For an input ranking \(q\), define its Kemeny cost against a society \(\mu\) by
\[
D(q,\mu)=\sum_{p\in\mathcal R}\mu_p\,\tau(q,p),
\qquad
\operatorname{OPT}(\mu)=\min_{s\in\mathcal R}D(s,\mu).
\]
The input to the continuous problem is \(m\), rational \(\eta\), and the observed rational distribution \(\rho\), given by its \(\tau\) positive-mass rankings. The compatible honest societies are
\[
\mathcal H_\eta(\rho)=
\{\mu\in\Delta(\mathcal R):\exists\nu\in\Delta(\mathcal R),\
\rho=(1-\eta)\mu+\eta\nu\}.
\]
The question is to return a ranking \(q\) minimizing
\[
\sup_{\mu\in\mathcal H_\eta(\rho)}
\frac{D(q,\mu)}{\operatorname{OPT}(\mu)}.
\]
When \(\operatorname{OPT}(\mu)=0\), take the ratio to be \(1\) if \(D(q,\mu)=0\), and \(+\infty\) otherwise. Require \(q\) to preserve every pairwise order that is unanimous in any compatible honest society; the output must work for every hidden honest population that could have produced the reports. A solution is the ranking, its worst-case ratio, and a certificate of the worst compatible society.
My lead anchor is Theorem 4, proved in the paper. It states that there is a tournament graph from a preference profile for which Byzantine nodes can change the edge weights so that the median of the resulting profile is a \(k/(k-2)\)-approximation to the optimal median, where \(k=n/t\); when \(t\) is close to \(n/3\), this is a \(3\)-approximation. The proof constructs indistinguishable views: different honest profiles, with different preferred rankings, can yield the same view after Byzantine reports are added. In the mass model, those profiles become two compatible rational distributions for the same \(\rho\). Thus the mirror asks for the best worst-case factor over all such observed distributions and decompositions. The theorem’s obstruction transfers directly: for the corresponding rational fault fractions, no rule seeing only \(\rho\) can beat \(1/(1-2\eta)\) on every compatible honest society.
A second anchor is Theorem 6, also proved in the paper. For \(t<n/3\), Algorithm 2 terminates within \(t+3\) rounds, exchanges \(O(tn^2m\log m)\) messages, and produces a consensus ranking satisfying the approximation lower bounds from Section 5.2 and Pareto-Validity. Its continuous counterpart is the algorithmic question for the same input \((m,\eta,\rho)\): can one compute a Pareto-valid ranking attaining the optimal robust factor for every rational-mass instance, in time expressed in \(m,\tau\), and the mass bit length \(L\)? The paper’s finite results suggest the sharp factor \(1/(1-2\eta)\), but do not establish that a static rule based only on \(\rho\) achieves it for every continuous instance. Theorem 6’s round and message bounds also do not bound local computation: Algorithm 2 computes a Kemeny median, whose exact computation the paper describes as NP-hard in its related-work discussion.
For that exact optimization question, I expect hardness to transfer. At \(\eta=0\), the only compatible honest society is \(\mu=\rho\); an optimal output is exactly a Kemeny median. The paper cites prior NP-hardness results for that computation, though they are not numbered hardness theorems proved in this paper. Whether the same runtime hardness holds when \(\eta\) is fixed strictly above zero is a further question. Other useful questions are whether the sharp factor remains \(1/(1-2\eta)\) for all rational mass distributions, and whether a compact pricing or separation method can compute good rankings without enumerating \(m!\) types.
The authors should recognize this as their problem’s continuous form: the objective is the same Kemeny distance to the honest voters, and the adversarial fraction models their Byzantine corruption. The paper’s discrete profiles are rational-mass societies, so the finite constructions remain valid instances. This mirrors the approximation quality of Kemeny consensus in Theorems 4 and 6; it does not mirror the \(t+3\)-round distributed protocol itself, May’s or Arrow’s axiomatic results, or their other agreement guarantees.
My weakest point is exactly that boundary. The continuous model collapses reports by ranking type and loses node identities, communication histories, and the different local views that the distributed protocol handles. The authors might accept the robust Kemeny objective as their central Section 5 question while rejecting it as a mirror of the protocol contribution. That limits the scope of the case, but leaves a precise, population-continuous problem anchored in the paper’s strongest approximation results.
The strongest objection is to the proposed mirror of Theorem 6. That theorem is about a distributed protocol: nodes exchange messages over rounds, reach a common ranking, and tolerate Byzantine nodes that may send different messages to different recipients. A computation on a single pooled distribution \(\rho\) has none of those requirements. To preserve the protocol’s contribution, a continuous model would need to retain node identities and local views; then it would no longer be a population model with a small set of repeated types. If it drops them, it becomes a batch robust-ranking problem. The theorem’s round and message bounds therefore do not transfer to the proposed computation.
That objection does not defeat the Theorem 4 anchor. Its indistinguishable-profile constructions survive normalization: the honest and Byzantine counts become rational masses, and the two executions give the same full distribution of reported rankings. In the binary construction, for example, the support has only two ranking types. Any rule seeing that same distribution must choose the same ranking in both cases, and one compatible honest society makes that choice incur the stated approximation loss. This is a direct continuous-population instance, not an argument based only on pairwise summaries. The ranking types retain everything Kemeny distance needs; the hidden honest society is exactly the uncertainty the robust objective represents.
A stronger version of the mirror would ask for the optimal worst-case Kemeny approximation over every honest population compatible with the observed distribution, with running time in \(m,\tau,L\). The paper’s construction supplies a lower-bound instance, not a solution to that broader problem. That gap makes the question larger than the theorem, but it does not make it a different or unworthy problem. Its possible hardness in \(m\) is also not a reason to dismiss it: locating such a boundary is part of the programme.
So the negative case is narrow. The proposed model should not be presented as a continuous version of Theorem 6’s distributed protocol. It is a batch robust Kemeny problem inspired by the approximation results in Section 5. But Theorem 4 gives it a compact, faithful population mirror, and I cannot honestly defend the universal claim that no worthwhile continuous mirror exists.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.