{"id":"751e94e7-7f55-4450-8c13-052f5ddc5658","arxiv_id":"2411.16624","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"This paper introduces leakage-robust Bayesian persuasion and proves that the price of worst-case robustness is Theta(min{2^k, n}) for supermodular preferences and Theta(k) for submodular preferences, with improved bounds under random leakage models.","lead":"This paper introduces a model of Bayesian persuasion in which private messages between a sender and receivers can leak to other receivers, and it quantifies how much sender utility is lost by making persuasion robust to such leaks. The main results are tight bounds on the price of robustness for worst-case and random leakage patterns, plus two general algorithmic transformations, subsampling and masking.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"PoDR lower bounds for k-broadcast and k-clique are proved only against prefix-based schemes, while OPT_expected is defined over all signaling schemes; Appendix F shows indirect schemes can beat direct ones, so the Θ(k) claims are not established for the defined benchmark.","rationale":"The reader's weakest_assumption correctly identifies a gap between the benchmark used in lower-bound proofs and the benchmark in the formal definition of OPT_expected. I agree this is the most load-bearing concern for the expected-downstream-utility results. However, I would sharpen the diagnosis: the direct-versus-indirect ambiguity does not threaten the upper bounds on PoDR, because those are lower bounds on OPT_expected obtained by exhibiting feasible direct schemes. The real problem is that the lower bounds on PoDR are established only against prefix-based schemes, which are a strict subclass of direct schemes; Appendix F shows that indirect schemes can be strictly better than direct schemes, so the gap is real. The paper itself flags the prefix-based restriction with '†' in Table 1, which is honest, but the abstract's unqualified 'Θ(k)' statements overstate what is proven. The worst-case robustness results (PoWR) appear sound and are supported by the LP characterization and subcube-partition argument, and the upper-bound constructions for downstream utility are valid as lower bounds on OPT_expected. Thus the paper should not be rejected outright; it should be conditionally accepted pending either a proof of the lower bounds against all schemes, a redefinition of the benchmark to prefix-based or direct schemes, or a correction of the abstract and table claims. My agreement with the reader is partial because the reader also lists the direct-scheme upper bounds as a concern, which I do not think is load-bearing for the reasons above.","tokens_in":37906,"tokens_out":5301,"duration_ms":49302,"concrete_test":"Solve, for the k-broadcast instance of Example 4.1 with n=6 and k=3, the optimization max over all direct signaling schemes (binary signal spaces) of expected downstream utility by enumerating the finitely many best-response regions and solving the resulting linear program. If the optimum exceeds the O(n/k) prefix-based bound used in Theorem 4.4, the claimed Ω(k) lower bound for OPT_expected fails immediately. If it does not, repeat with a ternary signal space, as Appendix F shows indirect schemes can strictly outperform binary ones; a ternary scheme beating the prefix bound would likewise falsify the lower bound. This directly tests whether the prefix-based restriction is benign for the central PoDR claims.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Section 2.3 defines OPT_expected(G) as a supremum over all signaling schemes µ, with no restriction to direct or prefix-based schemes. The upper bounds on PoDR (Theorems 3.7 and 3.9) are proven by explicit direct schemes, so they remain valid lower bounds on OPT_expected. The load-bearing gap is on the lower-bound side: Theorem 4.4 (k-broadcast) and Theorem 4.6 (k-clique) upper-bound the sender's expected utility only over prefix-based schemes (Definition 4.1). They do not bound OPT_expected, which ranges over all direct and indirect schemes. This matters because Appendix F gives an n=3 instance with deterministic leakage where an indirect scheme strictly outperforms every two-signal/direct scheme, so the direct/indirect distinction is not benign. Consequently, the paper has not established PoDR(k-broadcast) = Ω(k) or PoDR(k-clique) = Ω(k/log k) for the quantity OPT_expected defined in Section 2.3. The abstract's unqualified 'becoming Θ(k)' statements for downstream utility are therefore unsupported, and the entries in Table 1 marked '†' are only bounds against a restricted benchmark. This is a correctness risk for one of the paper's central advertised contributions.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a model of Bayesian persuasion with signal leakages, interpolating between private and public persuasion. Two robustness notions are studied: k-worst-case persuasiveness, where each receiver may observe up to k leaked signals and adopters must not deviate, and expected downstream utility robustness, where the leakage graph is random and receivers best respond to their observations. The main results are: (i) for worst-case robustness, the price of robustness PoWR_k is Θ(min{2^k,n}) for supermodular sender utilities and Θ(k) for submodular/XOS utilities, with constructive subsampling schemes and matching lower-bound instances; (ii) for expected downstream utility, the price PoDR is O(1) for the k-star model, O(k) or Θ(k) for k-broadcast and k-clique, and O(min{2^k,n}) for k-Erdős–Rényi leakages, with lower bounds for k-broadcast and k-clique proved only for prefix-based schemes. The paper also shows that subsampling and masking are general-purpose algorithmic paradigms for leakage-robust persuasion, and discusses the absence of a revelation principle in the expected-utility setting, including a small instance where indirect schemes outperform direct schemes.","tokens_in":38147,"tokens_out":13644,"duration_ms":123619,"significance":"If the downstream-utility claims can be brought fully in line with the defined benchmark, this will be a valuable contribution to algorithmic Bayesian persuasion. The worst-case results are the strongest part of the paper: the LP characterization in Section 3, the subsampling constructions (Lemmas 3.2 and 3.4), and the matching lower bounds in Section 4 are concrete, rigorous, and provide a genuine new understanding of the cost of worst-case leakage robustness. The k-star Θ(1) expected-utility result and the O(k) upper bounds are also useful and are established by explicit feasible schemes, so those directions are on solid ground. The paper's main weakness is that several advertised downstream lower bounds are proved only against a restricted class (prefix-based schemes), while the benchmark OPT_expected is defined over all signaling schemes; Appendix F shows the direct/indirect distinction is not benign. This is a correctness risk for one of the central advertised contributions, but it is fixable by either extending the proofs or explicitly scoping the claims.","major_comments":[{"comment":"OPT_expected(G) in Section 2.3 is defined as a supremum over all signaling schemes µ, with no restriction to direct or prefix-based schemes. The lower bounds in Theorems 4.4 and 4.6, however, upper-bound the sender's expected utility only over prefix-based schemes (Definition 4.1), and Appendix F gives an instance in which an indirect scheme strictly outperforms every two-signal scheme. Consequently, the paper does not establish PoDR(k-broadcast) = Ω(k) or PoDR(k-clique) = Ω(k/log k) for the quantity OPT_expected defined in Section 2.3; the entries marked '†' in Table 1 and the abstract's unqualified 'becoming Θ(k)' statements for downstream utility are supported only against a restricted benchmark. Please either prove these lower bounds for all signaling schemes, or redefine the benchmark and prominently qualify the claims as applying to prefix-based schemes only.","section":"Section 2.3, Theorems 4.4 and 4.6, Table 1"},{"comment":"The paper notes in Section 2.2 (footnote 4) that restricting to direct signaling schemes is not without loss of generality once leakages are present, and Appendix F demonstrates such a loss for the expected-utility objective. Yet OPT_persuasive_k in Definition 2.1 is defined only over direct schemes, and the lower bounds in Theorems 4.2 and 4.3 bound the sender's utility only within this class. Since the abstract presents PoWR_k as a property of the model rather than of direct schemes, please either establish a revelation principle for k-worst-case persuasiveness (showing that indirect schemes cannot improve OPT_persuasive_k), or explicitly scope the PoWR results to direct schemes and comment on the possible gap to unrestricted schemes.","section":"Section 2.2, Definition 2.1, Section 5"}],"minor_comments":[{"comment":"The abstract says 'Θ(log k) leakages are sufficient' in the discussion of the phase transition; the body (Section 1.1) and the result itself indicate that the intended quantity is Θ(log n), not Θ(log k). Please correct this.","section":"Abstract"},{"comment":"The abstract introduces the notation PoRU for the price of downstream robustness, while the rest of the paper uses PoDR. Please unify the notation.","section":"Abstract and Section 1.1"},{"comment":"In the proof of Lemma 3.6, after establishing V ∩ [i, i+⌊n/k⌋] = ∅, the text says the leaked signals 'are all 0'. This is not literally true for indices v < i, whose signals are 1 under both µ0 and µ1. The argument still works because such leaked signals are uninformative: their value is constant across all relevant signal realizations. Please rephrase to avoid the inaccurate statement.","section":"Appendix D.1, proof of Lemma 3.6"},{"comment":"The claim that no size-2 signal scheme can achieve the optimal private utility of 9/4 is reported as 'verified by an exhaustive search on a computer'. Since this separation is used to argue that the direct-scheme restriction is lossy, please provide a formal proof or a verifiable certificate, or explicitly state that this part is a computational finding rather than a theorem.","section":"Appendix F.2"},{"comment":"In the discussion of direct vs indirect schemes, the paper states that indirect schemes can be strictly better than direct ones, citing Appendix F. Given the computational nature of the two-signal lower bound, please clarify the status of this claim as either a formal theorem or a computational observation.","section":"Section 5"}],"recommendation":"major_revision","confidential_remarks":"The worst-case robustness results appear sound and constitute the paper's core contribution; the expected-downstream-utility lower bounds, however, are not established for the benchmark defined in Section 2.3. I would encourage the authors to either close this gap or clearly scope the claims. The paper is not circular and does not fit data to the model; the main issue is a mismatch between the defined optimization domain and the analyzed class of schemes. The Appendix F exhaustive-search claim should also be upgraded to a formal proof or explicitly labeled as computational."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the worst-case robustness results are the real contribution and they hold up; the expected-downstream-utility half has a definitional gap that leaves the Θ(k) claims for k-broadcast and k-clique unsupported as stated.\n\nWhat's new: a clean middle ground between private and public persuasion, parameterized by how many leaked signals each receiver sees. The k-worst-case persuasiveness notion is well defined, the LP characterization is useful, and the tight bounds PoWR_k = Θ(min{2^k,n}) for supermodular and Θ(k) for submodular/XOS utilities look correct. I went through the subcube-partition argument for the 2^k lower bound; the C_i versus K_i subtlety is fixable and the proof structure is sound. The subsampling and masking techniques are genuinely reusable, and the paper is honest enough to flag the prefix-based caveats in Table 1 and Section 5.\n\nThe soft spot is the PoDR lower bounds. OPT_expected(G) in Section 2.3 is defined as a supremum over all signaling schemes, with no direct or prefix-based restriction. But Theorems 4.4 and 4.6 bound the sender's utility only over prefix-based schemes, so the Ω(k) lower bounds for k-broadcast and k-clique do not bound the defined benchmark. This is not cosmetic: Appendix F gives an n=3 instance where an indirect scheme strictly outperforms every direct/two-signal scheme, so the distinction is real. The abstract's unqualified 'becoming Θ(k)' overstates what is proven; the table footnote is accurate, the abstract is not.\n\nThe upper bounds on PoDR are constructive direct schemes, so they stand as upper bounds on the price, but the matching lower bounds against the general benchmark are missing. The central worst-case claims hold up.\n\nWho benefits: anyone working on robust information design or on interpolations between private and public persuasion will use the PoWR results and the model. The downstream-utility part reads as a partial contribution with an honest open question, not the tight theory the abstract implies.\n\nRecommendation: send it to review. A serious referee can sort out the OPT_expected definition and the prefix-based caveat; the core worst-case results deserve to be in the literature.","headline":"The worst-case robustness results are the real contribution and they hold up; the expected-downstream-utility half has a definitional gap that leaves the Θ(k) claims for k-broadcast and k-clique unsupported as stated.","tokens_in":38786,"tokens_out":3178,"would_cite":true,"duration_ms":27933,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91A26","91B06"],"pacs":[],"model":"deepseek-v4-flash","headline":"Private persuasion's advantage collapses after Θ(log n) leaked signals, with worst-case cost Θ(min{2^k,n}) for supermodular utilities and Θ(k) for submodular ones.","keywords":["Bayesian persuasion","signal leakage","private persuasion","public persuasion","price of robustness","subsampling","masking","submodular utilities"],"falsifier":"On the n=3 leakage-cycle instance of Appendix F, optimize expected downstream utility over all signal spaces and all direct (size-2) spaces: if a size-3 scheme attains 9/4 while every size-2 scheme attains at most 17/8, then any PoDR claim proved only for direct schemes fails for the unrestricted OPT_expected(G).","tokens_in":128,"feed_emoji":"🔓","tokens_out":4195,"duration_ms":179269,"temperature":0.7,"pith_summary":"This paper introduces a middle ground between private and public Bayesian persuasion: a sender's private signals may leak to other receivers. It asks how much sender utility must be sacrificed to stay persuasive when each receiver sees up to k leaked signals, and what happens to utility when leakages are random and receivers simply best-respond. The paper claims that under worst-case leakages the price of robustness is exponential in k (up to n) for supermodular sender utilities, and linear in k for submodular/XOS utilities, so that Θ(log n) leaks suffice to wipe out private persuasion's advantage. Under random leakage patterns, it claims the price shrinks to constant for star-shaped leaks and to linear for broadcast and clique leaks. The constructive engine is a pair of generic transformations—subsampling and masking—that convert optimal private schemes into leakage-robust ones.","feed_headline":"Leaked signals can erase private persuasion's edge","feed_subtitle":"A Θ(log n) leak threshold collapses private persuasion to public; submodular senders lose only linearly.","key_machinery":"The workhorse is the linear-program characterization of k-worst-case persuasiveness, whose constraints require that for every receiver and every ≤k-signal leakage pattern, the probability mass of the recommended adoption under state ω0 does not exceed θ_i times the corresponding mass under state ω1. On top of this LP, the paper builds subsampling transformations: for supermodular utilities, replace the all-ones state-ω1 signal by independent 1/2-per-coordinate sampling, and scale the state-ω0 distribution by $2^{{-(k+1)}}$; for submodular/XOS utilities, subsample at rate 1/k and also subsample the ω0 draws, preserving utility by the XOS inequality. For expected downstream utility, masking removes or matches randomness in the signals most likely to be leaked, so that typical leakage patterns reveal nothing that changes any receiver's action.","core_discovery":"The central claim is that the optimal private persuasion scheme is maximally brittle: a single leaked 0-signal can reveal the state and collapse utility, because under the optimal scheme state ω1 always sends 1 to everyone. To fix this, the paper defines k-worst-case persuasive schemes and shows that subsampling the all-ones signal at rate 1/2 yields a scheme that is k-worst-case persuasive while retaining a $2^{{-(k+1)}}$ fraction of state-ω0 utility. This yields PoWR_k ≤ O(2^k) for all utility functions; a tight Ω(min{2^k,n}) lower bound is proved on a supermodular instance with exponentially declining persuasion levels, and a tighter O(k) upper bound follows for submodular and XOS utilities via subsampling at rate 1/k. For expected downstream utility under specific random leakage distributions, masking schemes give PoDR = O(1) for k-star, Θ(k) for k-broadcast, and Θ~(k) for k-clique (with lower bounds only against prefix-based schemes). The paper also shows that restricting to direct (recommendation) signaling schemes is not WLOG once leakages matter: an indirect scheme with a larger signal alphabet can strictly beat every direct scheme.","pith_inferences":["If the logarithmic threshold transfers to real settings, mechanism designers should treat the first ~log n leaks as the dangerous ones and concentrate robustness budgets there, matching the exponential-to-linear phase transition.","The direct-vs-indirect gap suggests a parallel with privacy amplification: allowing larger signal alphabets restores some of the lost utility, a direction the paper leaves open; one could test whether constant-size alphabets suffice for constant-factor approximation.","The k-clique and k-broadcast lower bounds hold only against prefix-based schemes; a natural next step is to check whether non-prefix or indirect schemes beat those lower bounds, which would change the Table 1 entries."],"forward_implications":["If the tight bounds are correct, any private persuasion scheme with supermodular sender preferences must lose a factor of roughly 2^k in worst-case utility to survive k leaks; no scheme can do better.","For submodular or XOS preferences, robustness is cheap: the price of worst-case robustness is only linear in k, so the same schemes tolerate many more leaks at moderate cost.","The Θ(log n) threshold means the power of private over public signaling evaporates after a logarithmic number of adversarial leaks in the worst case.","In the k-star leakage model, random leakages cost only a constant factor, so a sender can effectively ignore them and still keep a constant fraction of the private optimum.","The masking/subsampling constructions are generic: they take any optimal private scheme and output a leakage-robust one, so the algorithmic paradigm transfers to any instance with the same utility structure."],"supporting_citations":[{"why":"Supplies the private persuasion LP, the optimal prefix-based scheme structure, and the characterization of optimal private utility used throughout.","marker":"[AB19]"},{"why":"Sets the Bayesian persuasion framework and the public-signal benchmark.","marker":"[KG11]"},{"why":"Provides the private-vs-public gap baseline (price of anarchy) that motivates the robustness gap.","marker":"[NX22]"},{"why":"Supplies the non-monotonicity observation and the network-spillover model the paper extends.","marker":"[KT23]"},{"why":"Defines public Bayesian persuasion and the multi-receiver public setting used as the lower benchmark.","marker":"[CCG23]"}],"fun_headline_variants":["A single leaked signal can erase private persuasion's edge","Subsampling and masking give leakage-robust persuasion","Price of robustness: linear for submodular, exponential for supermodular","Logarithmic leak threshold collapses private persuasion","One leak can turn private persuasion into public"],"cache_read_input_tokens":40704,"weakest_assumption_plain":"The expected-downstream-utility bounds assume the sender uses direct recommendation signals; the paper itself shows an indirect scheme can beat every direct scheme on a small leakage instance, so if the formal optimum is over all signal spaces those bounds may not constrain it.","fun_headline_variants_meta":{"raw":{"variants":["A single leaked signal can erase private persuasion's edge","Subsampling and masking give leakage-robust persuasion","Price of robustness: linear for submodular, exponential for supermodular","Logarithmic leak threshold collapses private persuasion","One leak can turn private persuasion into public"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000586,"raw_usage":{"total_tokens":2859,"prompt_tokens":1154,"completion_tokens":1705,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":770,"completion_tokens_details":{"reasoning_tokens":1627}},"tokens_in":770,"tokens_out":1705,"duration_ms":15834,"temperature":1.0,"reasoning_tokens":1627,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T12:57:49.087725+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On the n=3 leakage-cycle instance of Appendix F, optimize expected downstream utility over all signal spaces and all direct (size-2) spaces: if a size-3 scheme attains 9/4 while every size-2 scheme attains at most 17/8, then any PoDR claim proved only for direct schemes fails for the unrestricted OPT_expected(G).","supporting_citations":[],"review_version":1}