Mechanism for allocating advertisements of varying intervals

• US 20060253319A1
• Filed: 05/04/2005
• Published: 11/09/2006
• Est. Priority Date: 05/04/2005
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Mahdian, Mohammad, Borgs, Christian H., Chayes, Jennifer T., Saberi, Amin, Immorlica, Nicole S., Feige, Uriel M.
• Application Number:
  US11/122,281
• Publication Number:
  US 20060253319A1
• Time in Patent Office: Days
• US Class Current: 705/14.520
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/0254 based on statistics
• CPC Class Codes: G06Q 30/0275 Auctions
• CPC Class Codes: G06Q 30/08 Auctions

Abstract

The subject invention leverages determined values of auction advertisement proposals to facilitate in determining advertisement interval allocations for the proposals. The advertisement “interval” can include, but is not limited to, physical dimensions or time. Instances of the subject invention further utilize allocation algorithms and auctioning mechanisms to provide for allocation of ads of varying intervals and to improve performance of ad auctions, including employing algorithms that automate the ad interval layout to maximize revenue. Other instances of the subject invention provide pricing for the allocated intervals as well.

Claims

1. A system that facilitates advertisement interval allocations for auctions, comprising:

a value component that receives information relating to advertisement proposals and determines values for the proposals; and

an allocation component that employs an allocation mechanism to determine advertisement allocations of varying intervals utilizing the proposal values.

2. The system of claim 1, the intervals comprising time and/or physical dimensions.

3. The system of claim 1, the allocation component utilizes an allocation mechanism that assumes an overall interval to be a small constant and determines a welfare-maximizing allocation where advertisers are allowed to submit multiple advertisements.

4. The system of claim 1, the allocation component utilizes an allocation mechanism that assumes that each advertiser submits only one advertisement and determines a welfare-maximizing allocation via a universal ordering on a set of advertisements where the maximum welfare of a feasible subset of the advertisements is realized by the universal ordering restricted to that subset.

5. The system of claim 1, the allocation component utilizes an allocation mechanism that employs a 2-approximation to determine a welfare-maximal allocation in polynomial time.

6. The system of claim 1, the allocation component utilizes an allocation mechanism that employs a greedy heuristic to determine a welfare-maximal allocation.

7. The system of claim 1, the value component utilizes, in part, click-through-rates (CTR) to facilitate in determining the proposal values.

8. The system of claim 7 further comprising:

a click-through-rate (CTR) determination component that determines a click-through-rate utilized by the value component;

the click through rate indicating the probability that the advertisement receives a click.

9. The system of claim 8, the CTR determination component employs a model where an ad A placed in intervals i, i+1, . . . with k competing ads displayed in slots 1 through i−

1 is an arbitrary function of A, i, and k.

10. The system of claim 8, the CTR determination component employs a model where an ad A placed in intervals i, i+1, . . . with k competing ads displayed in slots 1 through i−

1 is an arbitrary function of A and i.

11. The system of claim 8, the CTR determination component employs a model where each ad A has a normalized click-through-rate and an actual click-through-rate of an ad A occupying interval slots i through j with k competing ads displayed in interval slots 1 through i−

1 and is estimated by CTR_ijk(A)=α

_ijk*CTR(A), where α

_ijk are scaling factors independent of the ad A, CTR(A) is the probability that ad A receives a click when it is displayed at the top and/or beginning of an ad interval, and a value of ad A is denoted by s(A)=CPC(A)*CTR(A).

12. The system of claim 8, the CTR determination component employs a model where each ad A has a normalized click-through-rate and an actual click-through-rate of an ad A occupying interval slots i through j with k competing ads displayed in interval slots 1 through i−

1 and is estimated by CTR_ijk(A)=α

_ijk*CTR(A), where α

_ijk are scaling factors that depend only on k, CTR(A) is the probability that ad A receives a click when it is displayed at the top and/or beginning of an ad interval, and a value of ad A is denoted by s(A)=CPC(A)*CTR(A).

13. The system of claim 8, the CTR determination component employs a model where each ad A has a normalized click-through-rate and an actual click-through-rate of an ad A occupying interval slots i through j with k competing ads displayed in interval slots 1 through i−

1 and is estimated by CTR_ijk(A)=α

_ijk*CTR(A), where α

_ijk=(β

_i+ . . . β

_j)/(j−

i+1) and β

₁, . . . , β

_L are scaling factors and α

_ijk is independent of k and equal to an average of a scaling factor for interval slots that an ad occupies, CTR(A) is the probability that ad A receives a click when it is displayed at the top and/or beginning of an ad interval, and a value of ad A is denoted by s(A)=CPC(A)*CTR(A).

14. The system of claim 8, the click-through-rate is dependent on a total number of advertisements allotted in a total advertisement interval.

15. The system of claim 1 further comprising:

a pricing component that facilitates in determining pricing for the advertisement allocations determined by the allocation component.

16. The system of claim 15, the pricing component utilizes, at least in part, a Vickrey-Clark-Groves (VCG) method to facilitate in determining pricing for the advertisement allocations.

17. A method for facilitating advertisement interval allocations for auctions, comprising:

receiving information relating to advertisement proposals;

determining values for the advertisement proposals; and

determining advertisement allocations of varying intervals utilizing the proposal values.

18. The method of claim 17 further comprising:

utilizing a click-through-rate to facilitate in determining the values for the proposals;

the click-through-rate indicating a probability that a proposed advertisement receives a click.

19. The method of claim 17, the intervals comprising time and/or physical dimensions.

20. The method of claim 17 further comprising:

determining pricing for the advertisement allocations utilizing, at least in part, a Vickrey-Clark-Groves (VCG) method.