| paper | d4-conf-sigecom-2006-0023 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
Answer: Deciding \(W_N\le B\) is \(\mathsf{NP}\)-complete. For every valid instance, \(W_{N+1}\le W_N\); equality and strict decrease both occur. · discrete side: other · adjudication: proved
full proof & adversarial review →
Proposition 1
statement extracted from the paper’s text layer
Given finite product states \(\Theta\), signals \(S=\{s_1,\ldots,s_M\}\), rational prior \(p_\theta\), likelihoods \(f(s_j\mid\theta)\), reporting-cost bound \(C\), lying-benefit bounds \(\Delta(j,h)\), and a fixed number \(N\) of reference reports, set \(\mu_j=\sum_{\theta}p_\theta f(s_j\mid\theta)\). For each histogram \(\mathbf a=(a_1,\ldots,a_M)\) with \(\sum_\ell a_\ell=N\), let \(q_N(\mathbf a\mid j)\) be the paper’s conditional probability of that reference-report histogram given signal \(s_j\). Choose nonnegative payments \(\tau(r,\mathbf a)\) minimizing \(\sum_j\mu_j\sum_{\mathbf a}q_N(\mathbf a\mid j)\tau(j,\mathbf a)\), subject to truthful-reporting payoff differences of at least \(\Delta(j,h)+\eta\) for every \(j\ne h\), and truthful expected payments of at least \(C+\eta\) for every \(j\), for a specified \(\eta>0\). Return the optimal payment table and per-capita budget, and compare that optimum across values of \(N\).
A unit-mass cohort of buyers is distributed across private signal types \(s_j\) with masses \(\mu_j\) induced by the paper’s prior and likelihood model. Each buyer remains an individual strategic agent, and payments depend on that buyer’s report and a finite sample of \(N\) reference reports; the decision variables are the payment table \(\tau\), and the objective is expected payment per unit of cohort mass.
The mass vector is restricted to prior-predictive signal frequencies, rather than arbitrary realized cohort compositions, so the mirror covers a narrower population regime; this bounds its reach without defeating the ex-ante per-capita question.
fatal: False
The mirror covers Proposition 1’s claim about how the minimum payment budget changes with the number of reference reports, using the paper’s payment optimization. It leaves the probabilistic filtering results and their experiments outside the mirror.
The paper has no numbered result that classifies a problem as being in P, NP-hard, or similar. Its best named computational-design result is Proposition 1, proved here: for the paper’s incentive-compatible reputation mechanism, the minimum expected budget is weakly nonincreasing as the number of reference reporters increases. The proposition proves a change in the optimum, not a complexity classification. The paper’s complexity discussion in Section 3.3 is unnumbered, so it cannot serve as the required named complexity anchor.
The strongest positive mirror I can build is *Continuous Minimum-Budget Peer-Prediction with \(N\) References*, anchored to Proposition 1. Picture a large review cohort for one stable product or service: many buyers, but only \(M\) possible quality signals. Buyers with the same signal also share the paper’s reporting cost and lying incentives, so a signal \(s_j\) identifies a complete type. Type \(s_j\) has mass \(\mu_j\), its fraction of the cohort. In this regime, the number of buyers \(n\) is much larger than the number of types, with support size at most \(M\).
An instance gives a finite set of product states \(\Theta\), a rational prior \(p_\theta\), rational signal likelihoods \(f(s_j\mid\theta)\), a reporting-cost bound \(C\), lying-benefit bounds \(\Delta(j,h)\), and \(N\). The prior-predictive type masses are \(\mu_j=\sum_\theta p_\theta f(s_j\mid\theta)\). An agent who observes \(s_j\) is paid according to their report and the histogram \(\mathbf a=(a_1,\ldots,a_M)\) of \(N\) reference reports, where \(\sum_\ell a_\ell=N\). The joint hidden product state induces the conditional histogram probability
\[
q_N(\mathbf a\mid j)
=
\sum_{\theta\in\Theta}
\Pr(\theta\mid s_j)
\frac{N!}{\prod_\ell a_\ell!}
\prod_\ell f(s_\ell\mid\theta)^{a_\ell}.
\]
The question is to choose nonnegative payments \(\tau(h,\mathbf a)\) minimizing the expected payment per unit of population mass, \(\sum_j\mu_j\sum_{\mathbf a}q_N(\mathbf a\mid j)\tau(j,\mathbf a)\), while making honest reporting worthwhile. For a specified strictness margin \(\eta>0\), impose, for every \(j\ne h\), \(\sum_{\mathbf a}q_N(\mathbf a\mid j)[\tau(j,\mathbf a)-\tau(h,\mathbf a)]\ge\Delta(j,h)+\eta\), and require \(\sum_{\mathbf a}q_N(\mathbf a\mid j)\tau(j,\mathbf a)\ge C+\eta\) for each \(j\). A solution is an optimal payment table and its minimum expected per-capita budget.
This is a credible mirror of the authors’ mechanism-design question: it changes the accounting from expected payment to one buyer to payment integrated over a unit-mass cohort, while keeping the same incentive constraints and payment decisions. Proposition 1 then says that, for fixed signal model and incentive bounds, the optimum budget for this continuous problem cannot increase when \(N\) increases. It is proved in the paper by a duality argument. This covers the minimum-budget mechanism and its multiple-reference extension; it does not cover the later probabilistic filtering results.
My expectation is Class A when \(N\) is fixed: the displayed problem is an explicit LP with \(M\binom{N+M-1}{M-1}\) payment variables, polynomial in \(M\) for fixed \(N\). With \(N\) and \(M\) both variable, the histogram formulation is not polynomial-sized in general, and Proposition 1 says nothing about solving that version efficiently. I would treat succinct optimization for variable \(N\), and the limiting budget as \(N\) grows, as further questions—not claim a general polynomial-time result from the paper.
The soft spot is substantial: the population-size parameter \(n\) never drives the paper’s computation. Its LP already optimizes expected per-buyer payments using a finite signal distribution, so this mirror largely aggregates an existing formulation rather than opening a new complexity landscape. There is also a modeling care point: the signals are correlated through a shared hidden product state. A literal public continuum of realized signal masses could reveal that state and change agents’ incentives. The proposed mirror therefore assumes agents do not observe the cohort’s full type distribution and that reference reports remain finite random samples. If the authors or a referee regard those conditions as merely restating their existing Bayesian model, this is a thin continuous mirror.
The anchor is Proposition 1, but it does not classify the complexity of a computational problem. It proves that the minimum budget weakly decreases as the number \(N\) of reference reports increases. The paper’s complexity discussion is instead an unnumbered analysis of the finite payment LP and experimental runtimes. That leaves no named complexity result here for the programme’s usual kind of mirror.
The stronger problem is that population size never enters this mechanism’s computation. For \(n\) otherwise identical buyers, expected total spend is \(nW\), while the incentive constraints and feasible payment schedules are unchanged. Dividing by population mass gives \(W\), the paper’s existing per-buyer objective. In the proposed mirror, \(\mu_j\) is the prior-predictive probability of signal \(s_j\), derived from \(p_\theta\) and \(f(s_j\mid\theta)\); it is not an independently specified realized population composition. The optimization still runs on the same inputs—\(\Theta,S,p,f,N,C,\Delta\)—and the same LP.
A stronger attempt would give the continuum its realized signal masses. Conditional on product state \(\theta\), those masses are \(f(s_j\mid\theta)\). If agents or the mechanism can observe the aggregate, it can reveal the shared state and change the information structure that supports peer prediction. If that aggregate is hidden to preserve the paper’s setting, payments still depend on finite random reference samples, and the population mass contributes no new computational object. Taking \(N\) to infinity would study reference aggregation, which continuizes the mechanism’s sampling rather than the population alone.
Large review cohorts are a credible high-multiplicity regime, so the negative case is not that the population model is implausible. Its weak point is that the obvious mirror is easy to write and recognizable, yet appears to normalize an objective the paper already optimizes rather than pose a distinct computational question. A programme that counts any such high-multiplicity reformulation as worthwhile could still accept it; the case against it is strongest as a reason not to treat this paper as a substantive complexity-landscape mirror.
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.