Methods and systems for ad placement planning

Abstract

Methods and systems are disclosed which allow shifting inventory to fulfill guaranteed delivery advertisement contracts. Inventory may be allocated from a supply of unallocated inventory to one or more advertisers in accordance with guaranteed delivery agreements. Inventory may be reserved for the one or more advertisers from the remaining supply of unallocated inventory. Inventory may then be allocated to an additional advertiser by using unallocated inventory or shifted inventory, or a combination of unallocated inventory and shifted inventory. The shifted inventory is shifted out of the allocation for the first advertiser and the shifted inventory is replaced by the reserve inventory for the respective advertiser.

1 . A computerized method comprising:
 allocating an inventory of advertising impressions from a plurality of supply nodes to satisfy a demand for advertising impressions received from a plurality of demand nodes, wherein each demand node receives an allocation from at least some of the plurality of supply nodes, and wherein the inventory is allocated in accordance with advertiser targeting criteria associated with each demand node, respectively;   determining a reserve inventory of unallocated advertising impressions for each demand node such that, for each supply node, unallocated advertising impressions are partitioned for allocation among the demand nodes receiving an allocation from a supply node proportionally to the supply node's allocated inventory; and   allocating, for each new demand node, an additional inventory of advertising impressions, wherein the additional inventory satisfies advertiser targeting criteria associated with a new demand node and also satisfies advertiser targeting criteria associated with at least one other demand node, by shifting supply to accommodate the new demand node using a combination of unallocated inventory and shifted inventory, wherein the shifted inventory is shifted out of at least one other demand node's allocation, and wherein the shifted inventory is replaced by the reserve inventory partitioned for allocation to the at least one other demand node.   
     
     
         2 . The method of  claim 1 , further comprising modeling inventory allocation as a bipartite graph such that eligibility edges between the plurality of supply nodes and the plurality of demand nodes depict how much inventory is available for each demand node. 
     
     
         3 . The method of  claim 2 , wherein each demand node is connected via an eligibility edge to one or more eligible supply nodes based at least on advertiser targeting criteria associated with each demand node, respectively. 
     
     
         4 . The method of  claim 2 , wherein, for each eligibility edge, an allocation is represented by a fraction which specifies that an amount of inventory is reserved for a demand node. 
     
     
         5 . The method of  claim 1 , wherein each demand node has an associated demand which is a number of requested advertising impressions. 
     
     
         6 . The method of  claim 5 , wherein, the inventory of advertising impressions is divided among the plurality of demand nodes such that all demands for requested advertising impressions are met. 
     
     
         7 . The method of  claim 1 , wherein each supply node includes an associated weight that is a forecast for a number of impressions of a particular type. 
     
     
         8 . The method of  claim 1 , wherein, for a query demand node, a set of eligible impressions inside a query region are considered to be inside impressions, and other impressions outside the query region are considered to be outside impressions, and wherein for each demand node there is at least some reserved inventory, R j , available for shifting, such that up to R j  inventory currently allocated to a demand node may be shifted from inside impressions to outside impressions. 
     
     
         9 . The method of  claim 8 , wherein, for each demand node, if an amount of outside impressions, R′ j , is greater than an amount of currently allocated inside impressions, then all of the allocation is shifted outside the query region, and wherein if R′ j  is less than the amount of currently allocated inside impressions, then R′ j  is shifted outside the query region. 
     
     
         10 . The method of  claim 1 , further comprising:
 determining an amount of supply that must be shifted to accommodate a demand that cannot be accommodated without changing a previous allocation; and   splitting the amount of supply that must be shifted among allocated inventory proportional to a total amount of allocated inventory that each demand node is able to shift.   
     
     
         11 . A system comprising:
 one or more databases;   one or more server computers in communication with the one or more databases, the one or more server computers configured to:   allocate an inventory of advertising impressions from a plurality of supply nodes to satisfy a demand for advertising impressions received from a plurality of demand nodes, wherein each demand node receives an allocation from at least some of the plurality of supply nodes, and wherein the inventory is allocated in accordance with advertiser targeting criteria associated with each demand node, respectively;   determine a reserve inventory of unallocated advertising impressions for each demand node such that, for each supply node, unallocated advertising impressions are partitioned for allocation among the demand nodes receiving an allocation from a supply node proportionally to the supply node's allocated inventory; and   allocate, for each new demand node, an additional inventory of advertising impressions, wherein the additional inventory satisfies advertiser targeting criteria associated with a new demand node and also satisfies advertiser targeting criteria associated with at least one other demand node, by shifting supply to accommodate the new demand node using a combination of unallocated inventory and shifted inventory, wherein the shifted inventory is shifted out of at least one other demand node's allocation, and wherein the shifted inventory is replaced by the reserve inventory partitioned for allocation to the at least one other demand node.   
     
     
         12 . The system of  claim 11 , further comprising modeling inventory allocation as a bipartite graph such that eligibility edges between the plurality of supply nodes and the plurality of demand nodes depict how much inventory is available for each demand node. 
     
     
         13 . The system of  claim 12 , wherein each demand node is connected via an eligibility edge to one or more eligible supply nodes based at least on advertiser targeting criteria associated with each demand node, respectively. 
     
     
         14 . The system of  claim 12 , wherein, for each eligibility edge, an allocation is represented by a fraction which specifies that an amount of inventory is reserved for a demand node. 
     
     
         15 . The system of  claim 11 , wherein each demand node has an associated demand which is a number of requested advertising impressions. 
     
     
         16 . The system of  claim 15 , wherein, the inventory of advertising impressions is divided among the plurality of demand nodes such that all demands for requested advertising impressions are met. 
     
     
         17 . The system of  claim 11 , wherein each supply node includes an associated weight that is a forecast for a number of impressions of a particular type. 
     
     
         18 . The system of  claim 11 , wherein, for a query demand node, a set of eligible impressions inside a query region are considered to be inside impressions, and other impressions outside the query region are considered to be outside impressions, and wherein for each demand node there is at least some reserved inventory, R j , available for shifting, such that up to R j  inventory currently allocated to a demand node may be shifted from inside impressions to outside impressions. 
     
     
         19 . The system of  claim 18 , wherein, for each demand node, if an amount of outside impressions, R′ j , is greater than an amount of currently allocated inside impressions, then all of the allocation is shifted outside the query region, and wherein if R′ j  is less than the amount of currently allocated inside impressions, then R′ j  is shifted outside the query region. 
     
     
         20 . The system of  claim 11 , further comprising:
 determining an amount of supply that must be shifted to accommodate a demand that cannot be accommodated without changing a previous allocation; and   splitting the amount of supply that must be shifted among allocated inventory proportional to a total amount of allocated inventory that each demand node is able to shift.   
     
     
         21 . A computer program product embedded in a non-transitory computer readable medium comprising instructions executable by a computer processor for ad placement planning, the instructions being executable by a computer processor to execute processing comprising:
 allocating an inventory of advertising impressions from a plurality of supply nodes to satisfy a demand for advertising impressions received from a plurality of demand nodes, wherein each demand node receives an allocation from at least some of the plurality of supply nodes, and wherein the inventory is allocated in accordance with advertiser targeting criteria associated with each demand node, respectively;   determining a reserve inventory of unallocated advertising impressions for each demand node such that, for each supply node, unallocated advertising impressions are partitioned for allocation among the demand nodes receiving an allocation from a supply node proportionally to the supply node's allocated inventory; and   allocating, for each new demand node, an additional inventory of advertising impressions, wherein the additional inventory satisfies advertiser targeting criteria associated with a new demand node and also satisfies advertiser targeting criteria associated with at least one other demand node, by shifting supply to accommodate the new demand node using a combination of unallocated inventory and shifted inventory, wherein the shifted inventory is shifted out of at least one other demand node's allocation, and wherein the shifted inventory is replaced by the reserve inventory partitioned for allocation to the at least one other demand node.