Computer Science – Computer Science and Game Theory
Scientific paper
2008-05-08
Computer Science
Computer Science and Game Theory
10 pages, 1 figure
Scientific paper
Many advertisers buy advertisements (ads) on the Internet or on traditional media and seek simple, online mechanisms to reserve ad slots in advance. Media publishers represent a vast and varying inventory, and they too seek automatic, online mechanisms for pricing and allocating such reservations. In this paper, we present and study a simple model for auctioning such ad slots in advance. Bidders arrive sequentially and report which slots they are interested in. The seller must decide immediately whether or not to grant a reservation. Our model allows a seller to accept reservations, but possibly cancel the allocations later and pay the bidder a cancellation compensation (bump payment). Our main result is an online mechanism to derive prices and bump payments that is efficient to implement. This mechanism has many desirable properties. It is individually rational; winners have an incentive to be honest and bidding one's true value dominates any lower bid. Our mechanism's efficiency is within a constant fraction of the a posteriori optimally efficient solution. Its revenue is within a constant fraction of the a posteriori revenue of the Vickrey-Clarke-Groves mechanism. Our results make no assumptions about the order of arrival of bids or the value distribution of bidders and still hold if the items for sale are elements of a matroid, a more general setting than slot allocation.
Constantin Florin
Feldman Jon
Muthukrishnan Siddharth
Pal Martin
No associations
LandOfFree
Online Ad Slotting With Cancellations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Online Ad Slotting With Cancellations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Online Ad Slotting With Cancellations will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-53324