Database Reference
In-Depth Information
8.4.2
Definition of the Adwords Problem
Of course, the decision regarding which ads to show must be made on-line. Thus, we are
only going to consider on-line algorithms for solving the
adwords problem
, which is as fol-
lows.
• Given:
(1) A set of bids by advertisers for search queries.
(2) A click-through rate for each advertiser-query pair.
(3) A budget for each advertiser. We shall assume budgets are for a month, although
any unit of time could be used.
(4) A limit on the number of ads to be displayed with each search query.
• Respond to each search query with a set of advertisers such that:
(1) The size of the set is no larger than the limit on the number of ads per query.
(2) Each advertiser has bid on the search query.
(3) Each advertiser has enough budget left to pay for the ad if it is clicked upon.
The
revenue
of a selection of ads is the total value of the ads selected, where the
value
of
an ad is the product of the bid and the click-through rate for the ad and query. The merit of
an on-line algorithm is the total revenue obtained over a month (the time unit over which
budgets are assumed to apply). We shall try to measure the competitive ratio for algorithms,
that is, the minimum total revenue for that algorithm, on any sequence of search queries,
divided by the revenue of the optimum off-line algorithm for the same sequence of search
queries.
8.4.3
The Greedy Approach to the Adwords Problem
Since only an on-line algorithm is suitable for the adwords problem, we should first exam-
ine the performance of the obvious greedy algorithm. We shall make a number of simplific-
ations to the environment; our purpose is to show eventually that there is a better algorithm
than the obvious greedy algorithm. The simplifications:
(a) There is one ad shown for each query.
(b) All advertisers have the same budget.
(c) All click-through rates are the same.
(d) All bids are either 0 or 1. Alternatively, we may assume that the value of each ad
(product of bid and click-through rate) is the same.
