System and method using sampling for scheduling advertisements in an online auction with budget and time constraints
First Claim
1. A computer system for an online advertising auction, comprising:
- an input/output interface receiving, from each of a plurality of advertisers bidding for advertising slots in the online advertising auction;
a bid for an advertising slot based on a keyword, wherein said bid comprises;
an arrival time at the online advertising auction;
a departure time at the online advertising auction;
a budget to be spent between the arrival time and the departure time, wherein said budget may not be exceeded; and
a value per click;
wherein it is assumed that the budget is greater than the value per click;
a processor device configured as a multi-armed bandit engine learning a 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 by performing;
computing critical values for each of the plurality of advertisers in a given time period of the online advertising auction, wherein a critical value is a minimum value for the advertising slot in the given time period;
computing an interim price based upon the critical values for each of the plurality of advertisers in the online advertising auction;
charging the plurality of advertisers departing from the online advertising auction the computed interim price; and
updating a remaining budget of each of the plurality of advertisers in the online advertising auction; and
a storage device operably coupled to the multi-armed bandit engine 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;
wherein the computer system selects a plurality of advertisers for sampling advertisements in the online advertising auction and samples advertisements for a subset of the plurality of advertisers.
7 Assignments
0 Petitions
Accused Products
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.
18 Citations
11 Claims
-
1. A computer system for an online advertising auction, comprising:
-
an input/output interface receiving, from each of a plurality of advertisers bidding for advertising slots in the online advertising auction; a bid for an advertising slot based on a keyword, wherein said bid comprises; an arrival time at the online advertising auction; a departure time at the online advertising auction; a budget to be spent between the arrival time and the departure time, wherein said budget may not be exceeded; and a value per click; wherein it is assumed that the budget is greater than the value per click; a processor device configured as a multi-armed bandit engine learning a 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 by performing; computing critical values for each of the plurality of advertisers in a given time period of the online advertising auction, wherein a critical value is a minimum value for the advertising slot in the given time period; computing an interim price based upon the critical values for each of the plurality of advertisers in the online advertising auction; charging the plurality of advertisers departing from the online advertising auction the computed interim price; and updating a remaining budget of each of the plurality of advertisers in the online advertising auction; and a storage device operably coupled to the multi-armed bandit engine 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; wherein the computer system selects a plurality of advertisers for sampling advertisements in the online advertising auction and samples advertisements for a subset of the plurality of advertisers. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
Specification