How does a search engine company like Google decide what ads to display with each query so as to maximize its revenue? This turns out to be a generalization of the online bipartite matching problem.
We here introduce the notion of a tradeoff revealing LP and use it to derive an optimal algorithm achieving a competitive ratio of 1 - 1/e for this problem.
Introduction
Internet search engine companies, such as Google, Yahoo and MSN, have revolutionized notonly the use of the Internet by individuals but also the way businesses advertise to consumers.Instead of flooding consumers with unwanted ads, search engines open up the possibility of a dialogue between consumers and businesses, with consumers typing in keywords, called Ad-words by Google, that reveal what they are looking for and search engines displaying highly targeted ads relevant to the specific query.
The AdWords market is essentially a large auction where businesses place bids for individual keywords, together with limits specifying their maximum daily budget. The search engine company earns revenue from businesses when it displays their ads in response to a relevant search query (if the user actually clicks on the ad). Indeed, most of the revenues of search engine companies are derived in this manner.
It is well known that Internet companies, such as Amazon and eBay, are able to open up new markets by tapping into the fat tails of distributions. This holds for search engine companies as well: The advertising budgets of companies and organizations follows a power law distribution, and unlike conventional advertising, search engine companies are able to cater to low budget advertisers on the fat tail of this distribution. This is partially responsible for their dramatic success.The following computational problem, which we call the Adwords problem, was posed to us by Henzinger : assign user queries to advertisers to maximize the total revenue. Observe that the task is necessarily online { when returning results of a specific query, the search engine company needs to immediately determine what ads to display on the side. The computational problem is specified as follows: each advertiser places bids on a number of keywords and specifies a maximum daily budget. As queries arrive during the day, they must be assigned to advertisers.
The objective is to maximize the total revenue while respecting the daily budgets.
This market dwarfs the AdSense market where the ad is based on the actual contents of the website.According to a recent New York Times article (Feb 4, 2005), the revenue accrued by Google from this market in the last three months of 2004 alone was over a billion dollars.
In this article, we present a deterministic algorithm achieving a competitive ratio of 1-1/e for this problem, under the assumption that bids are small compared to budgets. The algorithm is simple and time efficient.
No randomized algorithm can achieve a better competitive ratio, even under this assumption of small bids.
how this Ad word advertisement works for search engines and its algorithm and analysis can be generalized to the following more realistic situations while still maintaining the same competitive ratio:
Previous work
The adwords problem is clearly a generalization of the online bipartite matching problem: the special case where each advertiser makes unit bids and has a unit daily budget is precisely the online matching problem. Even in this special case, the greedy algorithm achieves a competitive ratio of 1/2. The algorithm that allocates each query to a random interested advertiser does not do much better { it achieves a competitive ratio of 1/2 + O(log n/n)}.
In [KVV90], Karp, Vazirani and Vazirani gave a randomized algorithm for the online matching problem achieving a competitive ratio of 1- 1/e. Their algorithm, called RANKING, fixes a random permutation of the bidders in advance and breaks ties according to their ranking in this permutation. They further showed that no randomized online algorithm can achieve a better competitive ratio.
In another direction, Kalyanasundaram and Pruhs [KP00] considered the online b-matching problem which can be described as a special case of the adwords problem as follows: each advertiser has a daily budget of b dollars, but makes only 0/1 dollar bids on each query. Their online algorithm, called BALANCE, awards the query to that interested advertiser who has the highest unspent budget. They show that the competitive ratio of this algorithm tends to 1- 1/e as b tends to infnity. They also prove a lower bound of
1 - 1/e for deterministic algorithms.
New idea
To generalize the algorithms of [KP00] to arbitrary bids, it is instructive to examine the special case with bids restricted to {0; 1; 2}. The natural algorithm to try assigns each query to a highest bidder, using the previous heuristic to break ties (largest remaining budget). We provide an example in the appendix to show that such an algorithm achieves a competitive ratios strictly smaller and bounded away from 1 - 1/e.
This indicates the need to consider a much more delicate tradeo between the bid versus unspent budget. The correct tradeo® function is derived by a novel LP-based approach, which we outline below. The resulting algorithm is very simple, and is based on the following tradeoff function:
The algorithm assumes that the daily budget of advertisers is large compared to their bids.
Subscribe for new innovation in this area.
We here introduce the notion of a tradeoff revealing LP and use it to derive an optimal algorithm achieving a competitive ratio of 1 - 1/e for this problem.
Introduction
Internet search engine companies, such as Google, Yahoo and MSN, have revolutionized notonly the use of the Internet by individuals but also the way businesses advertise to consumers.Instead of flooding consumers with unwanted ads, search engines open up the possibility of a dialogue between consumers and businesses, with consumers typing in keywords, called Ad-words by Google, that reveal what they are looking for and search engines displaying highly targeted ads relevant to the specific query.
The AdWords market is essentially a large auction where businesses place bids for individual keywords, together with limits specifying their maximum daily budget. The search engine company earns revenue from businesses when it displays their ads in response to a relevant search query (if the user actually clicks on the ad). Indeed, most of the revenues of search engine companies are derived in this manner.
It is well known that Internet companies, such as Amazon and eBay, are able to open up new markets by tapping into the fat tails of distributions. This holds for search engine companies as well: The advertising budgets of companies and organizations follows a power law distribution, and unlike conventional advertising, search engine companies are able to cater to low budget advertisers on the fat tail of this distribution. This is partially responsible for their dramatic success.The following computational problem, which we call the Adwords problem, was posed to us by Henzinger : assign user queries to advertisers to maximize the total revenue. Observe that the task is necessarily online { when returning results of a specific query, the search engine company needs to immediately determine what ads to display on the side. The computational problem is specified as follows: each advertiser places bids on a number of keywords and specifies a maximum daily budget. As queries arrive during the day, they must be assigned to advertisers.
The objective is to maximize the total revenue while respecting the daily budgets.
This market dwarfs the AdSense market where the ad is based on the actual contents of the website.According to a recent New York Times article (Feb 4, 2005), the revenue accrued by Google from this market in the last three months of 2004 alone was over a billion dollars.
In this article, we present a deterministic algorithm achieving a competitive ratio of 1-1/e for this problem, under the assumption that bids are small compared to budgets. The algorithm is simple and time efficient.
No randomized algorithm can achieve a better competitive ratio, even under this assumption of small bids.
how this Ad word advertisement works for search engines and its algorithm and analysis can be generalized to the following more realistic situations while still maintaining the same competitive ratio:
- A bidder pays only if the user clicks on his ad.
- Advertisers have different daily budgets.
- Instead of charging a bidder his actual bid, the search engine company charges him the next highest bid.
- Multiple ads can appear with the results of a query.
- Advertisers enter at different times.
Previous work
The adwords problem is clearly a generalization of the online bipartite matching problem: the special case where each advertiser makes unit bids and has a unit daily budget is precisely the online matching problem. Even in this special case, the greedy algorithm achieves a competitive ratio of 1/2. The algorithm that allocates each query to a random interested advertiser does not do much better { it achieves a competitive ratio of 1/2 + O(log n/n)}.
In [KVV90], Karp, Vazirani and Vazirani gave a randomized algorithm for the online matching problem achieving a competitive ratio of 1- 1/e. Their algorithm, called RANKING, fixes a random permutation of the bidders in advance and breaks ties according to their ranking in this permutation. They further showed that no randomized online algorithm can achieve a better competitive ratio.
In another direction, Kalyanasundaram and Pruhs [KP00] considered the online b-matching problem which can be described as a special case of the adwords problem as follows: each advertiser has a daily budget of b dollars, but makes only 0/1 dollar bids on each query. Their online algorithm, called BALANCE, awards the query to that interested advertiser who has the highest unspent budget. They show that the competitive ratio of this algorithm tends to 1- 1/e as b tends to infnity. They also prove a lower bound of
1 - 1/e for deterministic algorithms.
New idea
To generalize the algorithms of [KP00] to arbitrary bids, it is instructive to examine the special case with bids restricted to {0; 1; 2}. The natural algorithm to try assigns each query to a highest bidder, using the previous heuristic to break ties (largest remaining budget). We provide an example in the appendix to show that such an algorithm achieves a competitive ratios strictly smaller and bounded away from 1 - 1/e.
This indicates the need to consider a much more delicate tradeo between the bid versus unspent budget. The correct tradeo® function is derived by a novel LP-based approach, which we outline below. The resulting algorithm is very simple, and is based on the following tradeoff function:
The algorithm assumes that the daily budget of advertisers is large compared to their bids.
Subscribe for new innovation in this area.
No comments:
Post a Comment