{"id":"de732eed-aed2-4f42-94c3-1a3fb8b569e0","arxiv_id":"2611.16327","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Forest hierarchies in binary-state Bayesian persuasion are tractable for symmetric or modular sender utilities, but supermodular utilities admit no FPTAS, and non-forest hierarchies are hard even for symmetric utilities.","lead":"This paper studies how a sender should share information with receivers arranged in a tree-like hierarchy, where each receiver sees the signals sent to those below them. It shows that for some objectives the optimal disclosure policy can be found quickly, while for others the problem is provably hard to approximate.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek/deepseek-v4-flash","headline":"Theorem 10's pivotal tightness step for the relaxed LP (14) is asserted by an informal construction and is the least externally-validated link; an undetected failure there would make the claimed V* computation an overestimate.","rationale":"I read the paper's core claims and checked the proof dependencies in good faith. The reader's weakest assumption, Fact 2 from Brooks-Frankel-Kamenica, is a published characterization that the paper applies to forest hierarchies with binary states and nested observation — squarely within that work's stated hypotheses — so I do not regard it as an internally suspect link. The genuinely load-bearing step is the internal proof of Theorem 10 that every feasible point of the relaxed LP (14) can be lifted to an inducible information structure with the same objective value. This lifting is proven by an involved recursive construction (preorder traversal, state-conditional root draws, children drawn from the mixture conditioned on the parent's pair) followed by an induction on depth. I traced the main equalities (posterior of each receiver equals q_i; objective preserved via the total count equaling κ_r) and found no concrete error, but the argument is informal, intricately layered, and completely unverified by independent means. Since the paper offers no implementations or formal proofs, this is the point where a silent gap would most plausibly hide. My concrete test — brute-force comparison of LP (14) against LP (1) on small chains and stars — would settle whether the relaxation is tight in the regimes the theorem claims. Given that no counterexample was identified, I do not move the verdict; the reader's ACCEPT with moderate confidence remains appropriate, though the test would raise confidence if it passes.","tokens_in":34304,"tokens_out":36206,"duration_ms":458363,"concrete_test":"Construct small forest instances and exhaustively compare the LP (14) optimum with the true V* from LP (1) over the same grid. Specifically, take a 3-receiver chain and a root-with-two-children star, uniform prior µ=1/2, grid Θ with m=4 evenly spaced points, random thresholds (t_i within the grid), and several random monotone symmetric utilities u(S)=f(|S|). For each instance, enumerate all joint grid posteriors to solve both LP (1) and LP (14) exactly, and check whether the LP (14) optimum strictly exceeds the LP (1) optimum. Repeat for at least 100 random instances per topology. Any instance with a strict gap is a counterexample to Theorem 10's tightness claim and shows the polynomial-time algorithm overstates V*; if all instances match, the construction's correctness is supported for small cases.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's centerpiece is the weakly polynomial algorithm for the symmetric sender-utility case. It solves the relaxed LP (14), whose optimum is claimed to equal V* via Theorem 10. The proof of this tightness is a recursive construction: after drawing roots' (q_i,κ_i) pairs from the state-conditional distributions Y^ω, each node's children are drawn from the unconditional mixture conditioned on the parent's pair. Correctness rests on several subclaims: (i) children's pairs are independent of ω given the parent's pair, so the induction (17) holds; (ii) the conditional-distribution equality (15) transfers the second constraint family of LP (14) into the constructed scheme; (iii) the induction showing each receiver's posterior equals q_i is sound; and (iv) the objective value is preserved because the total action count equals κ_r for a root r and its distribution matches that of X. Each step is plausible, but the argument is intricate and informal, with no formal verification or independent reimplementation. In contrast, the reader's flagged Fact 2 (Brooks, Frankel, Kamenica) is a published characterization used within its stated hypotheses, so that cited dependence is not itself a defect. The genuinely load-bearing, least externally supported step is the LP (14)-to-inducible lifting. If any part of that construction fails on some instance — for example, if the children's-pair independence does not survive the conditioning, or if the action-count distribution under X' diverges from that of X — then the relaxation is not tight and solving LP (14) yields a value larger than V*, invalidating Theorem 10. I found no concrete counterexample, so this is a verification-critical soft spot rather than a demonstrated error.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek/deepseek-v4-flash","summary":"The paper studies algorithmic aspects of Bayesian persuasion with a forest communication hierarchy, where receivers observe signals according to a rooted directed forest. The sender has a binary state, binary-action receivers, and a monotone utility function of the set of receivers taking a desirable action. The main results are: (1) a polynomial-time algorithm for symmetric sender utility (Theorem 10); (2) a polynomial-time algorithm for modular utility (Proposition 5); (3) NP-hardness and inapproximability (no FPTAS unless P=NP) for supermodular utility even for chains of three receivers (Theorem 7); (4) constant-factor approximation algorithms for supermodular and submodular utility with depth-dependent ratios (Propositions 8 and 9); (5) NP-hardness and inapproximability for non-forest hierarchies even with symmetric three-valued utility (Proposition 12). The paper uses linear programming characterizations, optimal transport ideas, and reductions from max-cut and minimum b-union.","tokens_in":34842,"tokens_out":4014,"duration_ms":33535,"significance":"If correct, the results significantly advance the understanding of computational tractability in multi-receiver Bayesian persuasion with hierarchical information. The positive result for symmetric utility is the first polynomial-time algorithm for forest hierarchies with non-modular objectives. The hardness results delineate the boundary between tractable and intractable cases, showing that the forest property is crucial. The approximation algorithms provide practical guarantees. The paper bridges private and public persuasion and contributes to algorithmic information design.","major_comments":[{"comment":"The proof that every feasible solution of the relaxed LP (14) can be transformed into an inducible information structure (the 'tightness' step) is presented as a recursive construction described in prose (paragraphs after (14) through the induction). The argument is intricate and relies on several subclaims: (i) children's pairs are independent of ω given the parent's pair, (ii) the conditional-distribution equality (15) transfers the second constraint family, (iii) the induction showing each receiver's posterior equals q_i is sound, and (iv) the objective value is preserved. However, the construction is not fully formalized; there is no explicit verification that the constructed distribution X' satisfies the Bayes-plausibility and mean-preserving spread constraints required by Fact 2, nor that the signaling scheme derived from X' respects the forest hierarchy. The paper acknowledges that the support may be exponential (Remark 11), but the correctness of the algorithm depends on the existence of a polynomial-time separation oracle for the dual, which in turn relies on the claim that the relaxed LP's optimum equals V*. If the tightness argument has a gap, the algorithm might compute an overestimate. The authors should provide a more rigorous proof, possibly by showing that the constraints of LP (14) are exactly those implied by Fact 2 for the symmetric case, or by giving an explicit mapping from a feasible solution of (14) to a feasible solution of the original LP (1) with the same objective. The current inductive construction is plausible but not fully convincing.","section":"§5, Theorem 10 and the proof of tightness of LP (14)","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The lexicographic reduction from max-cut relies on choosing M1 and M2 such that optimal signaling schemes must first maximize E[u1], then E[u2] subject to that, then E[u3]. The argument for M1 uses a constant C_v defined as the minimum nonzero difference between values of E_v at vertices of a polyhedron derived from Lemma 6. However, the polyhedron is not explicitly described, and it is not clear that C_v is a global constant independent of the instance size (k). The paper states C_v = O(1), but the polyhedron's vertices depend on the grid Θ and the chain structure; the minimum nonzero difference could be exponentially small in the representation of thresholds. The authors should clarify the derivation of C_v and argue that it is bounded below by a polynomial in the input size, or provide an alternative argument for the existence of polynomially bounded M1. Similarly, the choice of M2 = 4k^2 is based on bounding the gain in E[u3] by ρ·2k^2, but this bound assumes that the loss in E[u2] is at least ρ(k-1)/2. The argument that the loss is at least ρ(k-1)/2 relies on the fact that if not all X_v are equal, there are at least k-1 pairs with X_v ≠ X_w. However, the loss in E[u2] is ∑_{v≠w} E[(X_v - X_w)^2]/2, and if the X_v are not all equal, the sum could be as small as 1 (if only one pair differs). The paper should justify the lower bound of ρ(k-1)/2 or adjust the choice of M2 accordingly.","section":"§4.1, Theorem 7, choice of M1 and M2","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The approximation algorithm for supermodular utility achieves a 1/(h+1) multiplicative approximation. The proof constructs a signaling scheme that uses the private persuasion optimal scheme π_p with probability 1/(h+1) in each state, and otherwise sends uninformative signals. However, the analysis relies on the fact that the sender's optimal value under private persuasion is an upper bound for any communication hierarchy, which is cited from [8]. The paper should verify that the upper bound holds for the specific setting (binary state, binary actions, monotone utility). Additionally, the construction for ω=1 involves choosing a depth l uniformly and then drawing subsets Q_i according to the conditional distribution of S∩T_i under π_p given ω=0 and i∈S. This requires that ρ_i > 0; if ρ_i = 0, the construction is defined arbitrarily. The paper should discuss the case ρ_i = 0 and ensure the approximation guarantee still holds. Also, the proof of inequality (9) uses a lower bound on Pr_π[ω=1 ∩ Q_i] that assumes the probability of choosing l equal to the depth of i is exactly 1/(h+1), but the construction for ω=1 chooses l uniformly from {0,...,h}, so the probability that a given receiver i of depth d_i gets the 'special' treatment is 1/(h+1) only if the depth of i is exactly the chosen l. The analysis should account for the fact that receivers of different depths may have different probabilities of receiving the signal 1 under the construction. The current argument seems to assume that for each receiver i, the event that l equals its depth occurs with probability 1/(h+1), which is true, but the lower bound on Pr_π[ω=1 ∩ Q_i] uses only that case, ignoring contributions from other depths where i might still receive signal 1 (e.g., if l < depth of i, then i receives signal 1 because all receivers with depth strictly less than l get signal 1, but i's depth is greater than l, so i might not get signal 1 unless it is in the subtree of some node at depth l). The construction sends s_j = 1 to all receivers with depth strictly less than l, and for receivers at depth exactly l, it draws Q_i. Receivers with depth greater than l receive signal 1 only if they are in the subtree of a node at depth l that was selected. Thus, a receiver of depth > l may or may not receive signal 1.","section":"§4.2, Proposition 8, approximation ratio 1/(h+1)","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The proof that V* ≤ 3/4 - 1/(2 l^2 k^2) when every b-set has union > k contains several steps that are not fully justified. The argument deduces that conditional on ω=1, w.p. ≥ 1 - 2/(l^2 k^2) there are at least b set receivers with posterior 1 and at least k+1 element receivers with posterior 1. The derivation from the assumption that V* ≥ 3/4 - 1/(2 l^2 k^2) is not explicit; it uses the fact that u takes values in {0,0.5,1} and that there are l element receivers. The paper should provide a more detailed derivation, possibly using Markov's inequality or Chebyshev, to justify the probability bounds. Additionally, the final contradiction uses an inequality involving E[1-p_ei | p_ei < 1/2] Pr[p_ei < 1/2] ≥ E[max{1-2p_ei,0}] and then relates to Pr[p_ei = 1]. The step E[max{1-2p_ei,0}] ≥ Pr[p_ei = 1] is not generally true; it holds only if p_ei = 1 implies 1-2p_ei = -1, so max{1-2p_ei,0} = 0 when p_ei = 1. The inequality should be reversed: E[max{1-2p_ei,0}] ≤ Pr[p_ei = 1]? Actually, max{1-2p_ei,0} is 0 when p_ei ≥ 0.5, and positive when p_ei < 0.5. The event p_ei = 1 gives max{1-2p_ei,0}=0, so the expectation of max{1-2p_ei,0} is at most the probability that p_ei < 0.5, not directly comparable to Pr[p_ei = 1]. The contradiction seems to rely on an erroneous inequality. The authors should re-examine this part of the proof.","section":"§6, Proposition 12, proof of the lower bound on V* when no b-set has union ≤ k","authors_acknowledge":null,"authors_acknowledge_p":null}],"minor_comments":[{"comment":"The example uses a chain '1/Leftr⫯g⊸tl⫯ne⇒2/Leftr⫯g⊸tl⫯ne⇒3' which appears to be a formatting artifact. The intended relation should be clarified.","section":"§1, Example 1","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The definition of D_i as the set of receivers dominated by receiver i together with receiver i himself is clear, but later in §5, the variable k_i(¯l) is defined as |{j∈D_i∖{i} : τ_{l_j} ≥ t_j}|, which counts only descendants, not including i. This is consistent but could be explicitly noted to avoid confusion.","section":"§2, Notation 4","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The inequality (3) is derived for any q∈supp(p_v3). The case analysis is correct, but the statement 'with equality iff supp(p_v3)={t_v2, t_v3} and p_v2 ≥ t_v2 = 1/4 w.p.1' should be verified: equality in case 2 requires q=1/4 and I_{v3∈S}=1, which implies p_v3 = 3/4? Actually, case 2 is 1/4 ≤ q < 3/4, and LHS=2, RHS=1+4q, equality iff q=1/4. But if q=1/4, then I_{v3∈S}=0 because t_v3=3/4, so LHS=2*0+2*min{1,4q}=2*1=2, RHS=1+1=2. So equality holds when q=1/4 and p_v2 ≥ 1/4 w.p.1. The condition 'supp(p_v3)={t_v2, t_v3}' means p_v3 takes values 1/4 and 3/4, which is consistent. The text should be precise.","section":"§4.1, Step 2","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The computation of the probability that ω=0 and Point 2 holds is given as 1/8α - 1/8. For α=4/5, this becomes 1/(8*4/5) - 1/8 = 5/32 - 4/32 = 1/32. The text says '1/8α - 1/8 = 1/2 - 3/8α' leading to α=4/5. The derivation should be checked for arithmetic errors.","section":"§4.1, Step 4","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The second family of constraints in LP (14) is written as ∑_{¯l: p(¯l)_i = q_i, k_i(¯l)=κ_i} (τ_{l_j} - q_i)(µ x^1_¯l + (1-µ) x^0_¯l) = 0 for (j,i)∈E. The explanation says this is obtained by considering the difference of two sums of constraints from LP (1). However, the derivation is not fully explained; it would be helpful to show how the mean-preserving spread condition translates to this linear constraint.","section":"§5, LP (14)","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The dual variables γ_{iκ,l} and δ_{j,iκ,l} are introduced but their indices are not fully defined. The range for κ is 0 ≤ κ < d_i, but in the constraints, k_i(¯l) can be up to d_i - 1, which is consistent. However, the dual constraint for ω=1 includes a term µ ∑_{i=1}^n (1-τ_{l_i}) γ_{i k_i(¯l), l_i} + µ ∑_{(j,i)∈E} (τ_{l_j} - τ_{l_i}) δ_{j,i k_i(¯l), l_i} ≥ µ f(|S(¯l)|). The sign of the δ term should be checked: in the primal, the constraint is ∑ (τ_{l_j} - q_i)(µ x^1 + (1-µ) x^0) = 0, so the dual variable δ multiplies (τ_{l_j} - τ_{l_i}) which can be positive or negative. The dual constraint should have the same sign as in the primal. The paper should verify the dual derivation.","section":"§5, dual LP (18)","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The dynamic programming recursion (19) uses M_{i,b,l} = min_{κ_i, l_i: κ_i + I_{τ_{l_i} ≥ t_i} = b} {F(i, κ_i, l_i) + (τ_l - τ_{l_i}) δ_{j,i κ_i, l_i}}. The term (τ_l - τ_{l_i}) δ_{j,i κ_i, l_i} depends on l, the parent's posterior index. This is correct. However, the recursion for N_{jξ,b} uses M_{iξ,ζ,l} where ζ is the number of 'adopting' descendants including the child itself? The definition of b in M_{i,b,l} is the number of receivers in the subtree of i that take action 1, including i? The text says 'κ_i(b) + I_{τ_{l_i(b)} ≥ t_i} = b', so b is the total number of adopters in the subtree rooted at i (including i). Then in the recursion for N_{jξ,b}, ζ is the number of adopters in the subtree of the ξ-th child. This is consistent. The explanation is clear but could be more explicit about the base case for leaves.","section":"§5, separation oracle","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The reduction from minimum b-union uses a uniform prior and specific thresholds. The proof that V* = 3/4 when a b-set with union ≤ k exists is straightforward. The converse direction is more involved and contains the potential error noted in major comments. The paper should also clarify that the communication hierarchy is a directed bipartite graph, which is not a forest, and that the result holds even for symmetric utility taking only three values.","section":"§6, Proposition 12","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The proof uses a transformation that spreads probability mass from an interior point q to the nearest grid points τ_{j-1} and τ_j in a mean-preserving way. The argument that the parent's distribution is a mean-preserving spread of the new distribution is technical. The proof seems plausible but could be streamlined. There is a minor typo: 'the resultant distribution ν over {τ_{j-1}, τ_j}' should be 'over {τ_{j-1}, τ_j}'.","section":"Appendix A, proof of Lemma 3","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The paper uses the notation 'Leftr⫯g⊸tl⫯ne⇒' which appears to be a LaTeX artifact. It should be replaced with standard notation like '→' or 'dominates'.","section":"General","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"Reference [8] is listed as 'Babichenko, Talgam-Cohen, Xu, and Zabarnyi. Multi-channel Bayesian persuasion. ITCS 2022.' This is a published paper, so it is appropriate. However, the paper also cites [21] as 'Candogan, Guo, and Xu. On information design with spillovers. Available at SSRN 3537289, 2020.' This is a working paper; the authors should check if a published version exists.","section":"References","authors_acknowledge":null,"authors_acknowledge_p":null}],"recommendation":"major_revision"},"author_rebuttal":null,"desk_editor":{"model":"deepseek/deepseek-v4-flash","letter":"Dear colleague,\n\nThis is a solid piece of algorithmic information design. The main new results: exact poly-time for symmetric utilities on forest hierarchies (Theorem 10), no FPTAS for supermodular even on chains of depth 2 (Theorem 7), and no FPTAS for non-forest bipartite hierarchies even with symmetric 3-valued utilities (Proposition 12). The first and third are genuinely new relative to the private-persuasion benchmarks, and the paper positions them carefully against [7,2,8,21].\n\nWhat I like: the LP characterization (Lemma 6) is a nice generalization of the transportation approach in [4], and the proof of Theorem 7 is a careful lexicographic reduction from max-cut with explicit weights. The approximation results (Propositions 8 and 9) are simple but fill a gap. The paper is honest about the exponential support issue and the need for a dual separation oracle.\n\nThe main soft spot is Theorem 10's core step: showing that every feasible solution of the relaxed LP (14) can be lifted to an inducible information structure without changing the objective. The construction is recursive and plausible, but the tightness hinges on several conditional-independence and distribution-matching claims that are asserted rather than machine-checked. The stress-test note is right that this is the least externally validated link. I didn't find a counterexample, but the proof is intricate enough that I'd want a careful referee to re-derive equations (15)-(17).\n\nOther minor points: the paper assumes binary states and binary actions, which is standard, but the extension to more states is left open. The dependence on Fact 2 from Brooks et al. is fine because that's a published characterization. The self-citation to [8] is used only as an upper-bound benchmark, so no issue there.\n\nOverall, if the Theorem 10 argument is correct, this is an important contribution to the algorithmic study of hierarchical information design. Even without full formal verification, the rest of the paper stands on its own. I'd send it to a serious journal.\n\nRecommendation: engage with it, but tell the authors to tighten the proof of Theorem 10—either by giving a more detailed induction or by providing a verifiable certificate. It deserves peer review.","headline":"Solid algorithmic paper with a load-bearing but unverified lifting step in Theorem 10.","tokens_in":35634,"tokens_out":1563,"duration_ms":15145},"pith_extraction":{"msc":["91A28","91B44","68Q25","90C05"],"pacs":[],"model":"deepseek/deepseek-v4-flash","headline":"This paper claims that the forest structure of a communication hierarchy separates efficient from hard optimal persuasion: symmetric utilities are polynomial-time solvable, supermodular utilities have no FPTAS unless P=NP.","keywords":["Bayesian persuasion","multi-receiver persuasion","communication hierarchy","forest hierarchy","information design","computational complexity","optimal signaling","supermodular utility"],"falsifier":"Construct a concrete forest hierarchy with depth 2 and a monotone supermodular sender utility, run the $1/(h+1)$-approximation algorithm from Proposition 8, and compare its output with an exact or exhaustive computation on a small instance; if the value ever falls below $1/(h+1)$ of the optimum, the approximation guarantee is false. Alternatively, exhibit a non-forest directed bipartite hierarchy with a symmetric three-valued sender utility that admits an FPTAS, which would refute Proposition 12.","tokens_in":37421,"feed_emoji":"🌲","tokens_out":3991,"duration_ms":49851,"temperature":0.7,"pith_summary":"This paper studies an information-design setting where a sender sends signals to receivers arranged in a forest hierarchy, meaning some receivers see the signals meant for those below them. It claims that whether the sender's optimal signaling scheme can be computed efficiently hinges on two things: the shape of the hierarchy (forest versus general directed graph) and the structure of the sender's utility function over the set of adopting receivers. For symmetric utilities, where only the number of adopters matters, there is a polynomial-time algorithm for the optimal value, even though the optimal scheme itself may need exponentially many signals. For supermodular utilities, which model increasing returns, the problem admits no fully polynomial-time approximation scheme unless P=NP, but a simple depth-dependent approximation is available. If the claims are right, tree-like information hierarchies are both a sufficient condition for exact tractability in the symmetric case and, in a complexity-theoretic sense, necessary.","feed_headline":"Forest hierarchies decide tractability of optimal persuasion","feed_subtitle":"Polynomial-time algorithm for symmetric utilities; no FPTAS for supermodular unless P=NP","key_machinery":"The central object is Lemma 6, a linear program that characterizes every inducible distribution over joint posteriors for a forest hierarchy. Variables $x^w_{\\bar{l}}$ give the probability, conditional on state $w$, of realizing a grid-valued joint posterior indexed by $\\bar{l}$; constraints enforce Bayes plausibility for every subtree and capture the nesting of beliefs along edges. This LP generalizes the optimal-transport approach to private persuasion and is the workhorse of both the positive and negative results. For symmetric utilities the paper relaxes the LP to constraints that only involve each receiver's own posterior and the number of descendants who adopt; a recursive construction proves the relaxation is tight, and dynamic programming over the forest gives a polynomial-time separation oracle for the dual, yielding the exact algorithm of Theorem 10. The hardness results are produced by lexicographic reductions from max-cut and minimum b-union, using specifically chosen thresholds and supermodular components to force a max-cut structure in the forest-hierarchy instance.","core_discovery":"The paper's central claim is a delineation by hierarchy shape. For forest hierarchies with binary state and binary-action receivers, the sender's optimization problem is exactly solvable in weakly polynomial time when the utility is symmetric (Theorem 10), and also exactly solvable for modular utilities (Proposition 5). By contrast, for monotone supermodular utilities the problem is NP-hard and has no FPTAS unless P=NP, even when every tree component is a chain of three receivers (Theorem 7); the paper still provides a $1/(h+1)$-factor approximation, where $h$ is the depth of the forest (Proposition 8), and an analogous $(1-1/e)/(h+1)$-factor result for submodular utilities (Proposition 9). Once the hierarchy is allowed to be a non-forest directed graph, even a depth-1 bipartite graph, the symmetric utility case also loses all FPTAS possibilities unless P=NP (Proposition 12). The overarching conclusion is that the forest property carries the computational boundary: symmetric objectives are tractable exactly when the hierarchy is a forest, and supermodular objectives remain hard even within forests.","pith_inferences":["One implicit lesson is that computational tractability in information design may serve as a principled metric for when hierarchy shapes are simple enough to manage: forests, and especially shallow ones, are the workable regime.","The LP characterization might transfer to other settings with nested information, such as multi-stage supply chains or layered regulatory reporting, whenever the information order is a forest.","A testable extension would be to replace the binary state with more states and see whether symmetric-utility tractability disappears or only requires a more nuanced separation oracle; the paper leaves this open."],"forward_implications":["A sender who only cares about the total number of adopters can compute the exact optimal value in polynomial time for any forest hierarchy, even when the underlying optimal scheme is too large to write down explicitly.","For objectives with complementarities among adopters, even very shallow forest hierarchies made of chains of length three are computationally as hard as max-cut, so exact or near-exact algorithms will not exist unless P=NP.","The constant-factor approximations degrade linearly with hierarchy depth, meaning shallow organizations can still certify a meaningful fraction of the optimal persuasion value.","Non-forest information access creates hardness even for the simplest three-valued symmetric utilities, so in applications overlapping information channels should be treated as a computational warning sign."],"supporting_citations":[{"why":"Supplies the characterization of inducible marginals for forest hierarchies (Fact 2) that underlies the LP formulations.","marker":"[18]"},{"why":"Defines the private-persuasion benchmark and the symmetric-utility algorithm this paper generalizes.","marker":"[7]"},{"why":"Establishes supermodular-utility tractability under private persuasion, which the paper contrasts with its forest-hierarchy hardness.","marker":"[2]"},{"why":"Provides the modular-utility additive FPTAS and the private-persuasion upper bound used in the approximation arguments.","marker":"[8]"},{"why":"Provides the optimal-transport coupling view of private persuasion that Lemma 6 generalizes.","marker":"[4]"},{"why":"Studies hierarchical information spillovers and gives the non-forest hardness result that Proposition 12 strengthens.","marker":"[21]"}],"fun_headline_variants":[],"cache_read_input_tokens":0,"weakest_assumption_plain":"The load-bearing premise is the cited Fact 2 characterization that, for a forest hierarchy, a collection of marginal posterior distributions is inducible exactly when each marginal is Bayes-plausible and each parent marginal is a mean-preserving spread of each child marginal; if that characterization fails for this model, the LP lemma and both positive algorithms collapse.","fun_headline_variants_meta":{"raw":{"variants":[]},"model":"deepseek/deepseek-v4-flash","effort":"low","cost_usd":8.9e-05,"raw_usage":{"cost":8.86522e-05,"is_byok":false,"cost_details":{"upstream_inference_cost":8.86522e-05,"upstream_inference_prompt_cost":8.64682e-05,"upstream_inference_completions_cost":2.184e-06},"total_tokens":1167,"prompt_tokens":1155,"completion_tokens":12,"prompt_tokens_details":{"audio_tokens":0,"video_tokens":0,"cached_tokens":256,"cache_write_tokens":0},"completion_tokens_details":{"audio_tokens":0,"image_tokens":0,"reasoning_tokens":0}},"tokens_in":1155,"tokens_out":12,"cost_source":"openrouter_usage","duration_ms":2775,"image_pages":[],"temperature":1.0,"billed_attempts":1,"reasoning_tokens":0,"transport_provider":"openrouter","cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-11-13T07:03:19.038766+00:00","model_set":{"reader":"deepseek/deepseek-v4-flash"},"pipeline_version":"pith-pipeline@v1.4.1-daily-deepseek-or-medium","input_kind":null,"input_chars":null,"input_total_chars":null,"passes_missing":null,"published_standing":null,"published_confidence":null,"objection_audit":null,"run_record":null,"basis":{"kind":"not_recorded","source":null,"chars_given":null,"chars_total":null},"receipt":null,"falsifier":"Construct a concrete forest hierarchy with depth 2 and a monotone supermodular sender utility, run the $1/(h+1)$-approximation algorithm from Proposition 8, and compare its output with an exact or exhaustive computation on a small instance; if the value ever falls below $1/(h+1)$ of the optimum, the approximation guarantee is false. Alternatively, exhibit a non-forest directed bipartite hierarchy with a symmetric three-valued sender utility that admits an FPTAS, which would refute Proposition 12.","supporting_citations":[{"cited_title":"Information hierarchies.Econometrica, 90(5):2187–2214, 2022","cited_arxiv_id":null,"evidence_quote":"Supplies the characterization of inducible marginals for forest hierarchies (Fact 2) that underlies the LP formulations."},{"cited_title":"Computational Aspects of Private Bayesian Persuasion","cited_arxiv_id":"1603.01444","evidence_quote":"Defines the private-persuasion benchmark and the symmetric-utility algorithm this paper generalizes."},{"cited_title":"Private Bayesian persuasion.Journal of Economic Theory, 182: 185–217, 2019","cited_arxiv_id":null,"evidence_quote":"Establishes supermodular-utility tractability under private persuasion, which the paper contrasts with its forest-hierarchy hardness."},{"cited_title":"Multi-channel Bayesian persuasion","cited_arxiv_id":null,"evidence_quote":"Provides the modular-utility additive FPTAS and the private-persuasion upper bound used in the approximation arguments."},{"cited_title":"Persuasion as transportation","cited_arxiv_id":null,"evidence_quote":"Provides the optimal-transport coupling view of private persuasion that Lemma 6 generalizes."},{"cited_title":"On information design with spillovers.Available at SSRN 3537289, 2020","cited_arxiv_id":null,"evidence_quote":"Studies hierarchical information spillovers and gives the non-forest hardness result that Proposition 12 strengthens."}],"lane_accuracy":{"status":"not yet measured","lane":{"model":"deepseek/deepseek-v4-flash","input_kind":null},"url":"https://pith.science/accuracy"},"review_version":1}