Algorithmic aspects of private Bayesian persuasion

DOI10.4230/LIPICS.ITCS.2017.34MaRDI QIDQ4638086zbMATH OpenOpenAlexFDO

Authors Yakov Babichenko, Siddharth Barman

Publication date 3 May 2018

Full work available at URL https://arxiv.org/abs/1603.01444

zbMATH Keywords

Bayesian persuasionconcave closureeconomics of informationsignaling

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Signaling and communication in game theory (91A28) Economics of information (91B44)

Abstract: We study computational questions in a game-theoretic model that, in particular, aims to capture advertising/persuasion applications such as viral marketing. Specifically, we consider a multi-agent Bayesian persuasion model where an informed sender (marketer) tries to persuade a group of agents (consumers) to adopt a certain product. The quality of the product is known to the sender, but it is unknown to the agents. The sender is allowed to commit to a signaling policy where she sends a private signal---say, a viral marketing ad---to every agent. This work studies the computation aspects of finding a signaling policy that maximizes the sender's revenue. We show that if the sender's utility is a submodular function of the set of agents that adopt the product, then we can efficiently find a signaling policy whose revenue is at least (1-1/e) times the optimal. We also prove that approximating the sender's optimal revenue by a factor better than (1-1/e) is NP-hard and, hence, the developed approximation guarantee is essentially tight. When the senders' utility is a function of the number of agents that adopt the product (i.e., the utility function is anonymous), we show that an optimal signaling policy can be computed in polynomial time. Our results are based on an interesting connection between the Bayesian persuasion problem and the evaluation of the concave closure of a set function.

Recommendations

• Private Bayesian persuasion
• Algorithms for persuasion with limited communication
• Regret-minimizing Bayesian persuasion

Cites work

• Approximating theDomatic Number
• Bayesian persuasion with multiple senders and rich signal spaces
• Constrained signaling in auction design
• Convexity and Steinitz's exchange property
• Discrete Convex Analysis
• Expert advice to a voting body
• Finite supermodular design with interdependent valuations
• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• Inapproximability results for combinatorial auctions with submodular utility functions
• Information structures in optimal auctions
• Maximizing a monotone submodular function subject to a matroid constraint
• On the value of persuasion by experts
• Private Bayesian persuasion
• Repeated games with incomplete information. With the collaboration of Richard E. Stearns
• Strategic Information Transmission
• Stress tests and information disclosure

Cited in

(15)

• The secretary recommendation problem
• On the hardness of designing public signals
• Private Bayesian persuasion
• Regret minimization in online Bayesian persuasion: handling adversarial receiver's types under full and partial feedback models
• Modes of persuasion toward unanimous consent
• Bayesian markets to elicit private information
• BAYESIAN PERSUASION WITH PRIVATE EXPERIMENTATION
• Algorithms for persuasion with limited communication
• Public Bayesian persuasion: being almost optimal and almost persuasive
• Increasing revenue in Bayesian posted price auctions through signaling
• Multi-channel Bayesian persuasion
• A population's feasible posterior beliefs
• Delegated online search
• Bayesian calibrated click-through auctions
• Persuasion and incentives through the lens of duality

This page was built for publication: Algorithmic aspects of private Bayesian persuasion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4638086)