---
_id: '11795'
abstract:
- lang: eng
  text: "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.\r\n\r\nWe 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."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Riccardo
  full_name: Colini-Baldeschi, Riccardo
  last_name: Colini-Baldeschi
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Stefano
  full_name: Leonardi, Stefano
  last_name: Leonardi
- first_name: Martin
  full_name: Starnberger, Martin
  last_name: Starnberger
citation:
  ama: 'Colini-Baldeschi R, Henzinger MH, Leonardi S, Starnberger M. On multiple keyword
    sponsored search auctions with budgets. In: <i>39th International Colloquium on
    Automata, Languages, and Programming</i>. Vol 7392. Springer Nature; 2012:1–12.
    doi:<a href="https://doi.org/10.1007/978-3-642-31585-5_1">10.1007/978-3-642-31585-5_1</a>'
  apa: 'Colini-Baldeschi, R., Henzinger, M. H., Leonardi, S., &#38; Starnberger, M.
    (2012). On multiple keyword sponsored search auctions with budgets. In <i>39th
    International Colloquium on Automata, Languages, and Programming</i> (Vol. 7392,
    pp. 1–12). Warwick, United Kingdom: Springer Nature. <a href="https://doi.org/10.1007/978-3-642-31585-5_1">https://doi.org/10.1007/978-3-642-31585-5_1</a>'
  chicago: Colini-Baldeschi, Riccardo, Monika H Henzinger, Stefano Leonardi, and Martin
    Starnberger. “On Multiple Keyword Sponsored Search Auctions with Budgets.” In
    <i>39th International Colloquium on Automata, Languages, and Programming</i>,
    7392:1–12. Springer Nature, 2012. <a href="https://doi.org/10.1007/978-3-642-31585-5_1">https://doi.org/10.1007/978-3-642-31585-5_1</a>.
  ieee: R. Colini-Baldeschi, M. H. Henzinger, S. Leonardi, and M. Starnberger, “On
    multiple keyword sponsored search auctions with budgets,” in <i>39th International
    Colloquium on Automata, Languages, and Programming</i>, Warwick, United Kingdom,
    2012, vol. 7392, pp. 1–12.
  ista: 'Colini-Baldeschi R, Henzinger MH, Leonardi S, Starnberger M. 2012. On multiple
    keyword sponsored search auctions with budgets. 39th International Colloquium
    on Automata, Languages, and Programming. ICALP: International Colloquium on Automata,
    Languages, and Programming, LNCS, vol. 7392, 1–12.'
  mla: Colini-Baldeschi, Riccardo, et al. “On Multiple Keyword Sponsored Search Auctions
    with Budgets.” <i>39th International Colloquium on Automata, Languages, and Programming</i>,
    vol. 7392, Springer Nature, 2012, pp. 1–12, doi:<a href="https://doi.org/10.1007/978-3-642-31585-5_1">10.1007/978-3-642-31585-5_1</a>.
  short: R. Colini-Baldeschi, M.H. Henzinger, S. Leonardi, M. Starnberger, in:, 39th
    International Colloquium on Automata, Languages, and Programming, Springer Nature,
    2012, pp. 1–12.
conference:
  end_date: 2012-07-13
  location: Warwick, United Kingdom
  name: 'ICALP: International Colloquium on Automata, Languages, and Programming'
  start_date: 2012-07-09
date_created: 2022-08-11T11:46:51Z
date_published: 2012-07-01T00:00:00Z
date_updated: 2023-02-21T16:28:31Z
day: '01'
doi: 10.1007/978-3-642-31585-5_1
extern: '1'
intvolume: '      7392'
language:
- iso: eng
month: '07'
oa_version: None
page: 1–12
publication: 39th International Colloquium on Automata, Languages, and Programming
publication_identifier:
  isbn:
  - '9783642315848'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
  record:
  - id: '11795'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: On multiple keyword sponsored search auctions with budgets
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7392
year: '2012'
...