| paper | d4-conf-ijcai-2020-0672 |
| 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: polynomial-time solvable · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given finite support \(T\) with rational masses \(\mu_t>0\), summing to one, binary observations \(x_t\), rational refund coefficient \(c\), and rational posteriors \(p_t(z)\) for a random peer's observation \(z\in\{0,1\}\), assume both report values have positive mass. Define \(R_\mu(y)=\sum_{t:x_t=y}\mu_t\), \(q_\mu=R_\mu(0)\), and \(\rho_t(y)=\sum_{z\in\{0,1\}}p_t(z)\left(\frac{\mathbf{1}[y=z]}{R_\mu(y)}-1\right)\). For each type \(t\), let \(D_t(\alpha)=\alpha(\rho_t(x_t)-\rho_t(1-x_t))+c q_\mu(\mathbf{1}[x_t=0]-\mathbf{1}[1-x_t=0])\). Compute \(\alpha^*=\inf\{\alpha\ge 0:D_t(\alpha)>0\text{ for every }t\in T\}\), characterize the scales satisfying all strict inequalities, and return \(+\infty\) if none exist.
A nonatomic population of agents partitioned into finitely many complete types, each with a binary observation, posterior beliefs, and mass. Aggregate report masses determine PTSC rewards and the refund outcome; the decision variable is the common reward scale \(\alpha\), and the objective is to find its infimum subject to strict truthful-reporting incentives for every positive-mass type.
The threshold takes cohort beliefs and observations as given even though Infochain is designed to elicit those private quantities, so it is an offline incentive-analysis problem rather than a model of on-chain execution costs.
fatal: False
The mirror covers Theorem 1's truthfulness guarantee; it leaves aside the payment and savings bounds of Theorems 2 and 3, the bit-packing result, contract implementation, and gas experiments.
The strongest positive foothold is Theorem 1, which the paper proves. It says that in its binary-answer PTSC setting, with fully mixed priors and positive belief correlation \(\beta\), truthful reporting is a strict equilibrium despite the outside refund incentive when the reward scale satisfies
\[
\alpha > c\,\frac{1+(n-1)\gamma}{n\beta}.
\]
Here \(\beta=\min_i\left(\frac{P_i(x_p=1\mid x_i=1)}{P_i(x_p=1)}-\frac{P_i(x_p=0\mid x_i=1)}{P_i(x_p=0)}\right)\), and \(\gamma=\max_i P_i(x_p=0\mid x_i=1)\). The paper notes that the sufficient threshold tends to \(c\gamma/\beta\) as \(n\) grows. This is its most promising anchor because it already asks how incentives behave as the crowd grows.
A plausible regime is a large web service whose millions of users report whether response time met an SLA. Users fall into a relatively small number of cohorts with the same relevant observation and belief model and the same refund terms. A type records the cohort and the user’s binary observation, \(x\in\{0,1\}\); mass \(\mu_t\) is the fraction of users of each type. Each individual has zero mass, but the aggregate fractions determine the peer-report frequencies and the refund outcome. This makes the population itself continuous, rather than making service quality or payments divisible.
Here is one precise proposed mirror, the Continuum-PTSC Threshold problem. An instance gives a finite support \(T\), rational masses \(\mu_t>0\) summing to one, a common outside-incentive coefficient \(c\), and, for each type \(t\), its posterior probabilities \(p_t(z)\) that a randomly selected peer has observation \(z\in\{0,1\}\). Assume both report values have positive aggregate mass. Under truthful reporting, let \(R_\mu(y)\) be the mass reporting \(y\), and \(q_\mu=R_\mu(0)\). For a type with observation \(x\), define its PTSC reward per unit of \(\alpha\) from reporting \(y\) as
\[
\rho_t(y)=\sum_{z\in\{0,1\}}p_t(z)\left(\frac{\mathbf{1}[y=z]}{R_\mu(y)}-1\right).
\]
Its truthful-reporting advantage over lying is then
\[
\alpha\bigl(\rho_t(x)-\rho_t(1-x)\bigr)
+cq_\mu\bigl(\mathbf{1}[x=0]-\mathbf{1}[1-x=0]\bigr).
\]
The question is to compute the infimum \(\alpha^\star\ge 0\) for which every positive-mass type strictly prefers to report truthfully when all others do; report infeasibility if no such scale exists. Because the condition is strict, the infimum need not itself be an admissible scale. The output should give the threshold and characterize which scales satisfy the strict inequalities.
With positive truth-versus-lie PTSC slopes for all types, I expect this problem to be in Class A: compute aggregate report masses and typewise utility differences, then take the maximum of the rational thresholds. For explicit support, that takes polynomial time in \(\tau\) and the input bit length. It also raises natural follow-on questions about heterogeneous outside incentives, multiple task schedules, and robust thresholds when beliefs are given as intervals rather than exact probabilities. The paper’s sufficient bound suggests the large-population scale \(c\gamma/\beta\); the proposed problem asks for the tighter threshold from the full type data.
The scope is only Theorem 1’s truthfulness guarantee. I would not anchor a mirror in Proposition 1’s 42-answer packing result: bit packing and gas costs are implementation details tied to discrete words, not a population-complexity result. More broadly, the paper has no named computational-complexity result classifying a problem as polynomial-time solvable, hard, or parameterized-tractable. Theorem 1 is a formal incentive result, not a complexity theorem. So this is a credible continuous-population research question arising from the paper, but it does not meet the programme’s strongest anchor standard. Its weakest point is that the proposed threshold computation is a new computational framing of an analytic mechanism result; a referee could reasonably see it as outside ChoCo’s intended complexity landscape.
The only serious anchor is Theorem 1, and its result is about incentives: when truthful reporting is a strict equilibrium, given specified beliefs and outside incentives. The paper does not state a complexity result for computing an allocation, winner, or mechanism. Its Solidity optimizations and gas measurements are implementation results, not a complexity landscape over computational social choice problems.
The proposed mirror does capture a sensible population regime. Large groups of users reporting on the same service could fall into a small number of cohorts, and mass is a natural way to describe their shares. That is not a reason to object to it. The trouble is that the proposed computation takes the cohort masses and beliefs as input, though those are exactly the private, unverifiable facts Infochain is meant to elicit. If a requester already knows them, the threshold calculation is an offline model check, not a computation the oracle can run from its available data.
Even granting those inputs, with the proposed positive slopes the calculation reduces to typewise utility gaps of the form \(\Delta_t(\alpha)=a_t\alpha+b_t\). The strict truthfulness conditions give a threshold from the maximum of the resulting per-type bounds, with the endpoint handled according to the strict inequalities. That is a direct calculation over the listed types, not a pricing or optimization problem hidden in an exponential type space. Easiness alone would not disqualify a mirror; here it highlights that the computational question is being added to an incentive theorem, rather than extracted from a computational problem the paper studies.
A more faithful version could include each cohort’s observation, beliefs, question schedule, refund terms, and other relevant characteristics. That repairs the single-question simplification, but it does not change the basic issue: the mass model still needs private belief and observation data as input, while the on-chain costs still arise from individual commits, reveals, deposits, and peer selections. Replacing account counts with masses does not provide a way to execute or cost those transactions. One could instead pose a new optimization problem over peer assignments or reward schemes, but its computational core would come from the added design choices, not from continuizing a named result in this paper.
So the strongest negative case is about fit with ChoCo: the natural continuum here leads to a peer-prediction equilibrium analysis, not to the programme’s computational landscape. It is not an airtight claim that no useful continuum study exists. A model with publicly specified beliefs and a genuine optimization objective could be worthwhile, and the large-crowd regime is credible. But that would be a new mechanism-design project, not a compelling continuous mirror of this paper’s computational contributions.
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.