We study multiple keyword sponsored search auctions with budgets. Each keyword has multiple ad slots with a click-through rate. The bidders have additive valuations, which are linear in the click-through rates, and budgets, which are restricting their overall payments. Additionally, the number of slots per keyword assigned to a bidder is bounded. We show the following results: (1) We give the first mechanism for multiple keywords, where click-through rates differ among slots. Our mechanism is incentive compatible in expectation, individually rational in expectation, and Pareto optimal. (2) We study the combinatorial setting, where each bidder is only interested in a subset of the keywords. We give an incentive compatible, individually rational, Pareto optimal, and deterministic mechanism for identical click-through rates. (3) We give an impossibility result for incentive compatible, individually rational, Pareto optimal, and deterministic mechanisms for bidders with diminishing marginal valuations. © 2012 Springer-Verlag Berlin Heidelberg.

On multiple keyword sponsored search auctions with budgets / COLINI BALDESCHI, Riccardo; Monika, Henzinger; Leonardi, Stefano; Martin, Starnberger. - 7392 LNCS:PART 2(2012), pp. 1-12. (Intervento presentato al convegno 39th International Colloquium on Automata, Languages, and Programming, ICALP 2012 tenutosi a Warwick nel 9 July 2012 through 13 July 2012) [10.1007/978-3-642-31585-5-1].

On multiple keyword sponsored search auctions with budgets

COLINI BALDESCHI, RICCARDO;LEONARDI, Stefano;
2012

Abstract

We study multiple keyword sponsored search auctions with budgets. Each keyword has multiple ad slots with a click-through rate. The bidders have additive valuations, which are linear in the click-through rates, and budgets, which are restricting their overall payments. Additionally, the number of slots per keyword assigned to a bidder is bounded. We show the following results: (1) We give the first mechanism for multiple keywords, where click-through rates differ among slots. Our mechanism is incentive compatible in expectation, individually rational in expectation, and Pareto optimal. (2) We study the combinatorial setting, where each bidder is only interested in a subset of the keywords. We give an incentive compatible, individually rational, Pareto optimal, and deterministic mechanism for identical click-through rates. (3) We give an impossibility result for incentive compatible, individually rational, Pareto optimal, and deterministic mechanisms for bidders with diminishing marginal valuations. © 2012 Springer-Verlag Berlin Heidelberg.
2012
39th International Colloquium on Automata, Languages, and Programming, ICALP 2012
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
On multiple keyword sponsored search auctions with budgets / COLINI BALDESCHI, Riccardo; Monika, Henzinger; Leonardi, Stefano; Martin, Starnberger. - 7392 LNCS:PART 2(2012), pp. 1-12. (Intervento presentato al convegno 39th International Colloquium on Automata, Languages, and Programming, ICALP 2012 tenutosi a Warwick nel 9 July 2012 through 13 July 2012) [10.1007/978-3-642-31585-5-1].
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/480692
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 17
  • ???jsp.display-item.citation.isi??? 7
social impact