Algorithms for Persuasion with Limited Communication

Ronen Gradwohl, Niklas Hahn, Martin Hoefer, Rann Smorodinsky

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים

3 ציטוטים ‏(Scopus)

תקציר

The Bayesian persuasion paradigm of strategic communication models interaction between a privately informed sender and an ignorant but rational receiver. The goal is typically to design a (near-)optimal communication (or signaling) scheme for the sender. It enables the sender to disclose information to the receiver in a way as to incentivize her to take an action that is preferred by the sender. Finding the optimal signaling scheme is known to be computationally difficult in general. This hardness is further exacerbated when the message space is constrained, leading to NP-hardness of approximating the optimal sender utility within any constant factor. In this paper, we show that in several natural and prominent cases the optimization problem is tractable even when the message space is limited. In particular, we study signaling under a symmetry or an independence assumption on the distribution of utility values for the actions. For symmetric distributions, we provide a novel characterization of the optimal signaling scheme. It results in a polynomial-time algorithm to compute an optimal scheme for many compactly represented symmetric distributions. In the independent case, we design a constant-factor approximation algorithm, which stands in marked contrast to the hardness of approximation in the general case.

שפה מקוריתאנגלית
עמודים (מ-עד)2520-2545
מספר עמודים26
כתב עתMathematics of Operations Research
כרך47
מספר גיליון3
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - אוג׳ 2022

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Algorithms for Persuasion with Limited Communication'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי