| paper | d4-conf-wine-2024-0025 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in \(m,\tau,L\) by deterministic Ranked Pairs with exact rational weights. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 4.1
statement extracted from the paper’s text layer
Given a finite transaction set \(X\) and a finite-support rational distribution over pairs of true and reported strict orders, with at most mass \(\varepsilon\) on pairs that disagree, compute an ordering \(\pi\) using the reported-order marginal. Require that for every \(\gamma \in (1/2,1]\), if true-order mass at least \(\gamma\) ranks \(x\) before \(y\) but \(\pi\) reverses them, then \(\pi\) contains a reverse path from \(y\) to \(x\) whose every step has true-order mass at least \(\gamma-2\varepsilon\).
Types are complete pairs of true and reported rankings on \(X\), carrying rational mass. The algorithm aggregates reported pairwise masses, processes directed edges by decreasing weight, accepts an edge unless it creates a cycle, and outputs a topological order; the guarantee is measured against the true rankings.
The paper already computes from empirical order frequencies, so this mirror compresses its aggregation input without creating a new fairness question.
fatal: False
Covers Theorem 4.1's static Ranked Pairs fairness guarantee over a finite transaction set; leaves the streaming protocol, asymptotic liveness, and delay bounds uncovered.
The paper has no named theorem classifying a problem as polynomial-time, NP-hard, or otherwise by computational complexity. Its closest algorithmic anchor is Theorem 4.1, proved in this paper: given a vote from every replica over a finite transaction set, Ranked Pairs simultaneously satisfies \((\gamma,f/n)\)-minimal-batch-order-fairness for every \(\gamma\), without requiring a fixed bound on the number \(f\) of faulty replicas. I use it as an algorithmic anchor, while being explicit that it is not itself a named \(P\)-membership result.
A plausible regime is a large replicated service whose validators receive transactions through a modest number of shared network routes or configurations. Replicas in the same cohort observe the same order over a finite transaction window. A type is that complete observed order; its mass is the fraction of replicas of that type. The number of replicas can be much larger than the number \(\tau\) of distinct orders. This continuizes the replica population while keeping the output—a total ordering of transactions—discrete. The paper’s discussion of infinite-voter work is a nearby analytical tradition, not evidence that this computational mirror is already studied.
Call the mirror Mass-Weighted Ranked Pairs Fair Ordering. An instance gives a finite transaction set \(X\), a finite support of strict orders on \(X\) with binary-rational reported masses summing to one, and a rational fault-mass bound \(\varepsilon\). Assume the reports agree with the replicas’ actual observed orders except on at most \(\varepsilon\) of the population. The task is to output a total order \(\pi\) of \(X\) such that, simultaneously for every \(\gamma\in(1/2,1]\), if at least mass \(\gamma\) actually observed \(x\prec y\) but \(\pi\) places \(y\prec x\), then there is a path \(y=x_0,\ldots,x_k=x\) whose every step \(x_i\prec x_{i+1}\) was actually observed by at least mass \(\gamma-2\varepsilon\), and whose steps all appear in that direction in \(\pi\). The solution is an ordering, not an optimization: compute pairwise reported masses, process the directed edges by decreasing weight, accept each edge unless it creates a cycle, and topologically sort the accepted edges, with a fixed tie-break rule.
Theorem 4.1 is the anchor for this question: its fairness guarantee is the property being mirrored, and it is proved here. The finite-support version is tractable: the pairwise masses take \(O(\tau |X|^2)\) weighted contributions, and the Ranked Pairs computation uses polynomially many graph operations; the rational arithmetic has polynomial bit length. The authors should recognize this as the continuous-population form of their finite-input aggregation problem. It covers that static ordering result, not the paper’s streaming protocol or its liveness guarantees.
The weakest point is that the paper’s distinctive challenge is streaming over countably many transactions, while this mirror fixes a finite transaction window. A natural next question is whether a finite-support population of order types admits an append-only weighted streaming algorithm with asymptotic liveness—and a delay bound polynomial in \(\tau\)—while retaining the same fairness guarantee. Theorem 6.9’s finite-replica delay bound is not enough to answer that: its proof uses edge-weight granularity \(1/n\), and that argument does not automatically become a bound in the number of types.
Theorem 4.1 is a real algorithmic result, so I would not dismiss it as merely axiomatic. But its proposed mirror appears to collide with the paper’s own model. For a finite transaction set \(X\), let \(\mu\) be a distribution over strict orders, and define
\[
w(x,y)=\sum_t \mu_t\,\mathbf{1}[x\prec_t y].
\]
These are exactly the edge weights in the paper’s Ordering Graph. Ranked Pairs uses those weights to produce its output, and Theorem 4.1 states its fairness guarantee in terms of fractions of replicas. Every binary-rational \(\mu\) can be represented by finitely many replicas with a common denominator; conversely, every finite replica profile gives such a \(\mu\). If faults matter, types can record both an observed order and a reported order. The mapping preserves the graph, output, and fairness guarantee exactly.
So the proposed Mass-Weighted Ranked Pairs problem does not expose a new continuous question: it rewrites the paper’s aggregation input as a histogram. This is not an objection that the answer stays the same. The stronger point is that the paper already computes from the population’s normalized order frequencies. Its theorem and algorithm operate on precisely the statistic the continuous formulation would supply.
The continuous-programme criterion about named complexity results also weighs against this anchor, with a qualification. The paper has named algorithmic guarantees, including Theorem 4.1, but no theorem classifies a computational problem by complexity. Turning Theorem 4.1 into “compute the order that Ranked Pairs produces” gives an input-output task, but it simply restates the rule the paper already defines and analyzes.
The proponent’s better follow-up is a support-parameterized streaming bound. The paper’s streaming results already cover the underlying mass behavior: on each finite prefix, rational type masses give the same weighted graph as a finite replica profile, and the paper proves liveness and delay bounds for that graph. Its rounding result already trades weaker fairness for shorter delay. A bound expressed in support size \(\tau\) and bit length \(L\), rather than replica count or denominator, would be a genuine additional result. But that asks for a sharper parameterization of the paper’s existing streaming protocol; it does not reveal a population-continuity gap in the static fairness result. For full infinite orders, a finite-support stream also assumes that many replicas share one of only finitely many complete order trajectories, a restrictive regime for a system where arrival times and network conditions shape each replica’s observations.
This is the strongest negative case I can make, and it has a clear weak point: support-parameterized streaming liveness could be worth studying in its own right. I would still reject the specific static anchor as a worthwhile mirror, because the paper already expresses and analyzes that aggregation through population fractions. The case against a separate streaming mirror is less secure.
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.