Paper Info
Title
The adwords problem: online keyword matching with budgeted bidders under random permutations
Abstract
We consider the problem of a search engine trying to assign a sequence of search keywords to a set of competing bidders, each with a daily spending limit. The goal is to maximize the revenue generated by these keyword sales, bearing in mind that, as some bidders may eventually exceed their budget, not all keywords should be sold to the highest bidder. We assume that the sequence of keywords (or equivalently, of bids) is revealed on-line. Our concern will be the competitive ratio for this problem versus the off-line optimum. We extend the current literature on this problem by considering the setting where the keywords arrive in a random order. In this setting we are able to achieve a competitive ratio of 1-ε under some mild, but necessary, assumptions. In contrast, it is already known that when the keywords arrive in an adversarial order, the best competitive ratio is bounded away from 1. Our algorithm is motivated by PAC learning, and proceeds in two parts: a training phase, and an exploitation phase.
Year
DOI
Venue
2009
10.1145/1566374.1566384
EC
Keywords
Field
DocType
adwords problem,adversarial order,online keyword,exploitation phase,search keyword,competitive ratio,random permutation,current literature,random order,training phase,search engine,daily spending limit,pac learning,matching
Revenue,Mathematical economics,Mathematical optimization,Search engine,Computer science,Permutation,Random permutation,Artificial intelligence,Machine learning,Bounded function,Competitive analysis,Adversarial system
Conference
Citations 
PageRank 
References 
137
5.60
15
Authors
2
Search Limit
100137
Name
Order
Citations
PageRank
Nikhil R. Devanur1121795.84
Thomas P. Hayes265954.21