Automated web-based targeted advertising with quotas

• US 7,158,959 B1
• Filed: 01/31/2005
• Issued: 01/02/2007
• Est. Priority Date: 07/03/1999
• Status: Expired due to Term

• Current Assignee: Zhigu Holdings Limited
• Original Assignee: Microsoft Corporation
• Inventors: Chickering, David Maxwell, Heckerman, David E.
• Primary Examiner(s): STARKS, WILBERT L
• Application Number:
  US11/047,276
• Time in Patent Office: 701 Days
• Field of Search: 706/47, 707/100, 725/35, 725/42
• US Class Current: 706/47
• CPC Class Codes: G06Q 30/00 Commerce
• CPC Class Codes: G06Q 30/0269 based on user profile or attribute
• CPC Class Codes: G06Q 30/0273 Determination of fees for advertising
• CPC Class Codes: G06Q 30/0277 Online advertisement

Abstract

The invention provides systems and methods that can be used for targeted advertising. The system determines where to present impressions, such as advertisements, to maximize an expected utility subject to one or more constraints, which can include quotas and minimum utilities for groups of one or more impression. The traditional measure of utility in web-based advertising is click-though rates, but the present invention provides a broader definition of utility, including measures of sales, profits, or brand awareness, for example. This broader definition permits advertisements to be allocated more in accordance with the actual interests of advertisers.

Claims

1. A computer-implemented system for allocating advertisements among prospective presentation opportunities, comprising the following computer-executable components:

an input obtaining computer system component that obtains presentation requirements that relate to numbers of times or rates at which one or more of the advertisements are to be presented and to obtain utilities for the advertisements that depend on presentation opportunity characteristics; and

an advertisement assigning computer system component that allocates the advertisements to gain discrete dollar values among the prospective presentation opportunities based on at least the utilities and the presentation requirements.

2. The system of claim 1, further comprising:

the input obtaining computer system component obtains presentation opportunity occurrence rates, which relate to the rates of occurrence of the presentation opportunity characteristic among the prospective presentation opportunities; and

the advertisement assigning computer system component allocates the advertisements among the prospective presentation opportunities based on the presentation opportunity occurrence rates.

3. The system of claim 2, the advertisement assigning computer system component, in allocating the advertisements among the prospective presentation opportunities, solves an optimization problem involving the utilities and constraints relating to the presentation opportunity occurrence rates and the presentation requirements.

4. The system of claim 3, the optimization problem comprises maximizing a utility function subject to constraints comprising the presentation opportunity occurrence rates and the presentation requirements.

5. The system of claim 4, further comprising:

the advertisement assigning system divides the prospective presentation opportunities into clusters based on the presentation opportunity characteristics and allocates the advertisements among the clusters; and

the utility function is a sum taken over the clusters and over the advertisements of the quantity of each advertisement allocated to the cluster multiplied by a utility for the advertisement in the cluster.

6. The system of claim 3, the optimization problem gives weight to obtaining a uniform distribution of the advertisements among the presentation opportunities.

7. The system of claim 1, the responses are of a type for which the presence or absence of a response cannot be determined within the time in which an advertisement engendering the response is presented.

8. The system of claim 1, further comprising an advertisement selecting computer system component that receives allocations from the advertisement assigning computer system component and selects advertisements to fill the presentation opportunities based on the allocations.

9. The system of claim 1, the advertisement assigning computer system component modifies one or more of the utilities.

10. The system of claim 9, the advertisement assigning system divides the prospective presentation opportunities into clusters based on the presentation opportunity characteristics and allocates the advertisements among the clusters.

11. The system of claim 10, the advertisement assigning system employs a learning probabilistic model to define the clusters.

12. The system of claim 11, the learning probabilistic model is a Bayesian belief network model.

13. The system of claim 1, the utilities are of a type for which the utility cannot be determined within the time in which an advertisement engendering the utility is presented.

14. The system of claim 13, the utilities relate to number of sales.

15. A computer-implemented method of allocating advertisements among prospective presentation opportunities, comprising the following computer-executable acts:

obtaining probabilities of responses to the advertisements as functions of presentation opportunity characteristics; and

allocating the advertisements to gain discrete dollar values among the prospective presentation opportunities.

16. The method of claim 15, allocating the advertisements among the prospective presentation opportunities is based at least on the probabilities of responses.

17. The method of claim 16, the responses are of a type for which the presence or absence of a response cannot be determined within the time in which an advertisement engendering the response is presented.

18. A computer-readable medium for selecting advertisements to present to users, the computer-readable medium having computer-executable instructions for performing steps comprising:

obtaining data on users, data on user responses to advertisements, and presentation quotas; and

selecting advertisements to gain discrete dollar values to present to the users based at least on the data on users, the data on user responses to advertisements, and the presentation quotas.

19. The computer-readable medium of claim 18, the step of selecting advertisements to present to the users comprises solving an optimization problem involving the data on users, the data on user responses to advertisements, and the presentation quotas.

20. The computer-readable medium of claim 18, the optimization problem comprises maximizing a utility function subject to constraints based the data on the users and the presentation quotas.