1. Field of the Invention
The present invention relates generally to inserting advertisements in web pages, or more generally any medium in which ad performance can be measured and quantified. In particular, the present invention is directed towards determining an optimal allocation of advertisements in response to specified objectives and constraints.
2. Description of the Related Art
Web site advertising has traditionally included a variety of models. In one model, known as an auction model, advertisers bid for space on a web site. In the auction model, an advertising space, also known in the art as an impression, is given to the highest bidder (or bidders). In another model, called a guarantee model, the site guarantees a certain number of impressions to an advertiser in exchange for a fixed fee. The guarantee model also supports additional arrangements—for example, a site can guarantee that an impression will receive a minimum number of clicks, or will result in a minimum number of transactions.
The number of impressions available on a site is known as the site's inventory. Inventory is traditionally hard to precisely measure because of difficulties in estimating site traffic, since the amount of traffic on a site can be highly variable, and hence the number of impressions available in the future is unknown. In addition, available inventory is hard to track because of the existence of guarantee-based contracts. Consider the following example, which illustrates the difficulty of tracking inventory. Assume that a site has five keywords in its inventory of slots to which impressions can be allocated. Assume also that the site charges an advertiser a first amount for each impression and a second amount for each click on that impression. Assume the following amounts for four clients:
Client A pays $0.25 for clicks on keywords 1, 2 and 3, and $0.05 for each displayed impression. Client 1 has been guaranteed 10,000 impressions.
Client B pays $0.35 for clicks on keywords 2, 3 and 4, and $0.10 for each displayed impression. Client 2 has been guaranteed 15,000 impressions.
Client C pays $0.85 for clicks on keywords 2 and 4, and $0.05 for each displayed impression. Client 3 has been guaranteed 5,000 impressions.
Client D pays $0.05 for clicks on keywords 1 and 3, and $0.02 for each impression. Client 4 has been guaranteed 15,000 impressions.
Now assume that a potential client, client E, is willing to pay $0.20 for clicks on keywords 1 and 5, and is willing to pay $0.02 for each impression. Client E demands a guarantee of 11,000 impressions. The site has estimated its inventory of keyword 5 at 6,000 impressions, and inventory of keyword 1 as 4,000 impressions.
To determine whether accepting the contract with client E is possible, the site operator must determine whether an additional 1,000 impressions can be delivered for keywords 1 and 5 by shifting the existing allocation of keywords and not violating any guarantees made to the other advertisers. As the number of advertisers, keywords and guarantees grows, this problem becomes increasingly complex. Accommodating even a single new advertiser may necessitate the rescheduling of hundreds or even thousands of other advertisers (and their associated creatives) due to a ripple effect caused by moving one advertiser's allocation, which then causes another advertiser's allocation to be moved, etc.
There is therefore a need in the art for an efficient way to allocate advertising impressions across a web site while maximizing revenue for the site and honoring guarantees made to advertisers.