A truthful mechanism for offline ad slot scheduling

Jon Feldman; S. Muthukrishnan; Evdokia Nikolova; Martin Pál

doi:10.1007/978-3-540-79309-0_17

A truthful mechanism for offline ad slot scheduling

Jon Feldman, S. Muthukrishnan, Evdokia Nikolova, Martin Pál

School of Arts and Sciences, Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

17 Scopus citations

Abstract

We consider the Offline Ad Slot Scheduling problem, where advertisers must be scheduled to sponsored search slots during a given period of time. Advertisers specify a budget constraint, as well as a maximum cost per click, and may not be assigned to more than one slot for a particular search. We give a truthful mechanism under the utility model where bidders try to maximize their clicks, subject to their personal constraints. In addition, we show that the revenue-maximizing mechanism is not truthful, but has a Nash equilibrium whose outcome is identical to our mechanism. Our mechanism employs a descending-price auction that maintains a solution to a certain machine scheduling problem whose job lengths depend on the price, and hence are variable over the auction.

Original language	English (US)
Title of host publication	Algorithmic Game Theory - First International Symposium, SAGT 2008, Proceedings
Pages	182-193
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-540-79309-0_17
State	Published - 2008
Event	1st International Symposium on Algorithmic Game Theory, SAGT 2008 - Paderborn, Germany Duration: Apr 30 2008 → May 2 2008

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4997 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	1st International Symposium on Algorithmic Game Theory, SAGT 2008
Country/Territory	Germany
City	Paderborn
Period	4/30/08 → 5/2/08

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-540-79309-0_17

Cite this

Feldman, J., Muthukrishnan, S., Nikolova, E., & Pál, M. (2008). A truthful mechanism for offline ad slot scheduling. In Algorithmic Game Theory - First International Symposium, SAGT 2008, Proceedings (pp. 182-193). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4997 LNCS). https://doi.org/10.1007/978-3-540-79309-0_17

@inproceedings{67fe5a31e0ae45b6bb2de147e4fec6a5,

title = "A truthful mechanism for offline ad slot scheduling",

abstract = "We consider the Offline Ad Slot Scheduling problem, where advertisers must be scheduled to sponsored search slots during a given period of time. Advertisers specify a budget constraint, as well as a maximum cost per click, and may not be assigned to more than one slot for a particular search. We give a truthful mechanism under the utility model where bidders try to maximize their clicks, subject to their personal constraints. In addition, we show that the revenue-maximizing mechanism is not truthful, but has a Nash equilibrium whose outcome is identical to our mechanism. Our mechanism employs a descending-price auction that maintains a solution to a certain machine scheduling problem whose job lengths depend on the price, and hence are variable over the auction.",

author = "Jon Feldman and S. Muthukrishnan and Evdokia Nikolova and Martin P{\'a}l",

year = "2008",

doi = "10.1007/978-3-540-79309-0_17",

language = "English (US)",

isbn = "3540793089",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "182--193",

booktitle = "Algorithmic Game Theory - First International Symposium, SAGT 2008, Proceedings",

note = "1st International Symposium on Algorithmic Game Theory, SAGT 2008 ; Conference date: 30-04-2008 Through 02-05-2008",

}

Feldman, J, Muthukrishnan, S, Nikolova, E & Pál, M 2008, A truthful mechanism for offline ad slot scheduling. in Algorithmic Game Theory - First International Symposium, SAGT 2008, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4997 LNCS, pp. 182-193, 1st International Symposium on Algorithmic Game Theory, SAGT 2008, Paderborn, Germany, 4/30/08. https://doi.org/10.1007/978-3-540-79309-0_17

A truthful mechanism for offline ad slot scheduling. / Feldman, Jon; Muthukrishnan, S.; Nikolova, Evdokia et al.
Algorithmic Game Theory - First International Symposium, SAGT 2008, Proceedings. 2008. p. 182-193 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4997 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - A truthful mechanism for offline ad slot scheduling

AU - Feldman, Jon

AU - Muthukrishnan, S.

AU - Nikolova, Evdokia

AU - Pál, Martin

PY - 2008

Y1 - 2008

N2 - We consider the Offline Ad Slot Scheduling problem, where advertisers must be scheduled to sponsored search slots during a given period of time. Advertisers specify a budget constraint, as well as a maximum cost per click, and may not be assigned to more than one slot for a particular search. We give a truthful mechanism under the utility model where bidders try to maximize their clicks, subject to their personal constraints. In addition, we show that the revenue-maximizing mechanism is not truthful, but has a Nash equilibrium whose outcome is identical to our mechanism. Our mechanism employs a descending-price auction that maintains a solution to a certain machine scheduling problem whose job lengths depend on the price, and hence are variable over the auction.

AB - We consider the Offline Ad Slot Scheduling problem, where advertisers must be scheduled to sponsored search slots during a given period of time. Advertisers specify a budget constraint, as well as a maximum cost per click, and may not be assigned to more than one slot for a particular search. We give a truthful mechanism under the utility model where bidders try to maximize their clicks, subject to their personal constraints. In addition, we show that the revenue-maximizing mechanism is not truthful, but has a Nash equilibrium whose outcome is identical to our mechanism. Our mechanism employs a descending-price auction that maintains a solution to a certain machine scheduling problem whose job lengths depend on the price, and hence are variable over the auction.

UR - http://www.scopus.com/inward/record.url?scp=44449101637&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=44449101637&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-79309-0_17

DO - 10.1007/978-3-540-79309-0_17

M3 - Conference contribution

AN - SCOPUS:44449101637

SN - 3540793089

SN - 9783540793083

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 182

EP - 193

BT - Algorithmic Game Theory - First International Symposium, SAGT 2008, Proceedings

T2 - 1st International Symposium on Algorithmic Game Theory, SAGT 2008

Y2 - 30 April 2008 through 2 May 2008

ER -

Feldman J, Muthukrishnan S, Nikolova E, Pál M. A truthful mechanism for offline ad slot scheduling. In Algorithmic Game Theory - First International Symposium, SAGT 2008, Proceedings. 2008. p. 182-193. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-79309-0_17

A truthful mechanism for offline ad slot scheduling

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this