arXiv preprint ·

Designing Information in a Forest: Algorithmic Aspects

Konstantin Zabarnyi

Published
Source
arXiv preprint, posted before peer review
Original
Read it at arXiv
Topics
Computer Science & Game TheoryTheoretical Economics

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.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

Read it on ReadSearch

Each opens after you create an account, and brings you back to this paper.

Already a reader? Sign in

All new papers in Computer Science & Game Theory

Get the few papers worth your time in Computer Science & Game Theory every morning.

ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.

Papers belong to their authors and publishers; every page here links to the original. All research topics