Maximizing Truth Learning in a Social Network is NP-hard (aamas25-00233)

Given finitely many finite directed community templates \(H_t=(G_t,q,p)\), rational masses \(\mu_t\) with \(\sum_t\mu_t=1\), and Bayesian aggregation, choose distributions \(\lambda_{t,\sigma}\) over \(\Sigma_{r_t}\), with \(\lambda_{t,\sigma}\ge0\) and \(\sum_{\sigma\in\Sigma_{r_t}}\lambda_{t,\sigma}=1\), to maximize \(\frac{\sum_t\mu_t\sum_{\sigma\in\Sigma_{r_t}}\lambda_{t,\sigma}L(H_t,\sigma,\mu_B)}{\sum_t\mu_t r_t}\); decide whether the maximum is at least \(1-\varepsilon\).

A society is given by its support: a list of \(\tau\) community types with positive binary rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types.
Each type is an explicitly given finite directed graph \(G_t=(V_t,E_t)\), with \(r_t=|V_t|\geq1\). All types share binary rational parameters \(q\in(0,1)\) and \(p\in(1/2,1)\). Put \(m=\max_t r_t\), and let \(L\) be the total input bit length.
Within each community, \(\theta\sim\operatorname{Ber}(q)\); conditional on \(\theta\), private signals \(s_v\in\{0,1\}\) are independent with \(\Pr(s_v=\theta\mid\theta)=p\). Communities exchange no observations.
Let \(\Sigma_{r_t}\) denote all bijections \(\sigma:V_t\to\{1,\ldots,r_t\}\). Agents act once in this order, observing only their private signal and the actions of earlier in-neighbors. The graph, order, parameters, and aggregation rule are common knowledge.
Bayesian aggregation \(\mu_B\) announces the posterior-maximizing state given these observations, accounting for their correlations; posterior ties use independent fair coins. Define \(L(H_t,\sigma,\mu_B)=\sum_{v\in V_t}\Pr(a_v=\theta)\), including tie randomness.
Choose distributions \(\lambda_{t,\sigma}\geq0\), with \(\sum_{\sigma\in\Sigma_{r_t}}\lambda_{t,\sigma}=1\), independently of signals and states; the realized order is public. Maximize \(F(\lambda)=\frac{\sum_t\mu_t\sum_{\sigma\in\Sigma_{r_t}}\lambda_{t,\sigma}L(H_t,\sigma,\mu_B)}{\sum_t\mu_t r_t}\), and write \(F^*=\max_\lambda F(\lambda)\). Algorithmic solutions are represented by lists of orders and binary rational weights.

Does this continuous optimization problem admit a PTAS achieving \(F(\lambda)\geq(1-\eta)F^*\) for every \(\eta\in(0,1)\), or is it APX-hard? State running times in \(m,\tau,L\), and \(\eta\).

