d4-conf-aaai-2015-0492 (d4-conf-aaai-2015-0492)

Given a categorical outcome space with \(K\) outcomes, a common prior \(\alpha_0\), population scale \(H\), and rational masses \(\mu_t\) over reachable posterior report types \((p_t,b_t)\), can the two-sample score \(S(p,b,x_1,x_2)=\log p(x_1)+2b\mathbf{1}\{x_1=x_2\}-b^2\) elicit the reports and compute the aggregate predictive distribution \(q\) for the society?

Let \(m:=K\geq2\), with outcomes \([K]\), common prior \(\theta\sim\operatorname{Dirichlet}(\alpha_0)\), \(\alpha_0\in\mathbb{Q}_{>0}^{K}\), and population scale \(H\in\mathbb{Q}_{>0}\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. Here \(\mu_t>0\), \(\sum_t\mu_t=1\), and \(\tau\) is the support size, not the number of possible types.
Each listed report \((p_t,b_t)\) is binary rational and promised reachable: some unobserved count vector \(c_t\in\mathbb{Z}_{\geq0}^{K}\) gives posterior \(\operatorname{Dirichlet}(\alpha_0+c_t)\), with \(p_t(i)=\Pr_t(x_1=i)\) and \(b_t=\Pr_t(x_1=x_2)\).
Conditional on the same latent \(\theta\), all private observations and the principal's two samples \(x_1,x_2\) are independent categorical draws. Agents are risk neutral and report independently before seeing these two samples or others' reports.
Allowed reports are \((p,b)\in\Delta_K\times[0,1]\), scored by \(S(p,b,x_1,x_2)=\log p(x_1)+2b\mathbf{1}\{x_1=x_2\}-b^2\), with \(\log0=-\infty\). Truthful elicitation means the true pair uniquely maximizes posterior expected score.
The mass aggregate is the predictive distribution of \(\operatorname{Dirichlet}(\alpha_0+H\sum_t\mu_t c_t)\); the principal's scoring samples are excluded. Only reports, masses, the prior, and the scale are supplied, not the counts.
Let \(L\) be the total binary input length; state running times in \(m=K\), \(\tau\), and \(L\), including the encoded scale \(H\).

Does \(S\) truthfully elicit every reachable type in this society? Is exact computation of the mass aggregate \(q\) from the supplied reports polynomial-time solvable, or NP-hard?

For finitely many agents, this score achieves optimal aggregation under the categorical–Dirichlet model ([verified discrete result](https://ojs.aaai.org/index.php/AAAI/article/view/9315/9174)); the result states no computational complexity bound.
No result settling this exact rational-mass formulation was located in the search.

Result

The score truthfully elicits every reachable type, and the exact mass aggregate is polynomial-time computable. An explicit bound is \(O(m\tau L^3)\) bit operations, including the binary encoding of \(H\).

The proof consists of recovering each posterior concentration from its report, then performing exact rational aggregation.

1. Posterior moments and recovery of the hidden counts

Fix a reachable type \(t\). Define
\(\alpha_{t,i}=\alpha_{0,i}+c_t(i)\) and
\(A_t=\sum_{i=1}^{m}\alpha_{t,i}\).
Every coordinate is strictly positive.

For a Dirichlet distribution with positive parameter vector \(\alpha\), write \(A=\sum_i\alpha_i\). Its density normalizing integral is
\(Z(\alpha)=\prod_i\Gamma(\alpha_i)/\Gamma(A)\).
Multiplying the density by \(\theta_i\) or \(\theta_i^2\), and using \(\Gamma(z+1)=z\Gamma(z)\), gives

\[ \mathbb E[\theta_i] =\frac{Z(\alpha+e_i)}{Z(\alpha)} =\frac{\alpha_i}{A}, \qquad \mathbb E[\theta_i^2] =\frac{Z(\alpha+2e_i)}{Z(\alpha)} =\frac{\alpha_i(\alpha_i+1)}{A(A+1)}. \]

Here and below, these identities apply because all Dirichlet parameters are positive.

Conditional independence of the principal’s samples given \(\theta\) therefore implies

\[ p_t(i)=\frac{\alpha_{t,i}}{A_t}, \qquad b_t=\sum_{i=1}^{m}\mathbb E_t[\theta_i^2] =\frac{\sum_i\alpha_{t,i}^2+A_t}{A_t(A_t+1)}. \]

Define \(s_t=\sum_i p_t(i)^2\). Substituting
\(\alpha_{t,i}=A_t p_t(i)\) yields

\[ b_t=\frac{A_t s_t+1}{A_t+1}, \qquad b_t-s_t=\frac{1-s_t}{A_t+1}, \qquad 1-b_t=\frac{A_t(1-s_t)}{A_t+1}. \]

Because \(m\geq2\) and every \(p_t(i)>0\),

\[ 1-s_t =2\sum_{i<j}p_t(i)p_t(j)>0. \]

Consequently \(s_t<b_t<1\), so the following division is always valid:

\[ \boxed{ A_t=\frac{1-b_t}{b_t-\sum_i p_t(i)^2}. } \]

The hidden counts are then uniquely determined:

\[ \boxed{ c_t(i)= \frac{1-b_t}{b_t-\sum_j p_t(j)^2}\,p_t(i)-\alpha_{0,i}. } \]

Reachability guarantees that these recovered values are nonnegative integers: they equal the counts whose existence is promised. Thus no integer search or choice among compatible count vectors is necessary.

This concentration inversion also appears in Theorem 4 of the supplied [discrete aggregation paper](https://ojs.aaai.org/index.php/AAAI/article/view/9315/9174). The rational-mass and bit-complexity arguments below are explicit.

2. Unique truthful elicitation

Fix the same type and abbreviate its true report by \((p,b)\). Consider an arbitrary allowed report \((r,d)\).

If any \(r(i)=0\), then \(p(i)>0\), so the expected logarithmic score is \(-\infty\). The remaining score terms are bounded, whereas the truthful expected score is finite. Such a report cannot maximize expected score.

Suppose instead that every \(r(i)>0\). Linearity of expectation gives

\[ \mathbb E_t[S(r,d,x_1,x_2)] =\sum_i p(i)\log r(i)+2db-d^2. \]

This calculation uses only the marginal distribution of \(x_1\) and the probability of the collision event. It does not assume that the samples are independent after integrating out \(\theta\).

Subtracting this expression from the truthful expected score gives

\[ \mathbb E_t[S(p,b,x_1,x_2)] -\mathbb E_t[S(r,d,x_1,x_2)] = \sum_i p(i)\log\frac{p(i)}{r(i)} +(d-b)^2. \]

To verify the first term’s sign and equality condition directly, use
\(\log u\leq u-1\), with equality exactly when \(u=1\). Then

\[ \sum_i p(i)\log\frac{r(i)}{p(i)} \leq \sum_i p(i)\left(\frac{r(i)}{p(i)}-1\right) =\sum_i r(i)-\sum_i p(i)=0. \]

Since every weight \(p(i)\) is positive, equality holds exactly when every \(r(i)=p(i)\). The square vanishes exactly when \(d=b\).

Thus the true pair uniquely maximizes posterior expected score over the entire allowed report space. This proves truthful elicitation for every reachable type.

3. Exact aggregate formula

Let \(A_0=\sum_i\alpha_{0,i}\). The aggregate parameter vector specified in the question is

\[ \beta_i=\alpha_{0,i}+H\sum_{t=1}^{\tau}\mu_t c_t(i). \]

Using the recovered counts and \(\sum_t\mu_t=1\), we obtain

\[ \beta_i=(1-H)\alpha_{0,i} +H\sum_{t=1}^{\tau}\mu_t A_t p_t(i). \]

Although \(1-H\) may be negative, the original definition guarantees
\(\beta_i\geq\alpha_{0,i}>0\). Summing the coordinates gives

\[ \sum_i\beta_i=(1-H)A_0+H\sum_{t=1}^{\tau}\mu_t A_t. \]

The one-sample predictive distribution of \(\operatorname{Dirichlet}(\beta)\) is therefore

\[ \boxed{ q(i)= \frac{(1-H)\alpha_{0,i} +H\sum_{t=1}^{\tau}\mu_t A_t p_t(i)} {(1-H)A_0+H\sum_{t=1}^{\tau}\mu_t A_t}, \qquad A_t=\frac{1-b_t}{b_t-\sum_jp_t(j)^2}. } \]

Every operation in this expression is rational arithmetic. The principal’s scoring samples do not enter it, as required.

4. Binary complexity, including the scale

A rational formula alone is insufficient to establish polynomial bit complexity. We now bound the sizes of the integers used to evaluate it.

For each type, write
\(p_t(i)=u_{t,i}/v_{t,i}\) and \(b_t=z_t/e_t\), with positive denominators. Let \(\ell_t\) be the total encoding length of this type’s report. Define

\[ D_t=\prod_i v_{t,i}, \qquad P_{t,i}=u_{t,i}\frac{D_t}{v_{t,i}}, \qquad U_t=\sum_iP_{t,i}^2. \]

Then \(s_t=U_t/D_t^2\), and the concentration can be represented without any fraction reduction as

\[ A_t= \frac{(e_t-z_t)D_t^2} {z_tD_t^2-e_tU_t}. \]

Its denominator is strictly positive by \(b_t>s_t\).

The integer \(D_t\) has \(O(\ell_t)\) bits. Furthermore, \(p_t(i)\in[0,1]\) and \(s_t\leq1\) imply
\(P_{t,i}\leq D_t\) and \(U_t\leq D_t^2\).
Thus both displayed numerator and denominator of \(A_t\) have \(O(\ell_t)\) bits. Summed over the support, their encoding lengths are \(O(L)\).

Choose a global common denominator \(D\) as the product of:

• all supplied denominators of the prior coordinates, masses, predictive coordinates, and \(H\);
• the just-constructed denominators of all \(A_t\).

The total bit length of these factors is \(O(L)\), so \(D\) has \(O(L)\) bits. Each individual term in

\[ \beta_i=(1-H)\alpha_{0,i} +H\sum_t\mu_t A_t p_t(i) \]

has denominator dividing \(D\). Hence we can compute the integers
\(B_i=D\beta_i\) by exact integer multiplication, division, and addition, and return

\[ q(i)=\frac{B_i}{\sum_jB_j}. \]

All intermediate integers have \(O(L)\) bits. To see the numerator bound, every input numerator has at most \(L\) bits, each recovered \(A_t\) has \(O(\ell_t)\) bits, and the expressions contain only a constant number of factors per term. Summing at most \(\tau\) terms adds at most \(O(\log\tau)\) bits. Both \(\log\tau\) and \(\log m\) are bounded by \(O(L)\). The same bounds include the numerator and denominator of \(H\).

Constructing these quantities requires \(O(m\tau)\) arithmetic operations. Schoolbook multiplication and long division on \(O(L)\)-bit integers each take \(O(L^2)\) bit operations. Thus unreduced exact output takes \(O(m\tau L^2)\) bit operations.

If reduced output fractions are required, apply the Euclidean algorithm to each output numerator and denominator. A conservative bound of \(O(L)\) divisions per fraction gives \(O(mL^3)\) additional bit operations. Consequently,

\[ \boxed{ T(m,\tau,L)=O(m\tau L^2+mL^3) \subseteq O(m\tau L^3). } \]

Each output coordinate has \(O(L)\) bits, giving total output length \(O(mL)\). The algorithm processes only the listed support and the binary encodings; it performs no iteration proportional to the numerical value of \(H\) or to any hidden observation count.

Both requested conclusions are therefore established completely.

⟨structured verdict parsed — rendered above⟩

Verdict

The prover resolves both parts of USER_TASK. The score uniquely elicits every reachable type, and the exact rational-mass aggregate is computable in polynomial time. The stated bound \(O(m\tau L^3)\) is justified. I found no major or minor mathematical issues.

Step-by-step verification

1. Posterior moments and count recovery

The Dirichlet moment calculations are correct. Positivity of every parameter permits the stated normalizing-integral ratios and Gamma recurrence, yielding
\[ \mathbb E_t[\theta_i]=\frac{\alpha_{t,i}}{A_t}, \qquad \mathbb E_t[\theta_i^2] =\frac{\alpha_{t,i}(\alpha_{t,i}+1)}{A_t(A_t+1)}. \]

Conditional independence given \(\theta\) correctly gives the collision probability as the sum of second moments. The proof does not incorrectly assume independence under the posterior predictive distribution.

Substitution of \(\alpha_{t,i}=A_t p_t(i)\) correctly produces
\[ b_t=\frac{A_t s_t+1}{A_t+1}. \]

Since every predictive coordinate is positive and \(m\geq2\), the identity
\[ 1-s_t=2\sum_{i<j}p_t(i)p_t(j)>0 \]
is valid. Consequently, both \(b_t-s_t>0\) and \(1-b_t>0\). The concentration inversion therefore has no zero denominator and is algebraically correct.

The uniqueness claim also follows: any count vector consistent with the report must have this concentration and parameter vector \(A_t p_t\). Subtracting the supplied prior uniquely determines its counts. Reachability supplies nonnegativity and integrality; the algorithm need not search for or independently establish a compatible vector.

The bibliographic claim is accurate: the same concentration inversion appears in the proof of Theorem 4 of the [cited paper](https://ojs.aaai.org/index.php/AAAI/article/view/9315/9174). This citation is corroborative; the submitted derivation is self-contained.

2. Unique truthful elicitation

The boundary case is handled correctly. If a reported coordinate is zero, that outcome has positive posterior probability, so the expected logarithmic score is negative infinity. The other score terms are bounded and cannot offset it. Truthful reporting has finite expected score.

For strictly positive reported coordinates, the expected-score calculation and subtraction are correct:
\[ \mathbb E_t[S(p,b)]-\mathbb E_t[S(r,d)] =\sum_i p(i)\log\frac{p(i)}{r(i)}+(d-b)^2. \]

The application of \(\log u\leq u-1\) satisfies its domain requirement because \(r(i)/p(i)>0\). Normalization of both distributions gives the stated nonnegative divergence. Because every weight is positive, equality requires every coordinate to agree. The square requires \(d=b\).

Thus uniqueness holds over the entire allowed report space, including its boundary, rather than merely over reachable reports.

3. Exact mass aggregation

The expansion of the aggregate parameters correctly uses \(\sum_t\mu_t=1\). Summing those parameters gives precisely the displayed denominator of \(q(i)\).

Positivity follows from the original definition:
\[ \beta_i=\alpha_{0,i}+H\sum_t\mu_t c_t(i)\geq\alpha_{0,i}>0. \]
Hence cancellation in the expanded expression, including when \(H>1\), cannot cause an undefined aggregate.

The formula computes the predictive distribution specified by USER_TASK. It incorporates rational masses and the supplied scale, and excludes the principal’s scoring samples.

4. Bit complexity

The integer representation of each recovered concentration is correct:
\[ A_t=\frac{(e_t-z_t)D_t^2}{z_tD_t^2-e_tU_t}. \]

The size estimates hold. The product \(D_t\) has \(O(\ell_t)\) bits. Since \(P_{t,i}=D_t p_t(i)\), the bounds \(P_{t,i}\leq D_t\) and \(U_t\leq D_t^2\) follow from the report’s simplex membership. Both concentration integers therefore have \(O(\ell_t)\) bits, even if their positive difference is small.

The global denominator construction is valid when read as the stated product over all denominator occurrences. It retains multiplicities when numerical denominator values coincide. Each summand contains only one occurrence of each relevant factor, so its denominator divides that product.

The total factor bit length is \(O(L)\), including recovered concentration denominators. Thus the global denominator and all scaled term numerators have \(O(L)\) bits. Summing over the support or outcomes adds only logarithmic size overhead. Negative intermediate terms when \(H>1\) do not change these magnitude bounds.

The construction uses \(O(m\tau)\) arithmetic operations on integers of \(O(L)\) bits. Schoolbook multiplication and long division justify the unreduced-output bound \(O(m\tau L^2)\). The conservative Euclidean-algorithm estimate justifies the additional \(O(mL^3)\) cost for reduced fractions.

Accordingly,
\[ O(m\tau L^2+mL^3)\subseteq O(m\tau L^3) \]
is valid. The argument includes the binary encoding of \(H\) and does not iterate over its numerical value or the hidden counts.

5. Edge cases and required clarification

Zero observation counts, a single supported type, arbitrary positive rational scale, and very small positive concentration-recovery denominators are all covered by the argument.

No additional clarification is needed to verify the conclusions.

⟨structured verdict parsed — rendered above⟩