Regret minimization in online Bayesian persuasion: Handling adversarial receiver's types under full and partial feedback models

• Published in: Artificial intelligence 2023-01, Vol.314, p.103821, Article 103821
• Main Authors: Castiglioni, Matteo, Celli, Andrea, Marchesi, Alberto, Gatti, Nicola
• Format: Article
• Language: English
• Subjects: Algorithms; Bayesian analysis; Bayesian persuasion; Economic models; Feedback; Information structure design; Machine learning; Online learning; Optimization; Polynomials; Regret minimization; Signaling
• ISSN: 0004-3702; 1872-7921
• DOI: 10.1016/j.artint.2022.103821

In Bayesian persuasion, an informed sender has to design a signaling scheme that discloses the right amount of information so as to influence the behavior of a self-interested receiver. This kind of strategic interaction is ubiquitous in real-world economic scenarios. However, the seminal model by Kamenica and Gentzkow makes some stringent assumptions that limit its applicability in practice. One of the most limiting assumptions is, arguably, that the sender is required to know the receiver's utility function to compute an optimal signaling scheme. We relax this assumption through an online learning framework in which the sender repeatedly faces a receiver whose type is unknown and chosen adversarially at each round from a finite set of possible types. We are interested in no-regret algorithms prescribing a signaling scheme at each round of the repeated interaction with performances close to that of a best-in-hindsight signaling scheme. First, we prove a hardness result on the per-round running time required to achieve no-α-regret for any α