  We study signaling in Bayesian ad auctions, in which bidders' valuations
depend on a random, unknown state of nature. The auction mechanism has complete
knowledge of the actual state of nature, and it can send signals to bidders so
as to disclose information about the state and increase revenue. For instance,
a state may collectively encode some features of the user that are known to the
mechanism only, since the latter has access to data sources unaccessible to the
bidders. We study the problem of computing how the mechanism should send
signals to bidders in order to maximize revenue. While this problem has already
been addressed in the easier setting of second-price auctions, to the best of
our knowledge, our work is the first to explore ad auctions with more than one
slot. In this paper, we focus on public signaling and VCG mechanisms, under
which bidders truthfully report their valuations. We start with a negative
result, showing that, in general, the problem does not admit a PTAS unless P =
NP, even when bidders' valuations are known to the mechanism. The rest of the
paper is devoted to settings in which such negative result can be circumvented.
First, we prove that, with known valuations, the problem can indeed be solved
in polynomial time when either the number of states d or the number of slots m
is fixed. Moreover, in the same setting, we provide an FPTAS for the case in
which bidders are single minded, but d and m can be arbitrary. Then, we switch
to the random valuations setting, in which these are randomly drawn according
to some probability distribution. In this case, we show that the problem admits
an FPTAS, a PTAS, and a QPTAS, when, respectively, d is fixed, m is fixed, and
bidders' valuations are bounded away from zero.
