Mechanisms for Making Crowds Truthful (d4-journals-jair-2009-0011)

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 society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. Normalize total mass to \(1\).
Here \(\Theta\) indexes a common latent quality state with prior masses \(\pi_\theta>0\), \(\sum_\theta\pi_\theta=1\); conditional on state \(\theta\), the signal-\(1\) fraction is \(p_\theta\). Assume \(\tau=|\Theta|\ge2\) and pairwise distinct rational \(p_\theta\in(0,1)\).
Input also includes rational controlled mass \(0<\kappa<1\), rational margin \(\Lambda>0\), and a finite rational grid \(G\subseteq[0,1]\) containing \(0,1\); write \(m=|G|\) and let \(L\) be the total input bit length.
Choose finite-valued nonnegative continuous functions \(\tau_0,\tau_1:[0,1]\to\mathbb R_{\ge0}\), affine between consecutive grid points; \(\tau_i(q)\) pays report \(i\) when the aggregate positive-report fraction is \(q\).
For \(i\in\{0,1\}\), set \(a_{\theta,1}=p_\theta\), \(a_{\theta,0}=1-p_\theta\), and \(q_i=\sum_\theta\pi_\theta a_{\theta,i}\). Honest Bayesian incentives require \(\sum_\theta(\pi_\theta a_{\theta,i}/q_i)(\tau_i(p_\theta)-\tau_{1-i}(p_\theta))\ge\Lambda\) for both signals.
One controller pools the signals of mass \(\kappa\), can transfer utility, and chooses any positive-report mass \(r\in[0,\kappa]\); the remaining mass reports honestly. Define \(W_\theta(r)=r\tau_1((1-\kappa)p_\theta+r)+(\kappa-r)\tau_0((1-\kappa)p_\theta+r)\).
Require \(W_\theta(\kappa p_\theta)\ge W_\theta(r)+\Lambda\) for every \(\theta\in\Theta\) and every real \(r\in[0,\kappa]\setminus\{\kappa p_\theta\}\), and minimize \(B=\sum_\theta\pi_\theta((1-p_\theta)\tau_0(p_\theta)+p_\theta\tau_1(p_\theta))\).

Is feasibility and minimum-budget computation polynomial-time in \(m,\tau,L\), or is the decision problem asking whether a feasible mechanism has \(B\le b\), for an additional binary-rational threshold \(b\ge0\), NP-hard?

