System and method for generating a maximum utility slate of advertisements for online advertisement auctions
An improved system and method for generating a maximum utility slate of advertisements for online advertisement auctions is provided. Various utility factors for each advertisement that may be a candidate in a slate of advertisements may be applied within a framework in order to generate a maximum utility slate of advertisements. Either backward or forward dynamic programming may be applied to recursively evaluate the utility of subslates of advertisements in order to generate a maximum utility slate of advertisements. In an embodiment, a network with directed edges and associated costs may be defined, and the longest path may be found in the directed network for constructing a maximum utility slate of advertisements. Various utility factors may be applied for different objectives of an auctioneer and the framework presented may be extended for revenue ordering, exclusion of bidders, ordering slates according to first and second price utilities, and so forth.
1. A computer system for providing online advertisements, comprising:
a server comprising a processor device, an input/output interface, and memory, said server configured to perform:
receiving a query comprising a keyword;
obtaining from a data store:
bids from bidders in an online advertising auction, said bids for displaying advertisements, wherein said bidders are associated with the keyword;
click-through rates for advertisement positions on a web page; and
utility factors associated with the advertisement positions in a slate of advertisements;
using dynamic programming to recursively evaluate a utility of subslates of the advertisements in order to generate a maximum utility slate of the advertisements for the keyword, using a plurality of the bids, a plurality of the click-through rates, and a plurality of the utility factors;
wherein the maximum utility slate of the advertisements comprises a maximum number m of advertisement positions;
placing the advertisements from the bidders in the advertisement positions within the slate of advertisements;
padding any empty positions at an end of the slate of advertisements with dummy bidders to produce the maximum utility slate with exactly the maximum number m of the advertisement positions;
initializing the bids of the dummy bidders to a minimum bid amount;
initializing the utility factor of each dummy bidder to zero; and
outputting the maximum utility slate of advertisements; and
an advertisement store storing the slate of advertisements for the online advertising auction.
2. The system of claim 1 wherein the dynamic programming analysis engine further comprises an operably coupled backward analysis engine for performing dynamic programming using a backward recursive evaluation of the utility of subslates of advertisements.
3. The system of claim 1 wherein the dynamic programming analysis engine further comprises an operably coupled forward analysis engine for performing dynamic programming using a forward recursive evaluation of the utility of subslates of advertisements.
4. A computer-implemented method for providing online advertisements, comprising:
using an input/output interface receiving a query comprising a keyword;
obtaining from a data store:
bids of bidders in an online advertising auction, said bids for displaying advertisements, wherein said bidders are associated with the keyword;
click-through rates for advertisement positions on a web page; and
utility factors, each utility factor associated with a position of an advertisement in a slate of advertisements, wherein the slate of advertisements comprises an ordered list of advertisements;
generating, by a processor device, a maximum utility slate of the advertisements for the keyword, using a plurality of the bids, a plurality of click-through rates, and a plurality of the utility factors;
wherein the maximum utility slate of the advertisements comprises a maximum number m of advertisement positions;
placing the advertisements from the bidders in the advertisement positions within the slate of advertisements;
padding any empty positions at an end of the slate of advertisements with dummy bidders to produce the maximum utility slate with exactly the maximum number m of the advertisement positions;
initializing the bids of the dummy bidders to a minimum bid amount;
initializing the utility factor of each dummy bidder to zero;
determining the maximum utility slate of advertisements by applying dynamic programming to recursively evaluate the utility of subslates of advertisements in order to generate a maximum utility slate of advertisements; and
outputting the maximum utility slate of advertisements for the online advertising auction.
5. The method of claim 4 wherein applying dynamic programming to recursively evaluate the utility of subslates of advertisements in order to generate the maximum utility slate of advertisements comprises:
applying backward dynamic programming to recursively evaluate the utility of a set of subslates of advertisements; and
selecting a sub slate of advertisements with the maximum utility from the set of subslates of advertisements.
6. The method of claim 4 wherein applying dynamic programming to recursively evaluate the utility of subslates of advertisements in order to generate a the maximum utility slate of advertisements comprises applying forward dynamic programming to find a longest path from a node of origin to a terminal node within a directed network of nodes representing bidder and ad positions.
7. The method of claim 6 wherein applying forward dynamic programming to find a longest path from a node of origin to a terminal node within a directed network of nodes representing bidder and ad positions comprises steps of:
determining the directed network of nodes representing bidder and ad positions;
defining directed edges connecting the nodes of the directed network; and
assigning costs for defined directed edges, each cost representing a product of a utility factor, a click-through rate and a bid of a bidder.
8. The method of claim 7 wherein a utility factor comprises a weighted sum of a value of a first price utility and a value of a second price utility.
9. The method of claim 4 wherein each utility factor comprises a value representing ad fatigue.
10. The method of claim 4 wherein each utility factor comprises a value representing expected revenue.
11. The method of claim 4 wherein each utility factor comprises a value representing usage of a bidder's budget.
12. The method of claim 4 wherein determining the maximum utility slate of advertisements comprises using a plurality of quality scores.
13. The method of claim 12 further comprising obtaining the plurality of the quality scores for advertisements, each quality score representing a ratio of a first bid term and a second bid term.
14. A non-transitory computer-readable medium having computer-executable instructions for performing steps of:
receiving a query comprising a keyword;
obtaining from a data store:
bids from bidders in an online advertising auction, said bids for displaying advertisements, wherein said bidders are associated with the keyword;
click-through rates for advertisement positions on a web page; and
utility factors associated with the advertisement positions in a slate of advertisements;
using dynamic programming to recursively evaluate a utility of subslates of the advertisements in order to generate a maximum utility slate of the advertisements for the keyword, using a plurality of the bids, a plurality of the click-through rates, and a plurality of the utility factors;
wherein the maximum utility slate of the advertisements comprises a maximum number m of advertisement positions;
placing the advertisements from the bidders in the advertisement positions within the slate of advertisements;
padding any empty positions at an end of the slate of advertisements with dummy bidders to produce the maximum utility slate with exactly the maximum number m of the advertisement positions;
initializing the bids of the dummy bidders to a minimum bid amount;
initializing the utility factor of each dummy bidder to zero; and
outputting the maximum utility slate of advertisements; and
an advertisement store storing the slate of advertisements for the online advertising auction.