TY - GEN

T1 - Selling ad campaigns

T2 - 2009 ACM Conference on Electronic Commerce, EC'09

AU - Babaioff, Moshe

AU - Hartline, Jason D

AU - Kleinberg, Robert D.

PY - 2009/12/1

Y1 - 2009/12/1

N2 - We study online pricing problems in markets with cancellations, i.e., markets in which prior allocation decisions can be revoked, but at a cost. In our model, a seller receives requests online and chooses which requests to accept, subject to constraints on the subsets of requests which may be accepted simultaneously. A request, once accepted, can be canceled at a cost which is a fixed fraction of the request value. This scenario models a market for web advertising campaigns, in which the buyback cost represents the cost of canceling an existing contract. We analyze a simple constant-competitive algorithm for a single-item auction in this model, and we prove that its competitive ratio is optimal among deterministic algorithms, but that the competitive ratio can be improved using a randomized algorithm. We then model ad campaigns using knapsack domains, in which the requests differ in size as well as in value. We give a deterministic online algorithm that achieves a bi-criterion approximation in which both approximation factors approach 1 as the buyback factor and the size of the maximum request approach 0. We show that the bi-criterion approximation is unavoidable for deterministic algorithms, but that a randomized algorithm is capable of achieving a constant competitive ratio. Finally, we discuss an extension of our randomized algorithm to matroid domains (in which the sets of simultaneously satisfiable requests constitute the independent sets of a matroid) as well as present results for domains in which the buyback factor of different requests varies.

AB - We study online pricing problems in markets with cancellations, i.e., markets in which prior allocation decisions can be revoked, but at a cost. In our model, a seller receives requests online and chooses which requests to accept, subject to constraints on the subsets of requests which may be accepted simultaneously. A request, once accepted, can be canceled at a cost which is a fixed fraction of the request value. This scenario models a market for web advertising campaigns, in which the buyback cost represents the cost of canceling an existing contract. We analyze a simple constant-competitive algorithm for a single-item auction in this model, and we prove that its competitive ratio is optimal among deterministic algorithms, but that the competitive ratio can be improved using a randomized algorithm. We then model ad campaigns using knapsack domains, in which the requests differ in size as well as in value. We give a deterministic online algorithm that achieves a bi-criterion approximation in which both approximation factors approach 1 as the buyback factor and the size of the maximum request approach 0. We show that the bi-criterion approximation is unavoidable for deterministic algorithms, but that a randomized algorithm is capable of achieving a constant competitive ratio. Finally, we discuss an extension of our randomized algorithm to matroid domains (in which the sets of simultaneously satisfiable requests constitute the independent sets of a matroid) as well as present results for domains in which the buyback factor of different requests varies.

KW - Costly decision revocation

KW - Knapsack

KW - Matroids

KW - Online algorithms

KW - Selling advertisements

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

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

U2 - 10.1145/1566374.1566383

DO - 10.1145/1566374.1566383

M3 - Conference contribution

AN - SCOPUS:77950584430

SN - 9781605584584

T3 - Proceedings of the ACM Conference on Electronic Commerce

SP - 61

EP - 70

BT - EC'09 - Proceedings of the 2009 ACM Conference on Electronic Commerce

Y2 - 6 July 2009 through 10 July 2009

ER -