Optimal Hierarchical Signaling for Quadratic Cost Measures and General Distributions: A Copositive Program Characterization

Muhammed O. Sayin, Tamer BasararXiv 2019 · arXiv

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.

The Bayesian persuasion framework: A Sender strategically crafts a signal to influence a Receiver's learnt state.

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:

  1. Linearization: The traditionally non-linear constraints of Bayesian plausibility are naturally satisfied by the CP matrix structure.
  2. Convexity: The problem becomes a structured linear program, albeit over a specialized cone.
  3. 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.

Convergence of inner and outer approximations across Scenarios I, II, and III, demonstrating the algorithm's ability to reach a global optimum within a few dozen iterations.

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

Abstract

We address Bayesian persuasion between a sender and a receiver with state-dependent quadratic cost measures for general classes of distributions. The receiver seeks to make mean-square-error estimate of a state based on a signal sent by the sender while the sender signals strategically in order to control the receiver's estimate in a certain way. Such a scheme could model, e.g., deception and privacy, problems in multi-agent systems. Existing solution concepts are not viable since here the receiver has continuous action space. We show that for finite state spaces, optimal signaling strategies can be computed through an equivalent linear optimization problem over the cone of completely positive matrices. We then establish its strong duality to a copositive program. To exemplify the effectiveness of this equivalence result, we adopt sequential polyhedral approximation of completely-positive cones and analyze its performance numerically. We also quantify the approximation error for a quantized version of a continuous distribution and show that a semi-definite program relaxation of the equivalent problem could be a benchmark lower bound for the sender's cost for large state spaces.
BibTeX
@misc{sayin2019optimal,
  author = {Muhammed O. Sayin and Tamer Basar},
  title = {{Optimal Hierarchical Signaling for Quadratic Cost Measures and General Distributions: A Copositive Program Characterization}},
  year = {2019},
  eprint = {1907.09070},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1907.09070},
}
Figure