Algorithmic Persuasion with No Externalities
Algorithmic Persuasion with No Externalities
复制标题
无外部性的算法说服
DOI：
10.1145/3033274.3085152
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Haifeng Xu
中科院分区：
文献类型：
--
作者：
S. Dughmi;Haifeng Xu
我们研究信息结构设计的算法 - 又称说服力或信号传导---在Arieli和Babichenko引入的基本特殊情况下：多个代理，二进制动作，与此模型不同的外部工作。允许许多自然的状态。在效率和计算复杂性方面，当我们的结果是正面的，我们的结果在很大程度上是积极的，我们首先使用线性编程双重性和分离和优化的等效性）最佳信号和最大化目标函数加上其他功能的问题。超模型或匿名。 [Arieli和Babichenko，2016年]和[Babichenko and Barman，2016年]，将它们从大自然的二元状态扩展到许多州（Modulo，后来的结果中增加了）。具有次化物镜的二进制案例，并简化并稍微加强了[Babichenko and Barman，2016]的结果，以通过（1-1/e）的方案获得（1-1/e） - （i），该方案（i）对每个接收者独立信号ii）“忽略”是因为它不依赖于目标函数，只要允许公共信号，我们的结果是负面的。即使添加目标，我们也可以在任何不变的因素内近似最佳的公共方案。
We study the algorithmics of information structure design --- a.k.a. persuasion or signaling --- in a fundamental special case introduced by Arieli and Babichenko: multiple agents, binary actions, and no inter-agent externalities. Unlike prior work on this model, we allow many states of nature. We assume that the principal's objective is a monotone set function, and study the problem both in the public signal and private signal models, drawing a sharp contrast between the two in terms of both efficacy and computational complexity. When private signals are allowed, our results are largely positive and quite general. First, we use linear programming duality and the equivalence of separation and optimization to show polynomial-time equivalence between (exactly) optimal signaling and the problem of maximizing the objective function plus an additive function. This yields an efficient implementation of the optimal scheme when the objective is supermodular or anonymous. Second, we exhibit a (1-1/e)-approximation of the optimal private signaling scheme, modulo an additive loss of ε, when the objective function is submodular. These two results simplify, unify, and generalize results of [Arieli and Babichenko, 2016] and [Babichenko and Barman, 2016], extending them from a binary state of nature to many states (modulo the additive loss in the latter result). Third, we consider the binary-state case with a submodular objective, and simplify and slightly strengthen the result of [Babichenko and Barman, 2016] to obtain a (1-1/e)-approximation via a scheme which (i) signals independently to each receiver and (ii) is "oblivious" in that it does not depend on the objective function so long as it is monotone submodular. When only a public signal is allowed, our results are negative. First, we show that it is NP-hard to approximate the optimal public scheme, within any constant factor, even when the objective is additive. Second, we show that the optimal private scheme can outperform the optimal public scheme, in terms of maximizing the sender's objective, by a polynomial factor.