d4-journals-jet-2023-0106 (d4-journals-jet-2023-0106)

Given a unit-mass population with private signal \(x\in\{0,1\}\), masses \(\mu_x=1/2\), the paper’s signal precisions \(p,r\), and a single unit of prize mass, compute the optimal BIC allocation-rate density \(a_{b,y}\ge 0\), where \(b\) is the reported self-signal and \(y\) the referee report. Require \(\sum_{x,y}\nu_{xy}a_{x,y}=1\), where \(\nu_{xy}=\mu_x\Pr(Y=y\mid X=x)\), and for each \(x\in\{0,1\}\), require \(\sum_y\Pr(Y=y\mid X=x)a_{x,y}\ge\sum_y\Pr(Y=y\mid X=x)a_{1-x,y}\). Maximize \(\sum_{x,y}\nu_{xy}q_{xy}a_{x,y}\), where \(q_{xy}=\Pr(\Theta=1\mid X=x,Y=y)\); determine the optimum and compare it with the optimum under DSIC constraints.

A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) counts supported types, not possible types. Here the population has unit mass, private signals \(x\in\{0,1\}\), and \(\mu_0=\mu_1=1/2\), so \(\tau=2\).
Input precisions are binary rationals satisfying \(1/2<r\le p<1\). Latent suitability \(\Theta\in\{0,1\}\) has equal prior probabilities; conditional on \(\Theta\), private signal \(X\) and nonstrategic referee report \(Y\) are independent, with \(\Pr(X=\theta\mid\Theta=\theta)=p\) and \(\Pr(Y=\theta\mid\Theta=\theta)=r\) for both \(\theta\).
Write \(c_{xy}=\Pr(Y=y\mid X=x)\), \(\nu_{xy}=\mu_xc_{xy}\), and \(q_{xy}=\Pr(\Theta=1\mid X=x,Y=y)\). All these probabilities are determined by the specified information structure.
An anonymous mechanism without transfers assigns a finite nonnegative prize density \(a_{b,y}\) to reported private signal \(b\) and referee report \(y\); utility is proportional to this density. Densities may exceed one. One unit of prize mass must be allocated: \(\sum_{x,y}\nu_{xy}a_{x,y}=1\).
BIC requires \(\sum_y c_{xy}a_{x,y}\ge\sum_y c_{xy}a_{1-x,y}\) for each \(x\). The DSIC benchmark instead requires \(a_{x,y}\ge a_{1-x,y}\) for every \(x,y\). Indifference permits truthful reporting.
Let \(V_B(p,r)\) and \(V_D(p,r)\) be the respective maxima of \(\sum_{x,y}\nu_{xy}q_{xy}a_{x,y}\). For complexity, include a binary rational threshold \(t\); let \(L\) be the total input bit length and \(m=2\) the signal alphabet size.

Is deciding \(V_B(p,r)\ge t\) in P or NP-hard, with running times expressed in \(m,\tau,L\)?
What are \(V_B(p,r)\), its maximizing densities, and its comparison with \(V_D(p,r)\) throughout \(1/2<r\le p<1\)?

