System and method for payment over a series of time periods in an online market with budget and time constraints
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.
1. A computer-implemented method for payment in an online advertising auction, said method comprising:
using an input/output subsystem 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; and using a processor device to perform:
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 and computing the critical values comprises collecting status set parameters from the subset of advertisers;
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;
updating a remaining budget of each of the plurality of advertisers in the online advertising auction; and,
collecting the status set parameters comprises: allocating an advertising slot for each advertiser;
monitoring the advertising slot for each of the selected time periods;
determining a click-through status as a sum of clicks received during each of the selected time periods;
determining the critical value as a minimum sum of values that could have resulted in the click-through status, wherein the values comprise:
a first value representing a value for the advertising slot when the advertiser did not gain an impression during a time period;
a second value representing a value for the advertising slot when the advertiser had an impression but not a click through during a time period; and
a third value representing a value for the advertising slot when the advertiser had an impression and a click-through during a time period; and,
the sum of values represents a union of the first and third values.
2. The method of claim 1 wherein computing the critical values comprises:
selecting time periods occurring since the arrival times of the plurality of advertisers in the online advertising auction;
initializing status set parameters to zero for the advertisers entering and departing the online auction during the selected time periods;
selecting a subset of the advertisers for sampling from among the advertisers entering and departing the online auction during the selected time periods;
collecting status set parameters from the subset of advertisers; and
setting the critical values for the subset of advertisers based on the collected status set parameters.
3. The method of claim 2 wherein selecting the subset of advertisers comprises:
determining the advertisers currently in the online advertising auction; and
removing the advertisers with a payoff rate lower than a threshold.
4. The method of claim 2 wherein initializing the status set parameters comprises:
initializing the click-through rate for an advertiser to zero;
initializing the click-through status for an advertiser to zero; and
initializing the payoff rate per click to zero.
5. The method of claim 2 wherein determining the critical value further comprises:
determining a click-through rate as a probability of receiving a click when the advertiser is allotted an impression.
6. The method of claim 5 further comprising estimating an accuracy of the click-through rate based on a number of impressions received by the advertiser.
7. The method of claim 2 wherein determining the critical value further comprises:
incrementing a payoff rate when receiving a click; and
decrementing the payoff rate when not receiving a click.
8. A non-transitory computer-readable medium having computer-executable instructions for performing steps of:
using an input/output subsystem 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; and using a processor device to perform:
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 and computing the critical values comprises collecting status set parameters from the subset of advertisers;
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,
collecting the status set parameters comprises: allocating an advertising slot for each advertiser;
monitoring the advertising slot for each of the selected time periods;
determining a click-through status as a sum of clicks received during each of the selected time periods;
determining the critical value as a minimum sum of values that could have resulted in the click-through status, wherein the values comprise:
a first value representing a value for the advertising slot when the advertiser did not gain an impression during a time period;
a second value representing a value for the advertising slot when the advertiser had an impression but not a click through during a time period; and
a third value representing a value for the advertising slot when the advertiser had an impression and a click-through during a time period; and,
the sum of values represents a union of the first and third values.