Answer: \(\Delta^*(\nu)=\max\{G_{\mathrm I},G_{\mathrm{II}}\}>0\), with the explicit quantities defined above. The supremum is attained exactly when \(z_0>H\) or \(G_{\mathrm I}\geq G_{\mathrm{II}}\). Deciding \(\Delta^*(\nu)>g\) is in \(\mathrm P\). Every admitted prior admits arbitrarily near-optimal focal mechanisms with penalty \(c=1\); an exactly optimal focal mechanism exists precisely when the supremum is attained.
Theorem 3.5 — class: other
Given a rational finite-support prior \(\nu\) over latent qualities \(p\in(0,1)\), with \(\operatorname{Var}_{\nu}(p)>0\) and \(\mathbb{E}_{\nu}[p]\ne 1/2\), each realized atomless society has signal-type masses \(\mu_1=p\) and \(\mu_0=1-p\). Choose a normalized strictly proper peer-scoring rule and a penalty triggered by unanimous aggregate reports that maximize truth-telling's expected payoff gap over other informative atomless Bayesian Nash equilibria, and determine whether the penalty makes truth-telling strictly higher-paying than every other equilibrium, including equilibria with identity-based splits at indifference.
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. Here \(m=\tau=2\), with signal masses \(\mu_1=p\), \(\mu_0=1-p\).
The common prior \(\nu\) has \(k\) rational support points in \((0,1)\), positive binary-rational weights summing to \(1\), \(\operatorname{Var}_{\nu}(p)>0\), and \(\bar p=\mathbb E_{\nu}[p]\ne\tfrac12\). Agents observe only their own binary signal; identity provides no additional information. Set \(q_1=\mathbb E_{\nu}[p^2]/\bar p\) and \(q_0=\mathbb E_{\nu}[p(1-p)]/(1-\bar p)\).
Identities form a unit atomless probability space \((I,\lambda)\). A strategy is a measurable family \(x_b(i)\in[0,1]\) of probabilities of reporting \(1\) after signal \(b\); define \(a_b=\int_I x_b(i)\,d\lambda(i)\) and the realized report mass \(r_x(p)=(1-p)a_0+pa_1\). Profiles are identified up to null sets; allow private mixing and identity-dependent choices at indifference, without a public correlating device.
Choose a real payment matrix \(h_{z,a}=S(z,q_a)\) induced by a strictly proper binary scoring rule \(S\), normalized by \(\min_{z,a}h_{z,a}=0\), \(\max_{z,a}h_{z,a}=1\). An agent reporting \(a\) receives \(h_{Z,a}\), where, conditional on \(p\), the independently sampled peer report satisfies \(Z\sim\operatorname{Bernoulli}(r_x(p))\).
Optionally subtract a finite penalty \(c\ge0\) whenever \(r_x(p)\in\{0,1\}\); an individual deviation leaves this aggregate unchanged. Write \(U_i^c(x)\) for identity \(i\)'s ex ante expected payment, averaging over the prior, its signal, and private randomization. Bayesian Nash equilibrium requires best responses conditional on each signal for almost every identity.
Truth-telling \(T\) has \(x_0=0,x_1=1\). Only the two globally constant profiles \(\mathbf0,\mathbf1\) are called uninformative. Let \(\mathcal E_h\) be the equilibria without penalty and define \(\Delta_h=\inf_{x\in\mathcal E_h\setminus\{T,\mathbf0,\mathbf1\}}\operatorname*{ess\,inf}_{i\in I}(U_i^0(T)-U_i^0(x))\), \(\Delta^*(\nu)=\sup_h\Delta_h\). Truth-telling is focal if \(U_i^c(T)>U_i^c(x)\) for almost every identity in every other equilibrium of the penalized mechanism.
What is \(\Delta^*(\nu)\), and for which priors is its supremum attained rather than only approached?
For a binary-rational threshold \(g\), is deciding \(\Delta^*(\nu)>g\) in \(\mathrm P\) or \(\mathrm{NP}\)-hard?
For which priors can an optimal, or arbitrarily near-optimal, payment matrix be paired with a finite unanimity penalty making truth-telling focal, and for which is this impossible?
State running times in \(m,\tau,k,L\), where \(L\) is the total binary input length, including any threshold or requested accuracy.
For finite societies with binary, symmetric, positively correlated, signal-asymmetric priors, normalized peer payments have an explicitly characterized optimal informative-equilibrium gap, sometimes only a supremum; a unanimity penalty makes truth-telling focal when unanimous signals are sufficiently unlikely. [Kong, Schoenebeck, and Ligett](https://arxiv.org/html/1603.07319)
A continuum population has also been used to study peer-prediction replicator dynamics with finite groups sampled for tasks; that model does not establish this atomless design result. No result settling this exact target was located. [Measuring Performance of Peer Prediction Mechanisms Using Replicator Dynamics](https://www.ijcai.org/Proceedings/16/Papers/371.pdf)
The optimum depends only on the first two moments of the prior. It is always positive under the stated assumptions. Its supremum need not be attained, but arbitrarily near-optimal matrices can always be paired with a finite unanimity penalty making truth-telling focal.
Here is an explicit formula and attainment criterion.
First relabel the signals and reports, if necessary, so that the mean exceeds one half. Thus set
\[ (u,l,v)= \begin{cases} (\bar p,q_0,q_1),&\bar p>\tfrac12,\\ (1-\bar p,1-q_1,1-q_0),&\bar p<\tfrac12. \end{cases} \]
All formulas below use these relabeled quantities. They satisfy
\[ 0<l<u<v<1,\qquad u=\frac{l}{1-v+l}>\frac12,\qquad l+v>1. \]
Define
\[ \alpha=\frac{u}{v},\qquad \beta=\frac{1-u}{1-l},\qquad f=2u-1,\qquad d=v-l,\qquad H=\max\{l,1-l\}. \]
In particular, \(\alpha>\beta>0\). Set
\[ z_0= \frac{\sqrt{\alpha}\,v+\sqrt{\beta}\,l} {\sqrt{\alpha}+\sqrt{\beta}}, \qquad J(t)= \frac{\alpha\beta d(v-t)(t-l)} {t\bigl(\alpha(v-t)+\beta(t-l)\bigr)}, \]
and define the second candidate value by
\[ G_{\mathrm{II}}=J\bigl(\max\{H,z_0\}\bigr). \]
For the first candidate, set \(G_{\mathrm I}=0\) when \(l\geq\tfrac12\). When \(l<\tfrac12\), define
\[ z_{\mathrm I} = l+ \frac{\sqrt{f^2+\beta f(1-2l)}-f}{\beta}, \qquad G_{\mathrm I} = \frac{\beta(z_{\mathrm I}-l)^2}{1-z_{\mathrm I}}. \]
Then
\[ \boxed{\Delta^*(\nu)=\max\{G_{\mathrm I},G_{\mathrm{II}}\}>0.} \]
The exact attainment criterion is
\[ \boxed{ \text{The supremum is attained} \iff z_0>H\ \text{or}\ G_{\mathrm I}\geq G_{\mathrm{II}}. } \]
Consequently:
The proof below concerns the specified atomless model directly. The [finite-population analysis of Kong, Schoenebeck, and Ligett](https://arxiv.org/html/1603.07319) is useful context, but is not used as a theorem establishing these conclusions.
Write \(w=1-u\). Positive variance gives
\[ v-u=\frac{\operatorname{Var}_{\nu}(p)}{u}>0, \qquad u-l=\frac{\operatorname{Var}_{\nu}(p)}{w}>0. \]
Moreover,
\[ uv+wl=u, \]
because the left-hand side is \(\mathbb E[p^2]+\mathbb E[p(1-p)]\). Hence
\[ u(1-v)=wl,\qquad u=\frac{l}{1-v+l}. \]
Relabeling sends a matrix \(h\) to \(h'_{z,a}=h_{1-z,1-a}\), preserves normalization, and preserves every equilibrium payoff gap. It also preserves strict propriety by replacing \(S(z,q)\) with \(S(1-z,1-q)\). Thus the reduction to \(u>\tfrac12\) loses nothing.
For an arbitrary admissible matrix, let its expected payment after reporting \(a\), when the peer reports one with probability \(y\), be
\[ L_a(y)=(1-y)h_{0,a}+yh_{1,a}. \]
Strict propriety at the distinct forecasts \(l,v\) implies
\[ L_0(l)>L_1(l),\qquad L_1(v)>L_0(v). \]
Their difference is affine, so necessarily
\[ L_1(y)-L_0(y)=D(y-t) \]
for some \(D>0\) and \(l<t<v\). Write
\[ L_0(y)=A-Dsy \]
for a real parameter \(s\). Before normalization, the four entries, after subtracting \(A\) and dividing by \(D\), are
\[ \begin{pmatrix} 0&-t\\ -s&1-s-t \end{pmatrix}. \]
Later we prove that every matrix with a positive gap has \(l<s<v\). For such parameters, put
\[ C=\max\{s,t\},\qquad R=\max\{s,1-s,t,1-t\}. \]
The uniquely normalized matrix with these parameters is
\[ h(s,t)= \frac1R \begin{pmatrix} C&C-t\\ C-s&C+1-s-t \end{pmatrix}. \tag{1} \]
Indeed, the minimum of the four unnormalized entries is \(-C\), and their range is
\[ C+\max\{0,1-s-t\}=R. \]
Thus normalization forces \(A=C/R\) and \(D=1/R\).
There is no additional scoring-rule restriction on \(s\) or \(t\) beyond \(l<t<v\).
To verify this, choose a bounded, strictly positive density \(\rho\) on \([l,v]\) satisfying
\[ \int_l^v\rho(q)\,dq=D, \qquad \int_l^v q\rho(q)\,dq=Dt. \tag{2} \]
Such a density exists: choose two short intervals centered respectively at \(a<t<b\), both contained in \((l,v)\). Add a sufficiently small positive uniform component on \([l,v]\). The remaining two component weights can then be chosen positive so that the overall mean is exactly \(t\).
Construct a continuously differentiable, strictly convex function \(G\) with
\[ G(l)=A-Dsl,\qquad G'(l)=-Ds, \]
and with curvature density \(\rho\) on \([l,v]\). Extend it to \([0,1]\) using positive constant curvature outside this interval. Equation (2) gives
\[ G'(v)=D(1-s), \qquad G(v)-vG'(v)=A-Dt. \]
Now define
\[ S(0,q)=G(q)-qG'(q),\qquad S(1,q)=G(q)+(1-q)G'(q). \]
For a true probability \(p\), the expected score from forecast \(q\) is
\[ G(q)+G'(q)(p-q), \]
which is strictly smaller than \(G(p)\) whenever \(q\ne p\), by strict convexity. Therefore \(S\) is strictly proper and induces exactly the required two payment columns.
For an aggregate strategy \((a_0,a_1)\), the conditional probabilities of a peer report of one are
\[ y_0=a_0+(a_1-a_0)l,\qquad y_1=a_0+(a_1-a_0)v. \tag{3} \]
Every identity faces the same conditional best-response problem. Reporting one is strictly preferable when \(y_b>t\), reporting zero is strictly preferable when \(y_b<t\), and every private mixture is optimal when \(y_b=t\).
This gives the following complete list of equilibrium aggregates:
| Equilibrium | Aggregate \((a_0,a_1)\) | Existence condition |
|---|---|---|
| \(\mathbf0\) | \((0,0)\) | Always |
| \(\mathbf1\) | \((1,1)\) | Always |
| \(T\) | \((0,1)\) | Always |
| \(T_0\) | \((0,t/v)\) | Always |
| \(T_1\) | \(((t-l)/(1-l),1)\) | Always |
| \(Q\) | \((t,t)\) | Always |
| \(F_0\) | \((t/(1-l),0)\) | \(t\leq1-l\) |
| \(F_1\) | \((1,(t-1+v)/v)\) | \(t\geq1-v\) |
| \(F\) | \((1,0)\) | \(1-v\leq t\leq1-l\) |
Boundary coincidences in this table represent the same aggregate.
For completeness, if \(a_1>a_0\), then \(y_1>y_0\). The best-response conditions yield \(T\), or one of \(T_0,T_1\) when one signal is indifferent. If \(a_1<a_0\), then \(y_0>y_1\), yielding \(F,F_0,F_1\). If \(a_1=a_0=a\), both conditional probabilities equal \(a\), so equilibrium requires \(a=0\), \(a=1\), or \(a=t\). These are exactly \(\mathbf0,\mathbf1,Q\).
Because \(u>\tfrac12\), we have \(l>1-v\). Thus \(F_1\) always exists, while \(F_0\) and \(F\) exist exactly when \(t\leq1-l\).
Every aggregate listed is realized by an equilibrium profile, for example by using the same private mixing probabilities at every identity. Conversely, identity-dependent choices at indifference introduce no additional aggregates.
Crucially, they introduce no additional equilibrium payoffs either. At equilibrium, every identity receives the conditional best-response payment for each signal, even if identities choose different mixtures at indifference. Hence every identity has the same ex ante payoff.
Let
\[ M_x=wa_0+ua_1. \]
Using (3), that common equilibrium payoff is
\[ U(x)=A+D\left[-sM_x+w(y_0-t)_++u(y_1-t)_+\right], \tag{4} \]
where \((z)_+=\max\{z,0\}\). Truth-telling has
\[ U(T)=A+D[-su+u(v-t)]. \tag{5} \]
Therefore the essential infimum over identities in the question equals the ordinary payoff difference. The infinitely many profiles at indifference reduce to the finite table above.
The two equilibria \(T_0,T_1\) exist for every admissible matrix. Substituting into (4)–(5) gives their gaps as
\[ U(T)-U(T_0)=D\frac{u}{v}(v-t)(v-s), \]
and, using \(u(1-v)=wl\),
\[ U(T)-U(T_1)=D\frac{w}{1-l}(t-l)(s-l). \]
Thus a positive gap necessarily requires
\[ l<s<v. \tag{6} \]
We will exhibit positive gaps, so matrices violating (6) cannot affect the optimum.
For matrices satisfying (6), define the gap numerators
\[ N_0=\alpha(v-s)(v-t),\qquad N_1=\beta(s-l)(t-l). \]
Because \(D=1/R\), each equilibrium gap is its numerator divided by \(R\). Direct substitution into (4) gives:
| Equilibrium | Gap numerator |
|---|---|
| \(T_0\) | \(N_0\) |
| \(T_1\) | \(N_1\) |
| \(Q\) | \(N_0+(1-\alpha)st\) |
| \(F_0\) | \(N_1+\dfrac{ud}{1-l}(1-s-t)\) |
| \(F_1\) | \(N_1+(\alpha-\beta)(1-s)(1-t)\) |
| \(F\) | \(f(1-s-t)\) |
The coefficient signs needed below follow from
\[ 0<\alpha<1, \qquad \alpha-\beta = \frac{fd}{v(1-l)}>0. \tag{7} \]
Consequently, \(Q\) and \(F_1\) never determine the minimum gap.
If \(t\leq1-l\), the equilibrium \(F\) exists. A positive gap then requires \(s+t<1\). Under that condition, \(F_0\)'s gap is larger than \(T_1\)'s. Hence every positive gap in this region is
\[ \Delta_{h(s,t)} = \frac{\min\{N_0,N_1,f(1-s-t)\}}{R}. \tag{8} \]
If \(t>1-l\), both \(F\) and \(F_0\) disappear, and
\[ \Delta_{h(s,t)} = \frac{\min\{N_0,N_1\}}{R}. \tag{9} \]
These two regions account for the two candidate values.
Consider \(t\leq1-l\) and a positive gap. Necessarily \(s+t<1\). Put
\[ z=\frac{s+t}{2}. \]
Then \(l<z<\tfrac12\). Replacing \((s,t)\) with \((z,z)\) remains in this region.
At fixed \(s+t\), both products
\[ (v-s)(v-t),\qquad (s-l)(t-l) \]
increase when \(s,t\) are replaced by their average, because the product \(st\) increases. The numerator \(f(1-s-t)\) is unchanged. Also,
\[ R=1-\min\{s,t\}\geq1-z. \]
Since the gap is positive, these facts prove that averaging cannot decrease it.
Thus the first region reduces to \(s=t=z\), with \(l<z<\tfrac12\). Its gap is
\[ \frac{ \min\{\alpha(v-z)^2,\ \beta(z-l)^2,\ f(1-2z)\} }{1-z}. \tag{10} \]
The equality of the first two numerator terms occurs at \(z=z_0\). By (7),
\[ z_0>\frac{v+l}{2}>\frac12. \]
Therefore, throughout the domain of (10),
\[ \alpha(v-z)^2>\beta(z-l)^2. \]
It remains to maximize
\[ \min\left\{ \frac{\beta(z-l)^2}{1-z}, \frac{f(1-2z)}{1-z} \right\}. \]
The first function is strictly increasing on \((l,\tfrac12)\); the second is strictly decreasing. At \(z=l\), the first is zero and the second positive. At \(z=\tfrac12\), the second is zero and the first positive. Their unique intersection therefore gives the maximum.
Writing \(x=z-l\), the intersection equation is
\[ \beta x^2+2fx=f(1-2l), \]
whose positive root gives exactly \(z_{\mathrm I}\) stated above. In particular,
\[ l<z_{\mathrm I}<\frac12. \]
The first-region optimum is \(G_{\mathrm I}\), and it is attained.
When \(l\geq\tfrac12\), this region is empty because \(t>l\) and \(t\leq1-l\) are incompatible.
Here
\[ t>H=\max\{l,1-l\}. \]
For every \(s\in(l,v)\), this implies \(s+t>1\), so
\[ R=\max\{s,t\}. \]
If \(s>t\), replacing both parameters by their average remains feasible: the new threshold exceeds the old threshold and therefore still exceeds \(H\). Both numerator products increase and the denominator decreases. Hence it suffices to consider \(s\leq t\), where \(R=t\).
For fixed \(t\), \(N_0\) decreases strictly with \(s\), while \(N_1\) increases strictly. Their intersection is
\[ s(t)= \frac{\alpha v(v-t)+\beta l(t-l)} {\alpha(v-t)+\beta(t-l)}. \tag{11} \]
This lies strictly between \(l\) and \(v\). Moreover,
\[ s(t)\leq t\iff t\geq z_0. \]
Thus the largest gap for a fixed threshold is
\[ \begin{cases} \dfrac{\beta(t-l)^2}{t},&t\leq z_0,\\[6pt] J(t),&t\geq z_0. \end{cases} \tag{12} \]
Indeed, when \(t<z_0\), the intersection lies above the permitted interval \(s\leq t\), and the maximum occurs at \(s=t\). When \(t\geq z_0\), it occurs at (11). Substituting (11) yields the displayed formula for \(J\).
The first branch in (12) is strictly increasing, since
\[ \frac{d}{dt}\left(\frac{\beta(t-l)^2}{t}\right) = \beta\left(1-\frac{l^2}{t^2}\right)>0. \]
To study the second branch, observe that
\[ \frac1{J(t)} = \frac1{\alpha\beta d} \left( \frac{\alpha t}{t-l} + \frac{\beta t}{v-t} \right). \]
The derivative of the expression in parentheses is
\[ -\frac{\alpha l}{(t-l)^2} +\frac{\beta v}{(v-t)^2}. \]
It vanishes once, at
\[ t_*= \frac{\sqrt{\alpha l}\,v+\sqrt{\beta v}\,l} {\sqrt{\alpha l}+\sqrt{\beta v}}. \]
Since \(l<v\), the relative weight on \(v\) here is smaller than its relative weight in \(z_0\). Therefore \(t_*<z_0\). The derivative is positive for \(t>t_*\), proving that \(J\) is strictly decreasing on \([z_0,v)\).
It follows that:
These statements prove the formula for \(G_{\mathrm{II}}\).
Also, \(H<v\): both \(l<v\) and \(1-l<v\) hold. Since \(z_0\in(l,v)\), all factors defining \(G_{\mathrm{II}}\) are positive. Thus
\[ G_{\mathrm{II}}>0. \]
Combining the two regions proves both the formula for \(\Delta^*(\nu)\) and the claimed attainment criterion.
For a diagonal parameter choice \(s=t=z\), equation (1) becomes
\[ h(z,z)= \frac1{\max\{z,1-z\}} \begin{pmatrix} z&0\\ 0&1-z \end{pmatrix}. \tag{13} \]
Thus:
In the last case, \(H=1-l\). At the limiting threshold, \(F\) reappears. Because \(s(H)>l\),
\[ f(1-s(H)-H)<0. \]
Thus the limiting matrix itself has a negative gap against \(F\). This explains why taking the limit of the matrices does not produce an optimal matrix.
For example, take equal prior weights at
\[ p=\frac38,\qquad p=\frac{21}{32}. \]
Then
\[ u=\frac{33}{64},\quad l=\frac{471}{992},\quad v=\frac{195}{352},\quad H=\frac{521}{992}, \]
and
\[ \alpha=\frac{121}{130},\qquad \beta=\frac{961}{1042}. \]
Direct rational comparison gives
\[ \alpha(v-H)^2<\beta(H-l)^2, \]
which is equivalent to \(z_0<H\). Moreover,
\[ G_{\mathrm{II}}=\frac{365025}{142487248}>\frac1{500}, \]
whereas, since \(z_{\mathrm I}<\tfrac12\),
\[ G_{\mathrm I} < 2\beta\left(\frac12-l\right)^2 = \frac{625}{533504} < \frac1{800}. \]
Hence this prior has a strictly nonattained supremum.
Conversely, every relabeled prior with \(l\geq\tfrac12\) has an attained optimum, because then \(H=l<z_0\).
For every support point \(p\in(0,1)\),
\[ r_x(p)=(1-p)a_0+pa_1 \]
is a convex combination with both coefficients strictly positive. Consequently,
\[ r_x(p)=0\iff a_0=a_1=0, \qquad r_x(p)=1\iff a_0=a_1=1. \]
Since the strategies take values in \([0,1]\), these aggregate conditions force the respective globally constant profiles almost everywhere.
Therefore unanimity occurs precisely at \(\mathbf0,\mathbf1\). Every other profile, including truth-telling, receives no penalty at any support point.
An individual deviation leaves the aggregate unchanged, so the penalty adds the same conditional subtraction to both available reports. The equilibrium set is therefore unchanged.
For a normalized matrix, every unpenalized payment lies in \([0,1]\). Taking \(c=1\) gives
\[ U_i^1(\mathbf0)\leq0,\qquad U_i^1(\mathbf1)\leq0. \]
On the other hand, \(U_i^1(T)=U_i^0(T)>0\). Indeed, under truth-telling, every signal–peer-outcome pair has positive probability, and at least one normalized matrix entry equals one.
If \(\Delta_h>0\), every other nonconstant equilibrium has strictly smaller payoff than truth-telling, for every identity outside the null set on which equilibrium conditions may fail. Thus \(c=1\) makes truth-telling focal.
Conversely, a unanimity penalty cannot alter any nonconstant equilibrium payoff. Since there are only finitely many equilibrium payoff values, focality requires \(\Delta_h>0\). Hence
\[ \boxed{ \text{Some finite unanimity penalty makes }T\text{ focal} \iff \Delta_h>0. } \]
Because \(\Delta^*(\nu)>0\), every attained optimizer satisfies this condition. In the nonattained case, sufficiently near-optimal matrices satisfy it as well. The limiting matrix discussed above cannot be rescued by this penalty, but arbitrarily close matrices can.
Let \(L\) include the entire binary input, including the threshold or requested accuracy.
Computing \(u\) and \(\mathbb E[p^2]\), and hence \(l,v\), takes \(O(k)\) rational arithmetic operations. The intermediate rational numbers have \(O(L)\) bits.
The formulas then require only a constant number of rational operations, square roots, and exact comparisons. In particular:
Such comparisons can be performed exactly by isolating radicals and squaring with the necessary sign checks. They require only a constant number of operations on integers with \(O(L)\) bits. Equality cases are therefore decided exactly.
Using elementary integer arithmetic, a conservative bound for exact evaluation, attainment testing, and deciding \(\Delta^*(\nu)>g\) is
\[ O(kL^2+L^3) \]
bit operations. This establishes membership in \(\mathrm P\).
An attained optimum can be output exactly by the constant-size algebraic expression (13). For any positive rational accuracy \(\varepsilon\), a rational matrix with
\[ \Delta_h>\Delta^*(\nu)-\varepsilon, \qquad \Delta_h>0 \]
can also be constructed in \(O(kL^2+L^3)\) bit operations when \(L\) includes the encoding of \(\varepsilon\).
To justify the approximation bound, all relevant coefficients have \(O(L)\) bits and fixed algebraic degree. Nonzero feasibility margins consequently have magnitude at least \(2^{-O(L)}\). On an appropriately chosen feasible neighborhood, the displayed gap functions have derivatives bounded by \(2^{O(L)}\). Thus \(O(L)\) bits of parameter precision suffice. In the nonattained case, approximate from the side \(t>H\) using (11). Choosing the approximation sufficiently accurately also preserves a positive gap.
These bounds are for the promised setting \(m=\tau=2\); there is no enumeration of possible types and no further dependence on them. No complexity claim for unrestricted \(m\) or \(\tau\) is needed for this task.
⟨structured verdict parsed — rendered above⟩
The output resolves the target in substance. The equilibrium classification, payoff calculations, optimal gap, attainment criterion, focality result, and polynomial-time classification are correct. There is one minor issue: Section 5 describes a restricted optimization as the unrestricted optimum for a fixed threshold. The preceding reduction makes the restriction sufficient for the global optimization, so this wording error does not invalidate the final conclusions.
The identities
\(uv+(1-u)l=u\),
\(v-u=\operatorname{Var}_{\nu}(p)/u\), and
\(u-l=\operatorname{Var}_{\nu}(p)/(1-u)\)
are correct. The support assumptions ensure \(0<l<u<v<1\).
The reduction to \(u>\tfrac12\) preserves normalization, strict propriety, equilibrium payoffs, and the unanimity penalty. From \(u=l/(1-v+l)>\tfrac12\), the claimed inequality \(l+v>1\) follows.
Strict propriety at \(l\) and \(v\) gives opposite strict signs for the affine difference \(L_1-L_0\). Consequently, its representation as \(D(y-t)\), with \(D>0\) and \(l<t<v\), is justified.
For \(l<s<v\), the normalization calculation is correct: the minimum unnormalized entry is \(-\max\{s,t\}\), and the range is \(\max\{s,1-s,t,1-t\}\).
The scoring-rule construction supplies the required feasibility argument. A positive curvature density with the prescribed total mass and mean exists for every \(t\in(l,v)\). Its integration gives the stated endpoint values and derivatives. The resulting strictly convex function induces a strictly proper rule with precisely the desired payment columns. No additional restriction on \(s\) is needed.
Equation (3) correctly computes the conditional peer-report probabilities. Identity contributes no additional information, and individual deviations leave the aggregate unchanged, so these probabilities determine every identity’s conditional best responses.
The table exhausts the possibilities according to whether \(a_1>a_0\), \(a_1<a_0\), or \(a_1=a_0\). Its existence conditions and boundary coincidences are correct. In particular, \(l>1-v\) makes \(F_1\) always feasible, while \(F_0\) and \(F\) require \(t\leq1-l\).
Every listed aggregate is realizable by a measurable equilibrium profile. At indifferent signals, all mixtures have the same conditional payoff. Thus identity-dependent behavior introduces neither additional aggregate equilibria nor additional equilibrium payoff values.
Aggregates corresponding to \(T\), \(\mathbf0\), and \(\mathbf1\) force those profiles almost everywhere. Their exclusion therefore leaves no additional profiles with the same extreme aggregates.
Equation (4) correctly expresses the common equilibrium payoff. Consequently, the essential infimum over identities reduces to the ordinary payoff difference.
I checked the displayed gap formulas, including the expressions for \(Q,F_0,F_1,F\). They are correct.
The always-existing equilibria \(T_0,T_1\) show that a positive gap requires \(l<s<v\). Within this range, the stated coefficient signs correctly eliminate \(Q\) and \(F_1\) from the minimum.
When \(t\leq1-l\), positivity against \(F\) requires \(s+t<1\); this also makes \(F_0\)’s gap exceed \(T_1\)’s. Equation (8) follows. When \(t>1-l\), \(F\) and \(F_0\) disappear, giving equation (9). Boundary equilibria are accounted for.
Averaging \(s,t\) preserves feasibility, increases both product numerators, leaves the \(F\) numerator unchanged, and weakly decreases the normalization denominator. The reduction to \(s=t=z\) is valid.
The inequality \(z_0>\tfrac12\) correctly eliminates the first numerator from the minimum on \(l<z<\tfrac12\). The remaining two functions have the claimed strict monotonicity and endpoint behavior.
Their intersection equation and its positive root are correct. Thus \(G_{\mathrm I}\) is attained when \(l<\tfrac12\). When \(l\geq\tfrac12\), this region contains no admissible threshold.
Here \(t>H\) implies \(s+t>1\), so \(R=\max\{s,t\}\). Averaging a pair with \(s>t\) produces a feasible pair with no smaller gap. Therefore restricting the global optimization to \(s\leq t\) is justified.
Within that restricted family, equation (11), the condition \(s(t)\leq t\iff t\geq z_0\), and equation (12) are correct.
However, the sentence “Thus the largest gap for a fixed threshold is” is literally false without explicitly retaining the restriction \(s\leq t\). Averaging changes the threshold, so the preceding reduction does not establish unrestricted optimality at each fixed threshold.
A concrete example satisfies every prior assumption. Take support points \(\tfrac12,\tfrac9{10}\) with weights \(\tfrac38,\tfrac58\). Then
\(u=\tfrac34\), \(l=\tfrac35\), \(v=\tfrac45\),
\(\alpha=\tfrac{15}{16}\), and \(\beta=\tfrac58\).
At \(t=\tfrac{13}{20}\), one has \(H<t<z_0\). Equation (12) gives \(\tfrac1{416}\), attained within the restricted family at \(s=t\). But the admissible choice \(s=\tfrac{33}{50}>t\) has gap \(\tfrac1{352}>\tfrac1{416}\).
Minimum clarification: label equation (12) as the largest gap for a fixed threshold among pairs satisfying \(s\leq t\). No mathematical change to the global optimization is required.
The reciprocal calculation for \(J\), its derivative, and \(t_*<z_0\) are correct. Hence the restricted envelope increases up to \(z_0\) and decreases thereafter. This establishes the claimed \(G_{\mathrm{II}}\) and its attainment behavior.
Both regions together establish the displayed formula for \(\Delta^*(\nu)\). The inequalities \(H<v\) and \(z_0\in(l,v)\) ensure \(G_{\mathrm{II}}>0\).
The attainment criterion handles all equality cases correctly. In particular, \(z_0=H\) does not attain the second-region supremum because that region requires \(t>H\). An attained first-region value still supplies a global optimizer when \(G_{\mathrm I}\geq G_{\mathrm{II}}\).
The limiting-matrix explanation is consistent: in the nonattained case, \(H=1-l\), and the reappearing equilibrium \(F\) has a negative gap at the limit.
I independently checked the example’s moments, the comparison establishing \(z_0<H\), and the exact values
\(G_{\mathrm{II}}=\tfrac{365025}{142487248}\) and
\(2\beta(\tfrac12-l)^2=\tfrac{625}{533504}\).
They establish genuine nonattainment.
Because every support point lies strictly inside \((0,1)\), unanimity occurs exactly at the two constant aggregates. Those aggregates force the corresponding constant profiles almost everywhere.
The penalty does not change conditional best responses, since an individual deviation leaves its triggering event unchanged. It therefore preserves the equilibrium set and affects only constant-equilibrium payoffs.
Normalization gives constant-equilibrium payoffs at most zero after \(c=1\). Truth-telling has strictly positive payoff because every signal–peer-outcome pair has positive probability and at least one matrix entry equals one.
The equivalence between focality under some finite penalty and \(\Delta_h>0\) is justified. Its converse uses the finite number of equilibrium payoff values, which the earlier classification establishes. The conclusions for optimal and arbitrarily near-optimal matrices follow.
The moment computation uses \(O(k)\) rational operations with \(O(L)\)-bit intermediates. The candidate values involve only a constant number of radicals of bounded algebraic degree. Exact comparisons, including equality cases, therefore admit polynomial-time sign-controlled radical calculations.
The stated conservative bound \(O(kL^2+L^3)\) is consistent with elementary integer arithmetic. The approximation discussion also supports polynomial construction: the quantities have bounded algebraic degree and \(O(L)\)-bit defining data, permitting \(O(L)\) bits of parameter precision while maintaining feasibility and positivity.
Since the task fixes \(m=\tau=2\), explicitly stating this specialization adequately addresses the requested dependence on those parameters. The output establishes membership in \(\mathrm P\).
⟨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.