For finite populations of \(n\ge2\) agents, optimal anonymous BIC selection is characterized by shortlisting maximal referee reports and adjusting tie-breaking using self-reports; optimal BIC value strictly exceeds optimal DSIC value in this precision domain. [Bloch, Dutta and Dziubiński](https://wrap.warwick.ac.uk/id/eprint/176793/1/WRAP-selecting-winner-external-referees-Dutta-2023.pdf)
No result settling this exact density model was identified in the literature search.

1. Result

Throughout the specified domain \(1/2<r\le p<1\),
\[ V_B(p,r)=V_D(p,r)=r. \]
The unique maximizing density under either incentive requirement is
\[ a_{0,0}=a_{1,0}=0,\qquad a_{0,1}=a_{1,1}=2. \]
Thus deciding \(V_B(p,r)\ge t\) belongs to \(\mathrm P\): it amounts to comparing \(r\) and \(t\).

Here and below, the density model is interpreted exactly as stated, with finite nonnegative densities and the single aggregate prize-mass constraint.

2. Probabilities determined by the information structure

Define
\[ s=pr+(1-p)(1-r),\qquad d=p(1-r)+(1-p)r. \]
Then \(s+d=1\), \(d>0\), and
\[ s-\frac12=2\left(p-\frac12\right)\left(r-\frac12\right)>0. \]
Consequently, \(s>d>0\).

The symmetric prior and signal accuracy imply \(\Pr(X=0)=\Pr(X=1)=1/2\). Conditional independence given \(\Theta\) therefore gives
\[ (c_{xy})_{x,y\in\{0,1\}} = \begin{pmatrix} s&d\\ d&s \end{pmatrix}, \qquad (\nu_{xy})_{x,y\in\{0,1\}} = \frac12 \begin{pmatrix} s&d\\ d&s \end{pmatrix}. \]
Bayes’ rule gives
\[ (q_{xy})_{x,y\in\{0,1\}} = \begin{pmatrix} \dfrac{(1-p)(1-r)}s&\dfrac{(1-p)r}d\\[4pt] \dfrac{p(1-r)}d&\dfrac{pr}s \end{pmatrix}. \]
All denominators are strictly positive.

Write \(A=(1-p)(1-r)\) and \(B=pr\). The objective of a density \(a\) is consequently
\[ J(a)=\frac12\left[Aa_{0,0}+(1-p)r\,a_{0,1} +p(1-r)a_{1,0}+Ba_{1,1}\right]. \]

3. A complete upper bound for BIC

For any BIC density, define
\[ z=a_{0,0}-a_{1,0},\qquad w=a_{1,1}-a_{0,1}. \]
The incentive constraints for private signals \(0\) and \(1\), respectively, become
\[ sz\ge dw,\qquad sw\ge dz. \]
These inequalities force both differences to be nonnegative. Indeed,
\[ s^2z\ge sdw\ge d^2z, \]
so \((s^2-d^2)z\ge0\), and hence \(z\ge0\). Interchanging \(z\) and \(w\) gives \(w\ge0\).

Set
\[ u=a_{1,0}\ge0,\qquad v=a_{0,1}\ge0,\qquad h=z-\frac ds w\ge0. \]
Thus the four densities have the form
\[ (a_{0,0},a_{0,1},a_{1,0},a_{1,1}) =(u+z,v,u,v+w). \]
The prize-mass constraint becomes
\[ \frac12\left[u+v+s(z+w)\right]=1, \]
while the objective becomes
\[ J(a)=\frac12\left[(1-r)u+rv+Az+Bw\right]. \]

Subtracting this objective from \(r\) times the normalized prize mass yields
\[ r-J(a) =\frac12\left[(2r-1)u+(rs-A)z+(rs-B)w\right]. \]
Substitute \(z=h+(d/s)w\). Using \(s+d=1\), this gives
\[ r-J(a) =\frac12\left[(2r-1)u+(rs-A)h+ \left(r-B-\frac{Ad}s\right)w\right]. \]
The last coefficient simplifies explicitly:
\[ r-B-\frac{Ad}s =\frac{1-p}{s}\left[rs-(1-r)d\right] =\frac{1-p}{s}\left[s-(1-r)\right] =\frac{p(1-p)(2r-1)}s. \]
We have therefore proved the exact identity
\[ r-J(a) =\frac12\left[ (2r-1)u+(rs-A)h+ \frac{p(1-p)(2r-1)}s\,w \right]. \]

Every coefficient on the right is strictly positive. For the middle coefficient, \(r>1/2\) and \(s>1/2\) imply \(rs>1/4\), whereas \(p>1/2\) and \(r>1/2\) imply \(A<1/4\). Since \(u,h,w\) are nonnegative, this proves \(J(a)\le r\).

Moreover, equality requires \(u=h=w=0\). Then \(z=0\), and normalization forces \(v=2\). Hence any BIC maximizer must be precisely
\[ (a_{0,0},a_{0,1},a_{1,0},a_{1,1})=(0,2,0,2). \]
This density is feasible: both reports give identical utility for every referee report, and its prize mass is \(2\Pr(Y=1)=1\). Its objective is \(r\). Thus the BIC bound is attained, and the maximizer is unique.

4. DSIC and comparison with the finite-population result

DSIC imposes both \(a_{0,y}\ge a_{1,y}\) and \(a_{1,y}\ge a_{0,y}\). Therefore
\[ a_{0,0}=a_{1,0}=u,\qquad a_{0,1}=a_{1,1}=v. \]
Normalization and the objective reduce to
\[ \frac{u+v}{2}=1,\qquad J(a)=\frac{(1-r)u+rv}{2}. \]
Because \(r>1-r\), the unique optimum is \(u=0\), \(v=2\), with value \(r\).

Consequently, the BIC–DSIC gap is zero everywhere in the stated precision domain, including \(p=r\).

This does not contradict the cited finite-population result. That paper studies selection probabilities assigning one indivisible prize among finitely many contestants, as functions of their report profiles. Its feasibility requirement differs from the aggregate density constraint used here. [Bloch, Dutta and Dziubiński, *Selecting a Winner with External Referees*](https://wrap.warwick.ac.uk/id/eprint/176793/1/WRAP-selecting-winner-external-referees-Dutta-2023.pdf)

5. Exact decision algorithm and running time

On the promised input domain, the algorithm returns “yes” exactly when \(r\ge t\).

If \(r=N_r/D_r\) and \(t=N_t/D_t\), with positive denominators, this is the exact integer comparison
\[ N_rD_t\ge N_tD_r. \]
Using schoolbook multiplication, it takes \(O(L^2)\) bit operations and \(O(L)\) space. For dyadic rationals in explicit binary representation, comparison can instead be performed in \(O(L)\) bit operations.

In this family \(m=\tau=2\), so the bound is \(O(L^2)\), polynomial in \((m,\tau,L)\). The direct density formulation has \(\tau m=4\) variables and \(\tau(m-1)=2\) BIC inequalities; the explicit solution eliminates the need to solve that linear program. No enumeration of unsupported types is involved.

⟨structured verdict parsed — rendered above⟩

The prover’s output fully resolves the stated density model. The probability calculations, BIC upper bound, equality conditions, DSIC optimization, and polynomial-time decision algorithm are correct. No major or minor mathematical issues were found.

• Information structure and probabilities.

The symmetric prior and signal accuracies give \(\mu_0=\mu_1=1/2\). Conditional independence yields
\(s=pr+(1-p)(1-r)\) and \(d=p(1-r)+(1-p)r\), with \(s+d=1\).

The identity \(s-1/2=2(p-1/2)(r-1/2)\) is correct. The stated domain therefore ensures \(s>d>0\), justifying every subsequent division by \(s\) or \(d\).

The matrices for \(c_{xy}\) and \(\nu_{xy}\) have the correct indexing. Each posterior \(q_{xy}\) follows from Bayes’ rule with the displayed denominator. Multiplying \(\nu_{xy}\) by \(q_{xy}\) gives precisely the four coefficients in \(J(a)\).

• Translation of BIC constraints.

With \(z=a_{0,0}-a_{1,0}\) and \(w=a_{1,1}-a_{0,1}\), the signal-zero constraint is \(sz\ge dw\), and the signal-one constraint is \(sw\ge dz\). Both signs are correct.

Multiplying these inequalities by positive quantities gives \(s^2z\ge sdw\ge d^2z\). Since \(s^2-d^2>0\), this proves \(z\ge0\). The symmetric calculation proves \(w\ge0\). This argument does not presuppose the signs it establishes.

• Density decomposition and normalization.

The definitions \(u=a_{1,0}\), \(v=a_{0,1}\), and \(h=z-(d/s)w\) give \(u,v,h\ge0\), while the preceding argument gives \(w\ge0\).

Substitution into the four original density coordinates correctly gives
\((a_{0,0},a_{0,1},a_{1,0},a_{1,1})=(u+z,v,u,v+w)\).

The normalized prize mass is \([u+v+s(z+w)]/2=1\), and the objective is \([(1-r)u+rv+Az+Bw]/2\). Both formulas follow by collecting the displayed coefficients.

The proof does not assert that arbitrary nonnegative \(u,v,h,w\) satisfy both BIC constraints. It only uses properties necessary for every BIC-feasible density, which is sufficient for its upper bound.

• Upper-bound identity and coefficient signs.

Using normalization to subtract \(J(a)\) from \(r\) gives exactly
\(r-J(a)=[(2r-1)u+(rs-A)z+(rs-B)w]/2\).

Substituting \(z=h+(d/s)w\) produces the stated coefficient \(r-B-Ad/s\) on \(w\). Every equality in its simplification is correct: \(r-B=r(1-p)\), \(s+d=1\), and \(s-(1-r)=p(2r-1)\). Thus the final coefficient is \(p(1-p)(2r-1)/s\).

All three coefficients in the final identity are strictly positive throughout the promised domain. In particular, \(rs>1/4\) and \(A=(1-p)(1-r)<1/4\), so \(rs-A>0\). Consequently, the identity rigorously establishes \(J(a)\le r\) for every BIC-feasible density.

• Attainment and uniqueness.

Strict positivity of the coefficients makes equality possible only when \(u=h=w=0\). The definition of \(h\) then gives \(z=0\), and normalization gives \(v=2\). These implications uniquely determine the claimed density.

The candidate is nonnegative and finite. Its two reported-signal rows coincide, so both incentive constraints hold with equality. Its prize mass is one because \(\Pr(Y=1)=1/2\), and substitution into the objective gives \(r\). Thus both attainment and uniqueness are established.

• DSIC benchmark and domain coverage.

Requiring DSIC for both private signals forces equality between the two densities for each fixed referee report. The reduced normalization and objective are correct.

Since \(r>1-r\), the reduced problem has the unique optimizer \(u=0\), \(v=2\), with value \(r\). Therefore the claimed BIC–DSIC equality follows.

All strict inequalities used remain valid when \(p=r\). The excluded boundaries require no treatment, and no additional assumption such as \(p>r\) is introduced.

• Finite-population comparison.

The cited paper describes allocating a single indivisible prize among finitely many contestants, with selection probabilities depending on report profiles. This supports the prover’s explanation that its feasibility requirement differs from the aggregate density constraint here. The citation is contextual; the density-model proof does not depend on importing a theorem from that paper. [Bloch, Dutta and Dziubiński, *Selecting a Winner with External Referees*](https://wrap.warwick.ac.uk/id/eprint/176793/1/WRAP-selecting-winner-external-referees-Dutta-2023.pdf)

• Decision algorithm and complexity.

The established value reduces the promised decision problem exactly to comparing \(r\) with \(t\). Cross-multiplication is valid for positive denominators, including when the threshold numerator is negative.

The products have bit lengths bounded by \(O(L)\). Schoolbook multiplication and comparison therefore justify \(O(L^2)\) bit operations and \(O(L)\) space. The stated linear-time comparison for dyadic rationals is appropriately restricted to explicit binary representations.

With \(m=\tau=2\), the reported runtime is polynomial in \((m,\tau,L)\). The formulation indeed has four density variables and two BIC inequalities. The prover makes no unsupported claim about a family with variable alphabet or support size.

No repair or additional clarification is needed.

⟨structured verdict parsed — rendered above⟩