Public signaling in Vickrey-Clarke-Groves ad auctions

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 Thesis, 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 or the number of slots is fixed. Moreover, in the same setting, we provide an FPTAS for the case in which bidders are single minded, but the number of states of nature and the number of slots 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, the number of states of nature is fixed, the number of slots is fixed, and bidders' valuations are bounded away from zero.

In questa tesi si affronta lo studio di aste pubblicitarie Bayesiane, in cui le valutazioni degli offerenti dipendono da un stato di natura aleatorio. Il meccanismo dell'asta ha una conoscenza completa dello stato di natura reale e può inviare segnali agli offerenti in modo da rivelare parzialmente l'informazione su di esso e aumentare il proprio guadagno. Ad esempio, uno stato di natura può codificare alcune caratteristiche dell'utente che sono note solo al meccanismo, poiché quest'ultimo ha accesso a fonti di dati inaccessibili agli offerenti. In questa tesi si studia come un meccanismo d'asta debba inviare segnali agli offerenti al fine di massimizzare le proprie entrate. Mentre questo problema è già stato affrontato nel caso più semplice di aste second-price, al meglio della nostra conoscenza, in questa tesi si affronta per la prima volta il caso di aste pubblicitarie con più di un slot. In particolare, viene studiato il caso di uno schema di segnali pubblico e di un meccanismo VCG, in base ai quali gli offerenti riportano in modo veritiero le loro valutazioni. In primo luogo si dimostra che, in generale, il problema non ammette un PTAS a meno che P=NP, anche quando le valutazioni degli offerenti sono note al meccanismo. Per questo motivo, nel resto della tesi, vengono affrontati scenari in cui tale risultato negativo può essere aggirato. In primo luogo, si dimostra che, quando le valutazioni sono note al meccanismo, il problema può essere risolto in tempo polinomiale se il numero degli stati di natura o il numero di slots è fissato. Inoltre, nello stesso contesto, viene mostrata l'esistenza di un FPTAS per il caso in cui gli offerenti sono signle-minded, ma il numero di stati di natura e slots può essere arbitrariamente grande. Si passa poi al caso di valutazioni aleatorie, in cui queste sono estratte casualmente secondo una certa distribuzione di probabilità. In questo caso, si mostra che il problema ammette un FPTAS, un PTAS e un QPTAS, quando, rispettivamente, il numero di stati è fissato, il numero di slots è fissato e le valutazioni degli offerenti sono tutte maggiori di una certa quantità.