  The Bayesian persuasion paradigm of strategic communication models
interaction between a privately-informed agent, called the sender, and an
ignorant but rational agent, called the receiver. The goal is typically to
design a (near-)optimal communication (or signaling) scheme for the sender. It
enables the sender to disclose information to the receiver in a way as to
incentivize her to take an action that is preferred by the sender. Finding the
optimal signaling scheme is known to be computationally difficult in general.
This hardness is further exacerbated when there is also a constraint on the
size of the message space, leading to NP-hardness of approximating the optimal
sender utility within any constant factor.
  In this paper, we show that in several natural and prominent cases the
optimization problem is tractable even when the message space is limited. In
particular, we study signaling under a symmetry or an independence assumption
on the distribution of utility values for the actions. For symmetric
distributions, we provide a novel characterization of the optimal signaling
scheme. It results in a polynomial-time algorithm to compute an optimal scheme
for many compactly represented symmetric distributions. In the independent
case, we design a constant-factor approximation algorithm, which stands in
marked contrast to the hardness of approximation in the general case.
