ITERATIVE PROCESS FOR LARGE SCALE MARKETING SPEND OPTIMIZATION

A facility comprising systems and methods for calculating, for a given budget, an allocation of resources to improve a particular outcome, such as revenue, profit, target miss, etc. The facility takes advantage of first-order derivate information and can decrease both the computation time and memory use in the calculation of suggested spends or allocations, such as the amount of marketing resources to be allocated to various marketing channels. The facility comprises techniques for 1) determining, for a given budget and a response model, resource allocations that will improve the modeled business outcome, 2) determining, for a given budget and revenue response model, resource allocations that will increase profits, and 3) determining, for a given budget, a given set of revenue response models, and a given set of revenue targets, resource allocations that will reduce total target misses.

DETAILED DESCRIPTION

A facility comprising improved systems and methods for calculating, for a given budget, an allocation of resources to improve a particular outcome, such as revenue, profit, target miss, etc., is provided. The facility takes advantage of first-order derivate information and can decrease both computation time and memory use in the calculation of suggested spends or allocations, such as the amount of marketing resources to be allocated to various marketing channels. The facility comprises techniques for 1) determining, for a given budget and a response model, resource allocations that will improve the modeled business outcome, 2) determining, for a given budget and revenue response model, resource allocations that will increase profits, and 3) determining, for a given budget, a given set of revenue response models, and a given set of revenue targets, resource allocations that will reduce total target misses (i.e., the lesser of zero and the difference between a revenue target and the revenue determined by the model) for a set of revenue types or sources. In some embodiments, the generated allocations or spends are constrained to the set of allocations or spends that are consistent with a defined set of constraints. The disclosed techniques can be invoked periodically (e.g., hourly, daily, weekly, monthly, quarterly, yearly) to provide regular and dynamic updates to resource allocations based at least in part on current model data.

In some embodiments, the facility iteratively applies the Dorfman-Steiner rule or its variants—which states that an optimal level of advertising occurs when the ratio of advertising to sales is equal to the ratio of the advertising elasticities to the price elasticity or some function of them—to find an allocation of resources that will improve or optimize a particular business outcome based at least in part on a response model for that outcome. Starting with a set of spends (i.e., resource allocations), such as a company's current allocation of marketing resources, the facility solves, at each iteration, an approximation of a response model, such as a Cobb-Douglas approximation model (or its variants), or other suitable approximation models, based at least in part on the spends and their associated elasticities. The “solution” to the approximation is another set of spends that improves the predicted outcome of the response model. If a newly generated set of spends does not improve a predicted outcome over a previous sets of spends beyond a predetermined threshold, then the new set of spends is provided as an optimal (or near optimal) set of spends for the particular business outcome. The predetermined threshold can be specified, for example, by a user or by the facility. The nearer the predetermined threshold is to zero, the more likely a final set of new spends will correspond to an optimal allocation. “Near optimal” refers to an improvement between spends that satisfies the predetermined threshold. The new spends can then be employed to improve the relevant business outcome. For example, the facility may determine that a company currently allocating 30% of its marketing budget to television and 70% of its marketing budget to online marketing would find better results (e.g., increased revenue) if the company were to allocate 50% of its marketing budget to television marketing and 50% to online marketing. Assuming that the response model and elasticities are non-decreasing, spends generated by each iteration will provide a better solution than the set of spends generated by a previous iteration. Accordingly, each generated set of spends can be further processed to find another improved set of spends.

In some embodiments, the facility determines an allocation of resources that will provide an optimal (or near optimal) level of profits (revenue minus costs) for a given set of constraints and revenue response model. The facility initially creates a “fake” or “dummy” spend corresponding to resources that are effectively “saved” or not allocated to marketing efforts. Rather, these resources are, for the sake of the response model, allocated to or “spent on” a marketing budget surplus. The facility then updates the constraints to take into account the fake spend by, for example, constraining the sum of all marketing spends and the fake spend to the upper bound on spends (e.g., a marketing budget). For example, the constraint

could be updated to

The facility employs the marketing optimization technique described above (and further described below) using the fake spend and the updated constraints to determine an allocation of resources, including an allocation to a budget surplus, that provides an optimal (or near optimal) revenue.

