Method, algorithm, and computer program for optimizing the performance of messages including advertisements in an interactive measurable medium

• US 7,130,808 B1
• Filed: 06/02/2000
• Issued: 10/31/2006
• Est. Priority Date: 12/29/1999
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.), IQ Acquisition Corporation
• Original Assignee: The Product Engine, Inc.
• Inventors: Ranka, Sanjay, Lenderman, Jason S., Weisinger, James
• Primary Examiner(s): Elisca, Pierre E.
• Application Number:
  US09/586,387
• Time in Patent Office: 2,342 Days
• Field of Search: 705/10, 705/14, 705/27, 705/11, 705/12
• US Class Current: 705/14.43
• CPC Class Codes: G06Q 10/06315 Needs-based resource requirements planning or analysis
• CPC Class Codes: G06Q 10/0639 Performance analysis of employees; Performance analysis of enterprise or organisation operations
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/0201 Market modelling; Market analysis; Collecting market data
• CPC Class Codes: G06Q 30/0204 Market segmentation
• CPC Class Codes: G06Q 30/0205 Location or geographical consideration
• CPC Class Codes: G06Q 30/0241 Advertisements
• CPC Class Codes: G06Q 30/0242 Determining effectiveness of advertisements
• CPC Class Codes: G06Q 30/0244 Optimization
• CPC Class Codes: G06Q 30/0256 User search
• CPC Class Codes: G06Q 30/0277 Online advertisement
• CPC Class Codes: G06Q 30/0631 Item recommendations
• CPC Class Codes: G06Q 30/0633 Lists, e.g. purchase orders, compilation or processing

Abstract

Method, procedure, algorithm, system, and computer program for improving and attempting to optimize the performance of messaging campaigns, particularly to marketing campaigns in which advertisements or other messages are distributed over an interactive measurable medium such as the Internet. A goal is to allocate the message alternatives to the customer population to optimize business objectives. The includes reading prior stage message state data pertaining to a prior stage including a cumulative number of trials and a cumulative number of successes for a particular message. Message performance results representing message trials and message successes from the previous stage based on the prior-stage state are then read, and a current message state is computed. A current message allocation is generated based on the current message state. Desirably the cumulative number of trials and the cumulative number of successes are discounted based on the age of the information. This inventive procedure may be applied to various message types including, for example, web site banner advertisements, electronic advertisements generally, email messages and promotions, and the like. In one embodiment, the messages are internet web site banner ads, trials are impressions of the ads presented to the user, and successes are measured by clickthroughs from the banner ad to the web site associated with the banner ad. Computer system, computer program, and computer program product associated with the inventive method and procedures are also provided by the invention.

Claims

1. A method for improving the stage-to-stage performance of a message in a multi-stage message campaign in an interactive measurable medium;

said method including steps of;

(a) reading prior stage message state pertaining to a prior stage in a message campaign;

said prior stage message state including a cumulative number of trials and a cumulative number of successes for a particular message at the end of said prior stage;

(b) reading message performance results representing message trials and message successes from said prior stage based on said prior stage message state;

(c) computing a current message state on the basis of said prior stage message state and said message performance results; and

(d) generating a current message allocation based on said current message state;

wherein at least one of steps (a)–

(d) is performed by at least one processing device.

2. The method in claim 1, wherein said method further comprising step of:

(c) storing said current message state as prior stage message state for a next iteration of said method.

3. The method in claim 2, further including repeating steps (a)–

(c) for each stage in said message campaign.

4. The method in claim 1, wherein said prior stage message state comprises reading a state vector for the prior stage in a message campaign.

5. The method in claim 1, further comprising the step of storing said initial state vector in a database.

6. The method in claim 1, wherein said step of generating a current message allocation further includes applying a message allocation constraint.

7. The method in claim 1, further including the step of storing said current message allocation in a database.

8. The method in claim 1, wherein said message comprises a web banner ad.

9. The method in claim 1, wherein said message comprises an email.

10. The method in claim 1, wherein said current message state is updated at the end of each state of a message campaign to reflect the performance results of that stage.

11. The method in claim 1, wherein said current message state stores information that has been collected on a given message.

12. The method in claim 1, wherein said message comprises an advertisement, and said current message state stores information that has been collected for said advertisement.

13. The method in claim 1, wherein said message comprises an internet web site banner advertisement and said current message state stores information that has been collected for said banner advertisement at a given zone.

14. The method in claim 1, wherein said message comprises an email message and said current message state stores information that has been collected for said email message.

15. The method in claim 1, wherein said message comprises a banner advertisement and a constraints list stores any constraints on the allocation of banner ads to impressions.

16. The method in claim 1, wherein said step of (b) of reading message performance results further comprises storing said performance results of the most recent stage of the message campaign in a results vector.

17. The method in claim 16, wherein said message comprises an advertisement, and said results vector stores results of a most recent stage of the advertising campaign.

18. The method in claim 1, wherein said step (d) of generating a current message allocation further comprises storing a current message allocation into an allocations vector.

19. The method in claim 18, wherein said allocations vector stores an allocation of banners to available impressions for a future stage in the campaign.

20. The method in claim 18, wherein said allocations vector stores an allocation of messages to available trials for a future stage in the campaign.

21. The method in claim 20, wherein said future stage is a next stage.

22. The method in claim 1, wherein said step (d) of generating a current message allocation uses performance results from all prior stages in the message campaign.

23. The method in claim 1, wherein said step (d) of generating a current message allocation uses performance results form at least one prior stage in the campaign.

24. A method for improving the stage-to-stage performance of a message in a multi-stage message campaign in an interactive measurable medium;

said method including steps of;

(a) reading prior stage message state pertaining to a prior stage in a message campaign;

said prior stage message state including a cumulative number of trials and a cumulative number of successes for a particular message at the end of said prior stage;

(b) reading message performance results representing message trials and message successes from said prior stage based on said prior stage message state;

(c) computing a current message state on the basis of said prior stage message state and said message performance results; and

(d) generating a current message allocation based on said current message state;

wherein said cumulative number of trials and said cumulative number of successes comprise discounted cumulative number of trials and discounted cumulative number of successes;

wherein at least one of steps (a)–

(d) is performed by at least one processing device.

25. A method for improving the stage-to-stage performance of a message in a multi-stage message campaign in an interactive measurable medium;

said method including steps of;

(a) reading prior stage message state pertaining to a prior stage in a message campaign;

said prior stage message state including a cumulative number of trials and a cumulative number of successes for a particular message at the end of said prior stage;

(b) reading message performance results representing message trials and message successes from said prior stage based on said prior stage message state;

(c) computing a current message state on the basis of said prior stage message state and said message performance results;

(d) generating a current message allocation based on said current message state;

(e) storing said current message state as prior stage message state for a next iteration of said method; and

(f) repeating steps (a)–

(e) for each stage in said message campaign;

wherein said cumulative number of trials and said cumulative number of successes comprise discounted cumulative number of trials and discounted cumulative number of successes;

wherein said prior stage message state comprises reading a state vector for the prior stage in a message campaign;

wherein said step of generating a current message allocation further includes applying a message allocation constraint; and

wherein said message is selected from the group of messages consisting of an advertisement, an email, and combinations thereof;

wherein at least one of steps (a)–

(f) is performed by at least one processing device.

26. A method for improving the stage-to-stage performance of a message in a multi-stage message campaign in an interactive measurable medium, wherein the message comprises a banner advertisement and a constraints list stores any constraints on the allocation of banner ads to impressions;

said method including steps of;

(a) reading prior stage message state pertaining to a prior stage in a message campaign;

said prior stage message state including a cumulative number of trials and a cumulative number of successes for a particular message at the end of said prior stage;

(b) reading message performance results representing message trials and message successes from said prior stage based on said prior stage state;

(c) computing a current message state on the basis of said prior stage message state and said message performance results; and

(d) generating a current message allocation based on said current message state;

wherein said constraints includes a minimum number of banners to be retained at each state of an ad campaign and the identity of particular banners to be excluded from any zones;

wherein at least one of steps (a)–

(d) is performed by at least one processing device.

27. A method for improving the stage-to-stage performance of a message in a multi-stage message campaign in an interactive measurable medium;

said method including steps of;

(a) reading prior stage message state pertaining to a prior stage in a message campaign;

said prior stage message state including a cumulative number of trials and a cumulative number of successes for a particular message at the end of said prior stage;

(b) reading message performance results representing message trials and message successes from said prior stage based on said prior stage message state;

(c) computing a current message state on the basis of said prior stage message state and said message performance results; and

(d) generating a current message allocation based on said current message state using results from a predetermined number of most recent prior stages in the campaign;

wherein at least one of steps (a)–

(d) is performed by at least one processing device.

28. A method for improving the stage-to-stage performance of a message in a multi-stage message campaign in an interactive measurable medium;

said method including steps of;

(a) reading prior stage message state pertaining to a prior stage in a message campaign;

said prior stage message state including a cumulative number of trials and a cumulative number of successes for a particular message at the end of said prior stage;

(b) reading message performance results representing message trials and message successes from said prior stage based on said prior stage message state;

(c) computing a current message state on the basis of said prior stage message state and said message performance results; and

(d) generating a current message allocation based on said current message state using weighted results from a predetermined number of the most recent prior stages in the campaign so that more recent results are weighted more heavily than older results;

wherein at least one of steps (a)–

(d) is performed by at least one processing device.

29. A method for improving the stage-to-stage performance of a message in a multi-stage message campaign in an interactive measurable medium;

said method including steps of;

(a) reading prior stage message state pertaining to a prior stage in a message campaign;

said prior stage message state including a cumulative number of trials and a cumulative number of successes for a particular message at the end of said prior stage;

(b) reading message performance results representing message trials and message successes from said prior stage based on said prior stage message state;

(c) computing a current message state on the basis of said prior stage message state and said message performance results; and

(d) generating a current message allocation based on said current message state;

wherein, when multiple zones are possible for a message, said step (a)–

(d) are applied separately for each zone on a zone-by-zone basis;

wherein at least one of steps (a)–

(d) is performed by at least one processing device.

30. A method for improving the stage-to-stage performance of a message in a multi-stage message campaign in an interactive measurable medium;

said method including steps of;

(a) reading prior stage message state pertaining to a prior stage in a message campaign;

said prior stage message state including a cumulative number of trials and a cumulative number of successes for a particular message at the end of said prior stage;

(b) reading message performance results representing message trials and message successes from said prior stage based on said prior stage message state;

(c) computing a current message state on the basis of said prior stage message state and said message performance results; and

(d) generating a current message allocation based on said current message state;

wherein said performance results are discounted when computing a current state vector;

wherein at least one of steps (a)–

(d) is performed by at least one processing device.

31. The method in claim 30, wherein the performance results are discounted using a binary step function where performance data older than a given stage is ignored and performance data newer that the given stage is considered equally.

32. The method in claim 30, wherein the performance results are discounted using a weighting function wherein newer performance data is weighted more heavily than older performance data.

33. The method in claim 30, wherein the performance results are discounted by geometrical discounting where, at each stage, each performance data is discounted according to a geometrical discounting function.

34. A method for improving the stage-to-stage performance of a message in a multi-stage message campaign in an interactive measurable medium;

said method including steps of;

(a) reading prior stage message state pertaining to a prior stage in a message campaign;

said prior stage message state including a cumulative number of trials and a cumulative number of successes for a particular message at the end of said prior stage;

(b) reading message performance results representing message trials and message successes from said prior stage based on said prior stage message state;

(c) computing a current message state on the basis of said prior stage message state and said message performance results; and

(d) generating a current message allocation based on said current message state;

wherein, at each stage, performance data is discounted according to a geometrical discounting function;

wherein the geometrical discounting function multiplies each performance result at each stage by a number of one-stage discount factors β

, where β

is less-than-or-equal-to 1 (β

≦

1), corresponding to the number of stages, such that performance data that is n stages old at the time of execution are multiplied by β

raised to the n power (β

ⁿ);

wherein at least one of steps (a)–

(d) is performed by at least one processing device.

35. The method in claim 34, wherein the one-stage discount factor β

<

1.

36. The method in claim 34, wherein β

is in a range between about 0 and about 0.99.

37. The method in claim 34, wherein β

is in a range between about 0.5 and about 1.0.

38. The method in claim 34, wherein β

is in a range between about 0.8 and about 1.0.

39. The method in claim 34, wherein β

is in a range between about 0.85 and about 0.95.

40. The method in claim 34, wherein β

is substantially 0.9.

41. A method for improving the stage-to-stage performance of a message in a multi-stage message campaign in an interactive measurable medium;

said method including steps of;

(a) reading prior stage message state pertaining to a prior stage in a message campaign;

said prior stage message state including a cumulative number of trials and a cumulative number of successes for a particular (i^th) message at the end of said prior stage, wherein “

i”

is between 1 and “

n,”

wherein “

n”

is a number of messages in the multi-stage message campaign;

(b) reading message performance results representing message trials and message successes from said prior stage based on said prior stage message state;

(c) computing a current message state on the basis of said prior stage message state and said message performance results; and

(d) generating a current message allocation based on said current message state;

wherein said state comprises a state vector having a first state vector component s_i(t) for the total number of discounted cumulative clicks for the particular (i^th) message at the end of stage t, and a second state vector component n_i(t) for the cumulative number of impressions for the particular (i^th) message at the end of stage t;

wherein at least one of steps (a)–

(d) is performed by at least one processing device.

42. The method in claim 41, wherein:

s_i(t)=β

s_i(t−

1)+click_i(t−

1), for t≧

2;

n_i(t)=β

n_i(t−

1)+imp_i(t−

1), for t≧

2; and

s_i(1)=0 and n_i(1)=0; and

where;

imp_i(t) is the total number of impressions for the particular (i^th) message in stage t;

click_i(t) represent the total number of clicks for the particular (i^th) message in stage t; and

β

is a one stage discounting factor.

43. The method in claim 42, wherein β

≦

1.

44. The method in claim 41, wherein:

s_i(t)=G{click_i(1), . . . , click_i(t−

2), click_i(t−

1)}, for t≧

2; and

n_i(t)=G{imp_i(1), . . . , imp_i(t−

2), imp_i(t−

1)}, for t≧

2;

where

s_i(1)=0 and n_i(1)=0; and

where;

imp_i(t) is the total number of impressions for the particular (i^th) message in stage t;

click_i(t) represent the total number of clicks for the particular (i^th) message in stage t; and

G{ . . . } is a discounting factor.

45. The method in claim 44, wherein G{ . . . } is a geometric discounting function.

46. A method for improving the stage-to-stage performance of a message in a multi-stage message campaign in an interactive measurable medium;

said method including steps of;

(a) reading prior stage message state pertaining to a prior stage in a message campaign;

said prior stage message state including a cumulative number of trials and a cumulative number of successes for a particular i^th message at the end of said prior stage;

(b) reading message performance results representing message trials and message successes from said prior stage based on said prior stage message state;

(c) computing a current message state on the basis of said prior stage message state and said message performance results; and

(d) generating a current message allocation based on said current message state;

wherein, at each stage, available messages are partitioned into a first group of contending messages that remain in contention to become a best performing message, and a second group that are not in contention to become the best performing message;

wherein at least one of steps (a)–

(d) is performed by at least one processing device.

47. The method in claim 46, wherein said message comprises a banner ad.

48. The method in claim 46, wherein said message comprises an email.

49. The method in claim 46, wherein the available messages are further partitioned into a third group of unavailable messages for messages constrained not to be used on the given zone during a particular stage.

50. The method in claim 49, wherein each of said first group, said second group, and said third group may have none, one, or a plurality of members.

51. The method in claim 46, wherein a first proportion (γ

) of total available impressions are allocated to non-contenders at each stage and a second proportion (1−

γ

) of the total available impressions are allocated to contenders at each stage, at the beginning of a campaign.

52. The method in claim 51, wherein said first proportion (γ

) of the total available impressions is between about 0 and about 0.5.

53. The method in claim 51, wherein said first proportion (γ

) of the total available impressions is between about 0.01 and about 0.05.

54. The method in claim 51, wherein said first proportion (γ

) of the total available impressions is between about 0.02 and about 0.03.

55. The method in claim 46, wherein alternatives for each message are compared on a pair-wise basis to alternatives for each other message to determine a better performing set of pair-wise compared messages.

56. The method in claim 55, wherein the message comprises a banner ad.

