System and Method for a Data Driven Meta-Auction Mechanism for Sponsored Search

• US 20100161438A1
• Filed: 12/18/2008
• Published: 06/24/2010
• Est. Priority Date: 12/18/2008
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Tomak, Kerem
• Granted Patent: US 8,260,680 B2
• Time in Patent Office: Days
• US Class Current: 705/26
• CPC Class Codes: G06Q 30/0601 Electronic shopping [e-shopping]
• CPC Class Codes: G06Q 30/08 Auctions

Abstract

Apparatuses, methods, and systems directed to deriving optimal parameters of a learning algorithm to maximize an objective function of online keyword auctions for bidded terms. Some embodiments of the invention simulate online keyword auctions based on historical data for the bidded terms, wherein the parameters of the simulated auctions such as market reserve prices of the bidded terms are determined by an adaptive learning algorithm. The values of the parameters of the learning algorithm are optimized by a stochastic optimization method to maximize an objective function for the auctions of the bidded terms.

Claims

1. A method comprising:

accessing an adaptive learning algorithm to maximize an objective function for online auctions of one or more bidded terms each comprising one or more keywords, wherein the adaptive learning algorithm comprises one or more learning parameters, and each auction comprises one or more auction parameters;

determining optimal values of the one or more learning parameters by;

changing the values of the one or more learning parameters using a stochastic optimization method;

simulating one or more online auctions;

calculating values of the objective function based on the results of the one or more simulated auctions;

determining the optimal values of the learning parameters which maximize the objective function;

storing the determined optimal values of the learning parameters of the adaptive learning algorithm in a data store.

2. The method of claim 1, wherein the simulating step comprises:

assigning values to the one or more auction parameters, said values are chosen by the adaptive learning algorithm;

generating one or more bidders and bids for each auction based on historical data without making assumptions of the bidders;

deciding results of the simulated auctions based on the auction parameters and behavior of the generated bidders, wherein the behavior is derived from the historical data.

3. The method of claim 1, wherein the auction parameters comprise market reserve prices of the bidded terms.

4. The method of claim 1, wherein the historical data comprises information related to past auctions of a bidded term comprising the market reserve prices of the bidded term, the number of bidders and their bids, the duration of the auctions, and the winning bids.

5. The method of claim 1, wherein the adaptive learning algorithm comprises a softmax action selection process.

6. The method of claim 1, wherein the stochastic optimization method comprises the simultaneous perturbation stochastic approximation process.

7. The method of claim 1, wherein the behavior of a bidder for a bidded term comprise a range of values of the bidder'"'"'s valuation of the bidded term and a range of values of the bidder'"'"'s loss aversion.

8. The method of claim 1, wherein the objective function comprises an overall estimated revenue from the winning bids of the bidded terms in a period of time.

9. An apparatus, comprising:

a memory;

one or more processors;

logic encoded in one or more computer readable medium, wherein the logic when executed is operable to use the one or more processors to;

access an adaptive learning algorithm to maximize an objective function for online auctions of one or more bidded terms each comprising one or more keywords, wherein the adaptive learning algorithm comprises one or more learning parameters, and the auctions comprise one or more auction parameters;

determine optimal values of the learning parameters comprising the steps of;

changing the values of the learning parameters using a stochastic optimization method;

simulating the online auctions;

calculating values of the objective function based on the results of the simulated auctions;

computing the optimal values of the learning parameters which maximize the objective function.

10. A method comprising:

receiving one or more bids for a bidded term comprising one or more keywords from one or more bidders in an auction, wherein said auction occurs in an online auction platform;

retrieving data from a data store coupled to the online auction platform wherein the data comprises values of one or more auction parameters related to past auctions of the bidded term;

computing updated values of the one or more auction parameters based on the retrieved data using an adaptive learning algorithm;

acquiring a winning bid based on the computed auction parameters;

storing the bidded term, the one or more bids, the updated values of the auction parameters, and the winning bid in the data store.

11. The method of claim 10, wherein the auction parameters comprise a market reserve price for the bidded term and the acquiring step comprising:

excluding bids which are below the market reserve price;

selecting a winning bid from the remaining bids;

acquiring additional bids if all bids are excluded in the exclusion step, said acquiring step comprising;

outputting the updated values of the auction parameters for display;

receiving zero or more additional bids for the bidded term until the auction is completed.

12. The method of claim 10, wherein the one or more auction parameters comprise market reserve prices of the bidded term and durations of the auctions.

13. The method of claim 10, wherein the adaptive learning algorithm comprises one or more learning parameters optimized by a stochastic optimization method in simulated auctions using historical data.

14. The method of claim 10, wherein the adaptive learning algorithm comprises the softmax action selection process.

15. The method of claim 13, wherein the stochastic optimization method comprises the simultaneous perturbation stochastic approximation process.

16. An apparatus, comprising:

a memory;

one or more processors;

logic encoded in one or more computer readable medium, wherein the logic when executed is operable to use the one or more processors to;

receive one or more bids for a bidded term comprising one or more keywords from one or more bidders in an auction, said auction occurs in an online auction platform;

retrieve data from a data store coupled to the online auction platform wherein the data comprises values of one or more auction parameters and one or more bids related to past auctions of the bidded term;

compute updated values of the one or more auction parameters based on the retrieved data using an adaptive learning algorithm;

output the updated values of the auction parameters for display;

acquire zero or more additional bids for the bidded term until the auction is completed;

store the bidded term, the one or more bids, the updated values of the auction parameters, and the acquired additional bids in the data store.

17. A system for determining optimal values of one or more parameters of an adaptive learning algorithm to maximize an overall estimated revenue for online auctions of one or more bidded terms in a period of time, said system comprising:

a server changing the values of the one or more parameters of the adaptive learning algorithm using a stochastic optimization method;

an auction designer creating the auctions based on historical data, wherein each auction comprises a market reserve price of a bidded term, said market reserve price is determined by the adaptive learning algorithm with the changed values of the one or more parameters;

an auction simulator simulating one or more bidders and bids based on the historical data, said auction simulator computes an overall estimated revenue in a period of time;

a data store couple to the server to store information related to the auction designer and the auction simulator;

said information comprising optimal values of the one or more learning parameters established by the server which maximize the estimated overall revenue in the period of time.

18. The system of claim 17, wherein the adaptive learning algorithm comprises the softmax action selection process.

19. The system of claim 17, wherein the stochastic optimization method comprises the simultaneous perturbation stochastic approximation process.

20. A system for determining a market reserve price for a bidded term comprising one or more keywords for an auction, said system comprising:

a server receiving one or more bids from one or more bidders for the bidded term;

a data store couple to the server storing information related to one or more auctions of the bidded term;

the information comprising a market reserve price determined by the server using an adaptive learning algorithm, wherein the adaptive learning algorithm comprises one or more parameters optimized by a stochastic optimization method in simulated auctions.