| paper | d4-conf-aaai-2018-0072 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Answer: \(\mathrm{NP}\text{-hard}\) · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a finite signal set \(S\), a finite rational family of possible common signal models with prior \(\pi\), a finite grid of payment parameters, and \(H\) atomless reporting cohorts, does there exist an adaptive payment policy and a Bayesian–Nash equilibrium whose expected dishonest strategic mass is at most a given rational threshold \(q\)? The mechanism observes each cohort’s exact report-mass histogram, but not the true model.
Each cohort has a distribution over types \((x,r)\), where \(x\) is the private signal and \(r\) records strategic or heuristic reporting; the common signal model is hidden from the mechanism. A policy chooses a payment parameter from past report-mass histograms, and the objective is to minimize total strategic dishonest mass across the \(H\) cohorts.
The finite hidden-model family, prior, payment grid, and equilibrium-selection rule are extra modeling choices that affect the resulting policy problem.
fatal: False
The mirror concerns the dishonesty-limit result in Theorem 3 and AdaPTS’s adaptive performance; it leaves the truthfulness impossibility and the paper’s other mechanism properties unaddressed.
The strongest positive case is a crowdsourced poll or community-sensing service with very many respondents, a small signal alphabet, and a shared signal model and payment scheme. A type is a respondent’s signal \(x\), together with whether they are strategic or report heuristically; the shared belief model and other incentives are common. Within each reporting cohort, \(\mu_{\theta,x,r}\) is the fraction of mass of type \((x,r)\), where \(\theta\) is the hidden common signal model. The mechanism chooses a peer-prediction payment parameter \(P\) for each cohort, observes the mass of each reported answer, and seeks to minimize the mass of strategic respondents who misreport. This is a plausible high-multiplicity setting: each cohort has at most \(2m\) relevant types, while its population is atomless. The paper’s probability distributions over states and signals are not themselves a continuous population; the mirror is the mass of respondents in each signal type.
The closest anchor is Theorem 3, proved in this paper. It states that, in the paper’s discrete setting, the dishonesty limit—the minimum expected number of dishonest reports over minimal, limited-knowledge mechanisms and their equilibria—is \(\Theta(\log n)\). The upper bound comes from AdaPTS, which uses a multi-armed bandit policy; the lower bound says that any such mechanism must incur \(\Omega(\log n)\) dishonest reports. This is the paper’s main quantitative result, but it is not a computational-complexity result: the paper does not prove that a problem is in P, NP-hard, or in another standard complexity class. Under the requested strict anchor rule, there are therefore no qualifying anchors. Theorem 3 is the best candidate for a positive mirror, not a theorem of the kind the prompt asks analysts to anchor on.
A precise candidate is Atomless Peer-Prediction Dishonesty. An instance gives a finite signal set \(S\), a finite rational family \(\mathcal B\) of admissible common-prior signal models with a rational prior \(\pi\), a finite grid \(\mathcal P\) of admissible PTS payment parameters, and a horizon of \(H\) cohorts. The actual model \(\theta\in\mathcal B\) is hidden from the mechanism. Each cohort has mass \(1/H\), with within-cohort type proportions \(\mu_{\theta,x,r}\). Before each cohort reports, a minimal mechanism chooses \(P\in\mathcal P\) based on earlier report-mass histograms; respondents receive the corresponding one-peer payment and report once. Assume no single allowed payment is truthful for every model in \(\mathcal B\), so the mechanism has genuinely limited knowledge.
Given a rational threshold \(q\), ask whether there is an adaptive payment policy and an associated Bayesian–Nash equilibrium whose expected strategic dishonest mass is at most \(q\). For a strategy \(\sigma_{\theta,t}\), the objective is
\[ D_H = \sum_{\theta\in\mathcal B}\pi_\theta \frac{1}{H} \sum_{t=1}^{H} \sum_{x\in S} \mu_{\theta,x,\mathrm{str}} \bigl(1-\sigma_{\theta,t}(x\mid x)\bigr). \]
A solution is the policy and equilibrium strategy profile witnessing the threshold. As in the paper’s dishonesty-limit definition, this uses an optimistic choice among equilibria. It counts strategic misreporting, not random mistakes made by heuristic reporters.
For a fixed finite payment grid, I would expect this mass version to be tractable, and potentially much easier than the paper’s finite-population problem. An atomless cohort supplies exact report frequencies. The mechanism could probe each payment arm once, compare the resulting disagreement rates, then use the best arm; if the truthful region is represented in the grid and the relevant equilibrium is selected, only the finitely many probe cohorts need incur dishonesty. That suggests dishonest mass on the order of \(|\mathcal P|/H\), rather than a \(\Theta(\log n)\) count bound. This is a conjecture about the mirror, not a consequence of Theorem 3. It also makes the mirror useful: it asks whether the paper’s lower bound comes from population size itself or from finite-sample uncertainty in the feedback.
The weakest point is exactly that change in feedback. Replacing \(k\) sampled reports with exact cohort masses removes sampling noise, which is central to the bandit argument behind Theorem 3. The authors might accept mass-minimizing partial truthfulness as their problem, but they could reasonably reject the atomless-feedback version as changing the source of the result. A further question is how the answer depends on the signal alphabet size \(m\), the number of payment arms, and the model family’s support size—and whether a worst-case-equilibrium version retains any nonzero dishonest-mass bound. This mirror covers only the partial-truthfulness and dishonest-report overhead results, not the paper’s broader peer-prediction setting.
The strongest objection is that the paper gives no named computational result to mirror. Theorem 3 proves a \(\Theta(\log n)\) bound on dishonest reports; Theorem 2 gives an equilibrium performance bound for AdaPTS; Theorem 1 is an impossibility result about truthful elicitation. The paper analyzes a mechanism and its equilibria, but states no complexity classification for a computational problem and gives no runtime result for AdaPTS. Under ChoCo’s stated criterion, Theorem 3—the proponent’s sole anchor—is a learning and game-theoretic bound, not a computational-complexity result.
The natural rescue is to ask for the optimal adaptive mechanism: given a finite family of possible belief models, payment options, and a horizon, can a policy keep dishonest mass below a threshold? That is a plausible new computational problem. But it needs choices the paper does not make: a finite encoding of the belief family, a payment grid or representation of the continuous payment space, a prior over hidden models, and a rule for selecting among equilibria. The paper’s dishonesty limit instead quantifies over limited-knowledge mechanisms and equilibria in a general belief setting. The proposed \(D_H\) problem is therefore a designed extension, rather than a computational version of a result the paper establishes.
There is also a tension in making its population continuous while preserving the mechanism’s defining feedback. The paper keeps the group size \(k\) fixed and grows \(n\) by adding sequential groups. Each group’s reports are a finite, noisy observation, and the mechanism adapts its next payment using the ordered history. Aggregating reports into type masses across groups loses that chronology; including each group, payment, or history in the type description leaves only \(k\) agents in each relevant cell. If each group instead becomes atomless, its report frequencies become exact. That removes the finite-sample uncertainty central to the bandit analysis behind the \(\Theta(\log n)\) bound.
One can preserve uncertainty by making the true belief model a hidden state and giving the mechanism exact mass feedback under each payment. That is the strongest version of the proposed mirror. It may yield a meaningful finite-horizon identification or control problem, but its complexity would be driven by the chosen hidden-model family, action space, and policy representation. Those ingredients supply the computational problem; the paper’s theorem does not. Normalizing the cumulative dishonest count to population mass also makes a fixed number of exploratory cohorts vanish as the horizon grows. Keeping an unnormalized sum avoids that vanishing, but leaves a sequential policy objective whose natural units are cohort-equivalents.
The universal negative is not airtight: crowdsourced polling is a credible high-multiplicity setting, and authors interested in AdaPTS might recognize the hidden-model control problem as worth studying. I would not use the paper’s subject matter or its high-multiplicity potential as an objection. The stronger conclusion is narrower: the paper itself supplies no computational result for ChoCo to continue, and the best continuous formulation requires substantial new modeling choices before it becomes a complexity question. That makes the case for spending programme effort on this paper weak, even though a related project could be worthwhile on its own.
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.