NSF-BSF: AF: Small: Algorithmic Persuasion: Re-creating the Success of Mechanism Design

NSF-BSF：AF：小：算法说服：重新创造机制设计的成功

• 批准号: 2132506
• 负责人: Haifeng Xu
• 金额: $ 45.34万
• 依托单位: University of Virginia Main Campus
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-10-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2132506&HistoricalAwards=false
• 关键词: NSF; BSF; AF; Small; Algorithmic

In today’s increasingly connected world, particularly on the Internet, interactions among people and algorithms lead to important social and economic outcomes. Such interactions involve massive exchange of information, often by self-interested parties, on the basis of which individuals make decisions and choose their actions. An emerging research area termed "Bayesian persuasion" studies the optimal design of information mechanisms for such strategic communications, also known as signaling schemes. This project will promote this area of research through the computational lens, and aims at bringing current stylized models closer to practice and thus uncovering new structure that will help make progress on longstanding problems. It will combine algorithmic and game-theoretic tools to achieve better designs of information mechanisms, towards enhanced social welfare and economic surplus. Since one of the main characteristics of today’s digital economy is the collection of information and its dissemination among many self-interested parties, developing a modern algorithmic theory of persuasion is of imminent importance. As part of this project, the PIs will organize education activities (tutorials, workshops and surveys) to propel forward the relatively nascent research area of algorithmic persuasion to the research community, and will integrate research findings into courses to provide the next generation of computer scientists the ability of reasoning about the strategic role of information in complex environments. Like mechanism design, persuasion is inherently an optimization task. On a technical level, the main focus of this project is to identify and expand multiple new research frontiers driven by key applications of persuasion in today’s digital economy, with the ultimate goal of obtaining a mature algorithmic theory of persuasion. This includes the following. (1) Going beyond the basic models of persuasion studied algorithmically thus far, by taking into account additional structure present in important applications of persuasion, e.g., online advertising auctions. Utilizing structure is crucial in overcoming the hardness and impossibility results with which the general persuasion models are so rife. (2) Going beyond a flat model of persuasion to more realistic communication on networks. For example, how would information transmit over a social network when each agent is both an information sender and receiver? (3) Designing optimal or approximately-optimal persuasion schemes under realistic constraints: privacy-preservation, robustness, and communication restrictions.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

在当今越来越有联系的世界中，尤其是在互联网上，人们和算法之间的互动会带来重要的社会和经济成果。这种互动涉及大量的信息交流，通常是由自私当事方进行的，基于个人做出决定并选择其行动。一个称为“贝叶斯说服”的新兴研究领域研究了此类战略通信的信息机制的最佳设计，也称为信号方案。该项目将通过计算镜头来促进这一研究领域，并旨在使当前的风格模型更接近实践，从而发现新的结构，从而有助于在长期存在问题上取得进展。它将结合算法和游戏理论工具，以实现更好的信息机制设计，以增强社会福利和经济盈余。由于当今数字经济的主要特征之一是信息的收集及其在许多自我利益政党中的传播，因此开发一种现代的说服算法理论至关重要。作为该项目的一部分，PI将组织教育活动（教程，研讨会和调查），以推动算法说服力的相对新生研究领域向研究社区，并将研究结果纳入下一代计算机科学家在复杂环境中的战略作用的推理能力。像机制设计一样，说服力本质上是一项优化任务。从技术层面上讲，该项目的主要重点是确定和扩展由说服力在当今数字经济中的关键应用所驱动的多个新研究领域，其最终目标是获得成熟的说服力理论。这包括以下内容。 （1）到目前为止，通过考虑说服力应用中存在的其他结构，例如在线广告拍卖中，超越了说服算法的基本模型。利用结构对于克服一般说服模型的硬度和不可能结果至关重要。 （2）超越说服力的平坦模型，可以在网络上进行更现实的沟通。例如，当每个代理都是信息发送者和接收者时，信息将如何通过社交网络传播？ （3）在现实限制下设计最佳或大约最佳的说服计划：隐私保护，鲁棒性和沟通限制。该奖项反映了NSF的法定任务，并被认为是通过基金会的知识分子优点和更广泛的影响审查标准通过评估来评估的。

项目成果

Online Bayesian Recommendation with No Regret

• DOI: 10.1145/3490486.3538327
• 发表时间: 2022-02
• 期刊: Proceedings of the 23rd ACM Conference on Economics and Computation
• 作者: Yiding Feng;Wei Tang;Haifeng Xu

Sequential Information Design: Markov Persuasion Process and Its Efficient Reinforcement Learning

• DOI: 10.1145/3490486.3538313
• 发表时间: 2022-02
• 期刊: Proceedings of the 23rd ACM Conference on Economics and Computation
• 作者: Jibang Wu;Zixuan Zhang;Zhe Feng;Zhaoran Wang;Zhuoran Yang;Michael I. Jordan;Haifeng Xu

The Strange Role of Information Asymmetry in Auctions—Does More Accurate Value Estimation Benefit a Bidder?

信息不对称在拍卖中的奇怪作用——更准确的价值估算对投标人有利吗？

• DOI: 10.1609/aaai.v36i5.20459
• 发表时间: 2022
• 期刊: Proceedings of the AAAI Conference on Artificial Intelligence
• 作者: Xu, Haifeng;Cavallo, Ruggiero
• 通讯作者: Cavallo, Ruggiero

Algorithmic Information Design in Multi-Player Games: Possibilities and Limits in Singleton Congestion

多人游戏中的算法信息设计：单例拥塞的可能性和限制

• DOI: 10.1145/3490486.3538238
• 发表时间: 2022
• 期刊: Proc. 23th ACM Conference on Economics and Computation
• 作者: Zhou, Chenghan;Nguyen, Thanh H.;Xu, Haifeng
• 通讯作者: Xu, Haifeng