System and method for optimizing the reserve price and allocation of web page placements in an online keyword auction using generalized trade reduction

• US 20090150278A1
• Filed: 12/10/2007
• Published: 06/11/2009
• Est. Priority Date: 12/10/2007
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Gonen, Rica
• Granted Patent: US 7,860,754 B2
• Time in Patent Office: Days
• US Class Current: 705/37
• CPC Class Codes: G06Q 30/00 Commerce
• CPC Class Codes: G06Q 30/0633 Lists, e.g. purchase orders, compilation or processing
• CPC Class Codes: G06Q 40/04 Trading; Exchange, e.g. stocks, commodities, derivatives or currency exchange

Abstract

An improved system and method is provided for optimizing the reserve price and allocation of web page placements in an online keyword auction using generalized trade reduction. To do so, a generalized trade reduction engine may be provided to convert an implementation of an online keyword auction into a double-sided auction that may optimize the reserve price and allocation of web page placements to maximize revenue. An online keyword auction may be converted into a double-sided market by turning every bidder in the auction into a buyer and every web page placement into a virtual seller. The allocation of buyers and sellers may be divided into disjoint procurement sets and the generalized trade reduction engine may add or remove procurement sets in iterations until conditions of competition among remaining traders may be fulfilled to optimize the reserve price and allocation of web page placements to maximize revenue.

Claims

1. A computer system for an online keyword auction, comprising:

a generalized trade reduction engine for providing services to convert an online keyword auction into an implementation of an individually rational, incentive-compatible, and budget balanced mechanism for a double-sided auction that may optimize a reserve price and an allocation of web page placements for the online keyword auction to maximize revenue; and

a storage operably coupled to the generalized trade reduction engine for storing procurement sets of traders that may be reduced by the trade reduction engine.

2. The system of claim 1 further comprising an auction engine implementing an individually rational and incentive-compatible mechanism operably coupled to the generalized trade reduction engine for providing services for supporting an online keyword auction to allocate advertisements to web page placements.

3. A computer-readable medium having computer-executable components comprising the system of claim 1.

4. A computer-implemented method for an online keyword auction, comprising:

dividing a plurality of bidders for a keyword into a plurality of procurement sets of at least one pair of a bidder and a web page placement;

obtaining a procurement set from the plurality of procurement sets;

determining external competition exists for each bidder in the procurement set that also belongs to a set of at least one bidder closed under replacement;

determining internal competition exists for each bidder in the procurement set that does not also belong to the set of at least one bidder closed under replacement;

charging the at least one bidder in the procurement set for buying the web page placement for display of an advertisement; and

updating a reserve price for the keyword.

5. The method of claim 4 further comprising ordering the plurality of procurement sets by increasing value.

6. The method of claim 4 further comprising:

obtaining another procurement set from the plurality of procurement sets;

determining external competition does not exist for each bidder in the another procurement set that also belongs to the set of at least one bidder closed under replacement; and

removing each bidder in the another procurement set from buying the web page placement for display of an advertisement.

7. The method of claim 4 further comprising:

obtaining another procurement set from the plurality of procurement sets;

determining internal competition does not exist for each bidder in the another procurement set that does not also belong to the set of at least one bidder closed under replacement; and

removing each bidder in the another procurement set from buying the web page placement for display of an advertisement.

8. The method of claim 6 further comprising removing the web page placement for the keyword.

9. The method of claim 4 further comprising obtaining a number of a plurality of web page placements for the keyword in the online keyword auction.

10. The method of claim 4 further comprising obtaining the reserve price for the keyword in the online keyword auction.

11. The method of claim 4 further comprising assigning a cost to each web page placement of a plurality of web page placements for the keyword in the online keyword auction.

12. The method of claim 4 further comprising determining a valuation from each bidder for buying the web page placement for display of an advertisement for the keyword in the online keyword auction.

13. The method of claim 4 further comprising:

determining that at least one procurement set was not removed from the plurality of procurement sets; and

adding a web page placement to the plurality of web page placements for the keyword in the online keyword auction.

14. The method of claim 4 wherein dividing the plurality of bidders for the keyword into the plurality of procurement sets of at least one pair of the bidder and the web page placement comprises matching a plurality of bidders for the keyword to a plurality of web page placements.

15. The method of claim 14 wherein matching the plurality of bidders for the keyword to the plurality of web page placements comprises matching a list of the plurality of bidder sorted in order from highest valuation to lowest valuation with a list of the plurality of web page placements sorted in order from lowest cost to highest cost.

16. The method of claim 4 wherein charging the at least one bidder in the procurement set for buying the web page placement for display of an advertisement comprises charging the at least one bidder at least the reserve price for buying the web page placement for display of the advertisement.

17. The method of claim 4 wherein updating the reserve price for the keyword comprises setting the reserve price to be the cost of a web page placement with a highest assigned cost.

18. A computer-readable medium having computer-executable instructions for performing the method of claim 4.

19. A computer system for an online keyword auction, comprising:

means for converting an online keyword auction into into an implementation of a double-sided auction to optimize a reserve price and an allocation of a plurality of web page placements to maximize revenue;

means for optimizing the reserve price to maximize revenue in the implementation of the double-sided auction; and

means for charging each buyer of the allocation of web page placements for display of an advertisement.

20. The computer system of claim 19 further comprising means for optimizing the allocation of the plurality of web page placements to maximize revenue in the implementation of the double-sided auction.