Algorithmic Persuasion with Evidence
summary
Paper at ITCS 2021 studies persuasion with unforgeable evidence, gives a polynomial-time max-flow algorithm that computes a sequential equilibrium, and proves commitment can vastly change outcomes: sender’s committed strategy can raise acceptance from 0 to 0.8 (unbounded ratio) while receiver commitment helps up to factor two. From a complexity view persuasion is NP-hard to approximate to n^{1−ε}, delegation is tight 2-approximate, and Degree-2 states admit an SDP-based 1.1-approximation.
AI-written summary · about