Abstract
In Bayesian persuasion, a Sender strategically crafts information to influence a Receiver's actions. While foundational in economics, solving these problems for general probability distributions and continuous action spaces has remained computationally challenging due to non-convexity. This paper introduces a novel framework that transforms the signaling problem into a linear program over the cone of completely positive (CP) matrices. By leveraging copositive programming and semi-definite programming (SDP) relaxations, the authors provide a robust toolkit for finding global optima in strategic information-sharing games, moving beyond the limitations of traditional Gaussian-only models.
Introduction
Bayesian persuasion is a strategic framework where a "Sender" (e.g., a prosecutor) provides a signal to a "Receiver" (e.g., a judge) to influence their posterior beliefs and subsequent actions. The Sender commits to a signaling policy, and the Receiver, being rational, calculates an estimate based on the received signal.
This interaction is modeled as a Stackelberg game. The primary difficulty in solving such games arises when the state space is continuous or when the underlying distributions are non-Gaussian. Traditional methods often struggle with the non-convex nature of the Sender's optimization problem, frequently stalling at local optima.
The Copositive Programming Approach
The authors' core contribution is the observation that for quadratic cost measures, the Sender’s objective function depends solely on the correlation matrix of the Receiver’s posterior estimate. By exploiting this structure, they prove that the persuasion problem is equivalent to a linear program over the cone of completely positive (CP) matrices.
A matrix is completely positive if it can be factored into the product of two non-negative matrices. Shifting the problem into this CP space offers several advantages:
- Linearization: The traditionally non-linear constraints of Bayesian plausibility are naturally satisfied by the CP matrix structure.
- Convexity: The problem becomes a structured linear program, albeit over a specialized cone.
- Distributional Flexibility: The framework applies to any distribution with finite support, removing the need for Gaussian assumptions.
Computational Strategy and Convergence
Since optimizing directly over CP cones is NP-hard, the authors propose a sequential polyhedral approximation method. This iterative algorithm "sandwiches" the true solution between an inner and outer approximation, allowing for high-precision results.
Additionally, the authors provide an SDP relaxation that is proven to be perfectly tight for state spaces of size $n \le 4$. This is particularly significant for binary decision-making tasks or privacy-preserving signaling where state spaces are typically small.
Key Results and Scalability
The proposed methods were evaluated across several synthetic scenarios (Scenarios I-IV) simulating prosecutor-judge interactions with varying state space sizes (from 2 to 100 states).
- Optimality: The CP-based method consistently identified global optima where local search methods failed.
- Efficiency: In Scenario III (9 states), the SDP relaxation provided a tight lower bound that matched the optimal signaling cost, significantly outperforming benchmark Gaussian-based SDPs.
- Scalability: Even in Scenario IV with 100 states, the SDP relaxation remained computationally feasible on standard hardware, providing a more accurate benchmark than previous linear programming techniques.
Conclusion
By bridging game theory and copositive programming, this research provides a powerful new perspective on strategic signaling. While scalability to very large state spaces remains a challenge for future work, the current framework offers a rigorous and efficient path for solving complex Bayesian persuasion problems in diverse fields such as economics, control theory, and cybersecurity.
Summary updated