Research map / Learning theory and algorithms / Submodular and game algorithms
Computational Aspects of Bayesian Persuasion under Approximate Best Response
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies Bayesian persuasion when the receiver best-responds only approximately, giving polynomial-time exact algorithms for small state or action spaces, NP-hardness of exact computation in general, and a QPTAS.
Problem
Computing the sender's optimal signaling scheme in Bayesian persuasion when the receiver may choose any delta-suboptimal action, where the revelation principle fails.
Approach
Robust (max-min) Bayesian persuasion against delta-best-response receivers: an LP over signals encoding (approximate best-response set, best action) pairs; exploits the geometry of feasible response sets (cell counting and connectivity of a symmetric-difference graph) for small state spaces, and a k-uniform covering of posteriors for a quasi-polynomial approximation.
Key results
- Direct-revelation signaling schemes can be suboptimal by a factor of 2 or an additive gap of 1/2 in a 3-state, 2-action instance.
- Polynomial-time exact LP algorithm when the action space is small (size O(2^n mn)), and n^{O(m)} feasibility LPs for constant number of states m.
- Exact computation of the optimal robust utility is NP-hard; a QPTAS achieves epsilon-approximation in quasi-polynomial time.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| restrict signaling schemes to direct action recommendations | Robust Bayesian persuasion with approximate best responses · 3-state, 2-action instances | robust sender utility: ≤\frac{1}{2}\widehat{S}^\star_\delta; additive gap of \frac{1}{2} | Hurt |
| use full revelation with three state-specific signals instead of a two-signal scheme | Robust Bayesian persuasion example · 3-state, 2-action instance | robust sender utility: 1-\varepsilon; two-signal schemes are at most \frac{1-\varepsilon}{2} | Helped |
| use the LP formulation | Robust Bayesian persuasion with a constant number of actions · Small action space | computation | Helped |
| enumerate feasible signal tuples and then optimize over them | Robust Bayesian persuasion with a constant number of states · Small state space | computation | Helped |
| use the QPTAS with representative posterior cells | Robust Bayesian persuasion · General case | robust sender utility: \varepsilon | Helped |
| seek an exact polynomial-time algorithm without restrictions on the number of states or actions | Robust Bayesian persuasion · General case | computational complexity | Hurt |
Surprising findings
- The revelation principle fails under approximate best response, so direct-recommendation schemes lose at least a factor of 2.
Limitations
- General problem admits no polynomial-time exact algorithm unless P=NP.
- QPTAS runtime is quasi-polynomial and depends on epsilon exponentially in 1/epsilon^2.
Experimental setup
Metrics: robust sender utility
Baselines: direct-revelation signaling schemes
Builds on: revelation principle Bayesian persuasion (Kamenica and Gentzkow)
Closest papers by meaning
- Online Bayesian Persuasion Without a Clue (NeurIPS 2024 · similarity 0.91)
- Bayesian Persuasion with Externalities: Exploiting Agent Types (AAAI 2025 · similarity 0.90)
- Markov Persuasion Processes: Learning to Persuade From Scratch (NeurIPS 2025 · similarity 0.88)
- Persuasive Prediction via Decision Calibration (NeurIPS 2026 · similarity 0.87)
- Multi-Sender Persuasion: A Computational Perspective (ICML 2024 · similarity 0.86)
- Learning to Persuade a Biased Receiver (NeurIPS 2026 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.