论文标题
公共贝叶斯说服：几乎是最佳且几乎有说服力的
Public Bayesian Persuasion: Being Almost Optimal and Almost Persuasive
论文作者
论文摘要
说服力研究知情的委托人如何通过与回报相关的信息来影响代理人的行为。我们专注于Arieli和Babichenko（2019）的基本多收取模型，其中没有经济间的外部性。与以前关于此问题的工作不同，我们研究了一般环境中的公共说服问题：（i）任意状态空间； （ii）任意行动空间； （iii）任意发送者的实用程序功能。我们充分表征了计算最佳公共信号方案的双标准近似值的计算复杂性。特别是，我们在独立利益的投票环境中表明，解决此问题至少需要一个准多项式数量的步骤，即使在具有指数时间假设的情况下，在具有二进制动作空间的设置中也需要一个。在此过程中，我们证明了线性不平等问题的最大可行可行子系统的放松版本至少需要解决的准多项式时间。最后，我们通过为任意公共说服问题提供了一个准多项式时间双标准近似算法来缩小差距，这些算法在特定的情况下会产生QPTA。
Persuasion studies how an informed principal may influence the behavior of agents by the strategic provision of payoff-relevant information. We focus on the fundamental multi-receiver model by Arieli and Babichenko (2019), in which there are no inter-agent externalities. Unlike prior works on this problem, we study the public persuasion problem in the general setting with: (i) arbitrary state spaces; (ii) arbitrary action spaces; (iii) arbitrary sender's utility functions. We fully characterize the computational complexity of computing a bi-criteria approximation of an optimal public signaling scheme. In particular, we show, in a voting setting of independent interest, that solving this problem requires at least a quasi-polynomial number of steps even in settings with a binary action space, assuming the Exponential Time Hypothesis. In doing so, we prove that a relaxed version of the Maximum Feasible Subsystem of Linear Inequalities problem requires at least quasi-polynomial time to be solved. Finally, we close the gap by providing a quasi-polynomial time bi-criteria approximation algorithm for arbitrary public persuasion problems that, in specific settings, yields a QPTAS.