For a single finite network with a deterministic order, maximizing the Bayesian learning rate is APX-hard ([source](https://arxiv.org/html/2502.12704v1#S5)). No result specifically treating the distribution-over-community-types formulation was located.

1. Result and the external theorem used

The problem is \(\mathrm{APX}\text{-hard}\), under the same approximation-preserving reduction notion as the cited result. Consequently, it admits no PTAS unless \(\mathrm{P}=\mathrm{NP}\). Hardness already holds when the support consists of one community type.

An exact algorithm runs in
\(\tau\,m!\,2^m\operatorname{poly}(m,L)\) time, independently of \(\eta\). Thus, bounded community size permits exact optimization in polynomial time.

The external result used is Theorem 5.1 of Úradník–Wang–Gao: maximizing the average Bayesian learning rate over deterministic orders is \(\mathrm{APX}\text{-hard}\). Its model uses directed graphs, conditionally independent private signals, correlation-aware Bayesian aggregation, and fair posterior ties, matching the present assumptions. Its approximation reduction can choose rational signal accuracies: the required strict inequality \(p>\sqrt{\delta}\), for a requested approximation factor \(\delta<1\), admits a dyadic rational choice. [Theorem 5.1 and model definitions](https://arxiv.org/html/2502.12704v1#S5)

The proof below establishes the additional transfer to explicitly represented distributions. Merely observing that deterministic orders are feasible would not justify efficient extraction of a deterministic solution.

2. Proven claim: randomization does not improve the optimum

Write
\(\ell_t(\sigma)=L(H_t,\sigma,\mu_B)\),
\(M_t=\max_{\sigma\in\Sigma_{r_t}}\ell_t(\sigma)\), and
\(D=\sum_t\mu_t r_t>0\).

For every feasible distribution,
\[ \]
\( \sum_{\sigma}\lambda_{t,\sigma}\ell_t(\sigma) \leq \sum_{\sigma}\lambda_{t,\sigma}M_t=M_t. \)

Therefore,
\(F(\lambda)\leq D^{-1}\sum_t\mu_t M_t\).

For each type, choose an order \(\sigma_t^*\) attaining \(M_t\); this exists because its order set is finite. Assign weight \(1\) to that order. These choices are jointly feasible because there are no constraints coupling different types. They attain the upper bound. Hence

\( \displaystyle F^*=\frac{\sum_t\mu_t M_t}{D}. \)

In particular, an optimum has exactly one listed order per type, with binary rational weight \(1\). Neither irrational weights nor large supports are needed.

Also, if orders satisfy
\(\ell_t(\widehat\sigma_t)\geq(1-\eta)M_t\) for every type, then their deterministic distributions satisfy

\( \displaystyle F(\widehat\lambda) =\frac{\sum_t\mu_t\ell_t(\widehat\sigma_t)}{D} \geq(1-\eta)F^*. \)

3. Proven claim: exact evaluation of a fixed order

Consider a community of size \(r\), with ordered vertices \(v_1,\ldots,v_r\). Define

\( \displaystyle Q_i(\theta,h)= \Pr\bigl(\theta,(a_{v_1},\ldots,a_{v_i})=h\bigr), \qquad h\in\{0,1\}^i. \)

Initialize \(Q_0(1,\varnothing)=q\) and
\(Q_0(0,\varnothing)=1-q\).

Suppose \(Q_{i-1}\) is known. Let \(b_i(h)\) be the tuple of earlier in-neighbor actions observed by \(v_i\). For a possible observation \(b\) and private signal \(s\), compute

\( \displaystyle W_\theta(s,b)= \Pr(s_{v_i}=s\mid\theta) \sum_{h:\,b_i(h)=b}Q_{i-1}(\theta,h). \)

This factorization is valid because, conditional on \(\theta\), the current private signal is independent of all earlier actions. Earlier actions depend only on earlier private signals and independent tie coins.

The Bayesian action kernel \(K_i(a\mid s,b)\) is determined exactly by comparing \(W_1(s,b)\) with \(W_0(s,b)\): choose the larger-posterior state, or assign probability \(1/2\) to each action when they are equal. Observations with zero total probability can receive any kernel.

Update the joint distribution by

\( \displaystyle Q_i(\theta,(h,a)) = Q_{i-1}(\theta,h) \sum_{s\in\{0,1\}} \Pr(s_{v_i}=s\mid\theta) K_i(a\mid s,b_i(h)). \)

Fresh independent tie coins justify this transition. The correctness probability of \(v_i\) is then

\( \displaystyle \Pr(a_{v_i}=\theta) = \sum_{\theta}\sum_{h\in\{0,1\}^{i-1}} Q_i(\theta,(h,\theta)). \)

Summing these probabilities evaluates \(\ell_t(\sigma)\).

There are exponentially many action histories, but their rational encodings remain polynomially bounded. Indeed, write \(q=A/B\) and \(p=C/E\). Every entry of \(Q_i\) has denominator dividing

\( B E^i2^i. \)

This follows inductively because each transition introduces only signal probabilities with denominator \(E\) and action probabilities in \(\{0,1/2,1\}\). Thus all integers manipulated have \(\operatorname{poly}(r,L)\) bits. Grouping histories by their observed tuples gives total evaluation time

\( 2^r\operatorname{poly}(r,L). \)

This computation accounts exactly for correlations and tie randomness.

4. Proven claim: polynomial extraction on the hard instances

The cited reduction uses three-vertex variable cells and three-vertex clause gadgets. Edges between gadgets run only from variable cells to clause gadgets; a clause gadget receives edges from the cells of its three variables. [Definition 3.4](https://arxiv.org/html/2502.12704v1#S3)

Consequently, every vertex has an incoming ancestor set, including itself, of size at most \(12\):

• A variable-cell vertex has ancestors only within its three-vertex cell.
• A clause-gadget vertex has ancestors within its three-vertex gadget and at most three three-vertex variable cells.

Here an ancestor means a vertex having a directed path to the given vertex, regardless of the order.

For any vertex \(v\), let \(A_v\) be this ancestor set. No edge enters \(A_v\) from outside: such an edge would make its source another ancestor. Therefore, under any public order, the marginal action process on \(A_v\) is exactly the process on the induced graph restricted to \(A_v\), with the inherited relative order.

To justify this assertion, induct on the ordered vertices of \(A_v\). Each such agent observes only earlier agents in \(A_v\). The induction hypothesis gives the same joint distribution of those observations in the full and restricted processes. Its private signal has the same conditional distribution, and the state prior is unchanged. Hence its posterior and action kernel coincide. This proves the induction step.

Apply the evaluator from Section 3 to each induced graph. Since \(|A_v|\leq12\), the score of an arbitrary order on an \(m\)-vertex hard instance is computable in

\( m\,2^{12}\operatorname{poly}(L) \)

time.

Now let an algorithm output an explicit list of \(K\) orders with nonnegative weights summing to \(1\). Evaluate every listed order and choose a highest-scoring one, \(\widehat\sigma\). Then

\( \displaystyle \ell(\widehat\sigma) =\max_{j}\ell(\sigma_j) \geq\sum_j\lambda_j\ell(\sigma_j). \)

Extraction is polynomial in the input and output lengths. Crucially, it preserves the achieved objective value or improves it.

5. Proven claim: approximation hardness transfers

Take a deterministic-order hard instance \((G,q,p)\) from the cited reduction. Construct the society

\( \tau=1,\qquad G_1=G,\qquad \mu_1=1. \)

This is a valid instance: the mass is positive and sums to \(1\), and all parameter requirements are unchanged. Its size is polynomial in the source-instance size.

By Section 2,

\( \displaystyle F^*=\frac{\max_\sigma\ell(\sigma)}{|V|}. \)

Given any feasible output distribution, Section 4 extracts an order satisfying

\( \displaystyle \frac{\ell(\widehat\sigma)}{|V|} \geq F(\lambda). \)

Thus a \((1-\eta)\)-approximation for the society yields a \((1-\eta)\)-approximation for the deterministic hard instance, with polynomial decoding and no approximation loss. Composing this transformation with the cited hardness reduction proves \(\mathrm{APX}\text{-hardness}\).

The fixed-parameter corollary in the source also excludes sufficiently accurate approximation for every fixed \(p\in(\sqrt{7/8},1)\), with \(q=1/2\). In particular, the no-PTAS conclusion already holds with the dyadic constants \(q=1/2\) and \(p=31/32\). [Corollary 5.2](https://arxiv.org/html/2502.12704v1#S5)

Therefore, unless \(\mathrm{P}=\mathrm{NP}\), there is no algorithm achieving the requested guarantee for every \(\eta\in(0,1)\) in time polynomial in \(m,\tau,L\) for each fixed \(\eta\).

6. Running times and an elementary approximation

Enumerate all orders separately for each type, evaluate each exactly, and retain a maximizer. The running time is

\( \displaystyle \sum_{t=1}^{\tau}r_t!\,2^{r_t}\operatorname{poly}(r_t,L) \leq \tau\,m!\,2^m\operatorname{poly}(m,L). \)

The output contains one order per type with weight \(1\). This algorithm is exact, so its running time has no dependence on \(\eta\). It is fixed-parameter tractable in \(m\), despite the unrestricted approximation hardness.

For a polynomial-time constant approximation, output any order for each type. Every Bayesian agent can ignore its observations and always announce a most probable prior state. Posterior maximization has expected accuracy at least that policy’s accuracy, so every agent succeeds with probability at least
\(\max\{q,1-q\}\geq1/2\). Consequently,

\( F(\lambda)\geq1/2\geq F^*/2. \)

Constructing these orders takes
\(O(L+\tau m\log(m+1))\) time under indexed vertex encoding. This achieves the requested guarantee whenever \(\eta\geq1/2\).

⟨structured verdict parsed — rendered above⟩

The output resolves the assigned problem. Its hardness transfer handles the key computational issue: extracting a deterministic order from an explicitly represented distribution takes polynomial time on the cited hard instances. The exact evaluation algorithm and the stated running times are also valid. I found no mathematical issue requiring repair.

• External theorem and applicability

The cited Theorem 5.1 states APX-hardness under a PTAS reduction. Its model has directed graphs, a public deterministic order, binary private signals, correlation-aware Bayesian decisions, and fair posterior ties. The reduction uses \(q=1/2\) and the formula graphs of Definition 3.4. These satisfy the task’s restrictions. Choosing a dyadic \(p>\sqrt{\delta}\) preserves the reduction’s sufficient strict inequality while meeting the binary rational input requirement. [Model definitions and Theorem 5.1](https://arxiv.org/html/2502.12704v1#S5)

The prover explicitly limits its APX-hardness claim to the reduction notion used by the source. This qualification is appropriate.

The fixed rational example also satisfies the cited corollary’s range: \((31/32)^2=961/1024>7/8\), and \(31/32<1\). Thus the fixed-parameter no-PTAS claim applies. [Corollary 5.2](https://arxiv.org/html/2502.12704v1#S5)

• Randomization does not improve the optimum

For each type, \(\ell_t(\sigma)\leq M_t\). Multiplying by nonnegative weights and using their normalization gives
\[ \sum_\sigma\lambda_{t,\sigma}\ell_t(\sigma)\leq M_t. \]
The denominator \(D\) is positive because every mass is positive and every community has at least one vertex.

Each order set is finite and nonempty, so a maximizing order exists. The constraints impose no coupling between types, making the simultaneous choice of one maximizing order per type feasible. Consequently, the displayed formula for \(F^*\) follows.

Weight \(1\) is a valid binary rational representation. The argument therefore establishes attainment within the required output representation, rather than merely an abstract supremum.

The per-type approximation guarantee also follows by multiplying each inequality by its positive mass, summing, and dividing by \(D\).

• Exact evaluation of a fixed order

The initialization correctly includes the state prior.

The factorization defining \(W_\theta(s,b)\) is valid: conditional on the state, earlier actions depend only on earlier private signals and tie coins, which are independent of the current private signal. Summing over histories with the same observed tuple gives precisely the observation probability relevant to the current agent.

Comparing the two joint probabilities \(W_1(s,b)\) and \(W_0(s,b)\) correctly compares posterior probabilities whenever the observation has positive probability. The tie kernel implements the required fair coin. Arbitrary decisions at zero-probability observations do not affect the resulting distribution.

The transition formula correctly averages over the current private signal and action randomness. The correctness-probability formula then sums exactly those histories whose final action equals the state. No independence between observed neighbor actions is assumed.

The denominator bound is valid. Each transition introduces signal denominators dividing \(E\) and action denominators dividing \(2\), so the entries have denominators dividing \(BE^i2^i\). Their numerators and intermediate sums have polynomial bit length.

Grouping histories by observations avoids a separate full scan for every possible observation. The total number of histories processed across all stages is exponential in \(r\), with polynomial work per history. Thus the stated evaluation time \(2^r\operatorname{poly}(r,L)\) is justified.

• Polynomial extraction on the hard instances

The cited construction consists of three-vertex variable cells and three-vertex clause gadgets, with external edges directed from the relevant cells into clause gadgets. This verifies the ancestor bound of at most twelve vertices. [Definitions 3.2–3.4](https://arxiv.org/html/2502.12704v1#S3)

The incoming-closure argument is correct: an edge entering an ancestor set from outside would make its source an ancestor too.

The induction comparing the full and restricted processes is valid. Incoming closure preserves every agent’s observed earlier neighbors. The state prior, conditional signal law, and tie rule are also preserved. The public order carries no additional information about the state because orders are selected independently of it.

Evaluating each vertex on its ancestor set therefore computes its full-network success probability exactly. Summing these values evaluates any listed order in polynomial time on this family.

A finite weighted average cannot exceed its largest constituent score. Selecting the highest-scoring listed order consequently preserves or improves the distribution’s objective. Reading and evaluating the explicit list is polynomial in input and output length; a polynomial-time approximation algorithm necessarily produces polynomial-length output.

• Approximation-hardness transfer

The single-type construction is valid, with positive mass \(1\), unchanged graph and parameters, and polynomial encoding size.

Its objective is the deterministic learning rate averaged over the output distribution. Section 2 identifies its optimum with the deterministic optimum, and Section 4 supplies polynomial decoding without approximation loss.

Therefore, a society PTAS would yield a deterministic-order PTAS on the cited hard family. Composing this transfer with the cited reduction establishes the claimed APX-hardness and conditional exclusion of a PTAS.

• Running times and elementary approximation

Enumerating and evaluating all orders gives the stated bound
\[ \sum_t r_t!\,2^{r_t}\operatorname{poly}(r_t,L) \leq \tau m!\,2^m\operatorname{poly}(m,L). \]
The algorithm is exact, so it has no dependence on \(\eta\). This is fixed-parameter tractable in \(m\) and polynomial for bounded \(m\).

The constant-approximation argument is correct. Posterior maximization has expected accuracy at least that of the constant action selecting the more probable prior state. Thus every agent’s accuracy is at least \(1/2\). Since \(F^*\leq1\), arbitrary orders achieve \(F(\lambda)\geq F^*/2\), which satisfies the requested guarantee when \(\eta\geq1/2\).

The construction-time bound is consistent with reading the input and listing indexed orders and unit weights.

No additional mathematical clarification is needed.

⟨structured verdict parsed — rendered above⟩