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.
Proposition 1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateThe minimum budget required by an in- centive compatible reputation mechanism decreases as the number of reference reporters increases.
statement extracted from the paper’s text layer; consult the paper for the exact wording
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 society is given by its support: the list of \(\tau\) signal types with positive binary-rational masses \(\mu_j\), normalized to sum to \(1\); \(\tau\) is the support size, not the number of possible types. Write \(S=\{s_1,\ldots,s_m\}\), with \(m=\tau\ge2\).
Input also includes \(k\) product states \(\Theta\), a positive rational prior \(p\), rational likelihoods \(f(s_j\mid\theta)\ge0\) summing to \(1\) for each state, and \(\mu_j=\sum_\theta p_\theta f(s_j\mid\theta)>0\). All buyers share this model and are risk-neutral.
Reference reporters report honestly; their signals and the focal buyer's signal are independent conditional on the same product state. For a supplied unary integer \(N\ge1\), let \(A_N=\{\mathbf a\in\mathbb Z_{\ge0}^m:\sum_\ell a_\ell=N\}\) and
\(q_N(\mathbf a\mid j)=\sum_{\theta\in\Theta}\frac{p_\theta f(s_j\mid\theta)}{\mu_j}\frac{N!}{\prod_\ell a_\ell!}\prod_\ell f(s_\ell\mid\theta)^{a_\ell}\), with \(0^0=1\).
Given binary-rational \(C\ge0\), \(\Delta(j,h)\ge0\) for \(j\ne h\), and \(\eta>0\), choose nonnegative payments \(T(r,\mathbf a)\) satisfying, for every \(j\ne h\), \(\sum_{\mathbf a\in A_N}q_N(\mathbf a\mid j)[T(j,\mathbf a)-T(h,\mathbf a)]\ge\Delta(j,h)+\eta\), and, for every \(j\), \(\sum_{\mathbf a\in A_N}q_N(\mathbf a\mid j)T(j,\mathbf a)\ge C+\eta\). Abstention yields zero payoff.
Let \(W_N\) be the minimum per-capita budget \(\sum_j\mu_j\sum_{\mathbf a\in A_N}q_N(\mathbf a\mid j)T(j,\mathbf a)\), or \(+\infty\) if infeasible. The optimization problem returns this value and an attaining payment table; zero entries may be omitted. Let \(L\) be the total input bit length.
Is deciding \(W_N\le B\), for a supplied binary-rational \(B\ge0\), in \(\mathsf P\), with running time polynomial in \(m,\tau,k,N,L\), or is it NP-hard? How does \(W_N\) compare across successive values of \(N\)?
For finite agents, minimum-budget payments have an explicit histogram LP with \(m\binom{N+m-1}{m-1}\) variables; the established budget comparison is nonincrease with additional reference reporters. [Jurca–Faltings (2006)](https://www.cs.cmu.edu/~sandholm/www/cs15-892F13/p190-jurca.pdf)
Later work explicitly uses the posterior mixture of binomial reference-count distributions for binary signals. These verified results do not provide a uniform complexity classification for the general succinct input above. [Jurca–Faltings (2009)](https://arxiv.org/pdf/1401.3451)
The decision problem is \(\mathsf{NP}\)-complete under polynomial-time many-one reductions. Hardness holds even when all model probabilities and signal masses are dyadic rationals, \(\eta=C=1\), \(B=2\), and every constructed instance is feasible with \(W_N\le4\).
Consequently, a uniform algorithm polynomial in \(m,\tau,k,N,L\) would imply \(\mathsf P=\mathsf{NP}\). Allowing zero payment entries to be omitted does not remove the hardness: whenever the optimum is finite, an optimal table with at most \(m^2\) nonzero entries and polynomial encoding length exists.
For successive reference counts,
\(W_{N+1}\le W_N.\)
Equality and strict inequality both occur.
Write
\(E_j[T_r]=\sum_{\mathbf a\in A_N}q_N(\mathbf a\mid j)T(r,\mathbf a).\)
The problem is a finite rational LP with \(m^2\) incentive and participation inequalities. Its histogram formulation agrees with the formulation in [Jurca–Faltings (2006)](https://www.cs.cmu.edu/~sandholm/www/cs15-892F13/p190-jurca.pdf); its potentially exponential number of columns requires a separate complexity argument.
For any specified histogram, its probabilities \(q_N(\mathbf a\mid j)\) can be computed exactly in polynomial time. Their bit lengths are polynomial in the input length and unary \(N\): the formula uses factorials, powers with exponents at most \(N\), and sums over the explicitly supplied states.
First, every feasible instance attains its minimum. If a variable \(T(r,\mathbf a)\) has zero objective coefficient, then \(q_N(\mathbf a\mid r)=0\), because \(\mu_r>0\). Setting this variable to zero preserves participation and weakly improves every incentive inequality: it contributes nothing to report \(r\)'s truthful expectation and can only increase another type's expected payment from falsely reporting \(r\). Thus all zero-cost variables may be discarded.
Every remaining variable has a strictly positive objective coefficient. Given one feasible table of budget \(K\), the feasible set restricted to budget at most \(K\) is closed and bounded in its finite-dimensional space. It is therefore compact, so the objective attains a minimum.
We next prove the sparse rational optimum claim. Introduce nonnegative surplus variables to express the \(d=m^2\) inequalities as equalities. Among optimal solutions, choose one with the smallest number of positive coordinates, counting payments and surplus variables. The corresponding columns of the equality matrix must be linearly independent. Otherwise a nonzero dependence permits sufficiently small perturbations in both directions while preserving feasibility. Optimality forces the objective change along that dependence to be zero. Continuing in one direction until a positive coordinate becomes zero then contradicts minimality of the support.
There are consequently at most \(d\) positive coordinates. An invertible minor determines them from the rational right-hand side. Cramer's rule gives polynomial bit length, because the minor has order at most \(m^2\) and all its coefficients have polynomial bit length.
If \(W_N\le B\), this optimal table is therefore a polynomial-size certificate: list its nonzero payments and their histogram indices. A verifier computes the required probabilities only at those histograms and checks all constraints and the budget exactly. Hence the decision problem belongs to \(\mathsf{NP}\).
We reduce from Set Cover. Its input consists of a nonempty universe \(U\), sets \(F_1,\ldots,F_n\subseteq U\), and an integer \(t\) with \(1\le t\le n\). The question is whether at most \(t\) sets cover \(U\).
This restricted problem is \(\mathsf{NP}\)-hard. To recall a direct reduction from \(\mathsf{3SAT}\), create one universe element for each variable and each clause. For each variable, create two sets: both contain its variable element, and each contains the clause elements satisfied by its corresponding literal. With \(t\) equal to the number of variables, any cover must select exactly one set for each variable. Such a cover exists precisely when the formula is satisfiable. Thus \(t\) is polynomially bounded and may be supplied in unary.
We will construct an instance satisfying
\(W_{t+1}\le2\quad\Longleftrightarrow\quad U\text{ has a cover using at most }t\text{ sets}.\)
Use the signal alphabet
\(S=\{r,c,x_1,\ldots,x_n\},\qquad m=\tau=n+2,\qquad N=t+1.\)
Let \(u=|U|\) and \(R=u+2\). Choose \(\alpha,\beta,\gamma\) to be the largest reciprocal powers of two satisfying, respectively,
\(n\alpha\le\frac14,\qquad (n+1)\beta\le\frac12,\qquad R\gamma\le\frac{\beta}{16}.\)
Set \(\varepsilon=R\gamma\). These choices have polynomial bit length.
There are four kinds of product states.
| State | Prior | Likelihoods |
|---|---:|---|
| Desired state \(\theta_0\) | \(\gamma\) | \(f(r\mid\theta_0)=1-n\alpha\), \(f(c\mid\theta_0)=0\), \(f(x_i\mid\theta_0)=\alpha\) |
| Element state \(\theta_e\), for each \(e\in U\) | \(\gamma\) | \(f(c\mid\theta_e)=\frac14\), \(f(x_i\mid\theta_e)=\alpha\) if \(e\notin F_i\), and \(0\) otherwise; \(f(r\mid\theta_e)=\frac34-\alpha|\{i:e\notin F_i\}|\) |
| Blocker state \(\theta_b\) | \(\gamma\) | \(f(r\mid\theta_b)=0\), \(f(x_i\mid\theta_b)=\alpha\), \(f(c\mid\theta_b)=1-n\alpha\) |
| Pure state \(\phi_h\), for every \(h\ne r\) | Defined below | Signal \(h\) occurs with probability \(1\) |
The pure state \(\phi_{x_i}\) has prior \(\beta\). The pure state \(\phi_c\) has prior
\(p_{\phi_c}=1-n\beta-\varepsilon.\)
All likelihood vectors sum to one. The element-state likelihood of \(r\) is at least \(\frac12\), and the desired-state likelihood of \(r\) is at least \(\frac34\). All priors are positive and sum to one. Indeed,
\(p_{\phi_c}\ge\frac12+\beta-\varepsilon\ge\beta.\)
Define the input masses by the required marginalization,
\(\mu_h=\sum_\theta p_\theta f(h\mid\theta).\)
Every signal has positive mass: each \(h\ne r\) has its pure state, and \(r\) has positive likelihood in \(\theta_0\). All supplied probabilities and masses are dyadic rationals.
We will use the bounds
\(\mu_r\le\varepsilon,\qquad \mu_h\ge p_{\phi_h}\ge\beta\quad(h\ne r),\qquad \mu_h\le p_{\phi_h}+\varepsilon.\)
Finally, set
\(C=1,\qquad\eta=1,\qquad B=2,\)
and
\(\Delta(c,r)=1,\qquad\Delta(j,h)=0\text{ for every other ordered pair }j\ne h.\)
The number of states is \(u+n+3\), and \(N=t+1\le n+1\). Thus the construction, including unary \(N\), has polynomial size.
We claim that
\(\exists\mathbf a\in A_N:\ q_N(\mathbf a\mid r)>0,\ q_N(\mathbf a\mid c)=0\)
holds exactly when the Set Cover instance has a cover of size at most \(t\).
Because mixture terms are nonnegative and every prior is positive, \(q_N(\mathbf a\mid j)>0\) precisely when some state has both positive focal likelihood for \(j\) and positive likelihood for the reference histogram.
Suppose \(q_N(\mathbf a\mid r)>0\) and \(q_N(\mathbf a\mid c)=0\). The only states with positive focal likelihood for \(r\) are \(\theta_0\) and the element states. An element state contributing to the former probability would also contribute to the latter, since its likelihood of \(c\) is positive. Therefore \(\theta_0\) must give the histogram positive probability. In particular, \(a_c=0\).
Moreover, \(a_r\ge1\). Otherwise the histogram uses only the \(x_i\), all of which have positive likelihood in \(\theta_b\). Since the blocker also has positive focal likelihood for \(c\), this would contradict \(q_N(\mathbf a\mid c)=0\).
For an element state \(\theta_e\), the histogram now has positive likelihood exactly when every selected \(x_i\) satisfies \(e\notin F_i\). Its contribution to \(q_N(\mathbf a\mid c)\) must vanish. Hence, for every \(e\in U\), at least one \(i\) with \(a_{x_i}>0\) satisfies \(e\in F_i\). These selected sets cover \(U\), and their number is at most
\(\sum_i a_{x_i}=N-a_r\le N-1=t.\)
Conversely, suppose a set of indices \(I\) covers \(U\), with \(1\le|I|\le t\). Choose the histogram
\(a_{x_i}=1\text{ for }i\in I,\qquad a_{x_i}=0\text{ otherwise},\qquad a_c=0,\qquad a_r=N-|I|.\)
The desired state gives it positive probability. Every element state gives it zero probability because the cover includes a signal absent from that state. The blocker and every pure state give it zero probability because \(a_r\ge1\). Thus only \(\theta_0\) can generate it, and
\(q_N(\mathbf a\mid r)>0,\qquad q_N(\mathbf a\mid c)=0.\)
This proves the characterization.
Participation requires \(E_j[T_j]\ge2\) for every \(j\). Consequently, every feasible table has budget at least
\(\sum_j\mu_j\,2=2.\)
If its budget is at most \(2\), positivity of every \(\mu_j\) forces
\(E_j[T_j]=2\quad\text{for every }j.\)
The special incentive constraint for \((c,r)\) is
\(E_c[T_c]-E_c[T_r]\ge2.\)
Since \(E_c[T_c]=2\) and payments are nonnegative, \(E_c[T_r]=0\). On the other hand, \(E_r[T_r]=2\), so some histogram with positive payment satisfies
\(q_N(\mathbf a\mid r)>0,\qquad q_N(\mathbf a\mid c)=0.\)
Section 4 then gives a cover of size at most \(t\). By attainment, this argument also applies whenever \(W_N\le2\).
Suppose a cover exists, and let \(\mathbf a^\star\) be the histogram constructed in Section 4. Pay report \(r\) only there:
\(T(r,\mathbf a^\star)=\frac{2}{q_N(\mathbf a^\star\mid r)}.\)
Then \(E_r[T_r]=2\) and \(E_c[T_r]=0\).
Only \(\theta_0\) generates \(\mathbf a^\star\). Therefore, for every \(x_i\),
\(\frac{q_N(\mathbf a^\star\mid x_i)}{q_N(\mathbf a^\star\mid r)} =\frac{\alpha\mu_r}{(1-n\alpha)\mu_{x_i}} \le\frac{\varepsilon\alpha}{(3/4)\beta} \le\frac1{48}.\)
In particular, \(E_{x_i}[T_r]\le1\).
For every report \(h\ne r\), let \(\mathbf e_h\) denote its coordinate unit vector and pay only at the unanimous histogram:
\(T(h,N\mathbf e_h)=\frac{2}{q_N(N\mathbf e_h\mid h)}.\)
The denominator is positive, and
\(q_N(N\mathbf e_h\mid h)\ge\frac{p_{\phi_h}}{\mu_h} \ge\frac{p_{\phi_h}}{p_{\phi_h}+\varepsilon}\ge\frac12.\)
For \(j\ne h\), we have \(q_N(N\mathbf e_h\mid j)\le\frac14\). There are two cases:
Thus, for every \(j\ne h\),
\(E_j[T_h] =2\frac{q_N(N\mathbf e_h\mid j)}{q_N(N\mathbf e_h\mid h)} \le1.\)
All truthful expectations equal \(2\). Every ordinary incentive constraint therefore has truthful advantage at least \(1\); the special constraint for \((c,r)\) has advantage exactly \(2\). Participation holds, and the budget is \(2\).
We have proved
\(W_{t+1}\le2\quad\Longleftrightarrow\quad\text{the Set Cover instance is a yes-instance}.\)
Together with Section 1, this establishes \(\mathsf{NP}\)-completeness.
The hardness does not depend on infeasibility in no-instances.
Pay each report only at its own unanimous histogram, scaling the payment to make its truthful expectation \(4\). For reports \(h\ne r\), the preceding estimates give every cross-expectation at most \(2\).
For the unanimous \(r\)-histogram and any \(h\ne r\),
\(\frac{q_N(N\mathbf e_r\mid h)}{q_N(N\mathbf e_r\mid r)} \le\frac{\mu_r}{\mu_h} \max_{\theta:\,f(r\mid\theta)>0} \frac{f(h\mid\theta)}{f(r\mid\theta)} \le\frac{\varepsilon}{2\beta}\le\frac1{32}.\)
Here only the desired and element states enter the maximum, and their likelihood ratio is at most \(\frac12\). Hence a false report of \(r\) has expected payment at most \(\frac18\).
All required incentive margins, including the special margin \(2\), hold. Participation holds as well, and the budget is \(4\). Thus every constructed instance satisfies
\(2\le W_N\le4.\)
Fix any feasible table \(T_N\). For a histogram \(\mathbf b\in A_{N+1}\), define
\(T_{N+1}(r,\mathbf b) =\sum_{\ell:\,b_\ell>0}\frac{b_\ell}{N+1}T_N(r,\mathbf b-\mathbf e_\ell).\)
This averages the old payment after deleting one uniformly selected reference report. The resulting payment is nonnegative.
For completeness, write the state-conditional multinomial probability as
\(M_N^\theta(\mathbf a)=\frac{N!}{\prod_\ell a_\ell!}\prod_\ell f(s_\ell\mid\theta)^{a_\ell}.\)
Direct calculation gives, for every \(\mathbf a\in A_N\),
\(M_{N+1}^\theta(\mathbf a+\mathbf e_\ell)\frac{a_\ell+1}{N+1} =f(s_\ell\mid\theta)M_N^\theta(\mathbf a).\)
The identity also holds when likelihoods vanish, with the stipulated convention \(0^0=1\). Summing over \(\ell\) gives
\(\sum_\ell M_{N+1}^\theta(\mathbf a+\mathbf e_\ell)\frac{a_\ell+1}{N+1} =M_N^\theta(\mathbf a).\)
Consequently, conditional on each state, the new table has exactly the old expected payment for every report. Mixing with the posterior conditional on focal signal \(j\) yields
\(\sum_{\mathbf b\in A_{N+1}}q_{N+1}(\mathbf b\mid j)T_{N+1}(r,\mathbf b) =\sum_{\mathbf a\in A_N}q_N(\mathbf a\mid j)T_N(r,\mathbf a).\)
Every incentive expectation, participation expectation, and budget is preserved. Therefore
\(W_{N+1}\le W_N,\)
including the extended-real cases. This supplies a proof of the established nonincrease that directly respects the posterior-mixture model.
Suppose each signal has its own pure state and there are no other states. Conditional on focal signal \(j\), every reference reports \(j\), regardless of \(N\).
Define
\(d_j=\max\{C+\eta,\ \max_{h\ne j}(\Delta(j,h)+\eta)\}.\)
Nonnegativity and the constraints imply truthful expected payment at least \(d_j\). Paying \(d_j\) only for report \(j\) at histogram \(N\mathbf e_j\) attains these bounds. Hence, for every \(N\ge1\),
\(W_N=\sum_j\mu_jd_j.\)
Take two signals, two equally likely states, and likelihood vectors
\((3/4,1/4)\quad\text{and}\quad(1/4,3/4).\)
Set \(C=0\), \(\eta=1\), and both lying gains to zero. The signal masses are \((1/2,1/2)\).
Swapping the two signal labels preserves the LP and its objective. Averaging any feasible table with its swapped table therefore produces a symmetric feasible table of the same budget.
For \(N=1\), the reference distributions conditional on focal signals \(1\) and \(2\) are
\((5/8,3/8)\quad\text{and}\quad(3/8,5/8).\)
In a symmetric table, let \(x\) be the payment for a matching reference signal and \(y\) the payment for an opposing signal. Incentives require
\((x-y)/4\ge1.\)
The budget is \(5x/8+3y/8\), so nonnegativity gives a minimum of \(5/2\), attained by \(x=4,y=0\). Participation is satisfied.
For \(N=2\), ordered by the number of signal-\(1\) references, the conditional distributions are
\((3/16,3/8,7/16)\quad\text{and}\quad(7/16,3/8,3/16).\)
Let \(x\) be the payment for matching unanimous references, \(y\) for opposing unanimous references, and \(z\) for mixed references. Incentives again require \((x-y)/4\ge1\). The budget is
\(7x/16+3y/16+3z/8.\)
Its minimum is \(7/4\), attained by \(x=4,y=z=0\), which also satisfies participation. Thus
\(W_2=\frac74<\frac52=W_1.\)
⟨structured verdict parsed — rendered above⟩
The output resolves the task. The decision problem’s claimed \(\mathsf{NP}\)-completeness, the sparse optimum claim, and the comparison \(W_{N+1}\le W_N\) are supported by the written arguments. I found no major or minor mathematical issues.
1. Finite LP, attainment, and certificate size
There are exactly \(m(m-1)+m=m^2\) incentive and participation inequalities. The potentially exponential number of payment variables does not invalidate the subsequent certificate argument.
For a specified histogram, exact evaluation of \(q_N(\mathbf a\mid j)\) takes polynomial time and produces numbers of polynomial bit length. Unary encoding of \(N\) is essential here: factorials and likelihood powers have polynomial bit length, and the mixture sums over the explicitly listed states.
The removal of zero-cost variables is valid. Since \(\mu_r>0\), a zero objective coefficient implies \(q_N(\mathbf a\mid r)=0\). Removing that payment preserves the truthful expectation of type \(r\), reduces any affected deviation expectations, and therefore weakly improves incentive constraints.
After those variables are removed, every objective coefficient is positive. Restricting to the budget of any feasible table bounds each remaining payment individually. The restricted feasible set is nonempty, closed, and bounded in a finite-dimensional space, so the minimum is attained.
The sparse optimum argument also checks out:
Thus at most \(m^2\) coordinates are positive, counting both payments and surplus variables. In particular, at most \(m^2\) payments are nonzero.
An invertible minor determines these coordinates. Its dimension and coefficient bit lengths are polynomially bounded, so Cramer’s rule gives polynomial encoding length. Histogram indices also have polynomial encoding length. The claimed exact polynomial-time certificate verification therefore establishes membership in \(\mathsf{NP}\).
The histogram LP structure cited by the prover appears in Section 4.1 of [Jurca–Faltings (2006)](https://www.cs.cmu.edu/~sandholm/www/cs15-892F13/p190-jurca.pdf). The proof’s attainment and complexity arguments are supplied independently.
2. Source problem and reduction size
The stated reduction from \(\mathsf{3SAT}\) to restricted Set Cover is correct. Each variable element forces selection of a set associated with that variable. With the budget equal to the number of variables, exactly one of its two literal sets must be selected. Coverage of clause elements then corresponds precisely to satisfaction.
The constructed model has \(m=\tau=n+2\), \(N=t+1\le n+1\), and \(u+n+3\) states. Its explicit likelihood table and unary reference count therefore have polynomial size.
The reciprocal powers defining \(\alpha,\beta,\gamma\) have polynomial bit length and can be chosen in polynomial time.
3. Validity of the constructed Bayesian input
Every likelihood vector is normalized and nonnegative. In particular, the element-state likelihood of \(r\) is at least \(3/4-n\alpha\ge1/2\), and the desired-state likelihood is at least \(3/4\).
The prior calculation is correct: the nonpure states have total prior \(\varepsilon=(u+2)\gamma\), the pure \(x_i\)-states have total prior \(n\beta\), and the remaining prior is assigned to \(\phi_c\).
The bound \(p_{\phi_c}\ge1/2+\beta-\varepsilon\ge\beta>0\) follows from the parameter choices. Hence every prior is positive and their sum is one.
Every listed signal has positive marginal mass. The supplied masses are defined by the required marginalization, and all priors, likelihoods, and masses are dyadic rationals.
The bounds \(\mu_r\le\varepsilon\), \(\mu_h\ge p_{\phi_h}\ge\beta\), and \(\mu_h\le p_{\phi_h}+\varepsilon\) are valid. The support-size requirement is respected.
4. Histogram characterization
Both directions of the central characterization are correct.
For the forward direction:
The selected sets therefore cover \(U\), and their number is at most \(N-a_r\le t\).
For the converse, a cover of size at most \(t\) produces the stated histogram with at least one \(r\)-reference. The desired state generates it; each element state is excluded by a selected covering set; and the blocker and pure states are excluded by the positive \(r\)-count. Since \(U\) is nonempty, a covering index set is nonempty, as required.
5. Equivalence with budget at most two
The necessity argument is sound. Participation gives budget at least two. Because all masses are positive, budget at most two forces every truthful expectation to equal two.
The special constraint then forces \(E_c[T_r]=0\). Nonnegativity of payments and \(E_r[T_r]=2\) imply the existence of a paid histogram with positive conditional probability for \(r\) and zero conditional probability for \(c\). The characterization applies. Attainment justifies applying this argument to \(W_N\le2\).
For sufficiency, all payment denominators are positive. The desired-state likelihood ratio is correctly computed, and its numerical bound follows from \(\varepsilon/\beta\le1/16\), \(\alpha\le1/4\), and \(1-n\alpha\ge3/4\).
For reports \(h\ne r\), the unanimous-histogram truthful probability is at least \(1/2\). The cross-probability bounds cover every other focal signal:
Thus each ordinary deviation expectation is at most one, while every truthful expectation is two. The special deviation expectation is zero. All constraints hold with budget exactly two.
The reduction therefore establishes the claimed many-one equivalence and \(\mathsf{NP}\)-hardness.
6. Feasibility of every constructed instance
The additional budget-four construction is valid.
For reports other than \(r\), scaling the previously checked unanimous payments gives cross-expectations at most two.
For report \(r\), its unanimous histogram has positive truthful probability. Because \(N\ge1\), states with zero likelihood of \(r\) contribute nothing. In every remaining state, the likelihood ratio for another signal relative to \(r\) is at most \(1/2\). The displayed probability-ratio bound is consequently valid and gives cross-expectation at most \(1/8\).
Truthful expectations of four satisfy participation and all incentive margins, including the special margin two. Hence the claimed bound \(2\le W_N\le4\) holds for every constructed instance, including no-instances.
7. Successive reference counts
The deletion transformation is well-defined and nonnegative.
The multinomial identity is correct, including zero likelihoods under the stated convention \(0^0=1\). Summing it over the deleted coordinate preserves the state-conditional histogram distribution. Therefore the transformation preserves every report’s expected payment conditional on every focal signal after posterior mixing.
All incentive expectations, participation expectations, and the objective are preserved. Applying this to an attaining optimum proves \(W_{N+1}\le W_N\) when \(W_N\) is finite. When \(W_N=+\infty\), the inequality holds automatically in the extended-real order.
No independence conditional only on the focal signal is assumed. The argument uses the required independence conditional on the product state.
8. Equality and strict decrease
The pure-state equality example is correct. Conditional on focal signal \(j\), references are unanimously \(j\). Nonnegativity gives the stated lower bound \(d_j\), and the proposed payments attain it for every \(N\ge1\).
The strict-decrease example also checks out. Label swapping preserves the instance, feasibility, and objective, so averaging legitimately restricts the calculation to symmetric tables.
The conditional distributions for both reference counts are correct. For \(N=1\), the incentive condition forces \(x-y\ge4\), and the stated nonnegative minimizer gives \(W_1=5/2\). For \(N=2\), the same incentive condition applies, and the stated minimizer gives \(W_2=7/4\). Both minimizers satisfy participation.
Thus equality and strict inequality are both demonstrated.
No repair or additional clarification is needed.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.