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.