| paper | d4-conf-aaai-2015-0492 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: The score uniquely truthfully elicits every reachable type, and exact computation of the mass aggregate is polynomial-time solvable. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given a categorical outcome space with \(K\) outcomes, a common prior \(\alpha_0\), population scale \(H\), and rational masses \(\mu_t\) over reachable posterior report types \((p_t,b_t)\), can the two-sample score \(S(p,b,x_1,x_2)=\log p(x_1)+2b\mathbf{1}\{x_1=x_2\}-b^2\) elicit the reports and compute the aggregate predictive distribution \(q\) for the society?
Represent each type by its categorical sample-count vector \(z_t\in\mathbb{Z}_{\ge 0}^K\), with \(p_t=(\alpha_0+z_t)/\|\alpha_0+z_t\|_1\). Weight these sufficient statistics by their masses and compute \(q=(\alpha_0+H\sum_t\mu_tz_t)/\|\alpha_0+H\sum_t\mu_tz_t\|_1\); the fractional aggregate parameters are valid Dirichlet parameters.
The proposed input consists of report-type masses, so the mirror covers aggregation after elicitation rather than whether Theorem 4’s scoring mechanism elicits those reports.
fatal: False
The mirror covers Theorem 4’s categorical–Dirichlet aggregation result; it leaves the paper’s other distribution families, single-sample results, and broader mechanism-design contributions aside.
This paper has no named computational-complexity result: none of its numbered results classifies a problem as being in P, NP-hard, FPT, or similar. The closest useful anchor is Theorem 4, proved in this paper. It establishes that, for categorical observations with a Dirichlet prior, a principal who has two independent samples can use the score
\[
S(p,b,x_1,x_2)=\log p(x_1)+2b\,\mathbf{1}\{x_1=x_2\}-b^2
\]
to elicit each agent’s predictive distribution \(p\) and their probability \(b\) that the two samples agree, then optimally aggregate the agents’ information. That is a mechanism-achievability theorem, not a complexity result; under your strict anchor rule, it is not a qualifying anchor. It is nevertheless the paper’s strongest basis for a positive mirror.
A precise candidate is Continuous Categorical–Dirichlet Aggregation. An instance gives \(K\) outcomes, a common prior \(\alpha_0\in\mathbb{Q}_{>0}^K\), a population scale \(H>0\), and rational masses \(\mu_t\) on \(\tau\) report types \((p_t,b_t)\), with \(\sum_t\mu_t=1\). Each type must be reachable under the paper’s model: for some sample-count vector \(z_t\in\mathbb{Z}_{\ge0}^K\), its posterior parameter is \(\alpha_t=\alpha_0+z_t\), its report is \(p_t=\alpha_t/\|\alpha_t\|_1\), and \(b_t\) is its posterior probability that two independent outcomes agree. The task is to return the aggregate predictive distribution. For each type, recover
\[
n_t=\frac{1-b_t}{b_t-\|p_t\|_2^2},
\qquad
z_t=n_t p_t-\alpha_0,
\]
and output
\[
q=\frac{\alpha_0+H\sum_t\mu_t z_t}
{\left\|\alpha_0+H\sum_t\mu_t z_t\right\|_1}.
\]
There is no optimization objective here: a solution is the exact aggregate distribution. Fractional mass can produce fractional total sufficient statistics, a natural continuous extension because Dirichlet parameters may be positive reals.
The regime is a large forecasting or citizen-science crowd whose contributors share a common prior and observation protocol. For example, many people might each observe exactly \(r\) binary trials; their complete type for this aggregation problem is their head-count \(0,\ldots,r\), so the number of distinct types is at most \(r+1\), even as the crowd grows. Agents with the same count vector are interchangeable for the paper’s aggregation task. The mirror changes the society itself into a mass distribution; the fact that its output is a probability distribution is not the reason it is continuous.
This candidate should be tractable: the inversion and mass-weighted sum take polynomial time in \(K,\tau\), and the input bit length. It covers Theorem 4’s categorical–Dirichlet aggregation result, not the paper’s other distribution families or all its mechanism-design contributions. A natural follow-up is how aggregation changes when reports are approximate or the common-prior model is misspecified.
The weakness is substantial: Theorem 4 proves an incentive-compatible mechanism, not a computational-complexity claim, and the continuous aggregation formula follows from straightforward sufficient-statistic arithmetic. There is no discrete hardness anchor whose fate in the continuum can be studied. So this is a plausible population mirror of the paper’s central aggregation question, but a weak fit for the programme’s intended complexity landscape.
The paper has no named computational-complexity result to mirror. Theorem 4 is the closest anchor, and the proponent correctly concedes that it proves a mechanism-achievability result: a scoring rule elicits enough information for optimal Bayesian aggregation. It does not define or classify a computational problem. The other results characterize when aggregation is possible or give statistical identities; none supplies a complexity target.
The proponent’s population model is nevertheless coherent. A large forecasting crowd could have repeated, bounded observation-count types, and a distribution over those types could be a sensible continuous society. The aggregate formula
\[
q=\frac{\alpha_0+H\sum_t\mu_t z_t}
{\left\|\alpha_0+H\sum_t\mu_t z_t\right\|_1}
\]
is a reasonable mass version of pooling evidence. I see no sound objection based on type multiplicity, fractional mass, or the probabilistic output.
That model still does not give ChoCo a computational mirror of Theorem 4. It takes reachable report types as input and asks for the aggregate posterior. The theorem’s contribution is instead about whether a scoring mechanism can elicit sufficient information from agents. That incentive and identifiability question does not depend on the population’s type masses; the masses enter only when combining the information. A computational question about synthesizing mechanisms across families, or optimizing information acquisition costs, might be interesting, but it would need a new problem definition and would not mirror a computational result in this paper.
So the negative case is strong on programme fit, but weak as a universal claim that no worthwhile continuous mirror exists. The crowd model survives as a plausible continuous statistical question; what it lacks is the computational-social-choice complexity question this programme is meant to chart.
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.