{"id":"e06e4d5e-daa9-4ec8-9aa8-af5051c91815","arxiv_id":"2412.12859","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For Bayesian persuasion with externalities and agent types, the paper gives polynomial-time LP algorithms for optimal public, semi-private, and private signaling when the deviation coalition size is constant, and NP-hardness when it is not.","lead":"This paper designs algorithms for a persuader who sends signals to many agents whose choices affect each other. It shows that when agents come in a few types and at most a constant number can coordinate a deviation, optimal signaling can be computed efficiently, and becomes NP-hard otherwise.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Private-case proof hinges on undefined policy ~λ; stability of actual lottery policy λ(σ) is not established as written.","rationale":"The reader's verdict is CONDITIONAL, and my stress-test does not move that verdict. I agree that the private-case proof is the weakest link, but I identify the concrete defect slightly differently: the undefined ˜λ and the missing garbling step, rather than the proportionality factor itself, which can be repaired by a straightforward counting argument. The public and semi-private results (Thms 3.2 and 4.4) rest on more complete arguments and are not threatened by this gap. The LP constraints in Eq. (12) appear to encode exactly the stability condition for the actual λ(σ), so a fix to the proof is plausible; however, as written, the paper does not establish Theorem 5.4 because the chain from Lemma B.2 through Lemma B.4 to the LP is not fully specified. The paper deserves credit for a substantial novel framework and for the earlier proofs; the remaining issue is a verification gap in the most complex part of the argument, not an obvious counterexample to the central claim.","tokens_in":22991,"tokens_out":31209,"duration_ms":303500,"concrete_test":"Define ˜λ(σ) formally and enumerate the full posterior for a small instance (e.g., one world, two agents, actions {a,b}, d=1, σ=(a,b)/2+(b,a)/2) to verify Lemma B.2's equality for ˜λ, then check whether λ(σ) without m satisfies Eq. (12) for every deviation. A second analytical check is to derive the closed form Σ_{a'': a''_i=a'_i, ρ_{a''}=ρ''} c_{ρ''}/d = 1 using the multinomial counts; if either check fails, the private-persuasion polynomial-time claim needs revision.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing defect is in the proof of the private-case theorem (Thm 5.3, used by Thm 5.4). Lemma B.2 is stated for a policy ˜λ(σ) whose private signals include the lottery permutation m (see the proof's notation s=(a',(g',m))), but Definition 9 defines λ(σ) as sending (a',g') with no m. The lemma therefore does not directly justify the stability of the actual lottery policy λ(σ) that the LP (Eq. 12) enforces; the required garbling argument — that hiding m preserves stability — is never given. Moreover, the proportionality step in Eqs. (20)-(21) is asserted rather than proved: the factor Σ c_{ρ''}/d over compatible action vectors is claimed to be 1 from normalization, but the counting that makes it 1 (for profiles with positive count of the observed action) is not shown. If the factor varies, the posterior equality fails and Theorem 5.4 collapses; as written, the proof is not checkable.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies multi-agent Bayesian persuasion with externalities under a type-symmetric model. It defines a stability notion that allows coalitions of up to d agents to deviate jointly. The authors propose revelation-principle-style characterizations for public, semi-private, and private signaling, summarize optimal policies by representative action vectors and blocking profiles, and provide LP formulations. They claim that when d, the number of types, and the number of actions are constant, optimal stable policies can be computed in polynomial time for all three channels (Theorems 3.2, 4.4, 5.4), and that the problems become NP-hard when d is part of the input (Theorem 3.3). The private case introduces a 'lottery policy' to restore representability. The central technical difficulty is proving that randomization over type-preserving permutations preserves stability.","tokens_in":23150,"tokens_out":10630,"duration_ms":94229,"significance":"If the results are correct, they constitute a significant advance in algorithmic information design: they identify a natural tractable regime for multi-agent Bayesian persuasion with externalities, a problem that is generally intractable. The representative-action-vector and blocking-profile techniques are elegant and potentially reusable, and the counterexample in Proposition 5.1 that representative-only policies fail for private persuasion is illuminating. The paper also explicitly demonstrates the failure of the classical revelation principle under joint deviations, which is a conceptual contribution. However, the private-signaling theorem rests on a lottery-policy lemma whose proof is not checkable as written, and the NP-hardness proof is highly compressed. These gaps currently prevent the central algorithmic claims from being fully verified.","major_comments":[{"comment":"Lemma B.2 is stated for a policy \\tilde{λ}(σ) whose private signals include the lottery permutation m (see the proof's notation s' = (a',(g',m))), whereas Definition 9 defines λ(σ) as signaling (a',g') without m. Consequently the lemma does not establish the stability of the policy λ(σ) whose stability is enforced by the private-case LP (Eq. (12)). The missing garbling argument—that discarding the permutation m cannot create new profitable deviations—is nontrivial, since merging signals does not in general preserve stability (as the paper itself shows in the public case via blocking profiles). This gap directly affects Theorems 5.3 and 5.4.","section":"Appendix B.3 (Lemma B.2)"},{"comment":"The step concluding equality of posteriors from the proportionality in Eq. (20) is not justified. The factor c_{ρ''}/d multiplies the original posterior P(ρ'',ω|(a_{m(i)},g_{m(i)})) and may depend on ρ''. The fact that both sides sum to 1 over ρ'' and ω only implies a weighted-average equality; it does not imply that the coefficient is 1 for every ρ''. The authors need to prove that Σ_{a'':ρ_{a''}=ρ'', a''_i=a'_i} c_{ρ''}/d = 1 for each ρ'' separately, or provide an alternative argument. Without this, the claimed identity of agent i's posterior under the lottery policy and the original agent's posterior is unproven.","section":"Appendix B.3, Eqs. (20)–(21)"},{"comment":"The reduction from VERTEX COVER is only sketched. The assertions that 'in every optimal policy only the action vectors of ρ+, ρ− will be signaled' and that stability is equivalent to the posterior beliefs 'forming a graph cover of size k' are stated without derivation. The proof should explicitly show both directions of the equivalence between the existence of a size-k vertex cover and the existence of a stable policy with positive principal utility, including a complete case analysis of all deviations from ρ+ and ρ−. As written, the reduction is not checkable and the NP-hardness claim is not fully verified.","section":"Appendix B.1 (Theorem 3.3)"},{"comment":"The notational inconsistency between λ(σ) and \\tilde{λ}(σ) persists beyond Lemma B.2. Lemma B.3 concludes that \\tilde{λ}(σ) is optimal, while Lemma B.4 equates b(\\tilde{λ}(σ)) with λ(b(σ)), and the proof of Theorem 5.3 then concludes that λ(b(σ)) is stable and optimal. If \\tilde{λ}(σ) and λ(σ) are different policies, the chain of implications is invalid; if they are meant to be the same, the paper should define them consistently and remove the extra m from the proof of Lemma B.2.","section":"Appendix B.3 (Lemmas B.3–B.4, proof of Theorem 5.3)"}],"minor_comments":[{"comment":"In Lemma 4.1, r1,...,rm are said to be non-negative reals, but the proof makes r_i copies of each set and requires |\\tilde{B}_i| = r_i, which only makes sense for integers. The statement should restrict r_i to non-negative integers (which is sufficient for Lemma 4.2).","section":"Lemma 4.1"},{"comment":"The expression 'Eq. (16)' in Appendix A.2 refers to an equation that is not numbered in the main text; it is first introduced in the proof of Lemma B.2. Please add a visible equation number or a clearer cross-reference.","section":"Appendix A.2"},{"comment":"The permutation π used to convert a joint action a to its representative ¯a is not explicitly defined. Please state that π is any type-preserving bijection with ρ_{¯a} = ρ_a, and note why the choice of π does not affect the posterior argument.","section":"Appendix B.2 (proof of Lemma B.1)"},{"comment":"The full text contains minor typographical artifacts, such as missing spaces in the abstract; a careful proofreading pass is advised.","section":"Abstract"}],"recommendation":"major_revision","confidential_remarks":"The stress-test concern about the private-case proof is valid and should be addressed before the paper can be accepted. If Lemma B.2 cannot be repaired, the authors should consider reporting the public and semi-private results separately, or framing the private result as conditional. The NP-hardness proof also needs to be expanded to be verifiable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version: this paper has genuinely new machinery — blocking profiles, signatures, a semi-private channel, and lottery policies — and the public and semi-private polynomial-time results look credible. The private-case proof, as written, has a gap around Lemma B.2 that needs to be closed before Theorem 5.4 is established. I would still send it to peer review.\n\nWhat's actually new: the type-based succinct representation of multi-agent Bayesian persuasion with externalities, the demonstration that the classical revelation principle fails under joint deviations, and the replacement characterization in which signals are (representative action vector, blocking profile). That's a real contribution, not a routine extension. The LP formulations for public and semi-private persuasion are clearly derived from the stability constraints, and the size analysis is sound. The NP-hardness reduction for variable d is plausible but sketched; it needs to be written out in full.\n\nThe soft spots live in the private-channel machinery. Lemma B.2 is stated for a policy \\tilde{λ}(σ) whose private signals include the permutation m, but Definition 9 defines λ(σ) without m. The proof shows that posteriors coincide for \\tilde{λ}, then the paper asserts this carries over to λ with no garbling argument. That's not immediate: hiding m changes what agents know about the correlation device, and stability of the richer policy does not automatically imply stability of the poorer one. Also, the proportionality step in Eqs. (20)-(21) is asserted: the factor Σ c_{ρ''}/d is not shown to be 1 profile-by-profile; the 'posteriors sum to 1' argument only gives an average over profiles. Without that equality, the key posterior-invariance claim is unproven. The public and semi-private results survive, but Theorem 5.4 collapses as written.\n\nMinor issues: the abstract omits the constant-|T| and constant-|A| assumptions, and the definition of B^pub is ambiguous.\n\nBottom line: this is a serious paper by people who know the literature. The citation pattern is fine and the ideas are worth engaging with. The private case needs a real proof repair, and a careful referee should be asked to verify and help fix it, not to reject on sight. I'd bring it to reading group.","headline":"Real new machinery and credible public/semi-private results; the private-case lottery proof has a load-bearing gap that needs repair.","tokens_in":23669,"tokens_out":5137,"would_cite":true,"duration_ms":45268,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91A26","68Q17","90C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that Bayesian persuasion with externalities is polynomial-time solvable for public, semi-private, and private signaling when agent types, actions, and the number of jointly deviating agents are all constant.","keywords":["Bayesian persuasion","externalities","information design","agent types","linear programming","revelation principle","computational complexity","semi-private signaling"],"falsifier":"Run the reshuffling construction on the two-agent example the paper uses to show private persuasion needs non-representative signals, and compare each agent's belief about the action profile before and after reshuffling; if any belief changes, the private-case symmetry step fails.","tokens_in":22771,"feed_emoji":"📣","tokens_out":8447,"duration_ms":77822,"temperature":0.7,"pith_summary":"The paper studies a principal who observes the state of the world and sends signals to multiple agents whose utilities depend on one another's actions, so the principal must simultaneously inform and coordinate them. Its goal is to find the principal's optimal stable signaling policy, stability meaning no group of at most $d$ agents can jointly improve by disobeying the recommendation, under public, semi-private, and private signaling. The central claim is that when the number of agent types, the number of actions, and $d$ are all constant, an optimal stable policy can be found in polynomial time for all three channels, via linear programs over compressed signatures rather than over all possible joint actions. The paper also shows that once $d$ is part of the input, the same problems are NP-hard in every channel. If the construction is right, persuading many interacting agents stops being an exponential search and becomes a tractable optimization problem, with the constant-$d$ bound as the price of tractability.","feed_headline":"Few agent types and bounded collusion make Bayesian persuasion tractable","feed_subtitle":"With constant types, actions, and a cap on joint deviations, all three channels reduce to linear programs.","key_machinery":"The carrying object is the signature: a pair $(ar a, \\beta)$ where $\\bar a$ is a representative action vector, one joint action chosen for each action profile so that profiles are encoded by per-type counts, and $\\beta$ is a blocking profile, a concise record of why each possible joint deviation is not profitable. The linear programs in the paper take probabilities over signatures as variables, and the stability constraints require that every deviation listed in each signal's blocking profile be covered by an agent who weakly prefers the recommended action. For semi-private and private channels, a generalized Hall-type matching lemma compresses the blocking profiles from per-agent explanations to per-deviation explanations, keeping the signal space polynomial. For the private channel, the lottery policy, uniformly permuting the private parts of signals among agents of the same type, is the additional device that makes representative action vectors sufficient.","core_discovery":"The paper's central claim is that, in a Bayesian persuasion model where agents' utilities depend on each other's actions, the optimal stable signaling policy can be computed in polynomial time when the agents fall into a constant number of types, the action set is constant, and at most a constant number $d$ of agents may deviate jointly. This holds for all three communication channels: public (Theorem 3.2), semi-private (Theorem 4.4), and private (Theorem 5.4). The key move is a new revelation-principle-style characterization: because the classical revelation principle fails when groups can deviate together, each signal is represented by a signature made of a representative action vector and a blocking profile that records, for every possible deviation, a set of agents who would not gain from it. For private signaling, even this representation needs help, so the paper introduces lottery policies that uniformly permute private signals among agents of the same type; these restore polynomial-size representation, at the cost of a subtle symmetry argument. The paper also proves that if $d$ is part of the input, the problem becomes NP-hard for all three channels via a reduction from vertex cover.","pith_inferences":["Beyond the paper, the same representative-action-vector idea might compress state spaces in Bayesian implementation or correlated-equilibrium computation whenever payoffs depend on action profiles only through per-type counts.","A natural testable extension is the size of $d$: the proofs count deviations explicitly, so replacing the constant-$d$ assumption with $d = O(\\log n)$ should make the LP grow quasi-polynomially, leaving a sharp threshold to be pinned down.","If the lottery-policy lemma is right, symmetrization by uniform permutation is a free operation for the principal in any anonymous multi-agent information-design problem, not just the one studied here."],"forward_implications":["For constant $d$, $|T|$, and $|A|$, optimal public policies (Theorem 3.2), semi-private policies (Theorem 4.4), and private policies (Theorem 5.4) are all computable in polynomial time by linear programming.","When $d$ is part of the input, all three channels become NP-hard (Theorem 3.3), so the constant-$d$ bound is essential to the tractability results.","The classical revelation principle fails with joint deviations, so optimal signals must encode explanations of why each possible deviation is blocked; this changes what counts as a direct signal in multi-agent persuasion.","For private signaling, restricting to representative action vectors is not without loss (Proposition 5.1), and the lottery policy restores tractability by symmetrizing the agents' roles."],"supporting_citations":[{"why":"Defines Bayesian persuasion and the revelation principle whose failure under joint deviations motivates the paper's signature characterization.","marker":"Kamenica and Gentzkow 2011"},{"why":"Supplies Hall's theorem, whose generalization in Lemma 4.1 is used to compress blocking profiles to polynomial size.","marker":"Hall 1934"},{"why":"Supplies the multi-channel interpolation between public and private persuasion that the paper's semi-private channel adapts.","marker":"Babichenko et al. 2021"},{"why":"Supplies the prior NP-hardness of optimal public persuasion, the barrier the paper's constant-type and constant-$d$ restrictions aim to bypass.","marker":"Bhaskar et al. 2016"},{"why":"Establishes hardness of public signaling even in zero-sum games, providing a contrast for the paper's polynomial-time results.","marker":"Rubinstein 2017"},{"why":"Documents the difficulty of optimizing correlated equilibria in succinctly represented games, the same obstacle the paper avoids with agent types.","marker":"Papadimitriou and Roughgarden 2005"}],"fun_headline_variants":["Bounded collusion keeps Bayesian persuasion tractable","Constant types and small deviations tame Bayesian persuasion","Polynomial-time signaling with cap on collusion","Tractable Bayesian persuasion under limited deviation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The private-signaling algorithm depends on the claim that randomly reshuffling private signals among agents of the same type leaves every agent's beliefs about the world and about others' actions unchanged; if that symmetry step fails, the private-case polynomial-time result collapses.","fun_headline_variants_meta":{"raw":{"variants":["Bounded collusion keeps Bayesian persuasion tractable","Constant types and small deviations tame Bayesian persuasion","Polynomial-time signaling with cap on collusion","Tractable Bayesian persuasion under limited deviation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000221,"raw_usage":{"total_tokens":1450,"prompt_tokens":947,"completion_tokens":503,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":563,"completion_tokens_details":{"reasoning_tokens":447}},"tokens_in":563,"tokens_out":503,"duration_ms":5258,"temperature":1.0,"reasoning_tokens":447,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T13:40:08.640861+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the reshuffling construction on the two-agent example the paper uses to show private persuasion needs non-representative signals, and compare each agent's belief about the action profile before and after reshuffling; if any belief changes, the private-case symmetry step fails.","supporting_citations":[],"review_version":1}