Answer: \(\mathrm{NP}\text{-hard}\)
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe dishonesty limit is: DL = Θ(log n) Importance of the results. With the dishonesty limit con- cept, we are able to quantify what is possible in the context of minimal elicitation with limited knowledge. An exam- ple of an objective that is possible to reach with partially truthful mechanisms is elicitation of accurate aggregates. In particular, suppose that the goal is to elicit a distribution of signal values.
statement extracted from the paper’s text layer; consult the paper for the exact wording
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.
Let \(S\) be a signal set of size \(m\geq2\). The input contains \(R\) possible common signal models, a positive rational prior \(\pi\) on them, a nonempty grid \(G\) of \(K\) fully mixed rational distributions on \(S\), a rational noise rate \(0\leq\epsilon<1\), and a unary horizon \(H\geq1\).
Each model \(\theta\) specifies a finite latent-state distribution with positive rational weights and fully mixed rational conditional signal distributions \(p_\theta(x\mid\omega)\). Peer signals are conditionally independent given the state; their posterior distributions given distinct signals must differ. Let \(J\) be the total number of listed latent states.
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational; \(\tau\) is the support size, not the number of possible types. Here types are signal–behavior pairs, and the input lists their masses conditional on each model and state.
Every cohort has total mass one. Conditional on its state, strategic signal-\(x\) mass is \((1-\epsilon)p_\theta(x\mid\omega)\), and nonstrategic signal-\(x\) mass is \(\epsilon p_\theta(x\mid\omega)\); nonstrategic mass reports uniformly on \(S\). The model is drawn once from \(\pi\), and cohort states are independently drawn from that model.
Agents know the model but not the realized state; the mechanism knows only the input. Before each cohort reports, a committed adaptive policy chooses and announces \(P\in G\), possibly randomly, using previous exact report-mass histograms. Past histograms and chosen payments are public; each agent participates in only one cohort.
An agent reporting \(r\) is paired uniformly with a peer in that cohort and receives \(u_P(r,z)=\bigl(\mathbf{1}_{\{r=z\}}-\epsilon/m\bigr)/P(r)\) when the peer reports \(z\). Agents maximize expected payment; an individual has zero effect on histograms.
Promise that for every model some \(P\in G\) makes honest reporting a strict Bayesian–Nash equilibrium, but no single one-peer payment matrix makes honesty a strict Bayesian–Nash equilibrium for every listed model.
Allow Bayesian–Nash equilibria with arbitrary report fractions within each strategic signal type, depending on the model, public history, and announced payment; ties may be split arbitrarily. Dishonesty is the total strategic mass reporting a value different from its signal, summed over cohorts, with expectation over the model, states, and policy randomization.
For rational \(0\leq q\leq H(1-\epsilon)\), is deciding whether some adaptive payment policy and Bayesian–Nash equilibrium have expected dishonest strategic mass at most \(q\) in \(\mathrm{P}\), or is it NP-hard? State running times in \(m,\tau,R,J,K,H\) and the total input bit length \(L\).
For finite-agent minimal peer prediction with limited knowledge, the reported dishonesty limit is \(\Theta(\log n)\), with AdaPTS attaining the upper bound in a strict equilibrium ([Radanovic–Faltings](https://cdn.aaai.org/ojs/11511/11511-13-15039-1-2-20201228.pdf)). This is an asymptotic dishonesty bound, not a polynomial-time classification of the decision problem.
No result settling this exact atomless, exact-histogram policy-existence problem was located.
The decision problem is \(\mathrm{NP}\)-hard, already with
\(H=1\), \(R=3\), \(K=3\), \(\epsilon=0\), \(\tau=m\), and \(J=3m\).
The reduction below allows arbitrary mixed reporting fractions and satisfies both promises in the question. Thus, unless \(\mathrm{P}=\mathrm{NP}\), there is no algorithm polynomial in \(m,\tau,R,J,K,H,L\).
The one-cohort restriction is also in \(\mathrm{NP}\). For general horizons, a finite enumeration using linear programming gives an explicit, though much larger, upper bound.
We first construct models whose equilibria can be analyzed directly.
Let \(d\) be a fully mixed rational distribution on \(S\), and let \(b\) be rational with \(0<b<1\). Define a model \(M(d,b)\) with one latent state for each signal. State \(i\) has probability \(d_i\), and its conditional signal distribution is
\[ p(x\mid i)=(1-b)d_x+b\mathbf{1}_{\{x=i\}}. \]
Every state weight and conditional signal probability is positive. Conditional on the state, peer signals are independent.
The marginal signal distribution is \(d\). Writing \(t=b^2\), the joint signal probabilities are
\[ \Pr(X=x,Y=y)=(1-t)d_xd_y+t\,d_x\mathbf{1}_{\{x=y\}}. \]
Consequently, the peer-signal posterior is
\[ Q(y\mid x)=(1-t)d_y+t\mathbf{1}_{\{x=y\}}. \]
Distinct signals have distinct peer-signal posteriors, since their posterior vectors differ by \(t(e_x-e_{x'})\).
For the reduction, set \(\epsilon=0\). Let \(a_{xr}\) be the fraction of strategic signal-\(x\) agents reporting \(r\), so \(a_{xr}\geq0\) and \(\sum_r a_{xr}=1\). Define the marginal report mass
\[ c_r=\sum_x d_xa_{xr}. \]
Under payment distribution \(P\), the expected payoff to signal \(x\) from reporting \(r\) is
\[ U_x(r)=\frac{(1-t)c_r+t a_{xr}}{P_r}. \]
Thus \(a\) is an equilibrium exactly when every report with positive fraction in a row maximizes that row’s expected payoff. This characterization permits arbitrary splitting at ties.
Honest reporting is a strict equilibrium when \(P=d\): under \(a_{xr}=\mathbf{1}_{\{x=r\}}\),
\[ U_x(x)=1-t+\frac{t}{d_x}, \qquad U_x(r)=1-t\quad(r\neq x). \]
For a nonempty report set \(U\subseteq S\), define
\[ T_P(U)=\sum_{r\in U}P_r, \qquad F_{d,P}(U)=\sum_{r\in U}\min\left\{d_r,\frac{P_r}{T_P(U)}\right\}. \]
Also define
\[ \Delta(t,P)=\frac{t}{(1-t)\min_r P_r}. \]
Lemma 1. Every equilibrium of \(M(d,b)\) under \(P\), including mixed equilibria, has honest mass at most
\[ \max_{\varnothing\neq U\subseteq S}F_{d,P}(U)+\Delta(t,P). \]
Proof. Let \(U=\{r:c_r>0\}\), which is nonempty. Set
\[ M=\max_s\frac{c_s}{P_s}. \]
For each \(r\in U\), some signal \(x\) has \(a_{xr}>0\). Equilibrium therefore implies, for every \(s\),
\[ \frac{(1-t)c_r+t a_{xr}}{P_r} \geq \frac{(1-t)c_s+t a_{xs}}{P_s} \geq \frac{(1-t)c_s}{P_s}. \]
Using \(a_{xr}\leq1\), we obtain
\[ M-\Delta(t,P)\leq\frac{c_r}{P_r}\leq M. \]
The \(P\)-weighted average of these ratios over \(U\) is
\[ \frac{\sum_{r\in U}c_r}{T_P(U)}=\frac{1}{T_P(U)}. \]
Hence \(M\leq1/T_P(U)+\Delta(t,P)\), and therefore
\[ c_r\leq\frac{P_r}{T_P(U)}+P_r\Delta(t,P). \]
The honest mass reporting \(r\) is \(d_ra_{rr}\), which is at most both \(d_r\) and \(c_r\). Consequently,
\[ \begin{aligned} \sum_r d_ra_{rr} &\leq \sum_{r\in U}\min\{d_r,c_r\}\\ &\leq F_{d,P}(U)+T_P(U)\Delta(t,P)\\ &\leq F_{d,P}(U)+\Delta(t,P). \end{aligned} \]
This proves the lemma. \(\square\)
The proof also establishes the following fact for every used report \(r\):
\[ \frac{c_r}{P_r}\geq\frac{1}{T_P(U)}-\Delta(t,P). \tag{1} \]
Lemma 2. Suppose \(\varnothing\neq U\subseteq S\), write \(T=T_P(U)\), and assume
\[ (1-t)d_r\leq\frac{P_r}{T}\qquad(r\in U). \]
Then there is an equilibrium in which every signal in \(U\) reports honestly and every signal outside \(U\) reports within \(U\). Its honest mass is exactly \(\sum_{r\in U}d_r\).
Proof. Let
\[ d_D=1-\sum_{r\in U}d_r, \qquad C=(1-t)d_D+t, \]
and define
\[ v_r= \begin{cases} \displaystyle\frac{P_r/T-(1-t)d_r}{C},&r\in U,\\ 0,&r\notin U. \end{cases} \]
The assumed inequalities give \(v_r\geq0\). Moreover,
\[ \sum_r v_r = \frac{1-(1-t)(1-d_D)}{C}=1. \]
Have each signal \(x\in U\) report \(x\), and each signal outside \(U\) use report fractions \(v\). For \(r\in U\), the marginal report mass is \(c_r=d_r+d_Dv_r\). By construction,
\[ \frac{(1-t)c_r}{P_r} = \frac1T-\frac{t v_r}{P_r}. \]
A signal outside \(U\) therefore receives payoff \(1/T\) from every report in \(U\), and zero from every report outside \(U\).
A signal \(x\in U\) receives from its honest report
\[ U_x(x)=\frac1T+\frac{t(1-v_x)}{P_x}\geq\frac1T. \]
Every other report in \(U\) gives payoff at most \(1/T\), and every report outside \(U\) gives zero. All prescribed reports are therefore best responses. The claimed honest mass follows immediately. \(\square\)
We reduce from binary-encoded PARTITION: given positive integers \(a_1,\ldots,a_n\), determine whether some subset sums to half their total. This is an \(\mathrm{NP}\)-complete problem; see [Karp’s original reduction framework](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).
Let \(A=\sum_{i=1}^n a_i\), and use signals \(S=\{0,1,\ldots,n,\ast\}\), so \(m=n+2\). Define a payment distribution \(P\) and signal marginal \(d\) by
\[ P_0=\frac14,\qquad P_i=\frac{3a_i}{10A}\quad(1\leq i\leq n),\qquad P_\ast=\frac9{20}, \]
and
\[ d_0=\frac58,\qquad d_r=\frac{P_r}{2}\quad(r\neq0). \]
Both distributions are fully mixed and sum to one. Define
\[ \gamma=\frac{3}{160A}. \]
Lemma 3.
Proof. If \(0\notin U\), then \(P_r/T_P(U)\geq P_r>d_r\) for every \(r\in U\). Thus
\[ F_{d,P}(U)=\frac{T_P(U)}2\leq\frac38. \tag{2} \]
Now suppose \(0\in U\), and write \(T=T_P(U)\). The same calculation for the other signals gives
\[ F_{d,P}(U) = f(T):= \min\left\{\frac58,\frac{1}{4T}\right\} +\frac12\left(T-\frac14\right). \]
At \(T=2/5\), this equals \(7/10\).
For \(T\leq2/5\),
\[ \frac7{10}-f(T)=\frac12\left(\frac25-T\right). \]
For \(2/5\leq T\leq1\),
\[ \frac7{10}-f(T) = \frac{(T-2/5)(5/4-T)}{2T} \geq\frac{T-2/5}{8}. \]
Every attainable \(T\) with \(0\in U\) has the form
\[ T=\frac14+\frac{3B}{20A}, \]
where
\[ B=2\sum_{i\in U\cap\{1,\ldots,n\}}a_i +3A\mathbf{1}_{\{\ast\in U\}} \]
is an integer. Therefore \(T=2/5\) exactly when \(B=A\). Since the dummy contribution \(3A\) exceeds \(A\), this happens exactly when \(\ast\notin U\) and \(2\sum_{i\in U}a_i=A\).
If PARTITION has no solution, every such \(T\) differs from \(2/5\) by at least \(3/(20A)\). The preceding bounds then give a loss of at least \(\gamma\). Sets omitting \(0\) satisfy the same bound by (2), since \(3/8<7/10-\gamma\). \(\square\)
Let \(p_{\min}=\min_r P_r\), and choose
\[ b=\frac{\gamma p_{\min}}{100}, \qquad t=b^2, \qquad b_g=\frac{p_{\min}}{100}. \]
Define a shifted marginal
\[ d'=d+\frac{t}{1-t}(e_0-e_1). \]
Since \(b<1/100\),
\[ \frac{t}{1-t}\leq2b^2<\frac{p_{\min}}4. \]
Thus every coordinate of \(d'\) is positive. In particular,
\[ \min_r d_r\geq\frac{p_{\min}}2, \qquad \min_r d'_r\geq\frac{p_{\min}}4. \tag{3} \]
Use the following models and payment grid.
| Model | Signal model | A payment giving strict honesty |
|---|---|---|
| Hard | \(M(d,b)\) | \(d\) |
| Gate | \(M(P,b_g)\) | \(P\) |
| Witness | \(M(d',b)\) | \(d'\) |
Thus \(G=\{P,d,d'\}\). Set \(H=1\) and \(\epsilon=0\). There is one strategic type for each signal, with its conditional mass equal to the corresponding conditional signal probability.
This gives \(R=3\), \(K=3\), \(\tau=m\), and \(J=3m\).
Each model has a grid payment giving strict honesty, by the calculation in Section 1.
There is also no single one-peer payment matrix giving strict honesty in every model. Indeed, the hard model’s posterior after signal \(0\) is identical to the witness model’s posterior after signal \(1\):
\[ (1-t)d+t e_0 = (1-t)d'+t e_1. \]
For any common payment matrix, these two agents have exactly the same expected payoff from each report. Strict honesty would require report \(0\) to beat report \(1\) in the first model, and report \(1\) to beat report \(0\) in the second. These requirements contradict each other.
Lemma 4. Every equilibrium of the gate model under either payment \(d\) or payment \(d'\) has dishonest mass at least \(1/4\).
Proof. Write \(B\in\{d,d'\}\) for the chosen payment and \(t_g=b_g^2\). By (3),
\[ \Delta(t_g,B) \leq \frac{8p_{\min}}{10000} < \frac18. \]
The gate’s signal-\(0\) mass is \(P_0=1/4\).
If report \(0\) is unused, all that mass is dishonest. Otherwise, (1) gives
\[ c_0 \geq B_0\left(\frac1{T_B(U)}-\Delta(t_g,B)\right) \geq B_0-\Delta(t_g,B) \geq\frac12, \]
where we used \(T_B(U)\leq1\) and \(B_0\geq5/8\).
At most \(1/4\) of the mass reporting \(0\) can be honest. Therefore dishonest mass is at least \(c_0-1/4\geq1/4\). \(\square\)
Set
\[ w=\frac18, \qquad \eta=\frac{w\gamma}{8}, \]
and choose the positive model prior
\[ \pi_{\mathrm{hard}}=w,\qquad \pi_{\mathrm{witness}}=\eta,\qquad \pi_{\mathrm{gate}}=1-w-\eta. \]
Finally, set
\[ q=w\left(\frac3{10}+\frac{\gamma}{4}\right). \]
This is a rational threshold satisfying \(0<q<1\).
Suppose PARTITION has a solution. Choose payment \(P\).
By Lemma 3, there is a set \(U\) containing \(0\), omitting \(\ast\), and satisfying \(T_P(U)=2/5\). For every \(r\in U\),
\[ d_r\leq\frac{P_r}{T_P(U)}. \]
Thus Lemma 2 applies to the hard model. Its equilibrium has honest mass
\[ \sum_{r\in U}d_r = \frac58+\frac12\left(\frac25-\frac14\right) = \frac7{10}. \]
Its dishonest mass is therefore \(3/10\).
Use the strict honest equilibrium in the gate model. In the witness model, use the equilibrium in which everyone reports \(0\): report \(0\) pays positively and every other report pays zero. Its dishonest mass is at most one.
The resulting expected dishonest mass is at most
\[ w\frac3{10}+\eta = w\left(\frac3{10}+\frac{\gamma}{8}\right) <q. \]
Suppose PARTITION has no solution.
First consider payment \(P\). Its equilibrium error satisfies
\[ \Delta(t,P) = \frac{b^2}{(1-b^2)p_{\min}} \leq \frac{2\gamma^2p_{\min}}{10000} < \frac{\gamma}{4}. \]
Lemmas 1 and 3 therefore imply that every hard-model equilibrium has honest mass at most
\[ \frac7{10}-\gamma+\Delta(t,P) < \frac7{10}-\frac{3\gamma}{4}. \]
Hence expected dishonest mass under payment \(P\), even ignoring the other models, exceeds
\[ w\left(\frac3{10}+\frac{3\gamma}{4}\right)>q. \]
Now consider either other grid payment. Lemma 4 gives expected dishonest mass at least
\[ \frac{\pi_{\mathrm{gate}}}{4}. \]
Since \(\eta<1/8\), we have \(\pi_{\mathrm{gate}}>3/4\). Consequently,
\[ \frac{\pi_{\mathrm{gate}}}{4}>\frac3{16}>q. \]
With \(H=1\), the mechanism has no previous histogram. Its randomized payment is therefore independent of the model. Its expected dishonesty is a convex combination of the conditional expected dishonesty for the three payment choices. Every choice exceeds \(q\), for every admissible equilibrium, so randomization cannot succeed.
This proves the equivalence between PARTITION and the constructed instance.
All constructed rationals have bit length \(O(\log(A+1))\). There are \(O(m^2)\) conditional signal and type-mass entries. Hence the constructed input has
\[ L=O\!\left(m^2\log(A+1)\right), \]
and it can be constructed in \(O(m^2\operatorname{poly}(\log(A+1)))\) bit operations.
Both \(m\) and \(\log(A+1)\) are polynomially bounded by the source input length. The reduction is therefore a polynomial-time many-one reduction. It proves ordinary \(\mathrm{NP}\)-hardness; no strong-hardness claim is needed.
For a fixed model and payment, expected payoffs are affine functions of the reporting fractions.
Enumerate, for each strategic reporting row, a nonempty allowed report set. There are at most \((2^m-1)^\tau\) choices. For each choice, impose:
These are rational linear-programming constraints. Allowing an allowed report to have zero fraction is harmless: every report actually used is still a best response. Conversely, every equilibrium appears by choosing its actual positive supports.
For each payment, minimize dishonest mass separately in each model and average using \(\pi\). Agents know the model, so these equilibrium choices are independent. Randomization over payments cannot improve the minimum.
This gives a running time bounded by
\[ KR\,2^{m\tau}\operatorname{poly}(m,\tau,J,L). \]
Furthermore, a feasible support-constrained linear program has a rational feasible solution of polynomial encoding length. A payment and polynomial-size rational equilibrium certificate therefore establish membership in \(\mathrm{NP}\).
Thus the one-cohort restriction, including the promised family above, is \(\mathrm{NP}\)-complete as a promise problem.
A larger finite enumeration also handles adaptive policies.
First, policy randomization can be removed. For any fixed policy and equilibrium, there are finitely many reached public histories: each announced payment has at most \(J\) possible state-conditioned histograms. At each history, choose an action minimizing the conditional expected remaining dishonesty, and proceed backward. This preserves the current cohort’s equilibrium because agents participate only once and their individual reports have zero effect on future histograms. The resulting deterministic policy has no greater expected dishonesty.
For a deterministic policy, let
\[ N=\sum_{h=0}^{H-1}J^h \]
bound the number of cohort-decision nodes.
At each node, enumerate:
Histograms are affine in reporting fractions. Equality within a block is therefore linear; a selected coordinate and sign gives a strict linear inequality between blocks.
Once these partitions are fixed, each node’s model-conditioned reach probability is a product of sums of the listed state weights. These probabilities are rational constants. Consequently, expected total dishonesty is linear in the reporting fractions.
Every enumerated case is thus a rational linear feasibility problem, possibly with strict inequalities. Strict inequalities can be checked by introducing one common slack variable, bounding it between zero and one, and maximizing it. The original strict system is feasible exactly when the maximum slack is positive.
A conservative running-time bound is
\[ 2^{O\!\left( N\left[ R\tau m+\log(K+1)+J\log(J+1)+J^2\log(2m) \right]\right)} \operatorname{poly}(N,m,\tau,R,J,K,H,L). \]
This bound explicitly accounts for equality of exact histograms. No discretization of reporting fractions or observations is required.
The finite-agent \(\Theta(\log n)\) dishonesty result concerns an asymptotic equilibrium-performance bound, as stated in [Radanovic–Faltings](https://cdn.aaai.org/ojs/11511/11511-13-15039-1-2-20201228.pdf). The reduction here instead establishes computational hardness for the specified atomless decision problem, already before adaptivity arises.
⟨structured verdict parsed — rendered above⟩
The hardness reduction is correct in substance. It handles arbitrary mixed reporting fractions, satisfies both promises, and establishes ordinary \(\mathrm{NP}\)-hardness already for \(H=1\). I found no false central step or blocking issue. Two minor clarifications remain in the presentation of the upper bounds.
The construction of \(M(d,b)\) satisfies the model requirements:
The stated joint distribution and posterior are correct:
\[
\Pr(X=x,Y=y)=(1-b^2)d_xd_y+b^2d_x\mathbf{1}_{\{x=y\}}.
\]
Dividing by the positive marginal \(d_x\) gives the displayed posterior. Distinct posterior vectors differ by \(b^2(e_x-e_{x'})\), so the required distinctness holds.
For arbitrary reporting fractions, the payoff formula
\[
U_x(r)=\frac{(1-t)c_r+t a_{xr}}{P_r}
\]
correctly incorporates the posterior and the peer’s reporting fractions. The best-response characterization is necessary and sufficient: agents have zero individual effect on the fractions, and their own expected payoff is linear in their reporting choice.
The strict-honesty calculation for \(P=d\) is correct. Its strict payoff advantage is \(t/d_x>0\).
Assessment: Correct.
The proof covers mixed equilibria without assuming pure reporting.
For every used report \(r\), some row uses it positively. Applying that row’s best-response inequality and dropping the nonnegative term on the alternative-report side is valid. The resulting bound
\[
M-\Delta(t,P)\leq c_r/P_r\leq M
\]
has the correct constant.
The weighted-average argument is also valid. Since the average is \(1/T_P(U)\), it implies both the upper estimate used in the lemma and inequality (1).
The honest mass reporting \(r\) is bounded by both \(d_r\) and \(c_r\). The subsequent minimum inequality and summation preserve the inequality direction. Finally, \(T_P(U)\leq1\).
Assessment: Correct, including the additive error and its applicability to arbitrary ties.
The denominator \(C=(1-t)d_D+t\) is strictly positive, including when \(d_D=0\). The assumed inequalities ensure nonnegative \(v_r\), and the displayed normalization calculation is correct.
The identity relating \(c_r\) and \(v_r\) is correct. It gives equal payoff \(1/T\) for outside signals at every report in \(U\). For an inside signal, its honest payoff is at least \(1/T\), while its other payoffs are at most \(1/T\).
Reports outside \(U\) have zero payoff under the prescribed strategy. Since \(1/T>0\), they cannot invalidate any prescribed best response.
The honest mass is exactly the mass of signals in \(U\): outside signals report only inside \(U\), so none reports honestly.
Assessment: Correct. The case \(U=S\) is also covered.
Binary PARTITION with positive integer weights is a valid NP-complete source problem. Its formulation and hardness are supported by the standard reductions recorded in [Cornell’s complexity notes](https://www.cs.cornell.edu/courses/cs6820/2022fa/Handouts/NPC4.pdf).
The constructed distributions normalize correctly:
\[
\sum_r P_r=1,\qquad
\sum_r d_r=\frac58+\frac12\cdot\frac34=1.
\]
For sets omitting \(0\), the conclusion \(F_{d,P}(U)=T_P(U)/2\leq3/8\) is correct. The intermediate inequality \(P_r/T_P(U)\geq P_r\) can be an equality when \(T_P(U)=1\); the proof uses a non-strict inequality there, so this causes no problem.
For sets containing \(0\), the expression \(f(T)\), its value \(7/10\) at \(T=2/5\), and both loss formulas are correct. In particular, the lower bound on the right-hand side of the peak holds throughout \(2/5\leq T\leq1\).
The integer representation of attainable \(T\) is correct. The dummy contribution prevents \(T=2/5\) whenever the dummy is included. Otherwise, equality is precisely the PARTITION condition.
For a no-instance, the spacing \(3/(20A)\) and the weaker slope \(1/8\) give exactly the claimed separation
\[
\gamma=\frac{3}{160A}.
\]
Sets omitting \(0\) also satisfy the bound, including the smallest possible positive total \(A\).
Assessment: Correct.
The choices of \(b\), \(b_g\), and \(d'\) are rational. The positivity estimates for \(d'\) are sufficient: only coordinate \(1\) decreases, and its original mass is at least \(p_{\min}/2\).
The three grid distributions are distinct. Each model has a listed payment giving strict honesty.
The second promise is verified for arbitrary common one-peer payment matrices, not merely matrices belonging to the displayed grid. The equality
\[
(1-t)d+t e_0=(1-t)d'+t e_1
\]
is correct. Identical peer-signal posteriors produce identical expected-payoff vectors under a common matrix, whereas strict honesty requires opposite strict preferences between reports \(0\) and \(1\).
The construction has the stated parameters \(R=3\), \(K=3\), \(\tau=m\), and \(J=3m\). With \(\epsilon=0\), omitting nonstrategic types from the positive support is consistent with the task.
Assessment: Both promises hold.
The estimate on \(\Delta(t_g,B)\) follows from the minimum-coordinate bound and \(t_g<1/2\).
If report \(0\) is unused, all its signal mass \(1/4\) is dishonest. If it is used, inequality (1), \(T_B(U)\leq1\), and \(B_0\geq5/8\) give the claimed lower bound \(c_0\geq1/2\).
At most \(1/4\) of that report mass can be honest. Therefore the dishonest mass is at least \(1/4\).
Assessment: Correct.
In the yes-case, Lemma 2 applies to the PARTITION support. The calculated honest mass is \(7/10\). The gate can be honest, and unanimous reporting of \(0\) is an equilibrium in the witness model: its payoff is positive, while every other report pays zero.
The expected-dishonesty bound is strictly below \(q\).
In the no-case, the perturbation estimate satisfies \(\Delta(t,P)<\gamma/4\). Thus every hard-model equilibrium under \(P\) exceeds the threshold after weighting by \(w\). Under either other payment, the gate penalty alone exceeds \(q\).
With \(H=1\), the mechanism’s payment randomization is independent of the model. Taking a convex combination therefore cannot overcome these uniform lower bounds. This correctly covers model-dependent equilibrium selection and arbitrary report fractions.
The encoding-size estimate is sound. The construction uses a constant number of arithmetic operations per rational entry, and the rational bit lengths are \(O(\log(A+1))\). The number of explicitly listed entries is \(O(m^2)\). The reduction is polynomial in the binary source length; it does not establish strong NP-hardness, and does not claim to.
Assessment: The many-one reduction establishes the claimed hardness.
For a fixed model and payment, support enumeration is complete. Requiring every allowed report to be optimal may include zero-fraction reports, but introduces no invalid equilibrium. Every actual equilibrium appears under its positive supports.
The reporting constraints and dishonest-mass objective are rational and linear. Separate minimization across models is valid because agents know their model. Payment randomization cannot improve the minimum for one cohort.
The enumeration count and running-time bound
\[
KR\,2^{m\tau}\operatorname{poly}(m,\tau,J,L)
\]
are valid conservative bounds.
The polynomial-size rational-certificate claim is applicable to the bounded rational feasibility problems described. Together with polynomial-time verification, it supports membership in NP and hence the one-cohort promise-problem completeness claim.
Minor issue 1 — explicit LP theorem and bit accounting. Sections 6.1–6.2 invoke polynomial-time rational linear programming without explicitly stating the theorem in terms of binary encoding length. The relevant standard results support the claims; see [MIT’s LP notes](https://courses.csail.mit.edu/6.854/21/Notes/n11-lp.html) and [algorithm notes](https://courses.csail.mit.edu/6.854/21/Notes/n14-LP_algorithms.html).
Minimum clarification: State the exact rational-LP complexity and certificate-size result being invoked, and explicitly confirm that the constructed LP encoding lengths are polynomial in the arguments of the displayed polynomial factors. This requires routine bit accounting, not new mathematics.
For a fixed policy and equilibrium, the reached public-history tree is finite: payments have finitely many choices, and each fixed history/payment/model/state combination determines an exact histogram.
After determinization, the node bound
\[
N=\sum_{h=0}^{H-1}J^h
\]
is valid.
The proposed partition enumeration correctly handles exact observations. Equality of histograms is affine equality. For different blocks, choosing a coordinate and sign captures inequality through strict linear constraints. Enumerating all such witnesses is complete.
Once partitions are fixed, the model-conditioned reach probabilities depend only on the selected outcome blocks and listed state weights. The objective is therefore linear. The common-slack test for strict feasibility is valid because each enumerated system has finitely many strict inequalities.
The exponent conservatively covers payment choices, reporting supports, partitions, and inequality witnesses.
Minor issue 2 — determinization justification is compressed. The backward-selection paragraph explains why current agents have no incentive concerning future cohorts, but does not explicitly verify that retaining branches preserves the relevant conditional model distributions and continuation equilibria.
Minimum clarification: Specify that positive-probability payment branches are retained with their prescribed equilibria, and justify preservation of the conditional model distributions and sequential best-response conditions after pruning. Address arbitrary assignments at unreachable histories. This is a routine clarification under the stated information structure.
The main complexity question is settled by the written reduction. The finite-agent asymptotic dishonesty statement is not used as a computational-complexity premise.
No counterexample or false central assertion was found. The two issues concern exposition of the auxiliary upper bounds and do not undermine the hardness result.
⟨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.