| paper | d4-conf-atal-2007-0013 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | unclear |
Propositions 5 and 6 give analytic bounds on worst-case fault robustness, but neither asserts an algorithm, a complexity result, or a guarantee for computing robustness. The proposed per-capita model is a coherent extension, but it asks for the winner after evolving an expected mass distribution, rather than the paper’s probability that the winner remains unchanged after a specified number of faults.
fails bit a — no named computational result to mirror
The proposed limit draws on Propositions 5 and 6, but neither is a computational result; the paper’s other named robustness results are also analytic.
The honest positive case is narrow. The paper has named formal results, but none is a computational-complexity anchor in the sense you require: no theorem, proposition, or corollary classifies a problem as polynomial-time solvable, NP-hard, or similar.
The closest results are Proposition 5 and Proposition 6, both proved in the paper. Proposition 5 says that for a scoring rule \(F\), if \(a_F\) is the number of strict drops in its scoring vector, then its one-fault robustness satisfies \(\rho^{n,m}_1(F)\ge (m-1-a_F)/(m-1)\). Proposition 6 says that when \(m\) divides \(n\), the worst-case one-fault robustness also satisfies \(\rho^{n,m}_1(F)\le (m-a_F)/m\). These are useful quantitative results, but they are probability bounds, not complexity classifications. They cannot be presented as qualifying anchors.
A plausible extension, motivated by those results, is Continuous Per-Capita Noise Robustness. A type is a complete ranking of the \(m\) candidates, with any differing fault-channel parameters included in the type. The instance gives a rational distribution \(\mu\) over \(\tau\) ranking types, a scoring vector \(\alpha\), an initial unique winner \(c^\star\), and a rational noise intensity \(\lambda\). Each fault applies the paper’s uniformly random adjacent transposition. For a finite election with \(k/n\to\lambda\), the empirical distribution of rankings after the faults converges to \(\mu_\lambda=\mu e^{\lambda(P-I)}\), where \(P\) is the one-transposition transition matrix on rankings. The decision question is whether \(c^\star\) remains the winner under \(\mu_\lambda\). A margin promise can exclude near-ties: either \(c^\star\) leads every rival by at least \(\delta\), or some rival leads \(c^\star\) by at least \(\delta\).
This has a credible high-multiplicity regime: for example, a large fleet of software agents using a modest set of preference templates, with many agents sharing each ranking and fault channel. Then \(n\) is much larger than \(\tau\), and \(\mu_t\) is the fraction of agents of type \(t\). The population is the continuous object; the paper’s noise process supplies the transition mechanism. Scaling the number of faults with \(n\) is the co-modification that makes the limit informative.
For scoring rules, this problem has a strong Class A case. Even though \(P\) ranges over rankings, a candidate’s expected score depends only on its rank. The candidate’s rank follows an \(m\)-state Markov chain under adjacent transpositions, so the scores after noise can be computed from an \(m\times m\) matrix exponential and summed over the \(\tau\) supported types. With the margin promise, precision-controlled computation should determine the winner in polynomial time in the encoded input and requested precision. In finite elections with strict limiting margins, concentration gives the bridge: the probability that the noisy election selects the continuous model’s winner tends to \(1\).
I would expect the authors to recognize this as a meaningful high-multiplicity limit of their noise model: it keeps rankings, adjacent faults, and winner selection, while asking what happens when faults occur at a fixed per-capita rate. Its scope is the scoring-rule robustness results around Propositions 5 and 6, interpreted asymptotically. It does not give a continuous counterpart to those propositions’ exact worst-case bounds.
That qualification is the weakest point. The proposed question studies a per-instance asymptotic winner, while the paper studies the worst-case probability of a winner change after exactly \(k\) faults. At vanishing score margins, the continuous winner may discard the fluctuations that drive the paper’s probability bounds. The proposal is therefore a defensible new computational question inspired by the paper, rather than a mirror of a named computational-complexity result.
Propositions 5 and 6 are the strongest anchors, but they bound a probability; they do not classify the complexity of a computational problem. Theorem 1 is likewise an existence result about outcome changes. So this paper supplies no named computational result whose complexity landscape a continuous mirror would chart. That is the main gap in the positive case.
The software agents with shared preference templates make a plausible high-multiplicity scenario, and the proposed per-capita noise limit is mathematically coherent. But its winner question is not the paper’s robustness question. The paper asks for the probability that the winner stays the same after exactly \(k\) random faults, minimized over finite profiles. The proposal evolves the type distribution by the *expected* noise channel, then asks who wins that deterministic distribution. In general, the winner of an expected profile does not determine the probability that the winner of a randomly perturbed profile is unchanged.
The mismatch is sharpest where the paper’s worst-case bounds matter: near ties. With a fixed number of faults, each fault moves mass \(1/n\), so its effect disappears in the population limit unless score gaps also shrink at that scale. Those gaps, and the resulting probability of changing the winner, are precisely the finite-scale information the continuous distribution loses. A tangent model could retain first-order perturbations, but it would have to restore that vanishing scale.
Scaling faults with population size avoids that degeneration, but then the limiting winner is deterministic whenever the noisy scores have a strict margin. The proponent’s margin promise excludes the boundary where nontrivial winner-change probabilities survive. Keeping those probabilities would require extra fluctuation information, such as a finite-size or central-limit model; that may be a worthwhile new question, but it is no longer a direct mirror of Propositions 5 and 6. The proposed \(m\)-state score calculation reinforces the distinction: it computes expected scores under the noise channel, not the paper’s worst-case robustness probability.
So the negative case is strongest against this proposed anchor, not as a proof that no useful continuous question can be invented. The proposed limit is sensible, but the paper offers analytic robustness bounds rather than a computational result to mirror, and the natural population limit either loses the fixed-fault effect or changes the quantity being studied. A broader claim that no scenario could produce a worthwhile mirror remains hard to establish.
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.