Inventory allocation for advertising with changeable supply landscape

1. An advertisement impression distribution system, comprising:

a data processing system including a processor and memory,

the data processing system programmed to generate, as goal programming, an allocation plan for serving a number of advertisement impressions eligible to meet a demand of a plurality of advertisers, the allocation plan to allocate a first portion of advertisement impressions to satisfy guaranteed demand arising from pre-arranged contracts and a second portion of advertisement impressions to satisfy non-guaranteed demand auctioned in real time in an advertisement spot market, as the advertisement impressions become available,

where the guaranteed and non-guaranteed demands comprise competing demands for advertisement impressions having overlapping targeting attributes that target features matching advertiser targeting profiles in a high-dimensional targeting space, and the number of advertisement impressions are changeable as a result of one or more events;

where the data processing system includes an optimizer, the optimizer programmed to:

establish a relationship between the first portion of advertisement impressions and the second portion of advertisement impressions, the relationship defining a range of possible proportions of allocation of the first portion of advertisement impressions and the second portion of advertisement impressions; and

impose multiple objectives on the relationship, comprising:

maximizing guaranteed demand representativeness through proportionate allocation of advertisement impressions to advertisers with advertisements containing attributes matching the impressions; and

moderating an increase in the number of advertisement impressions available for allocation to the first and second portions, to minimize a cost associated with reducing a quality of the advertisement impressions as a volume of the advertisement impressions increases;

solve for a first of the objectives, resulting in a first requirement, then solve for a second of the objectives to generate a second requirement while relaxing the first requirement, where relaxing is to allow departure from a determined optimum value;

where the data processing system is further programmed to output the allocation plan to an ad serving module of the data processing system to control serving of the advertisement impressions according to the range of possible proportions of allocation between the first and the second portions.

2. The system of claim 1 , where the one or more events that cause the advertisement impressions to change comprise one or more of:

changing a score threshold for qualifying a user into a specified interest category;

changing navigational links on a web page; and

dynamically changing displayed content on a web page;

where the interest category depends on user behavior, and where the cost of the advertisement impressions comprises a cost associated with a function that increases with an increase in the number of advertisement impressions.

3. The system of claim 1 , where the multiple objectives further comprise: maximizing non-guaranteed demand revenue from non-guaranteed contracts of advertisers, and minimizing under-delivery penalties that result from not fulfilling guaranteed contract delivery requirements.

4. The method of claim 3 , where the first requirement comprises a minimum penalty cost and the second requirement comprises a maximum non-guaranteed demand revenue, and where relaxing the first requirement comprises allowing the first requirement to be greater than the solved minimum penalty cost.

5. The method of claim 3 , where the optimizer is further programmed to:

solve a third objective to generate a third requirement while relaxing one or more of the first and second requirements.

6. The system of claim 5 , where the first requirement comprises a maximum non-guaranteed demand revenue, the second requirement comprises a minimum penalty cost, and the third requirement comprises a maximum guaranteed demand representativeness, and where relaxing the one or more of the first and second requirements comprises one or more of:

allowing the first requirement to be less than the solved maximum non-guaranteed demand revenue; and

allowing the second requirement to be greater than the solved minimum penalty cost.

7. The system of claim 5 , further comprising:

solving a fourth objective to generate a fourth requirement while relaxing one or more of the first, second, and third requirements.

8. The system of claim 7 , where the first, second, and third requirements comprise a minimum penalty cost, a maximum non-guaranteed demand revenue, and a minimum supply cost of the advertising impressions in any order, and where the fourth requirement comprises a maximum guaranteed demand representativeness.

9. The system of claim 8 , where the first through fourth objectives are ordered according to priority and the highest priority objective is solved first.

10. The system of claim 3 , where the optimizer is further programmed to:

combine the under-delivery penalties, the non-guaranteed demand revenue, and the supply cost of the advertisement impressions using a weighted sum of monetary objectives, the method further including:

first optimizing the monetary objectives; and