In some embodiments, the facility determines an allocation of resources that will provide a minimal (or near minimal) total target miss for a given budget, a given set of response models, and a given set of revenue targets. A target miss is the difference between a revenue target and a corresponding revenue prediction for a set of spends based at least in part on a response model. If the predicted or actual revenue is greater than or equal to the target, then there is no target miss (i.e., the target miss is 0). A total target miss is the sum of a set of target misses. For example, a company may expect to collect or target $500,000 in revenue from in-store sales and $750,000 in revenue from online sales and may allocate resources to marketing efforts to achieve these goals. Using corresponding response models (i.e., an in-store revenue response model and an online revenue response model) and a set of spends, the target misses can be calculated. For example, if the models predict, for a current spend, $300,000 in revenue from in-store sales and $700,000 in revenue from online sales, the company would miss its in-store revenue target by $200,000 and its online revenue target by $50,000, with a total target miss of $250,000. The facility takes advantage of an iterative application of the Dorman-Steiner rule (discussed above and further discussed below) along with optimization techniques, such as a gradient descent method, a bundle level method (further discussed below), or other suitable methods, to find an allocation of resources that, for a given set of revenue response model and associated targets, provides a minimal (or near minimal) total target miss. The facility repeatedly generates sets of spends and tests those spends against the targets. If a newly generated set of spends does not result in a total target miss that is less than the total target miss for a previously generated set of spends by at least a predetermined threshold, then the new set of spends are provided as an optimal (or near optimal) set of spends and the resulting target miss is provided as a minimal (or near minimal) target miss. The predetermined threshold can be specified, for example, by a user or by the facility itself. The nearer the predetermined threshold is to zero, the more likely a final set of new spends will have a minimal target miss. “Near minimal” refers to an improvement between target misses for different sets of spends that satisfies the predetermined threshold.

FIG. 1is a block diagram illustrating an environment100in which a facility in accordance with an embodiment of the disclosed technology may operate. In this example, environment100includes server computer110, customer computers130, and network140. Server computer110includes facility120comprising a create constraint tree component121, an allocate component122, an approximate component123, a profit component124, a hit-target component125, a gradient descent component126, a bundle level component127, and a spend data store128. The construct constraint tree component121is invoked to generate a constraint tree based at least in part on a set of constraints, each constraint including a lower bound, an upper bound, and one or more spend categories. The allocate component122is invoked to determine a valid allocation of resources (i.e., an allocation of resources that conforms to a particular set of constraints) for a given response model that will result in an optimal (or near optimal) level of output for the response model. The approximate component123is invoked to generate a set of spends based at least in part on a constraint tree node and its associated tree, a budget, a set of elasticities, and another set of spends. The profit component124is invoked to determine a valid allocation of resources (i.e., consistent with a given set of constraints) that provides an optimal (or near optimal) profit level. The hit-target component125is invoked to find the allocation of resources that reduces the total target miss for a given budget and set of response models to a minimal (or near minimal) level. The gradient descent component126is invoked to generate or update a set of spends based at least in part on a budget, a constraint tree, a set of revenue response models (one for each revenue type), and a set of targets (one for each revenue type). The bundle level component127is invoked to generate or update a set of spends based at least in part on a budget, a constraint tree, a set of revenue response models (one for each revenue type), and a set of targets (one for each revenue type). Spend data stores118and131store spend information, such as various resource allocations over time, spend schedules, updates schedules and so on. In some embodiments, components of the facility120may be distributed between the server computer110and the client computers130. For example, instances of any of the constraint tree component121, the allocate component122, the approximate component123, the profit component124, the hit-target component125, the gradient descent component126, and/or the bundle level component127may reside at one or more customer computers130. In some embodiments, communication between computers may occur via the network140or directly via wired or wireless communication connection (e.g., radio frequency, WiFi, BLUETOOTH).

