Reducing the Gap Between Theory and Applications in Algorithmic Bayesian Persuasion

Matteo CastiglioniSpringerBriefs 2024 · DOI · OpenAlex

Introduction

Bayesian persuasion, often described as "strategic sweet talk," is a framework in algorithmic game theory that explores how an informed sender can influence the behavior of self-interested receivers by strategically disclosing information. While theoretically robust, the application of Bayesian persuasion to real-world scenarios—such as traffic routing, online advertising, and voting—has been hindered by two primary obstacles: the computational complexity of finding optimal signaling policies and the unrealistic assumption that the sender possesses perfect knowledge of the receivers' utility functions.

This work bridges the gap between theory and practice by establishing the "tractability frontier" for complex multi-agent systems and introducing an online learning framework to handle payoff uncertainty.

Computational Complexity in Structured Games

A significant portion of this research focuses on settling the complexity of computing optimal sender strategies in specific domains: voting, routing, and auctions.

Voting and Public vs. Private Signaling

In the context of voting, the research identifies a sharp divide based on the communication channel. Computing optimal private signals—where the sender provides individualized information to each voter—is shown to be computationally efficient (polynomial time). Conversely, providing a public signal to all voters simultaneously is NP-hard to even approximate within a constant factor under the Majority voting rule.

Routing and Symmetry

In network congestion games, such as traffic routing, the tractability of information disclosure depends on the symmetry of the players. If all receivers share the same source and destination (symmetric games), optimal information disclosure can be computed efficiently. However, in asymmetric networks where players have different origins or destinations, the problem becomes NP-hard.

Auctions and Revenue Maximization

For Bayesian posted-price auctions, the work develops a Polynomial-Time Approximation Scheme (PTAS). This demonstrates that while an exact solution may be computationally difficult, it is possible to efficiently achieve a revenue that is arbitrarily close to the theoretical optimum.

Relaxing the Omniscience Assumption: Online Persuasion

Classical Bayesian persuasion models assume the sender knows the receiver's utility function exactly. This work relaxes this assumption by framing persuasion as a repeated online game.

No-Regret Learning

The author develops adaptive information disclosure policies that learn the receiver's preferences over time. Two feedback models are explored:

  • Full Information Feedback: The sender eventually learns the receiver's type, leading to a regret bound of $O(T^{1/2})$.
  • Partial Information Feedback: The sender only observes the receiver's actions, resulting in a regret bound of $O(T^{4/5})$.

Type Reporting

A novel mechanism-design approach is introduced where receivers are asked to report their "type" (preferences) before receiving a signal. This "type reporting" step effectively transforms an otherwise intractable online problem into a solvable linear program.

Conclusion and Future Directions

By mapping the computational limits of information disclosure and developing algorithms for uncertain environments, this work provides a foundation for deploying Bayesian persuasion in practical systems. Future research will address externalities in online multi-receiver settings (such as routing) and expand the framework to handle infinite or continuous receiver types and heterogeneous prior beliefs.

Summary updated

Abstract

Abstract This work focuses on the following question: is it possible to influence the behavior of self-interested agents through the strategic provision of information ? This ‘sweet talk’ is ubiquitous among all sorts of economics and non-economics activities. In this work, we model these multi-agent systems as games between an informed sender and one or multiple receivers. We study the computational problem faced by an informed sender that wants to use his information advantage to influence rational receivers with the partial disclosure of information. In particular, the sender faces an information structure design problem that amounts to deciding ‘who gets to know what’. Bayesian persuasion provides a formal framework to model these settings as asymmetric-information games. In recent years, much attention has been given to Bayesian persuasion in the economics and artificial intelligence communities due also to the applicability of this framework to a large class of scenarios like online advertising, voting, traffic routing, recommendation systems, security, and product marketing. However, there is still a large gap between the theoretical study of information in games and its applications in real-world scenarios. This work contributes to close this gap along two directions. First, we study the persuasion problem in real-world scenarios, focusing on voting, routing, and auctions. While the Bayesian persuasion framework can be applied to all these settings, the algorithmic problem of designing optimal information disclosure polices introduces computational challenges related to the specific problem under study. Our goal is to settle the complexity of computing optimal sender’s strategies, showing when an optimal strategy can be implemented efficiently. Then, we relax stringent assumptions that limit the applicability of the Bayesian persuasion framework in practice. In particular, the classical model assumes that the sender has perfect knowledge of the receiver’s utility. We remove this assumption initiating the study of an online version of the persuasion problem. This is the first step in designing adaptive information disclosure policies that deal with the uncertainty intrinsic in all real-world applications.
BibTeX
@inproceedings{castiglioni2024reducing,
  author = {Matteo Castiglioni},
  title = {{Reducing the Gap Between Theory and Applications in Algorithmic Bayesian Persuasion}},
  booktitle = {SpringerBriefs},
  year = {2024},
  doi = {10.1007/978-3-031-51500-2\_1},
}
Figure