Designing Information in a Forest: Algorithmic Aspects

The Bayesian persuasion framework models strategic information revelation by a sender to one or more receivers. We study an intricate version of the multi-receiver persuasion setting in which the communication hierarchy is a forest - i.e., some receivers observe more informative signals than others, and the partial ordering of the receivers according to the information they get is represented by a pre-specified directed forest. This model naturally captures interactions in hierarchical organizations, and it lies in between the two most commonly studied versions of Bayesian persuasion: private persuasion and public persuasion. Inspired by the classic model of private persuasion, we focus on a setting with a binary state of nature and binary-action heterogeneous receivers s.t. the sender's utility is a monotone function of the set of receivers taking a specific desirable action. We extend the computational tractability result for symmetric sender's utility from private persuasion to the forest hierarchy framework using methodology inspired by optimal transport theory. We further provide a polynomial-time algorithm when the sender's utility is modular. On the negative side, we show that, unlike in private persuasion, the case of a supermodular sender's utility function leads to an NP-hard optimization problem which further does not admit an FPTAS unless P=NP; this result holds even when each tree component of the forest is a chain of 3 receivers. To complement the hardness result, we provide a simple approximation algorithm with the approximation ratio depending linearly on the depth of the forest hierarchy. We further provide an analogous algorithm for the submodular utility case. Finally, beyond forest communication hierarchies, we rule out an FPTAS for the sender's optimal utility even in the symmetric utility case, unless P=NP.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-12
DOI
https://doi.org/10.48550/arxiv.2611.16327
Primary Topic
Game Theory and Applications
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Designing Information in a Forest: Algorithmic Aspects

Konstantin Zabarnyi
arXiv (Cornell University)
Game Theory and Applications
preprint

Designing Information in a Forest: Algorithmic Aspects

Konstantin Zabarnyi
preprint en

Abstract

The Bayesian persuasion framework models strategic information revelation by a sender to one or more receivers. We study an intricate version of the multi-receiver persuasion setting in which the communication hierarchy is a forest - i.e., some receivers observe more informative signals than others, and the partial ordering of the receivers according to the information they get is represented by a pre-specified directed forest. This model naturally captures interactions in hierarchical organizations, and it lies in between the two most commonly studied versions of Bayesian persuasion: private persuasion and public persuasion. Inspired by the classic model of private persuasion, we focus on a setting with a binary state of nature and binary-action heterogeneous receivers s.t. the sender's utility is a monotone function of the set of receivers taking a specific desirable action. We extend the computational tractability result for symmetric sender's utility from private persuasion to the forest hierarchy framework using methodology inspired by optimal transport theory. We further provide a polynomial-time algorithm when the sender's utility is modular. On the negative side, we show that, unlike in private persuasion, the case of a supermodular sender's utility function leads to an NP-hard optimization problem which further does not admit an FPTAS unless P=NP; this result holds even when each tree component of the forest is a chain of 3 receivers. To complement the hardness result, we provide a simple approximation algorithm with the approximation ratio depending linearly on the depth of the forest hierarchy. We further provide an analogous algorithm for the submodular utility case. Finally, beyond forest communication hierarchies, we rule out an FPTAS for the sender's optimal utility even in the symmetric utility case, unless P=NP.

arXiv (Cornell University)
Game Theory and Applications
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon