We study the setting of ex ante- and ex post-constrained persuasion, which has applications to areas including ad auctions and limited attention. A future research direction, especially considering Theorem REF , is studying (nearly) optimal signaling schemes under common ex post constraints, such as KL divergence. Another interesting direction is constrained persuasion with private signaling, e.g., when Sender's utility is a function of the set of Receivers who adopt a certain action [1]}.


Alternative Proof of Fact  REF
The proof is similar to that of Theorem REF , but we add to the infinite LP \(m\)  constraints corresponding to the given ex ante constraints, rather than restricting the support of \(\Sigma \)  to a compact subset of \(\Delta *{\Omega }\) .

Denote the function and the constant specifying the \(i\) -th ex ante constraint (\(1\le i\le m\) ) by \(i\)  and \(c_i\) , respectively. We aim to solve:
\(\text{max}\;\;\;\;&E*{\Sigma ,u_s}\\\text{s.t.}\;\;\;\;\;\;&{p}*{\omega _0}=E*{\Sigma ,{p}_{\sigma }*{\omega _0}}\;\;\forall \omega _0 \in \Omega \\&E*{\Sigma ,f_i}\le c_i\;\;\forall 1\le i\le m\) 

The optimization problem specifies an infinite LP with \(k+m\)  constraints s.t. the “variables” are the distribution \(\Sigma \)  over elements of \(\Delta *{\Omega }\) . The rest of the proof is the same as for Theorem REF  with \(K=\Delta *{\Omega }\)  (using the notions of Theorem REF  proof); the only difference is that we have \(k+m\)  linear constraints rather than \(k\) , which yields a bound of \(2^{k+m}\)  on \({{\mathrm {supp}}*{\Sigma }}\)  in the third step and a bound of \(k+m\)  in the fourth step.

Proof of Proposition  REF
Fix \(k\) , \(m\)  and some \(\Omega \)  of size \(k\) . We shall define \(m\)  ex ante constraints and an upper semi-continuous \(u_s\)  s.t. any optimal signaling scheme has support size exactly \(k+m\) .
Let \(e_1,...,e_k\)  be the standard basis of \(\mathbb {R}^k\) . Take \(q_1,...,q_m\)  to be \(m\)  distinct interior points of \(\Delta *{\Omega }\setminus *{e_1,...,e_k}\)  with \(\frac{q_1+...+q_m}{m}=*{\frac{1}{k},...,\frac{1}{k}}\) ; set \(u_s\)  to be 1 on \(*{q_1,...,q_m}\) , \(\frac{1}{2}\)  on \(*{e_1,...,e_k}\)  and 0 on \(\Delta *{\Omega }\setminus *{e_1,...,e_k, q_1,...,q_m}\) ; let \(f_i\)  (\(1\le i\le m\) ) be some nonnegative continuous function, which is 1 on \(q_i\)  and 0 on the other \(q_j\) s; set \(c_1=...=c_m=\frac{1}{2m}\) ; choose \(p=*{\frac{1}{k},...,\frac{1}{k}}\) .
Then \(u_s\)  is upper semi-continuous and the \(f_i\) s are continuous. Furthermore, no valid signaling scheme under the ex ante constraints specified by the \(f_i\) s and the \(c_i\) s assigns probability greater than \(\frac{1}{2m}\)  to each \(q_i\) ; thus, the utility of a valid scheme is at most: \(m\cdot \frac{1}{2m}\cdot 1+*{1-m\cdot \frac{1}{2m}}\cdot \frac{1}{2}=\frac{3}{4}\) .
A utility of exactly \(\frac{3}{4}\)  is achieved by valid schemes that assign probability of exactly \(\frac{1}{2m}\)  to each \(q_i\)  and split the remaining probability between \(e_1,...,e_k\) . Bayes-plausibility implies that exactly one such scheme exists, assigning probability of \(\frac{1}{2m}\)  to each \(q_i\)  and probability of \(\frac{1}{2k}\)  to each \(e_j\) . Thus, there exists a single optimal valid scheme, which has support size exactly \(k+m\) .
Observation B.1 
One can modify our construction to make \(u_s\)  continuous.

For example, one can make \(u_s\)  to quickly decrease to 0 on all the rays originating from any \(q_i\)  or \(e_j\)  and require \(f_i\)  to be greater than 1 in a deleted neighbourhood of \(q_i\)  on which \(u_s\)  is nonzero.

Proof of Theorem  REF
[Proof of Theorem REF , part 1]
Suppose that \(u_s\)  is either \(O(1)\) -Lipschitz or piecewise constant, having a constant pieces number, with each piece covering a convex polygon in \(\Delta *{\Omega }\)  having a constant number of vertices. Then \(u_s\)  satisfies Assumption REF  with \(t*{\frac{1}{\epsilon }}:=\frac{1}{\epsilon }\) . Indeed, to define \(u_{\epsilon ,M}\) , one can divide \(\Delta *{\Omega }\)  to \({\mathrm {poly}}*{\frac{1}{\epsilon }}\)  simplices of diameters at most \(\frac{\epsilon }{M}\)  s.t. the supremum and the infimum of \(u_s\)  on every simplex differ at most by \(\epsilon \) , and then set \(u_{\epsilon ,M}\)  on every such simplex to be the supremum of \(u_s\)  on it.
An ex ante constraint specified by an \(O(1)\) -Lipschitz function trivially satisfies Assumption REF  with \(t*{\frac{1}{\epsilon }}:=\frac{1}{\epsilon }\)  – simply define \(g_i:=f_i\) . Consider now an ex ante constraint specified by a function of the form:
\(f_i*{p_{\sigma }}:=b\cdot \sum _{1\le j\le l} *{\sum _{\omega ^{\prime }\in \Omega _j} p_{\sigma }*{\omega ^{\prime }}}\ln \frac{\sum _{\omega ^{\prime }\in \Omega _j} p_{\sigma }*{\omega ^{\prime }}}{b_j},\) 
where \(*{\Omega _j}_{1\le j\le l}\)  is a partition of \(\Omega \) , \(b_1,...,b_l>0\)  are constants and \(b\)  is constant. We shall show that one can assume w.l.o.g. that \(f_i*{p_{\sigma }}\equiv \sum _{\omega ^{\prime }\in \Omega } p_{\sigma }*{\omega ^{\prime }}\ln p_{\sigma }*{\omega ^{\prime }}\) ; then we shall prove that the corresponding ex ante constraint satisfies Assumption REF  with \(t*{\frac{1}{\epsilon }}:=\frac{1}{\epsilon }\) .
First, assume w.l.o.g. that \(b=1\) : by dividing both \(f_i\)  and \(c_i\)  by \({b}\)  we can assume \(b\in \lbrace -1,1\rbrace \) ;The case \(b=0\)  is trivial. then note that if \(g_i\)  fits for \(f_i\) , then \(-\epsilon -g_i\)  fits for \(-f_i\) . Secondly, assume w.l.o.g. that \(l=k\)  and \(*{\Omega _j}=1\)  for every \(1\le j\le l\)  – just replace \(\Omega \)  with \(\Omega ^{\prime }:=*{\Omega _j}_{1\le j\le l}\) . Thirdly, by adding a linear function to \(f_i\) , assume w.l.o.g. that \(f_i*{p_{\sigma }}\equiv \sum _{\omega ^{\prime }\in \Omega } p_{\sigma }*{\omega ^{\prime }}\ln p_{\sigma }*{\omega ^{\prime }}\) ; it is possible since adding an \(O(1)\) -Lipschitz function does not affect the satisfaction of Assumption REF .
Let \(p^{\prime }\)  be the center of \(\Delta *{\Omega }\)  and let \(S_{\epsilon }\)  be the contraction (homothety) of \(\Delta *{\Omega }\)  centered at \(p^{\prime }\)  with coefficient \(\frac{1}{1+\epsilon ^2}\) . The restriction of \(f_i\)  to \(S_{\epsilon }\)  is \({\mathrm {poly}}*{\frac{1}{\epsilon }}\) -Lipschitz, since on \(S_{\epsilon }\)  one has: \(||\bigtriangledown f_i*{p_{\sigma }}||=O*{\sum _{\omega ^{\prime }\in \Omega } *{\ln p_{\sigma }*{\omega ^{\prime }}}}=O*{\sum _{\omega ^{\prime }\in \Omega }\frac{1}{p_{\sigma }*{\omega ^{\prime }}}}={\mathrm {poly}}*{\frac{1}{\epsilon }}\) . Extend this restriction of \(f_i\)  to a function \(\tilde{g_i}:\Delta *{\Omega }\rightarrow \mathbb {R}\)  s.t. for every \(q\in \Delta *{\Omega }\setminus S_{\epsilon }\) , \(\tilde{g_i}(q)\)  equals the value of \(f_i\)  on the projection of \(q\)  onto the closed, convex and nonempty set \(S_{\epsilon }\) . Finally, set \(g_i\equiv \tilde{g_i}-\frac{\epsilon }{2}\) .
Then \(g_i\)  is \({\mathrm {poly}}*{\frac{1}{\epsilon }}\) -Lipschitz, since \(f_i\)  is \({\mathrm {poly}}*{\frac{1}{\epsilon }}\) -Lipschitz and projection on a closed, convex and nonempty set is 1-Lipschitz. It remains to check that \(0\le f_i(q)-g_i(q)\le \epsilon \)  for every \(q\in \Delta *{\Omega }\) . It is immediate for \(q\in S_{\epsilon }\) . Fix now \(q\in \Delta *{\Omega }\setminus S_{\epsilon }\) . It is enough to show that \(*{f_i(q)-\tilde{g_i}(q)}\le \frac{\epsilon }{2}\) . Indeed, by the definition of \(\tilde{g_i}\) , \(\tilde{g_i}(q)=f_i*{q^{\prime }}\) , where \(q^{\prime }\)  is the projection of \(q\)  onto \(S_{\epsilon }\) . By the choice of \(S_{\epsilon }\)  we have \(||q-q^{\prime }||\le \epsilon ^2\) . Therefore, the change in \(f_i\)  between \(q\)  and \(q^{\prime }\)  is at most (for small enough \(\epsilon \) ):
\(k*{\epsilon ^2\ln \epsilon ^2}=O*{\epsilon ^2*{\ln \epsilon }}=o*{\epsilon },\) 
so \(*{f_i(q)-\tilde{g_i}(q)}=*{f_i(q)-f_i*{q^{\prime }}}=o*{\epsilon }\) . Thus, \(f_i\)  indeed satisfies Assumption REF  with \(t*{\frac{1}{\epsilon }}:=\frac{1}{\epsilon }\) , as desired.
We proved that \(u_s\)  and the constraints satisfy Assumptions REF  and REF  with \(t*{\frac{1}{\epsilon }}:=\frac{1}{\epsilon }\) ; thus, Theorem REF , part 1 follows from Lemma REF .

[Proof of Theorem REF , part 2]
Fix a constant \(\epsilon >0\) . If \(u_s\)  is piecewise constant, with a constant number of pieces, s.t. each piece covers a convex polygon in \(\Delta *{\Omega }\)  having a constant vertex number – it satisfies Assumption REF  with \(t*{\frac{1}{\epsilon }}:= 1\) : to define \(u_{\epsilon ,M}\) , one can just refine the pieces of \(u_s\)  by division to simplices of diameters at most \(\frac{\epsilon }{M}\) . If \(u_s\)  is continuous, then from the compactness of \(\Delta *{\Omega }\)  and the Heine–Cantor theorem, we get that \(u_s\)  is uniformly continuous. Therefore, \(u_s\)  satisfies Assumption REF  with \(t*{\frac{1}{\epsilon }}:= 1\) : to define \(u_{\epsilon ,M}\) , one can divide \(\Delta *{\Omega }\)  to simplices of small enough diameters; then one should define \(u_{\epsilon ,M}\)  on every such simplex to be the supremum of \(u_s\)  on it.
Furthermore, each ex ante constraint satisfies Assumption REF  with \(t*{\frac{1}{\epsilon }}:= 1\) . Indeed, given a continuous \(f_i\) , the compactness of \(\Delta *{\Omega }\)  and the Heine–Cantor theorem implies that \(f_i\)  is uniformly continuous. To define \(g_i\) , one should divide \(\Delta *{\Omega }\)  to simplices of small enough diameter; then one should temporarily set \(g_i\equiv f_i\)  on the vertices of the simplices and extend \(g_i\)  linearly on each simplex; finally, one should slightly shift down \(g_i\)  so that it is never above \(f_i\) .
Therefore, \(u_s\)  and the constraints satisfy Assumptions REF  and REF  with \(t*{\frac{1}{\epsilon }}:= 1\) ; hence, Theorem REF , part 2 follows from Lemma REF .

Proposition REF  – Proof and Similar Results
In this appendix, we formulate and prove the technical Lemma REF ; we use it to prove Proposition REF  and to demonstrate analogous results for other auction settings, including revenue maximization in single-item, second-price auctions and welfare maximization in sponsored search (slot) auctions.
Lemma D.1 
Fix \(1\le j\le n\)  and \(n\)  linear functions \(g_1,...,g_n: \Delta *{\Omega }\rightarrow \mathbb {R}_{\ge 0}\) . Define \(g^j:\Delta *{\Omega }\rightarrow \mathbb {R}_{\ge 0}\)  by setting \({g}^{j}*{y}\) , for every \(y\in \Delta *{\Omega }\) , to be the \(j\) -th maximal number among \(g_1*{y},...,g_n*{y}\) . Then \(g^j\)  satisfies Assumption REF  with \(M=2\) .

Fix \(y,z\in \Delta *{\Omega }\)  and \(\lambda \in [0,1]\) . We have to prove:
\(\lambda g^j*{y} +(1-\lambda ) g^j*{z}\le 2 g^j*{\lambda y +(1-\lambda ) z}.\) 
Assume w.l.o.g. that \(\lambda g^j*{y}\ge (1-\lambda ) g^j*{z}\)  and that \(g_1*{y}\ge g_2*{y}\ge ...\ge g_n*{y}\) . Then we get:
\(&\lambda g^j*{y} +(1-\lambda ) g^j*{z}\le 2\lambda g^j*{y}=2\lambda g_j (y)=2\lambda \min _{1\le i\le j}*{g_i (y)}\le 2\min _{1\le i\le j}*{\lambda g_i (y)+ (1-\lambda )g_i (z)}=_{*{*}}\\&2\min _{1\le i\le j}*{g_i*{\lambda y +(1-\lambda ) z}}\le 2 g^j*{\lambda y +(1-\lambda ) z},\) 

where \(*{*}\)  follows from the linearity of the \(g_i\) s.

Now we prove – using Lemma REF  – Proposition REF  and discuss analogous results for other auction settings.
[Proof of Proposition REF ]
Note that \(u_s\)  is an expectation of maximum of linear nonnegative functions. By Lemma REF , every term in the expectation satisfies Assumption REF  with \(M=2\) ; thus, the same holds for the expectation.

Similar results. The applications of Theorem REF  go beyond the setting from Section , which was chosen for the sake of simplicity. In particular, the revenue in single-item, second-price auctions and the welfare in sponsored search (slot) auctions are also expectations of certain linear combinations of functions of the form \(g^j\)  as described in Lemma REF . Therefore, they too satisfy Assumption REF  with \(M=2\) .

Proof of Proposition  REF

Fix \(m\)  and \(k=2^m\) . We shall show that the analysis from Section  is tight for \(M=2\) .
Take \(\Omega :=*{0,1}^m\)  and \(u_s*{p_{\sigma }}:=||p_{\sigma }||_{\infty }\) ; let \(p\)  be uniform over \(\Omega \) . By Lemma REF  (with \(j=1\)  and \(g_{\omega _0}:=p_{\sigma }*{\omega =\omega _0}\)  for every \(\omega _0\in \Omega \) ), \(u_s\)  satisfies Assumption REF  with \(M=2\) . Define for every \(1\le i\le m\) : \(f_i*{p_{\sigma }}:=p_{\sigma }*{\omega _i=1}=\sum _{\omega ^{\prime }=*{\omega ^{\prime }_1,...,\omega ^{\prime }_m}\in \Omega : \omega ^{\prime }_i=1} p_{\sigma }*{\omega =\omega ^{\prime }}\)  and \(c_i:=\frac{1}{2}\) . For every \(p_{\sigma }\in \Delta *{\Omega }\) , denote by \(R*{p_{\sigma },i}\)  the posterior obtained from \(p_{\sigma }\)  by assigning to each \(\omega ^{\prime }\in \Omega \)  the probability assigned by \(p_{\sigma }\)  to the state of nature obtained from \(\omega ^{\prime }\)  by reversing its \(i\) -th bit.
Consider the following \(m\)  runs of Algorithm  for the \(m\)  constraints. Start with \(\Sigma \)  representing full revelation (which is valid under the ex ante constraints specified by the \(f_i\) s and the \(c_i\) s). Then on the \(i\) -th run of Algorithm , pool every posterior \(p_{\sigma }\)  with \(R*{p_{\sigma },i}\) .
Inductively, just before two posteriors are pooled together, they have equal probability weights in the signaling scheme; therefore, their probability weights are moved entirely to the new posterior that the pooling creates. Note that for every \(1\le i\le m\) , the \(i\) -th run of Algorithm  is legal, since it only pools posteriors having \(f_i=0\)  with posteriors having \(f_i=1\) ; furthermore, at the end of the \(i\) -th run, all the posteriors in \({\mathrm {supp}}*{\Sigma }\)  have \(f_i=\frac{1}{2}\) . Moreover, inductively, at the end of the \(i\) -th run, every posterior in \({\mathrm {supp}}*{\Sigma }\)  specifies deterministically the last \(m-i\)  bits of \(\omega \)  and induces a uniform distribution on \(*{0,1}^i\)  for the prefix of length \(i\)  of \(\omega \) .
Therefore, after the \(m\) -th run, we end with \({\mathrm {supp}}*{\Sigma }=\lbrace p\rbrace \)  (i.e., the no revelation policy), yielding expected Sender's utility of \(\frac{1}{k}\) . We started with the full revelation policy, yielding utility of 1; thus, the total multiplicative utility loss is \(k=2^m=M^m\) .

Assume that \(m=1\)  and fix \(M\ge 1\) . We shall define \(u_s\)  satisfying Assumption REF  with \(M\)  and an ex ante constraint outperforming the corresponding ex post constraint by a multiplicative factor of \(M\) .
Take: \(\Omega :=*{0,1}\) ; \(p\)  uniform over \(\Omega \) ; \(f:=p_{\sigma }*{\omega =1}\) ; \(c:=\frac{1}{2}\) ; and \(u_s*{p_{\sigma }}:=\frac{1}{M}+\\*{p_{\sigma }*{\omega =1}-\frac{1}{2}}\cdot \frac{2*{M-1}}{M}\) .
Then \(u_s*{p_{\sigma }}\in *{\frac{1}{M},1}\)  for every \(p_{\sigma }\in \Delta *{\Omega }\) ; thus, \(u_s\)  satisfies Assumption REF  with \(M\) . Furthermore, \(f\)  is linear, thus convex. Under the ex post constraint specified by \(f\)  and \(c\) , the only valid signaling scheme has support \(\lbrace p\rbrace \) ; hence, the optimal expected Sender's utility is \(\frac{1}{M}\) ; the corresponding ex ante constraint allows full revelation, which yields expected Sender's utility of 1. Therefore, we have a multiplicative gap of \(M\)  between the two constraint types.

Fix \(m\)  and \(k=m+1\) . We shall prove that the multiplicative gap between ex ante and ex post constraints can be \(m+1\)  for \(M=2\) .
Take \(\Omega :=*{1,...,k}\)  with \(p\)  uniform on \(\Omega \) ; set \(u_s*{p_{\sigma }}:=||p_{\sigma }||_{\infty }\) , \(f_i:=p_{\sigma }*{\omega =i}\)  and \(c_i:=\frac{1}{k}\)  (\(1\le i\le m\) ). As explained in our proof of part 1, \(u_s\)  satisfies Assumption REF  with \(M=2\) .
On the one hand, for the ex post constraints specified by the \(f_i\) s and the \(c_i\) s, the only valid signaling scheme has support \(\lbrace p\rbrace \) , yielding expected Sender's utility of \(\frac{1}{k}\) . On the other hand, the corresponding ex ante constraints allow full revelation, yielding utility of 1. Thus, we get a multiplicative gap of \(k=m+1\) .

