System and method using sampling for scheduling advertisements in an online auction with budget and time constraints

• US 20090070212A1
• Filed: 09/10/2007
• Published: 03/12/2009
• Est. Priority Date: 09/10/2007
• Status: Active Grant

• Current Assignee: Yahoo AD Tech LLC
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Pavlov, Elan Y., Gonen, Rica
• Granted Patent: US 8,666,813 B2
• Time in Patent Office: Days
• US Class Current: 705/14.100
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/0207 Discounts or incentives, e.g. coupons or rebates
• CPC Class Codes: G06Q 30/08 Auctions

Abstract

An improved system and method is provided for using sampling for scheduling advertisements in an online auction with budget and time constraints. A multi-armed bandit engine may be provided for sampling new advertisements by allocating advertisements for web page placements of equal quality and optimizing payments to maximize the welfare of the advertisers while remaining within advertiser'"'"'s budget and time constraints. Advertisers may report their private information including arrival time, departure time, value per click, and budget. And the multi-armed bandit mechanism may approximate the maximal welfare that may be achieved under budget and time constraints by bounding the possible gain from any possible lie an advertiser might submit in reporting private information. Advertisers departing from the online auction may be charged using a payment method that may provide truthful guarantees on budget, arrivals, departures, and valuations for a budget-constrained online auction.

Claims

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

a multi-armed bandit engine for learning the valuation of advertisements through sampling by scheduling the advertisements for web page placements in an online advertising auction with budget and time constraints to optimize payments for maximizing welfare of advertisers; and

a storage operably coupled to the multi-armed bandit engine for storing a plurality of budgets and a plurality of bids each associated with an advertisement allocated to web page placements in the online advertising auction with budget and time constraints.

2. The system of claim 1 further comprising a model generator for creating a multi-armed bandit model used by the multi-armed bandit engine.

3. The system of claim 1 further comprising a payoff optimizer operably coupled to the multi-armed bandit engine for optimizing payments for the advertisements sampled in the online advertising auction with budget and time constraints to maximize the welfare of the advertisers.

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

5. A computer-implemented method for an online advertising auction, comprising:

receiving a budget that may not be exceeded between an arrival time and the departure time for each of a plurality of advertisers entering an online advertising auction;

receiving a value per click of an advertisement for each of the plurality of advertisers entering the online advertising auction;

selecting a plurality of advertisers for sampling advertisements in the online advertising auction;

sampling advertisements for a subset of the plurality of advertisers;

updating a click-through rate for each of the subset of the plurality of advertisers sampled in the online advertising auction;

updating a remaining budget of each of the plurality of advertisers in the online advertising auction; and

charging the plurality of advertisers departing from the online advertising auction.

6. The method of claim 5 further comprising receiving the arrival time and the departure time for each of the plurality of advertisers entering the online advertising auction.

7. The method of claim 5 further comprising initializing the click-through rate to zero for each of the plurality of advertisers entering the online advertising auction.

8. The method of claim 5 further comprising initializing total clicks of advertisements to zero for each of the plurality of advertisers entering the online advertising auction.

9. The method of claim 5 further comprising initializing the price charged for a click of an advertisement to zero for each of the plurality of advertisers entering the online advertising auction.

10. The method of claim 5 further comprising initializing an exposure parameter to zero for each of the plurality of advertisers entering the online advertising auction on a first visit.

11. The method of claim 5 wherein selecting the plurality of advertisers for sampling advertisements in the online advertising auction comprises:

determining a list of the plurality of advertisers currently in the online advertising auction;

removing advertisers with a click-through rate lower than a threshold from the list; and

outputting the remaining list of the plurality of advertisers for sampling advertisements in the online advertising auction.

12. The method of claim 5 wherein sampling advertisements for a subset of the plurality of advertisers in the online advertising auction comprises:

receiving a list of the plurality of advertisers for sampling advertisements in the online advertising auction;

randomly selecting a subset of advertisers from the list; and

sampling an advertisement for each of the subset of advertisers in the online advertising auction.

13. The method of claim 5 further comprising updating an exposure parameter for each of the subset of the plurality of advertisers sampled in the online advertising auction.

14. The method of claim 5 further comprising updating a payoff rate for each of the subset of the plurality of advertisers sampled in the online advertising auction.

15. The method of claim 5 further comprising updating a click-through status set for each of the subset of the plurality of advertisers sampled in the online advertising auction that received a click of an advertisement.

16. The method of claim 5 further comprising computing critical values for each of the plurality of advertisers in the online advertising auction.

17. The method of claim 5 further comprising computing an interim price for each of the plurality of advertisers in the online advertising auction.

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

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

means for receiving a budget that may not be exceeded between an arrival time and the departure time for each of a plurality of advertisers entering an online advertising auction;

means for receiving a value per click of an advertisement for each of the plurality of advertisers entering the online advertising auction;

means for sampling advertisements for a subset of the plurality of advertisers in the online auction; and

means for charging the plurality of advertisers departing from the online advertising auction.

20. The computer system of claim 19 further comprising:

means for selecting a plurality of advertisers for sampling advertisements in the online advertising auction;

means for updating a click-through rate for each of the subset of the plurality of advertisers sampled in the online advertising auction;

means for updating a remaining budget of each of the plurality of advertisers in the online advertising auction.