57. The message in claim 56, wherein, if a particular banner ad loses a pair-wise comparison by having a lower success rate than another banner ad, the particular banner ad is designated as a non-contender.

58. The method in claim 55, wherein the message comprises an email.

59. The method in claim 58, wherein the email message includes an attachment.

60. The method in claim 55, wherein pair-wise comparison guarantees that at least one contender will remain.

61. The method in claim 55, wherein the pair-wise comparison determines relative success rates for the two message alternatives utilizing a cutoff threshold value.

62. The method in claim 61, wherein said cutoff threshold value is a value between about 0.5 and about 1.0.

63. The method in claim 61, wherein said cutoff threshold value is a value of about ½

.

64. A method for improving the stage-to-stage performance of a message in a multi-stage message campaign in an interactive measurable medium;

said method including steps of;

(a) reading prior stage message state pertaining to a prior stage in a message campaign;

said prior stage message state including a cumulative number of trials and a cumulative number of successes for a particular i^th message at the end of said prior stage;

(b) reading message performance results representing message trials and message successes from said prior stage based on said prior stage message state;

(c) computing a current message state on the basis of said prior stage message state and said message performance results; and

(d) generating a current message allocation based on said current message state;

wherein said message is selected from the group of messages consisting of an advertisement, an internet web site banner ad, an email, an email advertisement, an email having an advertisement attachment, a solicitation, an interactive television message, and combinations thereof;

wherein at least one of steps (a)–

(d) is performed by at least one processing device.

65. A method for improving the stage-to-stage performance of a message in a multi-stage message campaign in an interactive measurable medium;

said method including steps of;

(a) reading prior stage message state pertaining to a prior stage in a message campaign;

said prior stage message state including a cumulative number of trials and a cumulative number of successes for a particular i^th message at the end of said prior stage;

(b) reading message performance results representing message trials and message successes from said prior stage based on said prior stage message state;

(c) computing a current message state on the basis of said prior stage message state and said message performance results; and

(d) generating a current message allocation based on said current message state;

wherein for providing more than two groups of alternatives, the alternatives are divided into multiple sets based on a performance value;

wherein at least one of steps (a)–

(d) is performed by at least one processing device.

66. The method in claim 65, wherein a number of impressions allocated to alternatives within a set are equal and the a number of sets is equal to the number of alternatives.

67. A method for improving the stage-to-stage performance of a message in a multi-stage message campaign in an interactive measurable medium;

said method including steps of;

(a) reading prior stage message state pertaining to a prior stage in a message campaign;

said prior stage message state including a cumulative number of trials and a cumulative number of successes for a particular (i^th) message at the end of said prior stage, wherein “

i”

is between 1 and “

n,”

wherein “

n”

is a number of messages in the multi-stage message campaign;

(b) reading message performance results representing message trials and message successes from said prior stage based on said prior stage message state;

(c) computing a current message state on the basis of said prior stage message state and said message performance results; and

(d) generating a current message allocation based on said current message state;

wherein said state comprises a first state vector component s_i(t) for the total number of discounted cumulative successes for the particular (i^th) message at the end of stage t, and a second state vector component n_i(t) for the cumulative number of trials for the particular (i^th) message at the end of stage t;

wherein at least one of steps (a)–

(d) is performed by at least one processing device.

68. The method in claim 67, wherein:

s_i(t)=H{success_i(1), . . . , success_i(t−

2), success_i(t−

1)}, for t≧

2; and

n_i(t)=H{trial_i(1), . . . , trial_i(t−

1), trial_i(t−

1)}, for t≧

2;

where

s_i(1)=0 and n_i(1)=0;

success_i(t) is the number of successful outcomes for the particular (i^th) message at stage t;

trial_i(t) is the number of trials of the particular (i^th) message at stage t; and

H{ . . . } is a functional operator of the bracketed parameters.

69. The method in claim 68, wherein H{ . . . } comprises a weighting function of trials and successes.

70. The method in claim 68, wherein H{ . . . } comprises a geometric discounting function wherein newer state data is counted more heavily than older state data.

71. A computer program for use in conjunction with a computer system, the computer program comprising a computer program mechanism embedded therein, the computer program mechanism, comprising:

