Convergence analysis for sponsored search auctions with price displaying

Since the early 2000’s online advertising has become one of the main revenue sources for companies, which have been using it to advertise their content and sponsor their goods. One of the main application fields for online advertising is search advertising, where the search engines submit to their users some sponsored contents next to the organic results. The way in which the displayed advertisements are selected is through a suitable auction mechanism. Mechanism design is a well studied sub field of game theory, and the problem of auctioneer’s mechanism selection and advertisers’ bidding strategy have a solid base in literature. However, very few studies have analyzed auctions in the context of e-commerce, namely sponsored auction with price display, where advertisements are associated to a price for the sponsored good and customers’ clicks are influenced by the comparison of those selling prices. In this work, we initially formalize the extension of a well known bidding strategy for the generalized second price auction, the balance bidding, to the scenario with price displaying. Our main result consists in the proposal of a new auction mechanism based on GSP that is guaranteed to converge to its equilibrium if advertisers bid according to the extended bidding strategy when prices are fixed. We also study the efficiency of the equilibrium with respect to a parameter of the mechanism called cut price, proposing a randomized algorithm that guarantees a lower bound of the equilibria social welfare in expectation. Lastly, we provide some experimental results, in order to empirically analyze the average convergence time and the average efficiency for different auction settings.

Sin dai primi anni 2000 la pubblicità online è diventata una delle maggiori fonti di guadagno per le aziende, che la utilizzano per sponsorizzare i loro contenuti e vedere i loro prodotti. Uno dei suoi maggiori campi di applicazione risiede nella pubblicità per motori di ricerca, dove i motori di ricerca mostrano agli utenti contenuti sponsorizzati assieme ai contenuti organici. Il modo in cui i contenuti pubblicitari vengono selezionati consiste nell’applicazione di un meccanismo di asta appropriato. La progettazione di meccanismi di asta è una branca della teoria dei giochi molto studiata, e sia il problema di implementazione di questi meccanismi da parte del venditore che lo studio di strategie di offerta da parte dei partecipanti all’asta sono problemi che trovano una base solida in letteratura. Tuttavia, pochi studi analizzano le aste nel contesto della vendita online, dove gli annunci sono associati a un prezzo di vendita e i click sono influenzati dal confronto degli utenti tra i prezzi stessi. In questo lavoro, formalizziamo inizialmente l’estensione di una nota strategia di offerta per meccanismi GSP, chiamata balance bidding, allo scenario in cui sono presenti i prezzi di vendita. Successivamente, il nostro risultato più significativo consiste nella proposta di un nuovo meccanismo di asta basato su GSP che fornisce garanzie di convergenza quando gli inserzionisti adottano la strategia di offerta descritta e i prezzi di vendita sono fissi. Studiamo inoltre la l’efficienza dell’equilibrio raggiunto, in relazione ad un parametro del meccanismo chiamato prezzo di taglio, proponendo un algoritmo randomizzato che garantisce un benessere sociale minimo atteso all’equilibrio. Per concludere, forniamo alcuni risultati sperimentali per analizzare empiricamente il tempo di convergenza del meccanismo e l’efficienza dell’equilibrio in relazione a diversi parametri dell’asta.