REVIEW 2 major objections 5 minor 43 references
Persuading Voters: It's Easy to Whisper, It's Hard to Speak Loud
T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read 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…
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (2)
- [§3, Formulation (2), Theorem 3] 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.
- [Supplementary Material, proof of Theorem 4 (α>0 case)] 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.
minor comments (5)
- [§3, Lemma 1, Eq. (1)] 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.
- [§3, Lemma 2] 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.
- [§6, Theorem 7 (only-if direction)] 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.
- [§6, Theorem 7 reduction] 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.
- [§5, proof of Theorem 6] 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.
Circularity Check
No circularity: results are derived from self-contained LPs, duality arguments, and an external NP-hardness reduction; cited prior work is background, not a self-citation chain.
full rationale
The paper's central claims are self-contained derivations. For private signaling under k-voting rules, Theorem 3 is proved via Lemmas 1 and 2, which restrict the search to persuasive marginal schemes, and then via a polynomial-size LP whose correctness is argued from the structure of the objective and from a cited combinatorial characterization of the probability that at least k receivers play c0. Theorem 4 is a tractability equivalence proved by primal-dual LP duality and the equivalence of optimization and separation; it does not assume the conclusion. Theorem 5 follows by enumerating the polynomially many anonymous outcome profiles and solving a max-cost flow problem. Theorem 6 is proved by reducing to the condition in Theorem 4 and solving the resulting weighted maximization problem. Theorem 7 is a direct approximation-preserving hardness reduction from MAXIMUM k-SUBSET INTERSECTION, an external NP-hard problem. No parameters are fitted to data, no quantity called a prediction is defined in terms of the target value, and the authors do not rely on their own prior theorems to force the results. The cited works by Arieli and Babichenko, Dughmi and Xu, and Xu are used as background, as a source of an auxiliary lemma, and as generalization targets; they are not self-citations and do not contain the paper's conclusions. The reviewer's flagged concern about a possible missing sign constraint on z in LP (2) is a correctness question about the printed proof, not a circularity: even if the LP as written overestimates the winning probability, the intended derivation is from a dual of an independent small LP, not from the result being proved. Accordingly, no circular step is present.
Assumptions & free parameters
assumptions (6)
- domain assumption Voter utilities satisfy no inter-agent externalities: each voter's utility depends only on her own action and the state of nature.
- domain assumption The sender can commit to a publicly known signaling scheme, and the prior over states is common knowledge to sender and voters.
- domain assumption Receivers break ties in favor of the sender.
- standard math MAXIMUM k-SUBSET INTERSECTION is NP-hard.
- standard math Ellipsoid optimization-separation equivalence (Khachiyan 1980; Grötschel-Lovász-Schrijver 1981).
- standard math Lemma 3 of Arieli-Babichenko (2019) characterizing the maximum probability that at least k receivers play c0.
Cite this review
Pith. "Pith review of Persuading Voters: It's Easy to Whisper, It's Hard to Speak Loud." pith.science (2026). https://pith.science/paper/3QAKRPWE
@misc{pith2026190810620,
author = {Pith},
title = {Pith review of: Persuading Voters: It's Easy to Whisper, It's Hard to Speak Loud},
year = {2026},
howpublished = {\url{https://pith.science/paper/3QAKRPWE}},
note = {Machine review of arXiv:1908.10620}
}
abstract
We focus on the following natural question: is it possible to influence the outcome of a voting process through the strategic provision of information to voters who update their beliefs rationally? We investigate whether it is computationally tractable to design a signaling scheme maximizing the probability with which the sender's preferred candidate is elected. We focus on the model recently introduced by Arieli and Babichenko (2019) (i.e., without inter-agent externalities), and consider, as explanatory examples, $k$-voting rule and plurality voting. There is a sharp contrast between the case in which private signals are allowed and the more restrictive setting in which only public signals are allowed. In the former, we show that an optimal signaling scheme can be computed efficiently both under a $k$-voting rule and plurality voting. In establishing these results, we provide two general (i.e., applicable to settings beyond voting) contributions. Specifically, we extend a well known result by Dughmi and Xu (2017) to more general settings, and prove that, when the sender's utility function is anonymous, computing an optimal signaling scheme is fixed parameter tractable w.r.t. the number of receivers' actions. In the public signaling case, we show that the sender's optimal expected return cannot be approximated to within any factor under a $k$-voting rule. This negative result easily extends to plurality voting and problems where utility functions are anonymous.
Figures
Reference graph
Works this paper leans on
-
[1]
write newline
" write newline "" before.all 'output.state := FUNCTION fin.entry add.period write newline FUNCTION new.block output.state before.all = 'skip after.block 'output.state := if FUNCTION new.sentence output.state after.block = 'skip output.state before.all = 'skip after.sentence 'output.state := if if FUNCTION not #0 #1 if FUNCTION and 'skip pop #0 if FUNCTIO...
-
[2]
Allcott, H., and Gentzkow, M. 2017. Social media and fake news in the 2016 election. J ECON PERSPECT 31(2):211--36
work page 2017
-
[3]
Alonso, R., and C \^a mara, O. 2016. Persuading voters. AM ECON REV 106(11):3590--3605
work page 2016
-
[4]
Arieli, I., and Babichenko, Y. 2019. Private bayesian persuasion. J ECON THEORY 182:185--217
work page 2019
-
[5]
Babichenko, Y., and Barman, S. 2016. Computational aspects of private bayesian persuasion. arXiv preprint arXiv:1603.01444
arXiv 2016
-
[6]
Bardhi, A., and Guo, Y. 2018. Modes of persuasion toward unanimous consent. THEOR ECON 13(3):1111--1149
work page 2018
-
[7]
Bergemann, D., and Morris, S. 2016a. Bayes correlated equilibrium and the comparison of information structures in games. THEOR ECON 11(2):487--522
-
[8]
Bergemann, D., and Morris, S. 2016b. Information design, Bayesian persuasion, and Bayes correlated equilibrium. AM ECON REV 106(5):586--91
Show all 43 references
-
[9]
Bergemann, D., and Morris, S. 2019. Information design: A unified perspective. J ECON LIT 57(1):44--95
2019
-
[10]
K.; and Swamy, C
Bhaskar, U.; Cheng, Y.; Ko, Y. K.; and Swamy, C. 2016. Hardness results for signaling in bayesian zero-sum and network routing games. In ACM EC , 479--496
2016
-
[11]
Blais, A.; Massicotte, L.; and Dobrzynska, A. 1997. Direct presidential elections: a world summary. ELECT STUD 16(4):441--455
1997
-
[12]
Brandt, F.; Conitzer, V.; Endriss, U.; Lang, J.; and Procaccia, A. D. 2016. Handbook of computational social choice . Cambridge University Press
2016
-
[13]
Candogan, O. 2019. Persuasion in networks: Public signals and k-cores. Available at SSRN
2019
-
[14]
Chan, J.; Gupta, S.; Li, F.; and Wang, Y. 2019. Pivotal persuasion. Journal of Economic Theory 180:178--202
2019
-
[15]
Chen, J.; Faliszewski, P.; Niedermeier, R.; and Talmon, N. 2017. Elections with few voters: candidate control can be easy. J ARTIF INTELL RES 60:937--1002
2017
-
[16]
Clifford, R., and Popa, A. 2011. Maximum subset intersection. Information Processing Letters 111(7):323--325
2011
-
[17]
Dughmi, S., and Xu, H. 2016. Algorithmic bayesian persuasion. In ACM STOC , 412--425
2016
-
[18]
Dughmi, S., and Xu, H. 2017. Algorithmic persuasion with no externalities. In ACM EC , 351--368
2017
-
[19]
Dughmi, S. 2017. Algorithmic information structure design: a survey. ACM SIGEC EX 15(2):2--24
2017
-
[20]
Dughmi, S. 2018. On the hardness of designing public signals. GAME ECON BEHAV
2018
-
[21]
Elkind, E.; Markakis, E.; Obraztsova, S.; and Skowron, P. 2015. Equilibria of plurality voting: Lazy and truth-biased voters. In SAGT , 110--122. Springer
2015
-
[22]
Erd \'e lyi, G.; Reger, C.; and Yang, Y. 2017. The complexity of bribery and control in group identification. In AAMAS , 1142--1150
2017
-
[23]
A.; and Rothe, J
Faliszewski, P.; Hemaspaandra, E.; Hemaspaandra, L. A.; and Rothe, J. 2009. Llull and copeland voting computationally resist bribery and constructive control. J ARTIF INTELL RES 35:275--341
2009
-
[24]
Faliszewski, P.; Gonen, R.; Kouteck \`y , M.; and Talmon, N. 2018. Opinion diffusion and campaigning on society graphs. In IJCAI , 219--225
2018
-
[25]
Faliszewski, P.; Hemaspaandra, E.; and Hemaspaandra, L. A. 2011. Multimode control attacks on elections. J ARTIF INTELL RES 40:305--351
2011
-
[26]
Gr \"o tschel, M.; Lov \'a sz, L.; and Schrijver, A. 1981. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2):169--197
1981
-
[27]
Kamenica, E., and Gentzkow, M. 2011. Bayesian persuasion. AM ECON REV 101(6):2590--2615
2011
-
[28]
Kamenica, E. 2018. Bayesian persuasion and information design. ANNU REV ECON 11
2018
-
[29]
Khachiyan, L. G. 1980. Polynomial algorithms in linear programming. USSR COMP MATH 20(1):53--72
1980
-
[30]
Liu, H.; Feng, H.; Zhu, D.; and Luan, J. 2009. Parameterized computational complexity of control problems in voting systems. THEOR COMPUT SCI 410(27-29):2746--2753
2009
-
[31]
B.; and Walsh, T
Loreggia, A.; Narodytska, N.; Rossi, F.; Venable, K. B.; and Walsh, T. 2015. Controlling elections by replacing candidates or votes. In AAMAS , 1737--1738
2015
-
[32]
Orlin, J. B. 1997. A polynomial time primal network simplex algorithm for minimum cost flows. MATH PROGRAM 78(2):109--129
1997
-
[33]
Rayo, L., and Segal, I. 2010. Optimal information disclosure. J POLIT ECON 118(5):949--987
2010
-
[34]
Rubinstein, A. 2015. Honest signaling in zero-sum games is hard, and lying is even harder. arXiv preprint arXiv:1510.04991
2015 arXiv
-
[35]
Schnakenberg, K. E. 2015. Expert advice to a voting body. J ECON THEORY 160:102--113
2015
-
[36]
Sina, S.; Hazon, N.; Hassidim, A.; and Kraus, S. 2015. Adapting the social network to affect elections. In AAMAS , 705--713
2015
-
[37]
Stanley, R. P. 2011. Enumerative Combinatorics: Volume 1 . Cambridge University Press, 2nd edition
2011
-
[38]
Taneva, I. A. 2015. Information design
2015
-
[39]
Wang, Y. 2013. Bayesian persuasion with multiple receivers. Available at SSRN 2625399
2013
-
[40]
Wilder, B., and Vorobeychik, Y. 2018. Controlling elections through social influence. In AAMAS , 265--273
2018
-
[41]
Wilder, B., and Vorobeychik, Y. 2019. Defending elections against malicious spread of misinformation. In AAAI , volume 33, 2213--2220
2019
-
[42]
Xavier, E. C. 2012. A note on a maximum k-subset intersection problem. Information Processing Letters 112(12):471--472
2012
-
[43]
Xu, H. 2019. On the tractability of public persuasion with no externalities. CoRR abs/1906.07359
2019 arXiv
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.