Our results and paper organization. Let \(m\)  and \(k\)  be the numbers of constraints and states of nature, respectively. Section  formally defines our model and describes the main motivations. Section  shows a tight bound of \(k\)  on the support size of an optimal ex post-constrained signaling scheme, which is the same as in the original setting of [1]}. For ex ante constraints, Section  proves tightness of the \(k+m\)  bound of [2]} on the support size and provides an alternative proof to this bound; in particular, it extends the lower bound result of [3]} beyond a single constraint. The support size of a signaling scheme is a common measure of its complexity, similar to menu-size complexity in auctions [4]}, [5]}. Section  provides an additive bi-criteria FPTAS for an optimal signaling scheme when \(k\)  is constant and improves it to single-criteria under a Slater-like regularity condition. This result holds for standard constraints – including Kullback–Leibler (KL) divergence, entropy and norm constraints (such as variation distance) – and standard objective functions: Lipschitz-continuous (corresponding to Receiver having a continuum of actions) or piecewise constant (for finite Receiver's action space). Although these objective and constraint families capture a wide range of scenarios, the same algorithm remains an additive bi-criteria PTAS – which improves to single-criteria under a Slater-like condition – for even more general families. Section  shows that for constant \(m\) , convex constraints and a wide family of objective functions, ex ante constraints outperform ex post constraints by a constant multiplicative factor. Subsection REF  concludes by applications to ad auctions with exponentially large states of nature space, using a generalization of the setting of [6]} [6]}.
