Multi-Channel Marketing with Budget Complementarities

Utility maximization under a budget constraint is a classical problem in economics and management science. It is commonly assumed that the utility is a "nice" known analytic function, for example, continuous and concave. In many domains, such as marketing, increased availability of computational resources and data has enabled the development of sophisticated simulations to evaluate the impact of allocating a fixed budget among alternatives (e.g., marketing channels) on outcomes, such as demand. While simulations enable high resolution evaluation of alternative budget allocation strategies, they significantly complicate the associated budget optimization problem. In particular, simulation runs are time consuming, significantly limiting the space of options that can be explored. An important second challenge is the common presence of budget complementarities, where non-negligible budget increments are required for an appreciable marginal impact from a channel. This introduces a combinatorial structure on the decision space. We propose to address these challenges by first converting the problem into a multi-choice knapsack optimization problem with unknown weights. We show that if weights (corresponding to marginal impact thresholds for each channel) are well approximated, we can achieve a solution within a factor of 2 of optimal, and this bound is tight. We then develop several parsimonious query algorithms for achieving this approximation in an online fashion. Experimental evaluation demonstrates the effectiveness of our approach.