The computing devices on which the disclosed systems are implemented may include a central processing unit, memory, input devices (e.g., keyboard and pointing devices), output devices (e.g., display devices), and storage devices (e.g., disk drives). The functions or algorithms described herein are implemented in hardware, and/or software in embodiments. The software comprises computer executable instructions on computer readable media. Non-transitory computer-readable media include tangible media such as hard drives, CD-ROMs, DVD-ROMS, and memories such as ROM, RAM, and Compact Flash memories that can store instructions. Signals on a carrier wave such as an optical or electrical carrier wave are examples of transitory computer-readable media. Further, such functions correspond to modules, which are software, hardware, firmware, or any suitable combination thereof. Multiple functions are performed in one or more modules as desired, and the embodiments described are merely examples. A digital signal processor, ASIC, microprocessor, or any other suitable type of processor operating on a system, such as a personal computer, server computer, supercomputing system, a router, or any other device capable of processing data including network interconnection devices executes the software. Instructions, data structures, and message structures may be transmitted via a data transmission medium, such as a signal on a communications link and may be encrypted. Various communications links may be used, such as the Internet, a local area network, a wide area network, a point-to-point dial-up connection, a cell phone network, and so on.

Many embodiments of the technology described herein may take the form of computer-executable instructions, including routines executed by a programmable computer. Those skilled in the relevant art will appreciate that aspects of the technology can be practiced on computer systems other than those shown and described herein. Embodiments of the technology may be implemented in and used with various operating environments that include personal computers, server computers, handheld or laptop devices, multiprocessor systems, microprocessor-based systems, programmable consumer electronics, digital cameras, network PCs, minicomputers, mainframe computers, computing environments that include any of the above systems or devices, and so on. Moreover, the technology can be embodied in a special-purpose computer or data processor that is specifically programmed, configured or constructed to perform one or more of the computer-executable instructions described herein. Accordingly, the terms “computer” or “system” as generally used herein refer to any suitable data processor and can include Internet appliances and handheld devices (including palmtop computers, wearable computers, cellular or mobile phones, multi-processor systems, processor-based or programmable consumer electronics, network computers, mini computers and the like). Information handled by these computers can be presented at any suitable display medium, including a CRT display or LCD.

The technology can also be practiced in distributed environments, where tasks or modules are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules or subroutines may be located in local and remote memory storage devices. Aspects of the technology described herein may be stored or distributed on computer-readable media, including magnetic or optically readable or removable computer disks, as well as distributed electronically over networks. Data structures and transmissions of data particular to aspects of the technology are also encompassed within the scope of the technology.

FIG. 2Ais a data structure diagram illustrating a set of constraints in accordance with an embodiment of the disclosed technology. In this example, data structure280contains four constraints281,282,283, and284. Constraint281is associated with four spends: spend1, spend2, spend3, and spend4and has a lower bound of 20 and an upper bound of 100 (e.g., dollars). Thus, the maximum allocation of resources to the sum of spend1+spend2+spend3+spend4should be 100, and the minimum allocation of resources to this sum should be 20. Constraint282is associated with two spends, spend1and spend2and has a lower bound of 10 and an upper bound of 50. Constraint283is associated with one spend, spend2, and has a lower bound of 5 and an upper bound of 25. Constraint284is associated with one spend, spend4, and has a lower bound of 5 and an upper bound of 40. One skilled in the art will recognize that whileFIG. 2Aprovides an illustration that is easily comprehensible by a human reader, the constraint information may be stored using any suitable data structure and/or suitable data organization techniques.

FIG. 2Bis a flow diagram illustrating the processing of a construct constraint tree component in accordance with an embodiment of the disclosed technology. The construct constraint tree component generates a constraint tree based at least in part on a set of constraints, each constraint having an associated lower bound, upper bound, and one or more spends (the lower bound and upper bound represent the constraints on the sum of the associated spend categories). The lower bound corresponds to the least amount that should be allocated to the associated spend or combination of spends, while the upper bound corresponds to the most that should be allocated to the associated spend or combination of spends. In other words, the lower bound and upper bound establish a range of values for allocations to a particular spend or combination of spends that are acceptable for, for example, a marketing department or other budget setting entity. In block205, the component sorts the constraints from constraints with the largest number of associated spends to constraints with the smallest number of associated spends. For example, a constraint on spend1+spend2has two associated spends (spend1and spend2) while a constraint on

has n associated spend categories (spend1, . . . , spend2). In block210, the component selects the next constraint, starting with the constraint having the largest number of associated spends. In decision block215, if a root node for the constraint tree has already been created, then the component continues at decision block225, else the component continues at block220. In block220, the component uses the selected constraint to create the root node and then continues at decision block255. In decision block225, if the number of spends associated with the current constraint are not less than the number of spends associated with the root node, then the component returns an error message, else the component continues at block230. In block230, the component identifies all potential parent nodes for the selected constraint. The potential parent nodes include all nodes that include any of the spends associated with the current constraint and that do not have any child nodes that include any of the spends associated with the currently selected constraint. For example, inFIG. 2Cnode292would qualify as a potential parent node for a constraint on spend1. Although node291also includes or is associated with spend1, node291would not qualify as a potential parent node for a constraint associated with spend1because node291has a child node that includes spend1(i.e., node292). In decision block235, if the number of identified potential parent nodes is not equal to one, then the component returns an error message, else the component continues at decision block240. In decision block240, if the identified potential parent node does not include all of the spends associated with the current constraint, then the component returns an error message, else the component continues at block245. In block245, the component uses the selected constraint to create a new node. In block250, the component sets the new node as a child of the identified potential parent node. In decision block255, if there are additional constraints, then the component loops back to block210to select the next constraint, else the component returns the constraint tree and completes. In some embodiments, the facility creates a node using a constraint by, for example, instantiating a node object and storing in the node object information corresponding to the associated spend, lower bound, and upper bound.

FIG. 2Cis a display diagram illustrating a constraint tree in accordance with an embodiment of the disclosed technology. Constraint tree290was generated based at least in part on the constraints provided in data structure280(FIG. 2A) and includes root node291, corresponding to constraint281and nodes292-294, each corresponding one of the constraints282-284. One skilled in the art will recognize that whileFIG. 2Cprovides an illustration that is easily comprehensible by a human reader, the actual information may be stored using different data structures and/or data organizations.

FIG. 3is a flow diagram illustrating the processing of an allocate component in accordance with an embodiment of the disclosed technology. The allocate component is invoked to determine a valid allocation of resources (i.e., an allocation of resources that conforms to a particular set of constraints) for a given response model that will result in an optimal (or near optimal) level of output for the response model (F). In block310, the component initializes a counting variable k to one. In block320, the component determines the current vector or set of spends (currentspends). The initial currentspends correspond to how a particular entity is currently allocating resources or how the entity has allocated resources in the past. For example, a company or client may provide an indication of how they are (or have) allocated resources to different channels (e.g., marketing channels). This information may be retrieved periodically and may be stored for later use. In block330, the component determines elasticities for each of the current spends X[1], . . . , X[n] based at least in part on, for example, the following formula:

where F represents a response model, X[1], . . . , X[n] represents a set of spends (and the inputs to the response model) (e.g., currentspends), and

represents the partial derivative of the response model with respect to a particular spend. Each elasticity represents the change in the outcome of the response model due to a change in a particular spend. In block340, the component invokes an approximate component. The approximate component generates a new set of spends (newspends) based at least in part on the root node of the constraint tree, a “maxspend” (i.e., the upper bound of the root node), the current spends (currentspends), and the calculated elasticities (elasticities). The approximate component, as discussed in further detail below with respect toFIG. 4, generates newspends based at least in part on an iterative Dorfman-Steiner algorithm or its variants. In decision block350, if k is less than K (a predetermined maximum number of iterations), then the component continues at decision block360, else the component returns the generated spends (newspends). In decision block360, if the invocation of the approximate component results in convergence, then the component returns the generated spends (newspends), else the component continues at block370. Convergence occurs, for example, when either

where each of ε and ε′ are predetermined tolerances or thresholds. In other words, the allocation component continues processing unless either the distance between newspends (a vector of spends) and currentspends (a vector of spends) is less than or equal to a predetermined threshold or if the difference between the output of the response model with newspends as inputs and the output of the response model with currentspends as inputs is less than or equal to a predetermined threshold or the number of iterations (k) reaches a predetermined maximum number (K). The lower the predetermined thresholds, the more likely the component will provide an optimal allocation of resources (i.e., set of spends). In block370, the component replaces currentspends with newspends. In block380, the component increments the counting variable k by 1 (k=k+1) and then loops back to block330to determine the elasticities for the updated currentspends.