a program module that directs the computer system to improving the stage-to-stage performance of a message in a multi-stage message, the program module including instructions for performing a method comprising;

(a) reading prior stage message state pertaining to a prior stage in a message campaign;

said prior stage message state including a cumulative number of trials and a cumulative number of successes for a particular message at the end of said prior stage;

(b) reading message performance results representing message trials and message successes from said prior stage based on said prior message stage state;

(c) computing a current message state on the basis of said prior stage message state and said message performance results; and

(d) generating a current message allocation based on said current message state.

72. The computer program in claim 71, wherein said program module further including instructions for:

(c) storing said current message state as prior stage message state for a next iteration of said method.

73. The computer program in claim 72, wherein said program module further includes instructions for repeating steps (a)–

(c) for each stage in said message campaign.

74. The computer program in claim 71, wherein said prior stage message state comprises reading a state vector for the prior stage in a message campaign.

75. The computer program in claim 71, wherein said step of generating a current message allocation further includes applying a message allocation constraint.

76. The computer program of claim 71, further comprising a tangible computer readable storage medium wherein the computer program is stored on the tangible computer readable storage medium.

77. The computer program of claim 76, wherein said tangible computer readable storage medium is a medium selected from the group consisting of a magnetic storage medium, a solid-state memory device, an optical storage medium, a CD-ROM disk, a DVD disc, a floppy-disc, and combinations thereof.

78. A computer program for use in conjunction with a computer system, the computer program comprising a computer program mechanism embedded therein, the computer program mechanism, comprising:

a program module that directs the computer system to improving the stage-to-stage performance of a message in a multi-stage message, the program module including tangible instructions for performing a method comprising;

(a) reading prior stage message state pertaining to a prior stage in a message campaign;

said prior stage message state including a cumulative number of trials and a cumulative number of successes for a particular message at the end of said prior stage;

(b) reading message performance results representing message trials and message successes from said prior stage based on said prior stage message state;

(c) computing a current message state on the basis of said prior stage message state and said message performance results; and

(d) generating a current message allocation based on said current message state;

wherein said cumulative number of trials and said cumulative number of successes comprise discounted cumulative number of trials and discounted cumulative number of successes.

79. A computer program for use in conjunction with a computer system, the computer program comprising a computer program mechanism embedded therein, the computer program mechanism, comprising:

a program module that directs the computer system to improving the stage-to-stage performance of a message in a multi-stage message, the program module including tangible instructions for performing a method comprising;

(a) reading prior stage message state pertaining to a prior stage in a message campaign;

said prior stage message state including a cumulative number of trials and a cumulative number of successes for a particular message at the end of said prior stage;

(b) reading message performance results representing message trials and message successes from said prior stage based on said prior stage message state;

(c) computing a current message state on the basis of said prior stage message state and said message performance results;

(d) generating a current message allocation based on said current message state;

(e) storing said current message state as prior stage message state for a next iteration of said method; and

(f) repeating steps (a)–

(c) for each stage in said message campaign;

wherein said cumulative number of trials and said cumulative number of successes comprise discounted cumulative number of trials and discounted cumulative number of successes;

wherein said prior stage message state comprises reading a state vector for the prior stage in a message campaign;

wherein said step of generating a current message allocation further includes applying a message allocation constraint; and

wherein said message selected from the group of messages consisting of an advertisement, an email, and combinations thereof.

80. A computer system comprising:

a server having a processor and a memory coupled to said processor;

an internet interface means for coupling said processor to the internet;

means for receiving performance results from a message service coupled to said internet;

means for transmitting a message allocation to said message service;

a message optimization procedure implemented as a computer program and comprising a computer program mechanism embedded therein and stored in said memory and executing in said processor;

said computer program mechanism, comprising a program module that directs the computer system to improving the stage-to-stage performance of a message in a multi-stage message, the program module including tangible instructions for performing a method comprising;

(a) reading prior stage message state pertaining to a prior stage in a message campaign;

said prior stage message state including a cumulative number of trials and a cumulative number of successes for a particular message at the end of said prior stage;

(b) reading message performance results representing message trials and message successes from said prior stage based on said prior stage message state;

(c) computing a current message state on the basis of said prior stage message state and said message performance results; and

(d) generating a current message allocation based on said current message state.