| paper | d4-conf-aaai-2021-1093 |
| 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. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given \(q\) ordered accuracy cohorts and rational report masses \(\mu_{j,b}\ge 0\), with \(\sum_{j=1}^q\sum_{b\in\{0,1\}}\mu_{j,b}=1\), choose \(y\in\{0,1\}\) minimizing \(D^\epsilon_\mu(y)=\sup_{1-\epsilon\ge p_1\ge\cdots\ge p_q\ge 1/2}\exp\!\left(\sum_{j=1}^q(\mu_{j,1-y}-\mu_{j,y})\log\frac{p_j}{1-p_j}\right)\).
Types are \((j,b)\): accuracy cohort \(j\) and report \(b\), with mass \(\mu_{j,b}\). The decision is \(y\in\{0,1\}\); minimize the per-capita worst-case likelihood ratio over ordered cohort accuracies \(p_1\ge\cdots\ge p_q\), computable by maximizing cumulative report-mass strength over cohort prefixes.
Under an exact i.i.d. infinite-population limit, each non-degenerate cohort’s report share reveals the truth, so this is a robust optimization over arbitrary mass profiles rather than a typical-data limit; that bounds its statistical interpretation.
fatal: False
Covers Theorem 1’s distortion-optimal rule; leaves the optimistic and pessimistic likelihood rules, scoring-rule results, other approaches, and experiments outside scope.
The strongest honest mirror is the paper’s distortion-optimal aggregator, in a regime with many forecasters but few accuracy cohorts. The paper contains no named hardness result to anchor a continuization; its numbered computational results are positive algorithms and characterizations. So the case rests on extending one of those algorithms to a society described by masses.
Lead: ranked-cohort distortion aggregation. Consider \(N\) forecasters divided into \(q\) ordered accuracy cohorts, with \(N\gg q\). For example, a forecasting service might have a large pool of people grouped into a small number of historical calibration bands. Members of a cohort share the same unknown accuracy parameter, are conditionally independent given the ground truth, and differ for this task only in whether they report \(0\) or \(1\). Cohort \(1\) is most accurate. This makes \(t=(j,b)\)—cohort \(j\), report \(b\)—a complete type for the aggregation problem. Its mass \(\mu_{j,b}\) is the fraction of the pool in that cohort reporting \(b\), with \(\sum_{j,b}\mu_{j,b}=1\). The input has at most \(2q\) positive-mass types.
The action is to predict \(y\in\{0,1\}\). The objective is the paper’s worst-case distortion, expressed per capita. For a feasible accuracy vector \(p\), define \(\mathcal L_\mu(y;p)=\exp\!\left(\sum_{j=1}^q[\mu_{j,y}\log p_j+\mu_{j,1-y}\log(1-p_j)]\right)\). Given any \(\epsilon\in(0,1/2)\), let \(D^\epsilon_\mu(y)=\sup_{1-\epsilon\ge p_1\ge\cdots\ge p_q\ge 1/2}\mathcal L_\mu(1-y;p)/\mathcal L_\mu(y;p)\). The problem is to return a prediction minimizing \(D^\epsilon_\mu(y)\). This is the normalized log-likelihood version of the paper’s ratio: if the masses have denominator \(N\), the finite-population likelihood ratio is its \(N\)th power, which has the same minimizer.
Anchor: Theorem 1, proved in this paper. For every \(\epsilon\in(0,1/2)\), \(n\in\mathbb N\), and judgment profile \(X\in\{0,1\}^n\), the paper’s distortion-optimal rule \(f_{\mathrm{dist}}\) satisfies \(f_{\mathrm{dist}}(X)=\arg\min_{y\in\{0,1\}}\operatorname{dist}_\epsilon(y;X)=\arg\max_{y\in\{0,1\}}s_X(y)\), where \(s_X(y)\) is the greatest excess of \(y\)-reports over \(1-y\)-reports in any prefix of the accuracy-ranked judgments. The theorem also states that the rule can be computed in linear time. This is proved here, using Lemma 1; it is not just a cited result.
The cohort version has the corresponding cumulative-mass strength \(s_\mu(y)=\max_{0\le k\le q}\sum_{j=1}^k(\mu_{j,y}-\mu_{j,1-y})\). The proposed continuous problem is to compute a minimizer of \(D^\epsilon_\mu\), and the expected answer is any \(y\in\arg\max_y s_\mu(y)\). The proof’s prefix argument carries over with counts replaced by masses: the worst likelihood ratio is attained by an accuracy profile that jumps between a high and a low value at a cohort boundary. Thus the rule can be evaluated in \(O(q)\) arithmetic operations, with rational input masses. This is a Class A mirror: a finite-prefix algorithm becomes a mass-based algorithm whose work depends on the number of cohorts, not the number of forecasters.
The high-multiplicity interpretation is plausible when the cohorts are genuine shared-accuracy bands, rather than a convenient way of compressing distinct individual ranks. The paper itself notes partial orders of experts by accuracy as a natural extension, which gives this grouped regime a foothold in the authors’ model. The continuous object is the forecaster population; probability remains part of the experts’ judgment model. This case covers the distortion-optimal aggregation result, not the paper’s optimistic and pessimistic likelihood rules, its scoring-rule results, or its experiments.
The weakest point is that the paper’s main input is a totally ordered bit string, while this mirror groups experts into tied accuracy cohorts and keeps only the report mass in each. If individual rank within a cohort carries information, this compression loses it; and if the application has many distinct reliability levels, then \(q\) may be as large as \(N\). I would therefore present this as a credible, bounded high-multiplicity version of the authors’ aggregation problem, not as a mirror of every instance they study.
The distortion-optimal rule is the strongest anchor, and the strongest case against it is narrower than a claim that its mass version is ill-posed.
The paper has a named computational result: Theorem 1 characterizes the distortion-optimal rule and gives a linear-time algorithm. So the “no computational result to mirror” ground does not apply. The objection is that the proponent’s \(q\)-cohort model only preserves the paper’s input when cohort members really are interchangeable for this problem. If experts have distinct accuracy ranks—as they may when ranked by poll recency, sample size, or a leaderboard—compressing them into broad bands discards information the paper explicitly uses. In that regime, \(q\) may grow with the population, and the proposed high-multiplicity gain disappears.
A stronger mirror could preserve every rank, representing reports as a measure over rank and bit. But then the paper’s prefix strength becomes a supremum over rank cutoffs. That is a sensible continuous formula, though it still needs a compact input representation to be a computational problem. With finite step-function input, it reduces to the same scan over mass changes; with a genuinely continuous rank distribution, its tractability depends on how that distribution is supplied. This makes the continuous model less compelling as a new algorithmic question, but it does not make it invalid.
There is also a semantic problem if “continuum” means taking the paper’s independent random judgments to an exact infinite-population limit. Within a cohort of shared accuracy \(p_j\ge 1/2\), the limiting share reporting the truth is \(p_j\). Unless every cohort has \(p_j=1/2\), the limiting report masses reveal the truth directly. The interesting finite-sample uncertainty then vanishes. But this objection does not defeat the proponent’s version: their \(\mu\) can be an arbitrary observed profile of report masses, including profiles that are atypical under the stochastic model. That is a legitimate high-multiplicity relaxation, even if it no longer describes the typical exact limit of independent judgments.
Indeed, for such arbitrary cohort masses, the proposed extension appears to work: normalizing the log-likelihood ratio gives a mass-weighted sum, and the paper’s prefix argument carries over. Thus the honest negative case is weak. The mirror may be a modest extension of an already simple algorithm, and its relevance depends on whether real settings have genuinely shared accuracy cohorts. But neither that modesty nor a different answer is enough to show that no worthwhile mirror exists. A convincing scenario with many experts in a few true accuracy classes would survive the objection.
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.