{"id":"39f33d59-4be2-49e6-9ca8-d9b08488fe73","arxiv_id":"1908.10620","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Efficient algorithms exist for optimal private Bayesian persuasion of voters under k-voting and plurality rules, but optimal public persuasion is NP-hard to approximate by any factor.","lead":"This paper studies whether an informed sender can efficiently design private or public information signals that persuade rational voters to elect the sender's preferred candidate. It finds a sharp contrast: optimal private persuasion is computationally tractable under k-voting and plurality rules, while optimal public persuasion is inapproximable to any factor.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Formulation (2) omits the sign constraint on z that the dual derivation requires; as printed the LP overestimates the k-voting winning probability, so Theorem 3 is unproven as written.","rationale":"The paper's headline contrast depends on three results: Theorem 3 (k-voting private easy), Theorem 6 (plurality private easy), and Theorem 7 (public hard). The most load-bearing technical step I found is the LP in Theorem 3: it is the first positive result and the model for the other private-side algorithms. As printed, the LP has a missing sign bound, and the proof's own dual argument implies that bound. This is not an externalities/consensus issue; it is an internal correctness gap. The paper deserves credit for the structural ideas and for the hardness reduction, which appears sound up to minor presentational fixes. However, because a central theorem's proof contains a demonstrably incorrect optimization formulation, acceptance should be conditional on correcting the LP and reproving Theorem 3. I do not see a reason to reject the paper's overall claim, and I agree with the reader that the no-externalities assumption limits applicability, hence 'partial' agreement with the reader's weakest-assumption diagnosis.","tokens_in":17564,"tokens_out":43317,"duration_ms":440361,"concrete_test":"Re-derive the dual of the auxiliary LP in the proof of Theorem 3 and verify the sign of the z variables; then solve a one-state instance with |R|=3, k=2 and marginals φ=(0.1,0.2,0.9) under both the printed LP and the LP with z≤0. If the printed LP returns β=0.6 while the corrected LP and the Arieli-Babichenko formula return 0.3, the missing sign constraint is confirmed.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Theorem 3's proof reduces K-V to LP (2), but LP (2) declares z∈R^{|Θ|×k×|R|} with no sign restriction. The proof says Constraints (2d)-(2e) encode q_{θ,m} as the sum of the lowest |R|-m values of {φ_r(θ,c0)} and are 'derived from the dual' of min_{y∈[0,1]^n, 1^T y=w} x^T y. In that dual, the variables corresponding to z are non-positive. With z free, (2e) allows z_{θ,m,r}=φ_r(θ,c0)-t, so (2d) becomes q_{θ,m} ≤ max_t[(|R|-m)t + Σ_r max(0,φ_r(θ,c0)-t)], which is a bound on a sum of largest marginals, not the smallest. Concretely, with |R|=3, k=2 and φ_r=(0.1,0.2,0.9), the printed LP permits βθ=0.6, whereas the true maximum probability of at least two c0-votes is min(1.2/2, 0.3/1)=0.3. Thus the LP as printed is not a valid formulation of K-V and Theorem 3 is not proven. The intended correction is to add z≤0 (or equivalently enforce the dual sign), which would restore the argument; but that correction is absent.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies Bayesian persuasion in elections under the no-inter-agent-externalities model of Arieli and Babichenko. The sender wants to maximize the probability that candidate c0 wins under k-voting and plurality rules. The paper claims that optimal private signaling schemes can be computed in polynomial time for both rules (Theorems 3 and 6), provides a general tractability condition for private persuasion (Theorem 4) and an FPT result for anonymous utilities (Theorem 5), and proves that public signaling for k-voting (and plurality) is inapproximable in polynomial time unless P=NP (Theorem 7, Corollary 1). The main proof tools are an LP formulation for the k-voting problem, a duality/separation argument for private persuasion, and a reduction from Maximum k-Subset Intersection for the public case.","tokens_in":17819,"tokens_out":35471,"duration_ms":364128,"significance":"If the results are correct, the paper makes a meaningful contribution: it establishes a clean computational dichotomy between private and public signaling in voting, and its negative result strengthens prior inapproximability from constant factors to any factor. The duality framework of Theorem 4 and the MSI reduction are valuable beyond the specific voting rules considered. The paper is generally careful about the model and discloses the key no-externalities assumption. However, the main positive result for k-voting is not proved as written because the LP formulation omits a sign constraint on the dual variables; until this is corrected, Theorem 3 does not follow. With the local fix, the central claim is likely defensible.","major_comments":[{"comment":"Formulation (2) is not a valid LP formulation of K-V as printed, because the vector z is declared unrestricted. The proof of Theorem 3 says that constraints (2d)–(2e) are derived from the dual of min_{y∈[0,1]^n, 1^T y=w} x^T y, but in that dual the variables for the upper bounds y_i≤1 are non-positive. With z free, for fixed φ and any m with k−m>0 one can choose t and set z_r=φ_r−t, so the right-hand side of (2d) equals w t + Σ_r(φ_r−t)=Σ_rφ_r+(w−n)t, which is unbounded above as t→−∞. Consequently constraints (2c)–(2e) no longer enforce that q_{θ,m} is the sum of the lowest |R|−m marginals; they only impose a bound of the form q_{θ,m} ≤ max_t[ w t + Σ_r max(0,φ_r−t) ], which is the wrong order statistic. For example, with |R|=3, k=2 and φ_r=(0.1,0.2,0.9), the printed LP permits β_θ=0.6, while the true probability that at least two voters choose c0 is 0.3. Thus Theorem 3 is unproven as stated. The fix is local: add z≤0 (or equivalently enforce the sign of the dual variables) in Formulation (2) and in the proof; with that change the dual characterization is sound.","section":"§3, Formulation (2), Theorem 3"},{"comment":"The converse direction of Theorem 4 is incomplete in the α>0 case. After scaling to α=1, the proof takes the dual LP (7), whose constraints are Σ_{s:s_r=c} p(s) ≤ β_r(c). If any β_r(c)<0, this constraint is infeasible because the left-hand side is nonnegative; equivalently, the primal LP (6) is unbounded. The manuscript's case analysis only treats α<0, α=0, and α>0 implicitly with β_r(c)≥0, and the reduction to a persuasion instance with utilities β_r(c) assumes that recommending c_θ in state θ_c is persuasive, which fails when β_r(c)<0. Please add the missing case or an argument that such coefficient vectors do not arise in the reduction from the maximization problem (3). As written, the converse direction of Theorem 4 is not fully proved, and Theorems 5 and 6 rely on it.","section":"Supplementary Material, proof of Theorem 4 (α>0 case)"}],"minor_comments":[{"comment":"The second argument of the min in the update rule appears to be a typo: Σ_{c∈C} φ_{r-1}(θ,(c0,s_{-r})) does not depend on c, whereas the intended expression is Σ_{c∈C} φ_{r-1}(θ,(c,s_{-r})), the total probability mass of the block. Please correct the displayed formula.","section":"§3, Lemma 1, Eq. (1)"},{"comment":"The construction assigns φ_r(θ,c*)=1−φ'_r(θ,c0) and φ_r(θ,c0)=φ'_r(θ,c0); these two values conflict when c0 is itself an argmax (c*=c0). The lemma remains true, but the proof should handle this case explicitly.","section":"§3, Lemma 2"},{"comment":"The displayed inequality φ(θe,γ0)−Σ_{θe′}φ(θe′,γ0)+φ(θe,γ0)≥0 is algebraically wrong; the correct expression is (q−1)φ(θe,γ0)−Σ_{θe′}φ(θe′,γ0)+φ(θe,γ0)≥0, equivalently qφ(θe,γ0)≥Σ_{θe′}φ(θe′,γ0), from which the stated conclusion follows.","section":"§6, Theorem 7 (only-if direction)"},{"comment":"The utility function for voters r_{e,j} divides by q−1, so the reduction is undefined for q=1. Since MSI with q=1 is easy (one can scan elements for a common element contained in k sets), the authors should explicitly assume q≥2 or handle q=1 separately.","section":"§6, Theorem 7 reduction"},{"comment":"The treatment of non-winning profiles in the separation problem for plurality voting is terse. If the unconstrained maximizer of Σ_r w_r(s_r) is itself a winning profile, the upper bound is not attainable within the non-winning set; the proof should state that in this case the winning-profile computation already yields a value at least 1+Σ_r w_r(s_r), which dominates all non-winning profiles, so the relaxed upper bound can be discarded.","section":"§5, proof of Theorem 6"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is a solid contribution and the sign-constraint issue appears to be a fixable omission rather than a fundamental error. The editor may wish to ask the authors to add the z≤0 constraint and to tighten the proof of Theorem 4's converse regarding negative coefficients."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version: this paper is worth reading and worth citing, but one of its central positive results is currently unproven because of a missing sign constraint in an LP. The negative result for public signaling is solid.\n\nWhat's genuinely new: Theorem 4 gives a necessary and sufficient condition for efficient private persuasion that generalizes Dughmi-Xu from binary actions to arbitrary action sets, via a duality-based separation argument. Theorems 5 and 6 draw out the expected consequences: fixed-parameter tractability for anonymous utilities and polynomial time for plurality voting. Theorem 7 strengthens the Dughmi-Xu inapproximability for public signaling from any constant factor to any factor, using a clean reduction from MAXIMUM k-SUBSET INTERSECTION. I checked the reduction's arithmetic; it works.\n\nThe soft spot is Theorem 3. The LP (2) in the proof is supposed to encode q_{θ,m} as the sum of the lowest |R|-m values of {φ_r(θ,c0)}. The proof says constraints (2d)-(2e) come from the dual of min_{y∈[0,1]^n, 1^T y=w} x^T y. In that dual, the variables that play the role of z are non-positive. The printed LP omits the z≤0 constraint. With z free, for any φ the constraints can be satisfied with arbitrarily large q (take t very negative and z_i = φ_i - t), so the objective can overstate the true winning probability. Concretely, for |R|=3, k=2, φ=(0.1,0.2,0.9), the printed LP permits β=0.6, while the true maximum probability of at least two c0 votes is 0.3. The correct constraint is z≤0; adding it restores the argument and makes Theorem 3 go through. This is a fixable typo, not a structural flaw, but as it stands the theorem is unproven. The authors need to add the sign and re-run the proof.\n\nOther notes: the no-externalities assumption is standard and stated up front; I don't consider it a weakness. The proofs are dense, and Lemma 1's notation has some rough edges, but those are minor.\n\nWho's this for: algorithmic game theory and computational social choice people working on information design. The public-signaling hardness is the most robust contribution and will be useful independently. I think a serious editor should send this to review; the missing sign is easily fixed, and once fixed, the paper makes a genuine contribution. I'd accept after major revision.","headline":"Solid paper on persuasion in voting, but Theorem 3's LP is missing a sign constraint and that theorem is unproven as written; the fix is trivial and the rest holds up.","tokens_in":18374,"tokens_out":9495,"would_cite":true,"duration_ms":86382,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","91B12","91A26"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper shows that a sender who can send private messages to voters can compute an optimal persuasion plan in polynomial time, while a sender restricted to public messages faces a problem that cannot be approximated to any factor…","keywords":["Bayesian persuasion","private signaling","public signaling","voting manipulation","computational complexity","inapproximability","plurality voting","k-voting rules"],"falsifier":"For Theorem 3, brute-force the optimal private scheme on a small instance (say, three voters, two candidates, three states) and compare with the value of LP (2); a higher LP value would indicate that the persuasion constraints are not sufficient. For Theorem 7, any polynomial-time algorithm that outputs a persuasive public scheme for two-candidate k-voting with value at least a constant fraction of the optimum would refute the inapproximability claim, unless P=NP.","tokens_in":17319,"feed_emoji":"🗳️","tokens_out":11738,"duration_ms":112405,"temperature":0.7,"pith_summary":"The paper establishes a computational split in voter persuasion. If a sender can whisper different messages to different voters, the optimal persuasive signaling scheme is computable in polynomial time under k-voting rules and plurality voting, and it is fixed-parameter tractable in the number of candidates whenever the sender's payoff is anonymous. If the sender must broadcast the same public message to everyone, the same optimization problem cannot be approximated to within any factor unless P=NP, even with only two candidates. The point of caring is that the results fix where algorithmic manipulation is a live threat: targeted whisper campaigns are efficiently optimizable, loud public campaigns are not.","feed_headline":"Whisper to voters: easy. Broadcast to all: hopeless","feed_subtitle":"Optimal private signaling is polynomial-time for k-voting and plurality; public signaling is inapproximable unless P=NP.","key_machinery":"The mechanism that carries the private-side argument is the direct-and-persuasive revelation-principle reduction: an optimal scheme can be taken to recommend a candidate to each voter and to satisfy per-voter incentive constraints. The main private-side tool is the condition max_c f(c) + Σ_r w_r(c_r): the dual of the persuasion LP has exponentially many constraints, and separating over them is exactly this weighted welfare maximization, so a polynomial-time oracle for that maximization makes the whole LP polynomial. For k-voting, the LP (2) encodes the probability that at least k voters follow the recommendation through order statistics of the marginal recommendation probabilities. The public-side hardness is carried by the reduction from MAXIMUM k-SUBSET INTERSECTION, the problem of finding k sets whose intersection size is at least q; voters' incentives encode set membership and the election threshold encodes the intersection requirement, so any positive winning probability decodes a solution.","core_discovery":"The central claim is a tractability contrast between private and public signaling under the no-externalities model of voter preferences. For private signaling, the optimal scheme is found in polynomial time for k-voting rules (Theorem 3) and for plurality voting (Theorem 6). The engine is a necessary and sufficient condition (Theorem 4): private persuasion over a class of sender utility functions is polynomial-time solvable exactly when the weighted maximization of f(c) plus the sum of receivers' weights is polynomial-time solvable; anonymity makes the problem fixed-parameter tractable in the number of candidates (Theorem 5). For public signaling, Theorem 7 reduces from the maximum k-subset-intersection problem to show that approximating the optimal public scheme for a two-candidate k-voting election to within any factor is NP-hard unless P=NP, and Corollary 1 extends the hardness to plurality. On the paper's account, the computational difficulty of manipulating an election comes from the public/private communication restriction, not from the choice of voting rule.","pith_inferences":["Beyond the paper, Theorem 4 gives a reusable recipe: to prove private tractability for a new voting rule, it suffices to solve weighted welfare maximization over action profiles; any rule whose weighted welfare maximization is NP-hard would inherit private-persuasion hardness.","Beyond the paper, the private-versus-public value gap can be measured directly on synthetic elections; the paper proves an algorithmic contrast but does not quantify how much private signaling gains over public broadcasting.","Beyond the paper, if private persuasion is polynomial-time and public persuasion is inapproximable, then restrictions on micro-targeted messaging constrain the computationally feasible manipulation more than restrictions on broadcast messages."],"forward_implications":["For any k-voting or plurality election, a sender with private channels can compute the exact optimal persuasion plan in polynomial time in the number of states, candidates, and voters.","For any anonymous voting rule, optimal private persuasion is fixed-parameter tractable in the number of candidates, so few-candidate elections remain computationally easy as the electorate grows.","The public-signaling versions of the same rules cannot be approximated to within any factor in polynomial time unless P=NP, even with two candidates.","The hardness transfers from k-voting to plurality voting, so the public/private contrast is not an artifact of the threshold rule."],"supporting_citations":[{"why":"Supplies the no-externalities model and the binary-action characterization, including the lemma giving the probability that at least k receivers follow a recommendation.","marker":"Arieli and Babichenko (2019)"},{"why":"Provides the original necessary-and-sufficient condition for binary-action private persuasion and the prior public-signaling inapproximability result that Theorem 7 strengthens.","marker":"Dughmi and Xu (2017)"},{"why":"Founds the Bayesian-persuasion model and the direct-and-persuasive revelation-principle argument used throughout.","marker":"Kamenica and Gentzkow (2011)"},{"why":"Supplies the duality-based LP reformulation and public-signaling analysis that Theorem 4's proof extends to non-binary action spaces.","marker":"Xu (2019)"},{"why":"Defines MAXIMUM k-SUBSET INTERSECTION, the NP-hard source problem for the public-signaling reduction.","marker":"Clifford and Popa (2011)"},{"why":"Establishes NP-hardness of MAXIMUM k-SUBSET INTERSECTION, the hardness fact the reduction relies on.","marker":"Xavier (2012)"},{"why":"Provides the polynomial-time minimum-cost flow algorithm used to solve the integer assignment LPs in the plurality and anonymous-utility proofs.","marker":"Orlin (1997)"},{"why":"The linear-programming polynomial-time result used to convert the separation oracle in Theorem 4's proof into an efficient algorithm.","marker":"Khachiyan (1980)"},{"why":"The optimization-separation equivalence invoked with Khachiyan's result to make the dual-based argument polynomial.","marker":"Grötschel, Lovász, and Schrijver (1981)"}],"fun_headline_variants":["Whisper to voters: polynomial time. Shout: inapproximable","Private whispers to voters: easy. Public broadcast: NP-hard","Optimal private signaling: easy. Public: inapproximable","Private voter signaling is easy; public is NP-hard"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Each voter's payoff depends only on her own vote and the state of nature, never on how other voters vote; if voters cared about other voters' choices, the private-signaling tractability results would no longer follow.","fun_headline_variants_meta":{"raw":{"variants":["Whisper to voters: polynomial time. Shout: inapproximable","Private whispers to voters: easy. Public broadcast: NP-hard","Optimal private signaling: easy. Public: inapproximable","Private voter signaling is easy; public is NP-hard"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000706,"raw_usage":{"total_tokens":3219,"prompt_tokens":1019,"completion_tokens":2200,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":635,"completion_tokens_details":{"reasoning_tokens":2126}},"tokens_in":635,"tokens_out":2200,"duration_ms":16285,"temperature":1.0,"reasoning_tokens":2126,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T10:38:06.580292+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For Theorem 3, brute-force the optimal private scheme on a small instance (say, three voters, two candidates, three states) and compare with the value of LP (2); a higher LP value would indicate that the persuasion constraints are not sufficient. For Theorem 7, any polynomial-time algorithm that outputs a persuasive public scheme for two-candidate k-voting with value at least a constant fraction of the optimum would refute the inapproximability claim, unless P=NP.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the no-externalities model and the binary-action characterization, including the lemma giving the probability that at least k receivers follow a recommendation."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Founds the Bayesian-persuasion model and the direct-and-persuasive revelation-principle argument used throughout."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines MAXIMUM k-SUBSET INTERSECTION, the NP-hard source problem for the public-signaling reduction."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes NP-hardness of MAXIMUM k-SUBSET INTERSECTION, the hardness fact the reduction relies on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the polynomial-time minimum-cost flow algorithm used to solve the integer assignment LPs in the plurality and anonymous-utility proofs."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The linear-programming polynomial-time result used to convert the separation oracle in Theorem 4's proof into an efficient algorithm."}],"review_version":1}