Article Preview
TopIntroduction
Internet search engine companies, such as Google, Yahoo! and Baidu, have revolutionized not only the use of the Internet by individuals but also the way that businesses advertise to consumers. Online advertising mechanisms used by search engines, such as Google’s AdWords, are essentially large auctions where businesses place bids for individual keywords, together with limits specifying their maximum daily budget. A search engine company earns revenue when it displays its ads in response to a relevant search query (if a user clicks on the ad). The process of online sponsored search auction is as shown in Figure 1.
Figure 1. The process of online sponsored search auction
Due to seeking profit essence, many enterprises bid for a good advertising position with a high price but sell inferior goods, so a lot of inferior advertisements are seen on the screen and the interests of the multiple customers are seriously harmed, which also effects the reputation and revenues of search engine companies. To improve the trustworthiness of advertiser and the ad quality, how to improve the auction mechanism becomes a very urgent problem to be solved in search engine companies. Obviously, if the correlation and credibility are high, then the internet users are more satisfied and they are more willing to click on the ads. In the long term, users tend to use this search engine, which will also bring more benefits to the search engine company.
The AdWords problem is a typical online advertising example. The Online allocation problem studied is proposed and analyzed by Mehta et al. (2005). Many advertisers compete to display their advertisements on a given web page which would result from a search query with in a search engine, or which would simply be known to attract traffic from internet users. An online advertising service aims at maximizing its revenue by choosing the best possible advertisement to display on a web page. The goal is to maximize the total revenue of all allocations. The bids of advertisers are different with limited budget. A question is how to maximize the benefits of search engines by AdWords online matching. The AdWords problem is described as follows: There are N bidders, each with a specified daily budget 
. 
is a set of query keywords. Each bidder 
specifies a bid 
for query word 
. A sequence 
of query words 
arrive online during the day, and each query 
must be assigned to some bidder 
(for a revenue of 
). The objective is to maximize the total revenue at the end of the day while respecting the daily budgets of the bidders.
Throughout this article, we will assume that each bid is smaller compared to the corresponding budget, that is, 
is smaller compared to 
for all 
. For the applications of this problem, it is a reasonable assumption.