Discrete: a constructive mechanism encourages truthful aggregate reporting when one controller owns all but one report; minimum-budget design for a fixed coalition is a finite LP. [Source](https://arxiv.org/pdf/1401.3451)
Continuous: no result settling this exact grid-constrained mass problem was located.

Answer for the stated problem

Every admissible instance is infeasible. Consequently, feasibility and budget decision are polynomial-time decidable, and minimum-budget computation always reports infeasibility.

The obstruction is the fixed positive margin against arbitrarily small deviations. To distinguish this from an impossibility of truthful reporting itself, a nontrivial example under a weaker controller condition is given below.

Proof of infeasibility

Fix any state \(\theta\), and write \(p=p_\theta\) and \(r^*=\kappa p\). Because \(0<p<1\) and \(\kappa>0\), we have \(0<r^*<\kappa\).

For every \(r\in[0,\kappa]\), the payment argument lies in its prescribed domain:
\[ 0\le (1-\kappa)p+r\le (1-\kappa)p+\kappa\le1. \]
Thus continuity of \(\tau_0,\tau_1\), together with continuity of products and sums, implies that \(W_\theta\) is continuous on \([0,\kappa]\).

For each positive integer \(n\), set \(r_n=r^*+(\kappa-r^*)/(n+1)\). Then \(r_n\in(r^*,\kappa)\) and \(r_n\to r^*\). The required controller inequality applies to every \(r_n\), giving
\[ W_\theta(r^*)-W_\theta(r_n)\ge\Lambda. \]
Continuity makes the left-hand side converge to \(0\). Taking limits therefore gives \(0\ge\Lambda\), contradicting \(\Lambda>0\).

This contradiction uses just one state. It applies regardless of the grid, prior, Bayesian incentive constraints, or budget.

Computational consequences

On inputs satisfying the stated promises, the algorithm simply returns infeasible, and the budget decision returns NO for every threshold \(b\). Checking the rational input promises, if required, also takes polynomial time.

There is no minimum over feasible mechanisms because the feasible set is empty. Under the extended-real convention, its budget infimum is \(\inf\varnothing=+\infty\).

The decision language has no yes-instances, so it is not NP-hard under polynomial-time many-one reductions: a reduction from any language with a yes-instance would have to map that instance to a yes-instance of the empty language.

A nontrivial comparison: strict controller truthfulness

For this section only, replace the controller requirement by \(W_\theta(\kappa p_\theta)>W_\theta(r)\) for every \(r\ne\kappa p_\theta\), while retaining the honest Bayesian margin \(\Lambda=1\). This modified condition can be satisfied.

Take \(\pi_1=\pi_2=1/2\), \(p_1=1/4\), \(p_2=3/4\), \(\kappa=1/4\), and
\[ G=\{0,3/16,7/16,9/16,13/16,1\}. \]
The attainable aggregate intervals are \(I_1=[3/16,7/16]\) and \(I_2=[9/16,13/16]\). Define payments there by

| Interval | \(\tau_0(q)\) | \(\tau_1(q)\) |
|---|---|---|
| \(I_1\) | \(4+12(q-1/4)\) | \(2-4(q-1/4)\) |
| \(I_2\) | \(4+4(q-3/4)\) | \(6-12(q-3/4)\) |

Interpolate affinely across \([7/16,9/16]\), and extend constantly to \(0\) and \(1\). These functions are continuous and affine between consecutive grid points. Their values on the two specified intervals satisfy
\[ \tau_0(I_1)\subseteq[13/4,25/4],\quad \tau_1(I_1)\subseteq[5/4,9/4], \]
and
\[ \tau_0(I_2)\subseteq[13/4,17/4],\quad \tau_1(I_2)\subseteq[21/4,33/4]. \]
Interpolation between positive endpoint values preserves nonnegativity.

At the truthful aggregates, the payment differences are \(d_1=-2\) and \(d_2=2\), where \(d_j=\tau_1(p_j)-\tau_0(p_j)\). Since \(q_0=q_1=1/2\), the honest signal-\(1\) incentive equals
\[ \frac{\frac12(\frac14)(-2)+\frac12(\frac34)(2)}{1/2}=1, \]
and the honest signal-\(0\) incentive equals
\[ \frac{\frac12(\frac34)(2)+\frac12(\frac14)(-2)}{1/2}=1. \]

To verify controller incentives, put \(h=r-\kappa p_j\). The aggregate payment argument is \(p_j+h\), always within \(I_j\). If \(b_{0,j},b_{1,j}\) denote the slopes in the table, expansion gives
\[ W_j(r)-W_j(\kappa p_j) =h\bigl[d_j+\kappa((1-p_j)b_{0,j}+p_jb_{1,j})\bigr] +h^2(b_{1,j}-b_{0,j}). \]
For the first state, the linear coefficient is \(-2+\frac14(\frac34\cdot12+\frac14\cdot(-4))=0\). For the second, it is \(2+\frac14(\frac14\cdot4+\frac34\cdot(-12))=0\). Both quadratic coefficients equal \(-16\). Hence
\[ W_j(\kappa p_j)-W_j(r)=16(r-\kappa p_j)^2>0 \]
for every nontruthful report. The mechanism has budget \(B=9/2\).

Thus strict truthful optimality is possible, but its gap approaches zero near truth. The [discrete source, Section 4.5](https://arxiv.org/pdf/1401.3451), compares finitely many integer report counts; a finite set of strictly positive gaps can be scaled to a common positive margin. Here continuity prevents that step.

⟨structured verdict parsed — rendered above⟩

Verdict

The output resolves the stated problem correctly and rigorously. Every admissible instance is infeasible because continuity is incompatible with a fixed positive payoff margin against every nonzero real deviation. No major or minor mathematical issues were found.

This conclusion uses the controller condition exactly as stated in USER_TASK; it does not depend on an unintended interpretation or a degenerate input.

Step-by-step verification

• The truthful report is interior.

Fixing any state is legitimate because the controller requirement must hold for every state. The assumptions \(0<p_\theta<1\) and \(0<\kappa<1\) imply
\(0<r^*=\kappa p_\theta<\kappa\).
Thus arbitrarily small admissible nontruthful deviations exist.

• Every payment evaluation is within its domain.

For \(r\in[0,\kappa]\), the argument satisfies
\(0\le(1-\kappa)p_\theta+r\le(1-\kappa)p_\theta+\kappa\le1\).
All inequalities follow from the stated bounds on \(p_\theta\), \(\kappa\), and \(r\). Consequently, the functions are evaluated only on their prescribed domain.

• The controller payoff is continuous.

The map \(r\mapsto(1-\kappa)p_\theta+r\) is continuous and takes values in \([0,1]\). Composing it with either continuous payment function, multiplying by the continuous factors \(r\) and \(\kappa-r\), and adding gives a continuous, finite-valued \(W_\theta\). The elementary continuity rules used here have all their hypotheses satisfied.

• The deviation sequence is valid.

For every positive integer \(n\),
\(r_n=r^*+(\kappa-r^*)/(n+1)\) lies strictly between \(r^*\) and \(\kappa\), since \(\kappa-r^*>0\) and \(0<1/(n+1)<1\).
Therefore \(r_n\) is admissible and nontruthful. Moreover, \(r_n\to r^*\).

• The margin condition contradicts continuity.

The universal controller constraint gives
\(W_\theta(r^*)-W_\theta(r_n)\ge\Lambda\) for every \(n\).
Continuity implies that these differences converge to \(0\). Passing to the limit preserves the weak inequality, giving \(0\ge\Lambda\), contrary to \(\Lambda>0\).

This establishes infeasibility without any assumptions about differentiability, grid alignment, Bayesian incentives, or budget.

• The computational conclusions follow.

On promised inputs, returning “infeasible” and answering “NO” to every budget query is correct and takes constant time after input access. If promise validation is required, comparisons, distinctness checks, and sums of binary rationals can be performed in polynomial time in the total input length.

Since the feasible set is empty, no minimum budget exists. The stated extended-real convention \(\inf\varnothing=+\infty\) is correct.

The empty decision language cannot be NP-hard under polynomial-time many-one reductions: the reduction equivalence would fail on any yes-instance of the source language. The prover explicitly identifies the reduction notion, so there is no ambiguity in this claim.

Verification of the supplementary example

The comparison concerns an explicitly modified controller condition and is not presented as a feasible mechanism for the original task.

• Grid and attainable intervals: Substituting the two states and \(\kappa=1/4\) gives exactly \(I_1=[3/16,7/16]\) and \(I_2=[9/16,13/16]\). The specified affine pieces, connecting interpolation, and constant extensions satisfy the grid and continuity requirements.

• Nonnegativity: Evaluating the affine functions at interval endpoints yields exactly the four stated value ranges. Positive endpoints also ensure positivity throughout the connecting affine segment and constant extensions.

• Bayesian incentives: The truthful payment pairs are \((4,2)\) and \((4,6)\), hence \(d_1=-2\), \(d_2=2\), and \(q_0=q_1=1/2\). Both displayed incentive calculations evaluate to \(1\), with the correct sign for each signal.

• Controller calculation: The aggregate argument is \(p_j+h\). Expanding the specified payoff gives precisely the displayed linear and quadratic coefficients. The linear coefficients vanish in both states, and both quadratic coefficients equal \(-16\). Thus the claimed gap \(16(r-\kappa p_j)^2\) is positive for every nontruthful report and tends to zero near truth.

• Budget: The two statewise budgets are \(7/2\) and \(11/2\). Their equally weighted average is \(9/2\), as claimed.

The source comparison is accurate: Section 4.5 uses finitely many integer coalition report counts and states the corresponding positive-margin constraints in equation (16). [Jurca and Faltings, Section 4.5](https://arxiv.org/pdf/1401.3451). The prover’s scaling observation is valid for a finite collection of strictly positive payoff gaps.

Repair feedback

None is needed. The main proof is complete, and the supplementary computations are internally consistent.

⟨structured verdict parsed — rendered above⟩