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.
Honest signaling in zero-sum games is hard, and lying is even harder
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We prove that, assuming the exponential time hypothesis, finding an \epsilon-approximately optimal symmetric signaling scheme in a two-player zero-sum game requires quasi-polynomial time. This is tight by [Cheng et al., FOCS'15] and resolves an open question of [Dughmi, FOCS'14]. We also prove that finding a multiplicative approximation is NP-hard. We also introduce a new model where a dishonest signaler may publicly commit to use one scheme, but post signals according to a different scheme. For this model, we prove that even finding a (1-2^{-n})-approximately optimal scheme is NP-hard.
fields
cs.GT 1years
2019 1verdicts
ACCEPT 1representative citing papers
citing papers explorer
-
Persuading Voters: It's Easy to Whisper, It's Hard to Speak Loud
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.