FIG. 4is a flow diagram illustrating the processing of an approximate component in accordance with an embodiment of the disclosed technology. The approximate component is invoked to generate a set of spends (newspends) based at least in part on a constraint tree node (node) and its associated tree, a budget, a set of elasticities, and a set of spends (spends). In block405, the component solves for an adjustment factor, v based at least in part on, for example, the following formula:

where n is a node within a constraint tree, K represents the number of n's children, nlbrepresents n's lower bound, nubrepresents n's upper bound, nirepresents a child of n, andnspendscomprises all of the spends within n that are not part of or associated with any of n's children, and function g is a user specified function Examples of function g include, for example,a. g(elasticities[i], i, currentspends)=elasticities[i], which gives the Dorfman-Steiner ruleb.

where r is a user-defined constant, X represents the variables of function F, and example function “b” represents a variant of the Dorfman-Steiner rule. Using node292as an example, K would be 1, nlbwould be 10, nubwould be 50, n1would be node293(in this example node292only has one child), andnspendscomprises spend1. To solve for v, the component sets bnode(v) (i.e., the above bn(v) formula with the received node node as n) equal to the received budget and then solves for v. In some embodiments, the component solves for v using a root-finding algorithm, such as Brent's method, a bisection method, a secant method, an interpolation method, or another suitable root-finding algorithm. In block410, the component initializes j, a counting variable, to one. In blocks415-430, the component loops through each of the spends to determine whether a new allocation amount should be calculated for the spend. In decision block415, if spendjis a member of node then the component continues at decision block420, else the component continues at decision block430. In decision block420, if spendjis a member of any child node of node then the component continues at decision block430, else the component continues at block425. In block425, the component calculates a new allocation amount for the jthspend based at least in part on, for example, the following formula,

where g represents a user-specified function, such as example equations “a” and “b” discussed above. In decision block430, if there are additional spends, then the component continues at block435, else the component continues at block440. In block435, the component increments j and then loops back to decision block415. In decision block440, if node has any child nodes, then the component continues at block445, else the component returns the calculated newspends. In blocks445-460, the component loops through each of node's children and recursively invokes the approximate component to continue the calculation of newspends. In block450, the component calculates b based at least in part on, for example, the following formula:

where nodelbrepresents the lower bound of node, nodeubrepresents the upper bound of node, v represents the adjustment factor, and child represents the currently selected child node. In block455, the component recursively invokes the approximate component to update newspends based at least in part on the currently selected child node child, the calculated value of b, the modified newspends, and the elasticities (elasticities). In other words, the component invokes the approximate component to continue calculating spends for newspends. In block460, the component selects the next child node of node, if any, and then loops back to block445. If all of the child nodes have been processed, the component returns the calculated newspends. Accordingly, newspends can be calculated without determining a second derivative for the model.

FIG. 5is a flow diagram illustrating the processing of a profit component in accordance with an embodiment of the disclosed technology. The profit component is invoked to determine the allocation of resources that provides an optimal (or near optimal) level of profits from among the valid allocations of resources (i.e., consistent with a given set of constraints). The profit component creates a fake “spend,” modifies an existing constraint tree with the fake spend, and then invokes the allocate component based at least in part on the modified constraint tree. The fake spend represents resources that will not be allocated or otherwise spent on, for example, advertising. In other words, these resources are saved to create a budget surplus. In block510, the component updates the constraint tree by adding the fake spend spendfaketo the root node. Using the constraint tree inFIG. 2Cfor example, the root node would be modified from

In block520, the component invokes the allocate component, passing to the allocate component the updated constraint tree. The component then returns the new spends provided by the allocate component. These spends represent the allocation of resources that provide an optimal (or near optimal) level of profits from among the possible allocations of resources.

FIG. 6is a flow diagram illustrating the processing of a hit-target component in accordance with an embodiment of the disclosed technology. The hit-target component is invoked to find the allocation of resources that reduces the total target miss to a minimal (or near minimal) level. The hit-target component generates a set of spends corresponding to the allocation of resources that reduces the amount of target misses to an optimal (or near optimal) level based at least in part on a constraint tree, revenue response models, and revenue targets. In block604, the component initializesbas the upper bound of the total budget based at least in part on, for example, the following formula:

where spends[i] represents the ithspend and Ω represents the set of feasible spends within a given set of constraints. In block608, the component initializesbas the lower bound of the total budget based at least in part on, for example, the following formula:

where spend[i] represents the ithspend and Ω represents the set of feasible spends within a given set of budget constraints. In block612, the component sets variable b, an iteration budget, equal tob. In block616, the component calculates the best target miss, D, for the current iteration budget, the set of revenue response models, the revenue targets, and the constraints associated with the constraint tree, based at least in part on, for example, the following formula:

where spends[i] represents the ithspend of the set of spends spends (for example, spends[1] represents the first spend in the set of spends spends while spends[3] represents the third spend in the set of spends spends, Ω represents the set of feasible spends within a given set of constraints, Tjrepresents a revenue target for the jthrevenue type, Fjrepresents a revenue response model for the jthrevenue type, and J represents the number of revenue types. In decision block620, if the component is applying a gradient descent method for reducing total target miss, then the component continues at block628and invokes a gradient descent component, else the component continues at block624and invokes a bundle level component. Each of the gradient descent and bundle level components generates or updates a set of spends based at least in part on a budget, a constraint tree, a set of revenue response models, and a set of revenue targets. The gradient descent and bundle level components each provide a set of spends and a set of weighted elasticities (we). One skilled in the art will recognize that other suitable optimizing components could be employed. In decision block632, if the target miss for the spends generated or updated in block624or block628is equal to the best target miss, D, then the component continues at block648, else the component continues at block636. The target miss for the generated or updated spends can be calculated based at least in part on, for example, the following formula:

where spends[i] represents the ithspend of the generated or updated set of spends spends (e.g., spends[1] represents the first spend), Ω represents the set of feasible spends within a given set of constraints, Tjrepresents a revenue target for the jthrevenue type, Fjrepresents a revenue response model for the jthrevenue type, and J represents the number of revenue types. In some embodiments, the target miss for the generated or updated spends can be calculated based at least in part on, for example, the following formula:

where spends[i] represents the ithspend of the generated or updated set of spends spends, Ω represents the set of feasible spends within a given set of constraints, weights[j] represents the jthweight of the set of weights provided by either the gradient descent component (box628) or the bundle level component (box624), Tjrepresents a revenue target for the jthrevenue type, Fjrepresents a revenue response model for the jthrevenue type, and J represents the number of revenue types.
In blocks636-644, the component updates the iteration budget and the lower bound for the budget. In block636, the component stores (e.g., temporarily) the current lower boundb. In block640, the component replaces the current lower boundbwith the iteration budget b. In block644, the component replaces the iteration budget with the average of the current upper boundband the previous lower bound value (i.e., the lower bound temporarily stored in block636).

In block648, the component calculates elasticities for each spend of the generated set of spends, newspends, based at least in part on, for example, the following formula:

represents the partial derivative of the response model associated with the jthrevenue type with respect to the ithspend of a set of spends X. In block652, the component initializes k, a counting variable, to one. In decision block656, if we[k] (i.e., the weighted elasticity for the kthspend of newspends) is less than or equal to the product of C and elasticities[k], the elasticity for the kthspend of newspends, then the component continues at block660, else the component continues at decision block664. C is a predetermined value that is used to vary the probability that a spend will be cut. As C increases, the probability that a spend will be cut increases and, conversely, as C gets closer to 0, the probability that a spend will be cut decreases. In block660, the component cuts or trims the kthspend of newspends. In decision block664, if there are additional spends of newspends to be processed, then the component continues at block668, else the component continues at block672. In block668, the component increments k and then loops back to decision block656to test another set of elasticities.

In block672, the component calculates the total budget reduction (Δb) resulting from the spend cuts (block660), based at least in part on, for example, the following formula:

Δb represents the maximum spend cut that is consistent with the constraints. In block676, the component stores (e.g., temporarily) the current iteration budget b. In block680, the component updates the iteration budget b based at least in part on, for example, the following formula:

In block684, the component replaces the iteration budget upper bound with the previous iteration budget (i.e., the value temporarily stored in block676). In decision block688, ifb−b≦θ, where θ is a predetermined threshold, then the component returns newspends, else the component loops back to block620to continue processing spends for the updated iteration budget.

FIG. 7is a flow diagram illustrating the processing of a gradient descent component in accordance with an embodiment of the disclosed technology. The gradient descent component is invoked to generate or update a set of spends based at least in part on a budget (budget), a constraint tree, a set of revenue response models (F) (one for each revenue type), and a set of targets (T) (one for each revenue type). In block704, the component determines the current set of spends (currentspends). The initial currentspends correspond to how a particular entity is currently allocating resources or how the entity has allocated resources in the past. For example, a company or client may provide an indication of how they are allocating (or have allocated) resources to different channels (e.g., marketing channels). This information may be retrieved periodically and may be stored for later use. In blocks708-724, the component loops through each of the revenue types and initializes a weight (weights), an upper bound (upperbounds), and a lower bound (lowerbounds) for the revenue type. In this example, the component initializes each weight to 1 (block712), each upper bound to 1 (block716), and each lower bound to 0 (block720). In block724, the component loops back to select the next revenue type, if any. In block728, the component calculates a current best miss value (bestmiss) based at least in part on the current spends (currentspends) based at least in part on, for example, the following formula:

where currentspends[i] represents the ithspend of currentspends, Ω represents the set of feasible spends within a given set of budget constraints, Tjrepresents a revenue target for the jthrevenue type, Fjrepresents a revenue response model for the jthrevenue type, and J represents the number of revenue types.

In block732, the component calculates weighted elasticities (we) for each revenue type based at least in part on, for example, the following formula:

represents the partial derivative of the revenue response model associated with the jthrevenue type with respect to the ithspend of a set of spends X times the weight associated with the jthrevenue type. In block736, the component invokes an approximate component. The approximate component generates a new set of spends (newspends) based at least in part on the constraint tree, the received budget, the current spends (currentspends), and the calculated weighted elasticities (we). In blocks740-764, the component loops through the revenue types to determine whether the upper bound for each revenue type is to be updated and, if so, the component updates the upper bound. In decision block744, if the revenue for the currently selected revenue type (based at least in part on the revenue response model Frevenueand generated newspends) would meet or exceed the target for the currently selected revenue type (Trevenue), then the component continues at block748, else the component continues at block756. In block748, the component updates or replaces the upper bound for the currently-selected revenue type (upperbounds[revenue]) with the weight for the currently selected revenue type (weights[revenue]). In block752, the component updates the weight for the currently selected revenue type (weights[revenue]) based at least in part on, for example, the following formula:

where Trevenuerepresents a target for a particular revenue type and Frevenue(newspends) represents the outcome of the revenue response model associated with a particular revenue type using newspends as input. In block756, the component updates or replaces the lower bound for the currently selected revenue type (lowerbounds[revenue]) with the weight for the currently selected revenue type (weights[revenue]). In block760, the component updates the weight for the currently selected revenue type (weights[revenue]) based at least in part on, for example, the following formula:

where Trevenuerepresents a target for a particular revenue type and Frevenue(newspends) represents the outcome of the revenue response model associated with a particular revenue type when applied to newspends. In block764, the component loops back to select the next revenue type, if any. In block768, the component calculates a new total miss value (newmiss) based at least in part on the generated spends (newspends) based at least in part on, for example, the following formula:

where newspends[i] represents the ithspend of newspends, Tjrepresents a revenue target for the jthrevenue type, Fjrepresents a revenue response model for the jthrevenue type, and J represents the number of revenue types. In decision block772, if newspends would result in all of the revenue response models meeting or exceeding the associated targets (i.e., if Frevenue(newspends)≧Trevenuefor all revenue types), then the component returns the generated spends (newspends) and weighted elasticities (we), else the component continues at decision block776. In decision block776, if the difference between be and newmiss does not exceed a predetermined threshold u, then the component returns newspends, we, and weights, else the component continues at decision block780. In decision block780, if bestmiss is greater than newmiss, then the component continues at block784, else the component continues at block788. In block784, the component replaces bestmiss with newmiss. In block788, the component updates or replaces currentspends with newspends and then loops back to block732to calculate weighted elasticities based at least in part on the updated spends and weights.

FIG. 8is a flow diagram illustrating the processing of a bundle level component in accordance with an embodiment of the disclosed technology. The bundle level component is invoked to generate or update a set of spends (newspends) based at least in part on a set of spends, a budget (budget), a constraint tree, a set of revenue response models (F) (one for each revenue type), and a set of targets (T) (one for each revenue type). In block801, the component initializes n, a counting variable, to one. In block805, the component initializes a set of weights (weights[1]) for each revenue type by setting each weight equal to one. In this example, weights represents multiple sets of weights, one set for each loop through block820-870. Thus, weights[n] corresponds to a particular set of weights (the nthset of weights) while weights[n] [m] represents a particular weight within a set of weights (the mthweight of the nthset of weights).

In block810, the component determines the current set of spends (currentspends). The initial currentspends correspond to how a particular entity is currently allocating resources or how the entity has allocated resources in the past. For example, a company or client may provide an indication of how they are (or have) allocated resources to different channels (e.g., marketing channels). This information may be retrieved periodically and may be stored for later use. In block815, the component sets S[n] equal to currentspends. Thus, S (labeled “spends” inFIG. 8) is a set of sets of spends such that each entry of S (e.g., S[1] or S[2]) is a set of spends, and S[n] [p] represents a particular spend. In block817, the component initializes candidatespends[1] to currentspends. The set candidatespends, like S, is a set of a set of spends. In block820, the component calculates weighted elasticities (we) for each revenue type based at least in part on, for example, the following formula:

represents the partial derivative of the revenue response model associated with the jthrevenue type with respect to the ithspend of a set of spends X times the nthweight associated with the jthrevenue type. In block825, the component invokes an approximate component. The approximate component generates a new set of spends (S[n+1]) based at least in part on the root node (root) of the constraint tree, the received budget, spends (S[n]), and the calculated weighted elasticities (we). In decision block830, if the target miss for S[n+1] is less than the target miss for candidatespends[n], then the component continues at block840, else the component continues at block835. As discussed above, the target miss for a set of spends X, a set of revenue response models F, and a set of targets T can be calculated based at least in part on, for example, the following formula:

where J represents the number of revenue types. In block835, the component updates or replaces S[n+1] with the candidatespends[n]. In block840, the component constructsH[n] (S[n+1]), a piecewise linear function approximation to the target miss function with respect to the S[n+1], based at least in part on, for example, the following piecewise linear function:

where J represents the number of revenue types, S[v] represents a set of spends, and

represents the transposition of

In block845component constructsH[n] (S) based at least in part on, for example, the following piecewise linear function:

where J represents the number of revenue types and S represents a set of spends. In block850, the component calculates the “level” (δ), or minimum gap betweenH[n] (S) andH[n] (weights) based at least in part on, for example, the following formula:

In decision block855, if δ is less than φ, predetermined tolerance or threshold, then the component returns S[n+1], we, and weights, else the component continues at block860. In block860, the component generates candidatespends[n+1] and weights[n+1] based at least in part on, for example, the following formula:

where J represents a number of revenue types, and Ω represents the set of feasible spends within a given set of budget constraints. The above formula for generating candidatespends[n+1] and weights[n+1] is subject to:

where X represents a set of spends, w represents a set of weights, I represents the number of spends in X, J represents the number of weights in w, T represents a set of targets, and F represents a set of revenue response models. In block865, the component removes the linear constraints within

that have zero Lagrangian multipliers (standard output from quadratic programming solvers, such as Interior Point OPTimizer (IPOPT) or other suitable optimizers). In block870, the component increments n by 1 and then loops back to block820to calculate new weighted elasticities.

From the foregoing, it will be appreciated that specific embodiments of the technology have been described herein for purposes of illustration, but that various modifications may be made without deviating from the disclosure. As used herein, indexes into a set of objects (e.g., an array of values or set of spends) are represented using either bracket notation (e.g., set[index]) or subscript notation (e.g., setindex), such that the first object of a set of n objects can be represented as either set[1] or set1and the last or nthobject as either set[n] or setn. The facility can include additional components or features, and/or different combinations of the components or features described herein. Additionally, while advantages associated with certain embodiments of the new technology have been described in the context of those embodiments, other embodiments may also exhibit such advantages, and not all embodiments need necessarily exhibit such advantages to fall within the scope of the technology. Accordingly, the disclosure and associated technology can encompass other embodiments not expressly shown or described herein.