| paper | Mechanisms for Making Crowds Truthful |
| authors | R. Jurca, B. Faltings |
| venue | JAIR 2009 |
| filed under | frontier · opinion-networks |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Feasibility and budget decision are in \(\mathrm{P}\): every admissible instance is infeasible. Minimum-budget computation reports infeasibility. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Proposition 4.8
statement extracted from the paper’s text layer
Given finite \(\Theta\), rational prior \(\pi\), rational signal probabilities \(p_\theta=\Pr[1\mid\theta]\), controlled mass \(\kappa\in[0,1]\), margin \(\Lambda>0\), and a rational breakpoint grid \(G\subseteq[0,1]\), choose nonnegative continuous piecewise-linear payment functions \(\tau_0,\tau_1\) with breakpoints \(G\) to minimize \(B=\sum_\theta\pi_\theta((1-p_\theta)\tau_0(p_\theta)+p_\theta\tau_1(p_\theta))\), subject to honest Bayesian incentive inequalities and \(W_\theta(\kappa p_\theta)\ge W_\theta(r)+\Lambda\) for every \(\theta\) and \(r\in[0,\kappa]\setminus\{\kappa p_\theta\}\), where \(W_\theta(r)=r\tau_1((1-\kappa)p_\theta+r)+(\kappa-r)\tau_0((1-\kappa)p_\theta+r)\); decide feasibility and compute the optimum.
A high-multiplicity peer-prediction and sybil-contract model with types \(t=(\chi,o)\), conditional masses determined by \(\kappa\) and \(p_\theta\), report-mass decision \(r\), anonymous payment functions \(\tau_o(q)\), and minimum truthful expected payment as the objective.
In the atomless limit, \(\mu_\theta(1)=p_\theta\) exactly, so distinct \(p_\theta\) reveal \(\theta\) and turn the proper-scoring argument into a public-state mass contract; the proponent acknowledges this but does not establish that the authors would accept the altered information structure.
fatal: False
The mirror covers the aggregate sybil mechanism of Proposition 4.8 and its mass-based payment optimization. It leaves the finite symmetric and asymmetric equilibrium results, mixed strategies, \(n\)-ary feedback, and the general \(N\)-dependent MILP formulations untouched; Proposition 4.7 is not preserved as an individual-dominant-strategy mirror.
There is a real, though formally borderline, positive case. The strongest mirror is the paper’s sybil-attack result, Proposition 4.8, proved in this paper. I would use Proposition 4.7 as a second, negative boundary anchor. The important caveat is that the paper contains no numbered NP-hardness, P, or parameterized-complexity theorem. Thus, under a strictly literal computational-anchor gate, this paper may fail eligibility. Under the prompt’s allowance for named constructive results, however, the following is a credible continuous-population programme.
The population is a unit mass of reporters. A complete type is \(t=(\chi,o)\), where \(\chi\in\{\mathrm{honest},\mathrm{sybil}\}\) records whether the identity is controlled by the strategic coalition and \(o\in\{0,1\}\) is the private signal observed by that reporter. The common product state \(\theta\in\Theta\) remains a latent environment state, not a population type. If \(p_\theta=\Pr[1\mid\theta]\), and a strategic entity controls mass \(\kappa\), then conditional on \(\theta\) the four type masses are \((1-\kappa)p_\theta\), \((1-\kappa)(1-p_\theta)\), \(\kappa p_\theta\), and \(\kappa(1-p_\theta)\).
The mechanism chooses nonnegative payment functions \(\tau_0,\tau_1:[0,1]\to\mathbb{R}_{+}\). A report \(a\in\{0,1\}\) receives \(\tau_a(q)\), where \(q\) is the total mass of positive reports in the reference population. Since every individual has zero mass, an individual’s own report does not change \(q\). A coalition can transfer mass between report types: if \(r\in[0,\kappa]\) is the mass of sybil identities reporting \(1\), then \(r\) is the continuous analogue of the paper’s integer \(r\).
My lead problem is Continuous Mass-Sybil Reward Design. Its input is \(\Theta\), the prior \(\pi\), the signal probabilities \(p_\theta\), the controlled mass \(\kappa\), and a truthfulness margin \(\Lambda>0\). The output is a pair of payment functions \(\tau_0,\tau_1\) minimizing the expected truthful payment \(B(\tau)=\sum_{\theta}\pi_\theta\bigl((1-p_\theta)\tau_0(p_\theta)+p_\theta\tau_1(p_\theta)\bigr)\), subject to honest individual incentive constraints and coalition truthfulness.
If the honest mass reports truthfully, its positive mass is \(h_\theta=(1-\kappa)p_\theta\). If the strategic coalition reports positive mass \(r\), its total revenue in state \(\theta\) is \(W_\theta(r)=r\tau_1(h_\theta+r)+(\kappa-r)\tau_0(h_\theta+r)\). The continuous truthfulness requirement is \(W_\theta(\kappa p_\theta)\ge W_\theta(r)+\Lambda\) for every \(\theta\) and every \(r\in[0,\kappa]\) with \(r\neq\kappa p_\theta\). Thus the problem asks whether a mass coalition is best off reporting the mass of positive signals it actually observed, exactly the aggregate objective in the paper’s sybil model.
Proposition 4.8 states, in full, that for a finite report group of size \(N\), when one strategic agent controls \(N-1\) reports, the mechanism designer can choose payments that make honest aggregate reporting optimal. Given the type set \(\Theta\), prior probabilities \(\Pr[\theta]\), conditional signal probabilities \(\Pr[1\mid\theta]\), and \(N\), the proposition defines payments from a proper scoring rule \(SR(i,j)\): it specifies \(\tau(0,0)=SR(0,0)/N_{\mathrm{col}}\), \(\tau(0,1)=SR(1,0)/N_{\mathrm{col}}\), the endpoint payment printed as \(\tau(1,N)=SR(1,N-1)/N_{\mathrm{col}}\), and, for \(x=1,\ldots,N-1\), \(\tau(0,x+1)=((x+1)SR(1,x)-xSR(0,x+1))/N_{\mathrm{col}}\) and \(\tau(1,x)=((N-1-x)SR(0,x+1)-(N-2-x)SR(1,x))/N_{\mathrm{col}}\). The printed \(\tau(1,N)\) appears to contain an indexing typo, since a report has only \(N-1\) reference reports. The proof shows that the coalition’s expected revenue from reporting \(r\) positive reports equals a proper-scoring-rule payoff and is therefore strictly maximized at the true number \(c\) of positive signals; scaling the score gives margin \(\Lambda\). This proposition is proved here.
The continuous problem is the same construction with counts replaced by masses: the coalition observes positive-signal mass \(c\), chooses report mass \(r\), and the mechanism must make \(r=c\) optimal. A natural restricted version replaces the finite proper score by a strictly proper continuous score \(S(u,v)\) on \(u,v\in[0,1]\), for example a shifted negative square loss, and asks whether it can be decomposed into anonymous per-report payments \(\tau_0(q),\tau_1(q)\). The unrestricted version is a semi-infinite linear programme, because the constraints range over \(r\in[0,\kappa]\).
I expect the scoring-rule-restricted problem to be Class A: it has a one-dimensional mass deviation, a finite latent-type description, and an explicit proper-scoring construction suggested directly by Proposition 4.8. The unrestricted payment-design problem is a worthwhile open pricing/separation problem rather than something the paper already solves. It may still be tractable under a finite piecewise-linear representation of \(\tau\), but that would be a new result.
The second anchor is Proposition 4.7, also proved here. It states that when more than half of the \(N\) reports are controlled by colluders, \(N_{\mathrm{col}}>N/2\), no incentive-compatible payment mechanism can make truth-telling a dominant strategy for the colluders. The proof considers the constraints for every possible number of positive reports supplied by the other colluders, constructs a dual solution with arbitrarily large objective value, and concludes that the corresponding primal payment-design problem is infeasible. The paper also says the bound is tight in its numerical examples.
Its continuous mirror is Continuous Mass-Dominant Truthfulness. Given controlled mass \(\kappa\), the problem asks whether there exist payment functions making each strategic reporter prefer truth-telling for every possible positive-report mass \(z\) supplied by the other strategic identities. If \(h_\theta=(1-\kappa)p_\theta\), the dominant-strategy constraints take the form \(D_1(z)\ge\Lambda\) and \(D_0(z)\ge\Lambda\) for every \(z\in[0,\kappa]\), where \(D_1(z)=\sum_\theta\Pr[\theta\mid1]\bigl(\tau_1(h_\theta+z)-\tau_0(h_\theta+z)\bigr)\), with the analogous reversed expression for \(D_0(z)\). The question is to decide feasibility and, when feasible, minimize the truthful budget.
For \(\kappa>1/2\), I expect the paper’s impossibility to transfer: the colluding mass can overwhelm the honest mass and reproduce the dual contradiction continuously. For \(\kappa\le1/2\), the problem becomes a natural continuous analogue of the paper’s LP 4.2, asking for the exact budget and the precise conditions under which dominant truthfulness is possible. Algorithmically this is likely Class A as a one-dimensional semi-infinite feasibility problem, although its substantive boundary is an impossibility transfer rather than a hardness result.
This mirror is plausible because Section 4.5 is explicitly about one strategic entity controlling many online identities and maximizing their aggregate revenue. Replacing \(N-1\) named identities by a mass \(\kappa\), and replacing the integer report count by report mass \(r\), preserves the paper’s strategic question. It also preserves the paper’s distinction between individual truthfulness and aggregate truthfulness: a sybil operator need not make every identity honest, but the aggregate report must reflect the aggregate experience.
The scope is deliberately narrow. It covers the sybil and dominant-truthfulness results of Propositions 4.8 and 4.7, not every collusion scenario, mixed equilibria, nonbinary feedback, or the paper’s general automated-mechanism-design discussion. It continuizes the reporter population, not the outcome space or the prior itself.
The weakest point is serious. In an atomless population observing the same product, the aggregate signal fraction may reveal \(\theta\) exactly whenever the \(p_\theta\) are distinct. That can collapse the Bayesian peer-prediction difficulty that motivates the finite paper. Also, the paper does not prove a named complexity classification; its propositions are constructive and impossibility results. So this is not a strong Class A/B complexity anchor in the same sense as a paper proving NP-hardness or polynomial-time solvability. The positive case survives only if the authors accept the high-multiplicity sybil model—with mass-controlled identities and aggregate-report decisions—as their problem, and regard the resulting semi-infinite payment-design question as the computational object worth studying.
The paper is a poor fit for the programme before one even reaches the modelling question. It contains no numbered theorem, lemma, or corollary giving a worst-case complexity classification or an exact, approximation, or parameterized algorithm. Its “efficiently” claims concern finite linear programs, while Proposition 4.8 is a closed-form existence construction and Proposition 4.7 is a finite impossibility result. Thus neither is a computational-complexity anchor in the programme’s strict sense.
Even granting the broader reading proposed by the other analyst, the population axis does not survive in a useful way. The paper’s \(N\) is the size of one finite reference batch, not the size of a society whose aggregate composition is the object of study. There are only two coherent continuizations.
One can retain finite reference batches and have a continuum of such batches. Then the population mass merely duplicates independent copies of the original game. The payment mechanism still acts on \(N-1\) individual reference reports, and the continuous population is not used in the computational problem.
Alternatively, one can replace a batch by an atomless population and let payments depend on aggregate report mass. That changes the information structure fundamentally. Conditional on \(\theta\), the population has, almost surely, exact signal masses
\[ \mu_\theta(1)=p_\theta,\qquad \mu_\theta(0)=1-p_\theta. \]
The binomial uncertainty that drives the paper’s payment constraints disappears. If the \(p_\theta\) are distinct, an aggregate honest report reveals \(\theta\) exactly. The mechanism is no longer eliciting a private report by comparing it with a noisy finite reference sample; it is contracting on an essentially public statistic. That may be a new mechanism-design problem, but it is not a continuous-population mirror of the paper’s results.
This defeats Proposition 4.8 in particular. Its proof depends on one strategic owner controlling \(N-1\) identities while the remaining honest report supplies a finite random outcome. The proper-scoring-rule identity works because the coalition’s payoff remains an expectation over that held-out report. In the proposed continuum, the coalition observes a mass
\[ c=\kappa p_\theta \]
almost surely. With distinct \(p_\theta\), it learns the state and the target aggregate report exactly. The proposed \(W_\theta(r)\) is therefore not the continuum version of the paper’s peer-prediction payoff; it is a deterministic contract over a scalar action \(r\).
That scalar contract can certainly be studied, but it has two bad alternatives. If arbitrary functions \(\tau_0,\tau_1:[0,1]\to\mathbb{R}_+\) are allowed, the problem is not finitely encoded, so there is no computational problem until one specifies a representation, such as piecewise-linear functions with rational breakpoints or an oracle model. If one restricts to a natural finite-dimensional scoring family, the result is essentially supplied by the proper-scoring construction already: a one-dimensional aggregate-report contract with finitely many latent states. The population continuum contributes no new complexity landscape.
The obvious repair is to retain a random finite reference sample from the continuum. But then the relevant object is again the finite sample size and its report-count distribution. The continuum is merely a reservoir from which the original finite game samples agents. Conversely, adding heterogeneous signals or persistent individual uncertainty to prevent the law-of-large-numbers collapse changes the information model beyond the paper’s finite-\(\Theta\), conditionally independent binary-signal setting.
Proposition 4.7 is even less suitable. It concerns separate colluders with non-transferable utilities and asks whether truthful reporting is a dominant strategy for each individual against every possible report configuration of the other colluders. Proposition 4.8 concerns one strategic entity with transferable utility maximizing the coalition’s total revenue. The proposed mass model merges these two cases: its \(W_\theta(r)\) is explicitly a coalition-level, transferable-utility objective, while its “dominant truthfulness” constraints are borrowed from the individual, non-transferable setting. A single mass parameter \(\kappa\) cannot preserve both strategic interpretations.
For an atomless population, an individual deviation has zero mass and does not change the aggregate report. One may still correlate payments with the eventual aggregate statistic through the common state, but that is a public-signal contract, not the finite pivotal-report structure used in Proposition 4.7. If instead one gives deviations positive mass so that the finite dominance argument remains meaningful, one has reintroduced finite blocks or atoms; if one lets block size tend to zero, the original individual-deviation notion degenerates. If one lets the whole coalition choose \(r\), the question becomes the aggregate-report problem of Proposition 4.8 rather than the dominant-strategy result of Proposition 4.7.
The finite “more than half” threshold is therefore not a canonical continuum boundary. It depends on the finite combinatorics of how many reports can offset how many honest reports, together with the distinction between individual and transferable coalition utility. A continuum version requires choosing a new deviation model, and different choices produce different problems.
The negative case is not a mathematical proof that no platform could ever study aggregate reporting by a large crowd. Such a model could be sensible and perhaps useful. But it would be a new contract-design problem, not a worthwhile continuous mirror of this paper for ChoCo. The paper has no genuine computational-complexity anchor, and its two strongest constructive/impossibility results either collapse under atomless aggregation or survive only by retaining the finite interaction that the proposed continuization was supposed to replace.
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.