Online Algorithms for Bayesian Persuasion

信息设计，也被称为贝叶斯说服，是一个研究知情的代理(发送者)如何共享信息以激励不知情的代理(接收者)采取某些对发送者有利的行动的领域。贝叶斯说服因其广泛的应用而在经济学中得到了广泛的关注，但其背后的算法问题还没有得到很好的理解。在这个项目中，我们的目标是提高说服和推荐问题中算法理论的艺术水平。我们专注于在线环境，在这种环境中，信息共享和收集逐渐并同时发生。我们的目标是为发送者分析和计算最优和接近最优的说服策略。在线设置与最优停止理论密切相关，特别是与组合秘书和预言者不等式问题密切相关。这里，接收者可以在对所选动作的子集的不同组合限制下选择几个动作。最突出的是，我们将重点关注背包或匹配等包装结构。首要目标是研究说服方案的计算复杂性，这些方案优化发送者的预期效用，同时激励接收者遵循任何建议的行动。我们还对竞争分析感兴趣，即，与离线设置(当知道未来时)中的最优方案相比，设计具有有限的发送者效用损失的好方案。更根本的是，我们想看看是否存在“黑箱”减少，使用它我们可以将好的在线算法转换为好的在线信令方案。通过这种方式，我们为(线上和线下)说服和推荐问题提供了算法工具箱。

Information design, alternatively known also as Bayesian persuasion, is a field that studies how an informed agent (sender) can share information in order to motivate an uninformed agent (receiver) to take certain actions that are beneficial to the sender. Bayesian persuasion has received a lot of attention in economics due to its many applications, but the underlying algorithmic problems are not well-understood. In this project, our goal is to advance the state of the art of algorithmic theory in persuasion and recommendation problems. We focus on online settings where information sharing and gathering happen gradually and concurrently. Our goal is to analyze and compute optimal and near-optimal persuasion strategies for the sender. The online setting is closely related to optimal stopping theory, in particular, to combinatorial secretary and prophet inequality problems. Here a receiver can select several actions, under different combinatorial restrictions on the subset of selected actions. Most prominently, we will focus on packing structures such as knapsack or matching. The overarching goal is to study the computational complexity of persuasion schemes that optimize the expected utility of the sender, while incentivizing the receiver to follow any recommended action. We are also interested in competitive analysis, i.e., designing good schemes with a bounded loss in sender utility compared to optimal schemes in the offline setting (when knowing the future). More fundamentally, we want to see if there are “black-box”-reductions, using which we can transform good online algorithms into good online signaling schemes. In this way, we contribute to the algorithmic toolbox for (online and offline) persuasion and recommendation problems.