  Bayesian persuasion is the study of information sharing policies among
strategic agents. A prime example is signaling in online ad auctions: what
information should a platform signal to an advertiser regarding a user when
selling the opportunity to advertise to her? Practical considerations such as
preventing discrimination, protecting privacy or acknowledging limited
attention of the information receiver impose constraints on information
sharing. In this work, we propose and analyze a simple way to mathematically
model such constraints as restrictions on Receiver's admissible posterior
beliefs.
  We consider two families of constraints - ex ante and ex post, where the
latter limits each instance of Sender-Receiver communication, while the former
more general family can also pose restrictions in expectation. For the ex ante
family, Doval and Skreta establish the existence of an optimal signaling scheme
with a small number of signals - at most the number of constraints plus the
number of states of nature; we show this result is tight and provide an
alternative proof for it. For the ex post family, we tighten a bound of
V{\o}lund, showing that the required number of signals is at most the number of
states of nature, as in the original Kamenica-Gentzkow setting. As our main
algorithmic result, we provide an additive bi-criteria FPTAS for an optimal
constrained signaling scheme assuming a constant number of states; we improve
the approximation to single-criteria under a Slater-like regularity condition.
The FPTAS holds under standard assumptions; relaxed assumptions yield a PTAS.
Finally, we bound the ratio between Sender's optimal utility under convex ex
ante constraints and the corresponding ex post constraints. This bound applies
to finding an approximately welfare-maximizing constrained signaling scheme in
ad auctions.
