Answer: Universal strict truthful elicitation is possible.
Theorem 3 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateKnowledge-Free Peer Prediction has a strict truthful Perfect Bayesian equilibrium for the signal elicita- tion query for all information structures that satisfy second order stochastic relevance.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Let a latent event draw a mass vector \(q\in\Delta(\Theta)\) from an unknown prior \(\nu\), and let an atomless unit-mass society have signal types \(\theta\in\Theta\) with masses \(q_\theta\). Is there a mechanism independent of \(\nu\) that uses a measure-preserving peer matching, signal reports, and peer forecasts of \(q\), scored against the aggregate report masses, to make truthful reporting a strict Bayesian equilibrium for almost every agent whenever distinct signals satisfy the corresponding second-order relevance condition? In that condition, for every \(\theta\ne\theta'\), there is a peer signal \(z\) with \(\Pr[z\mid\theta]>0\) such that, if \(\Pr[\theta'\mid z]>0\), then \(\mathcal L(q\mid\theta,z)\ne\mathcal L(q\mid\theta',z)\); otherwise \(\mathcal L(q\mid\theta,z)\ne\mathcal L(q\mid z)\).
Let \(\Theta\) be a finite signal set of size \(m\geq2\). An atomless society has total mass \(1\); a latent event draws \(q\in\Delta(\Theta)\) from a common prior \(\nu\), known to agents but unknown to the designer, with \(\mathbb E_\nu[q_\theta]>0\) for every \(\theta\). Agents are risk-neutral, care only about payments, and initially observe only their own signal; identities convey no information.
Each realized society is represented by its support: the list of its \(\tau\) types with positive mass, each mass a binary rational. Thus \(\nu\) is supported on rational mass vectors; \(\tau\) denotes realized support size, not the number of possible types. Let \(L\) be this encoding's bit length; any running-time claims must use \(m,\tau,L\) and other explicit parameters. The encoding is not disclosed before reporting.
Peer matching is a randomized, type-blind, measure-preserving bijection \(T\), with \(a,T(a),T^{-1}(a)\) distinct almost everywhere and assignments hidden before initial reports. Conditional on \(q\), an agent's signal \(\theta\) and a matched peer's signal \(z\) have joint law \(\Pr[\theta,z\mid q]=q_\theta q_z\); all conditional probabilities below use this law and \(\nu\).
Agents first simultaneously report \(x_a\in\Theta\), then privately receive \(x_{T^{-1}(a)}\) and report a probability law \(p_a\) on \(\Delta(\Theta)\). Aggregate report masses \(\widehat q\) are revealed only after forecasts; an individual deviation does not change them. Admissible payments use only own and matched agents' messages and strictly proper scores \(R(p,\widehat q)\), with no verified signals or access to \(\nu\). Payments may be signed; conditional expected-payoff comparisons must be well defined.
Truthful play reports \(x_a=\theta_a\) and, upon receiving \(z\), forecasts \(\mathcal L(q\mid\theta_a,z)\). At an impossible incoming report, where \(\Pr[z\mid\theta_a]=0\), the prescribed belief and forecast are \(\mathcal L(q\mid\theta_a)\). Use strict perfect Bayesian equilibrium, with strictness at each information set for almost every agent.
Second-order relevance means that for every ordered pair \(\theta\ne\theta'\), some \(z\) satisfies \(\Pr[z\mid\theta]>0\), and: if \(\Pr[\theta'\mid z]>0\), then \(\mathcal L(q\mid\theta,z)\ne\mathcal L(q\mid\theta',z)\); otherwise \(\mathcal L(q\mid\theta,z)\ne\mathcal L(q\mid z)\).
Is there a single admissible mechanism, independent of \(\nu\), admitting a strict truthful perfect Bayesian equilibrium for almost every agent for every \(\nu\) satisfying second-order relevance, or is such universal elicitation impossible?
For finite populations with \(n\geq3\), Knowledge-Free Peer Prediction admits a strict truthful perfect Bayesian equilibrium under second-order stochastic relevance without designer knowledge of the common prior. [Zhang and Chen](https://www.ifaamas.org/Proceedings/aamas2014/aamas/p245.pdf)
Bayesian Truth Serum establishes truthful Nash equilibrium for a countably infinite population under common-prior and distinct-posterior assumptions, eliciting expected frequencies rather than peer-conditioned probability laws. [Prelec](https://nel.mit.edu/wp-content/uploads/2016/10/bts.pdf) No result settling the precise atomless protocol above was verified.
Theorem. For every finite signal set \(\Theta\), there is a mechanism independent of \(\nu\) that admits the prescribed strict truthful perfect Bayesian equilibrium for every prior satisfying second-order relevance.
The payment is the sum of an agent’s own forecast score and the forecast score of the peer who receives that agent’s initial report. This follows the payment structure of [Zhang and Chen’s Knowledge-Free Peer Prediction mechanism, Section 4](https://www.ifaamas.org/Proceedings/aamas2014/aamas/p245.pdf). Below, we prove its validity for the stated atomless protocol, including bounded payments and the prescribed beliefs at impossible incoming reports.
Write \(X=\Delta(\Theta)\), with its Borel sigma-algebra, and identify its coordinates with \(\{1,\ldots,m\}\). Reports are Borel probability measures on \(X\).
Enumerate the countable family of sets
\( A_t=\{u\in X:u_i\leq t_i\text{ for every }i\}, \qquad t\in(\mathbb Q\cap[0,1])^m, \)
as \((A_k)_{k\geq1}\). This family contains \(X\), is closed under finite intersections, and generates the Borel sigma-algebra of \(X\). Indeed, setting all thresholds except one equal to \(1\) gives every rational coordinate sublevel set; those sets generate the relative topology’s Borel sigma-algebra.
For a reported law \(p\) and outcome \(u\in X\), define
\( R(p,u)= \sum_{k=1}^{\infty}2^{-k} \left(2p(A_k)\mathbf 1_{A_k}(u)-p(A_k)^2\right). \)
Each summand’s parenthesized expression lies in \([-1,1]\). Consequently, the series converges absolutely and uniformly, and \(|R(p,u)|\leq1\).
For probability laws \(P,p\), let
\( S(P,p)=\int_X R(p,u)\,P(du). \)
Uniform absolute convergence permits integration term by term. Subtraction gives
\( S(P,P)-S(P,p) = \sum_{k=1}^{\infty}2^{-k}\bigl(P(A_k)-p(A_k)\bigr)^2. \)
Denote this quantity by \(D(P,p)\). It is nonnegative. Moreover, if it equals zero, \(P\) and \(p\) agree on every \(A_k\). The uniqueness theorem for probability measures on a generating intersection-closed family then implies \(P=p\). Thus
\( D(P,p)>0\quad\text{whenever }P\neq p, \)
so \(R\) is strictly proper on the entire report space. Its boundedness ensures that every conditional expected-payoff comparison below is finite.
Use the matching \(T\) from the question and retain exactly the prescribed two reporting stages.
After forecasts and aggregate reports are available, pay agent \(a\)
\( U_a=R(p_a,\widehat q)+R(p_{T(a)},\widehat q). \)
This payment uses only the agent’s forecast, the matched recipient’s forecast, and strictly proper scores against the aggregate report masses. It requires no knowledge of \(\nu\).
Under truthful initial reports, \(\widehat q=q\). A unilateral deviation leaves this equality intact, because an individual has zero mass.
Fix an agent outside the null set of matching exceptions, and write
\( h=T^{-1}(a),\qquad b=T(a). \)
These three agents are distinct. The initial report of \(a\) is delivered to \(b\); the incoming report of \(a\) comes from \(h\).
For every signal \(\theta\), define
\( \lambda_\theta=\mathbb E_\nu[q_\theta]>0, \qquad M_{\theta z}=\mathbb E_\nu[q_\theta q_z]. \)
The stipulated signal law gives
\( \Pr[z\mid\theta]=\frac{M_{\theta z}}{\lambda_\theta}. \)
For a Borel set \(B\subseteq X\), define
\( P_\theta(B) = \frac{\int_B q_\theta\,\nu(dq)}{\lambda_\theta}. \)
When \(M_{\theta z}>0\), also define
\( P_{\theta z}(B) = \frac{\int_B q_\theta q_z\,\nu(dq)}{M_{\theta z}}. \)
These are respectively \(\mathcal L(q\mid\theta)\) and \(\mathcal L(q\mid\theta,z)\). In particular, \(P_{\theta z}=P_{z\theta}\).
Define the forecast function
\( F(\theta,z)= \begin{cases} P_{\theta z},&M_{\theta z}>0,\\ P_\theta,&M_{\theta z}=0. \end{cases} \)
The proposed strategy is:
At every incoming report with positive conditional probability, beliefs follow Bayes’ rule. At an impossible incoming report, retain the conditional law \(P_\theta\), as required by the question.
These off-path beliefs can regard the predecessor’s message as an uninformative deviation while retaining truthful reporting by everyone else. Such histories are compatible with the protocol, and a predecessor’s individual deviation leaves aggregate masses equal to \(q\). Bayes’ rule imposes no restriction at these zero-probability information sets.
After an agent’s own initial misreport, the same forecasting prescription applies: the agent remembers their true signal, and their misreport does not affect the predecessor’s already submitted report.
Fix own signal \(\theta\), own earlier report \(x\), and incoming report \(z\), including an impossible incoming report.
The agent’s belief about the scoring outcome \(\widehat q=q\) is \(F(\theta,z)\). Changing \(p_a\) affects only the first term of
\( U_a=R(p_a,q)+R(p_b,q). \)
Indeed, forecasts are simultaneous, and \(b\)’s forecast depends on \(b\)’s own signal and the initial report \(x\), rather than on \(p_a\).
Therefore the conditional expected payoff difference between the prescribed forecast and any alternative \(p\) is exactly
\( S(F(\theta,z),F(\theta,z)) - S(F(\theta,z),p) = D(F(\theta,z),p). \)
This difference is strictly positive whenever \(p\neq F(\theta,z)\). The prescribed forecast is consequently the unique optimal action at every forecasting information set, including those following an initial misreport or an impossible incoming report.
Fix true signal \(\theta\), and suppose all other agents follow the proposed strategy.
Changing the initial report affects neither \(q\) nor the predecessor’s initial report. Thus the agent’s information available for forecasting has the same distribution under every initial report.
By strict propriety, the maximum expected own forecast score is
\( V_\theta = \sum_{\substack{w\in\Theta\\M_{\theta w}>0}} \frac{M_{\theta w}}{\lambda_\theta} S(P_{\theta w},P_{\theta w}). \)
This value is attainable after any initial report by following the prescribed forecasting strategy. No alternative continuation can yield a larger expected own forecast score.
Suppose the initial report is \(x\). If recipient \(b\)’s true signal is \(z\), its forecast is \(F(z,x)\). Under the deviating agent’s actual signal \(\theta\), the conditional law of \(q\) given the recipient’s signal \(z\) is \(P_{\theta z}\), whenever \(M_{\theta z}>0\).
Hence the expected recipient-score component is
\( I_\theta(x) = \sum_{\substack{z\in\Theta\\M_{\theta z}>0}} \frac{M_{\theta z}}{\lambda_\theta} S(P_{\theta z},F(z,x)). \)
For a truthful report, \(F(z,\theta)=P_{\theta z}\) on every term in this sum. Therefore
\( I_\theta(\theta)-I_\theta(x) = \sum_{\substack{z\in\Theta\\M_{\theta z}>0}} \frac{M_{\theta z}}{\lambda_\theta} D(P_{\theta z},F(z,x)). \)
Every term is nonnegative. If \(x\neq\theta\), second-order relevance provides a signal \(z\) with \(M_{\theta z}>0\) satisfying one of two cases:
In either case, the corresponding divergence is strictly positive and has positive weight. Consequently,
\( I_\theta(\theta)>I_\theta(x) \qquad\text{for every }x\neq\theta. \)
Truthful reporting with optimal forecasting yields \(V_\theta+I_\theta(\theta)\). Any deviation beginning with report \(x\neq\theta\), even with an arbitrary subsequent forecasting strategy, yields at most \(V_\theta+I_\theta(x)\), which is strictly smaller.
Thus the true signal is the unique optimal initial report. Randomization cannot improve this conclusion: any positive probability of a false initial report causes a strictly positive expected loss.
The assessment satisfies Bayes’ rule wherever applicable, uses the specified beliefs at impossible incoming reports, and gives a unique optimal action at every information set. It is therefore a strict truthful perfect Bayesian equilibrium for almost every agent.
The mechanism and scoring rule are independent of \(\nu\). Payments lie in \([-2,2]\), so no integrability qualification is needed. The proof actually accommodates arbitrary Borel priors on \(\Delta(\Theta)\); rational realized mass vectors are a permitted special case.
This establishes existence in the stated report space of probability laws. No finite-time implementation claim is made: the task specifies an encoding for realized societies, but does not specify finite encodings or evaluation procedures for forecast laws.
⟨structured verdict parsed — rendered above⟩
Result: proved. The proposed mechanism resolves the existence question as stated. Its scoring rule is bounded and strictly proper, its payments are admissible, and second-order relevance supplies a strictly positive loss for every false initial report. The argument also verifies strict forecasting incentives at the prescribed off-path information sets.
No major or minor mathematical issues were found. No additional clarification is required for the stated existence result.
The mechanism is
\[
U_a=R(p_a,\widehat q)+R(p_{T(a)},\widehat q).
\]
It uses the agent’s forecast, the matched recipient’s forecast, and scores against the aggregate report vector, exactly within the permitted payment structure. Neither the scoring rule nor the payment formula depends on \(\nu\).
The assertion \(\widehat q=q\) under truthful play and under a unilateral deviation follows from the task’s explicit assumption that an individual deviation does not change aggregate masses.
The attribution of the two-score payment structure to [Zhang and Chen, Section 4](https://www.ifaamas.org/Proceedings/aamas2014/aamas/p245.pdf) is accurate. The prover supplies its own argument for the atomless protocol, so it does not rely on transferring the finite-population equilibrium theorem without checking its hypotheses.
The family \((A_k)\) is countable, contains \(X\), and is closed under finite intersections: intersecting two threshold sets takes the coordinatewise minimum of their rational thresholds.
It generates the Borel sigma-algebra of \(X\). In particular, choosing all but one threshold equal to \(1\) supplies the rational sublevel sets for each coordinate. Those coordinate sets generate the relative Borel sigma-algebra.
For \(r=p(A_k)\), the parenthesized summand is either
\[
-r^2
\]
or
\[
2r-r^2.
\]
Since \(r\in[0,1]\), both lie in \([-1,1]\). The weights sum to \(1\), so the claimed uniform absolute convergence and bound \(|R(p,u)|\leq1\) are correct. For fixed \(p\), the score is Borel measurable in \(u\).
Termwise integration is justified by this uniform absolute bound. Rechecking the subtraction gives precisely
\[
S(P,P)-S(P,p)
=
\sum_{k=1}^{\infty}2^{-k}\bigl(P(A_k)-p(A_k)\bigr)^2.
\]
Every weight is positive. Thus zero divergence implies agreement on every \(A_k\). The probability-measure uniqueness theorem applies because the family is intersection-closed and generates the entire Borel sigma-algebra; both measures have the same total mass. Consequently, the score is strictly proper on the whole stated report space.
There is no integrability gap: all scores are bounded.
The definitions
\[
\lambda_\theta=\mathbb E_\nu[q_\theta],
\qquad
M_{\theta z}=\mathbb E_\nu[q_\theta q_z]
\]
give the stated conditional probabilities and posterior laws under the stipulated matched-pair signal law.
All divisions have valid denominators:
The symmetry \(P_{\theta z}=P_{z\theta}\) follows directly from the symmetric product in both numerator and denominator.
The definition of \(F(\theta,z)\) matches the required prescription at both possible and impossible incoming reports. In particular, when \(M_{\theta z}=0\), it uses \(P_\theta\), rather than an undefined two-signal posterior.
At positive-probability histories, the displayed beliefs follow Bayes’ rule. At impossible incoming reports, the proposed law \(P_\theta\) is expressly required by the task, and ordinary perfect Bayesian equilibrium imposes no Bayesian updating restriction at those zero-probability histories.
The proposed interpretation of an impossible report as an uninformative individual deviation is compatible with the protocol: such a deviation does not change the aggregate scoring outcome.
The continuation following an agent’s own false initial report is also consistent. The agent retains their true signal, and their report does not affect the predecessor’s already submitted message.
At a forecasting information set, changing \(p_a\) changes only \(R(p_a,q)\). The recipient’s forecast depends on its own signal and the already submitted initial report, and forecasts are simultaneous. Therefore the conditional payoff difference is exactly
\[
D(F(\theta,z),p).
\]
Strict propriety makes this positive for every distinct forecast \(p\). This verifies unique optimality at every forecasting information set, including those following an initial misreport or an impossible incoming report.
The agent’s own optimal forecast value \(V_\theta\) is correctly computed. The incoming-report distribution and the aggregate outcome are unaffected by the agent’s initial report, so this value is available after every initial report.
For the recipient’s score, conditional on the agent’s actual signal \(\theta\) and the recipient’s signal \(z\), the outcome law is \(P_{\theta z}\). Thus the formula for \(I_\theta(x)\) uses the correct weights, outcome distributions, and recipient forecasts.
For a truthful initial report,
\[
F(z,\theta)=P_{\theta z}
\]
on every positive-weight term. The resulting difference
\[
I_\theta(\theta)-I_\theta(x)
=
\sum_{z:M_{\theta z}>0}
\frac{M_{\theta z}}{\lambda_\theta}
D(P_{\theta z},F(z,x))
\]
is therefore correct.
The application of second-order relevance respects its ordered-pair quantifiers. For each fixed \(x\neq\theta\), it supplies a witness \(z\) with positive weight. Both branches are handled correctly:
Hence at least one divergence is strictly positive, and all remaining terms are nonnegative. This establishes the claimed strict initial-report inequality.
Arbitrary forecasting continuations cannot defeat this comparison: they cannot exceed \(V_\theta\) in the own-score component or change the recipient’s forecast. Randomized false initial reports likewise produce a strictly positive expected loss.
No conditional independence assumption involving all three agents is used; the specified pair laws suffice for the separate expected-score calculations.
The proof establishes sequential optimality at each information set, Bayesian consistency wherever applicable, the prescribed impossible-report beliefs, and strictness for agents whose matching neighbors are distinct. The matching assumption makes this an almost-everywhere statement, as required.
The payment bound \([-2,2]\) follows from the two score bounds. Rational realized mass vectors cause no additional restriction on the argument.
The output establishes mathematical existence, with no finite-time implementation or complexity claim. Its infinite scoring series is not a defect under the stated admissibility conditions. Accordingly, the requested complexity field is marked unresolved solely because no complexity classification is established.
⟨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.