next optimizing the guaranteed demand representativeness.

11. A method for distributing advertisement impressions, the method executable by a data processing system having a processor and memory, and in the memory stored instructions, comprising:

generating, with the system through execution of the instructions and as goal programming, an allocation plan for serving a number of advertisement impressions eligible to meet a demand of a plurality of advertisers, the allocation plan to allocate a first portion of advertisement impressions to satisfy guaranteed demand arising from pre-arranged contracts and a second portion of advertisement impressions to satisfy non-guaranteed demand auctioned in real time in an advertisement spot market, as the advertisement impressions become available,

where the guaranteed and non-guaranteed demands comprise competing demands for advertisement impressions having overlapping targeting attributes that target features matching advertiser targeting profiles in a high-dimensional targeting space, and the number of advertisement impressions being changeable as a result of one or more events, where generating comprises:

establishing a relationship between the first portion of advertisement impressions and the second portion of advertisement impressions, the relationship defining a range of possible proportions of allocation of the first portion of advertisement impressions and the second portion of advertisement impressions; and

imposing multiple objectives on the relationship, comprising:

maximizing guaranteed demand representativeness through proportionate allocation of advertisement impressions to advertisers with advertisements containing attributes matching the impressions; and

moderating an increase in the number of advertisement impressions available for allocation to the first and second portions, to minimize a cost associated with reducing a quality of the advertisement impressions as a volume of the advertisement impressions increases;

solving for a first of the objectives, resulting in a first requirement, followed by solving for a second of the objectives to generate a second requirement while relaxing the first requirement, where relaxing is to allow departure from a determined optimum value; and

outputting the allocation plan to an ad serving module of the system through execution of the instructions, to control serving of the advertisement impressions according to the range of possible proportions of allocation between the first and the second portions.

12. The method of claim 11 , where the one or more events that cause the advertisement impressions to change comprise one or more of:

changing a score threshold for qualifying a user into a specified interest category;

changing navigational links on a web page; and

dynamically changing displayed content on a web page;

where the interest category depends on user behavior, and where the cost of the advertisement impressions comprises a cost associated with a function that increases with an increase in the number of advertisement impressions.

13. The method of claim 11 , where the multiple objectives further comprise: maximizing non-guaranteed demand revenue from non-guaranteed contracts of advertisers, and minimizing under-delivery penalties that result from not fulfilling guaranteed contract delivery requirements.

14. The method of claim 13 , where the first requirement comprises a minimum penalty cost and the second requirement comprises a maximum non-guaranteed demand revenue, and where relaxing the first requirement comprises allowing the first requirement to be greater than the solved minimum penalty cost.

15. The method of claim 13 , further comprising:

solving a third objective to generate a third requirement while relaxing one or more of the first and second requirements.

16. The method of claim 15 , where the first requirement comprises a maximum non-guaranteed demand revenue, the second requirement comprises a minimum penalty cost, and the third requirement comprises a maximum guaranteed demand representativeness, and where relaxing the one or more of the first and second requirements comprises one or more of:

allowing the first requirement to be less than the solved maximum non-guaranteed demand revenue; and

allowing the second requirement to be greater than the solved minimum penalty cost.

17. The method of claim 15 , further comprising:

solving a fourth objective to generate a fourth requirement while relaxing one or more of the first, second, and third requirements.

18. The method of claim 17 , where the first, second, and third requirements comprise a minimum penalty cost, a maximum non-guaranteed demand revenue, and a minimum supply cost of the advertising impressions in any order, and where the fourth requirement comprises a maximum guaranteed demand representativeness.

19. The method of claim 17 , where the first through fourth objectives are ordered according to priority and the highest priority objective is solved first.

20. The method of claim 13 , further comprising:

combining the under-delivery penalties, the non-guaranteed demand revenue, and the supply cost of the advertisement impressions using a weighted sum of monetary objectives, the method further including:

first optimizing the monetary objectives; and

next optimizing the guaranteed demand representativeness.