Optimizing Scalable Targeted Marketing Policies with Constraints

Research on training targeting policies has grown rapidly in recent years, with most of the research (including this paper) adopting a predict-then-optimize approach. Intuitively, the firm first solves an “estimation problem”, in which it estimates customer response functions from a sample of training data. After solving the estimation problem, the firm solves an “optimization problem”, in which the estimated customer response functions are used to design a policy that optimizes an objective function (typically firm profit). The contributions of the two problems was recently investigated by Feldman et al. (2022). They compare the relative contribution of a state-of-the-art estimation method with a state-of-the-art optimization method. They demonstrate that sophisticated estimation may not out-perform a relatively simple estimation method that has been properly optimized.

In Table 1, we list eight examples of recent papers that are published after 2020 and investigate methods for targeting a range of different marketing actions. The focus of all of these papers is on the estimation problem, rather than the optimization problem. While some of the papers consider budget constraints, these constraints are simple in nature, and can be solved using rudimentary greedy algorithms. The inclusion of more complicated constraints, and an increase in either the number of decision variables or the number of constraints, require more sophisticated optimization algorithms. We focus on targeting problems with larger and more complicated sets of constraints.

Personalization and targeting have also received recent interest outside the marketing literature, in both operations research and management. For example, Golrezaei et al. (2014) consider the problem of personalizing product assortments in a dynamic setting, and propose an index-based multi-armed bandit method. Chen et al. (2022) apply statistical learning to customize revenue management policies. Derakhshan et al. (2022) also use linear programming to solve personalization problem, where they focus on personalized reserve prices. We refer interested readers to Rafieian and Yoganarasimhan (2023) for a recent review of personalization and targeting within and beyond marketing. As far as we know, none of the papers consider the scalability of personalization problems in the presence of constraints.

Beyond targeting, other research in marketing has investigated how to include constraints when optimizing marketing actions. Examples include research studying conjoint analysis (Toubia et al. 2004), product line design (Luo 2011), retail assortments (Fisher and Vaidyanathan 2014), and content arrangements on social media (Kanuri et al. 2018).

Our findings highlight the challenge of optimizing firm actions in the presence of fairness constraints. There is a long history of studying the role of fairness in firm’s marketing actions, and the use of algorithms to make marketing decisions has renewed interest in fairness as a research topic. A distinguishing feature of algorithm fairness is that unfair marketing actions are often an unintended outcome. Algorithms that are designed to optimize seemingly innocuous goals, can lead to unintended and unanticipated differences in how customers are treated. For example, Lambrecht and Tucker (2019) documents how an algorithm delivering advertisements promoting job opportunities led to unintended discrimination. Although the advertisement was designed to be gender neutral, the algorithm optimized cost effectiveness, which led to the ad being shown to more men than women. They conclude by showing that this result generalizes across different digital ad platforms. Similarly, Zhang et al. (2021) shows that the introduction of smart-pricing algorithms increased the gap between the revenue earned by black and white hosts on Airbnb.

There have been several theoretical studies investigating the implications of fairness for firm’s marketing decisions (see for example Cui et al. 2007, Guo 2015, Li and Jain 2016, Guo and Jiang 2016, and Fu et al. 2021). The fairness of firm’s pricing decisions has probably received the most attention (see for example Wirtz and Kimes 2007, Campbell 2008, Anderson and Simester 2008, Bolton et al. 2018 and Allender et al. 2021), while research on methods to anticipate or mitigate algorithmic fairness concerns in marketing is only now beginning to emerge. One notable example is Ascarza and Israeli (2022), who propose using bias-eliminating adapted trees to adjust the potential bias in personalization policies. We contribute to this emerging literature by illustrating how to incorporate fairness concerns, and how to optimize these problems when the number of customers or constraints is large.

Algorithm fairness has also generated considerable interest in the computer science and machine learning literature. This includes an ongoing debate about the definition of fairness. The definitions are many and varied (see for example Castelnovo et al. 2021, and Mehrabi et al. 2021). It is beyond the scope of this paper to resolve the differences between these definitions. Instead, we will interpret a fairness constraint as an example of a Similarity constraint (see the discussion in Section 3).

The computer science literature has also proposed different methods to identify and restrict discrimination in policies trained using algorithms. The methods can be classified into three types: pre-process, in-process, and post-process (see review papers such as Pessach and Shmueli 2022). Our method belongs to the in-process class of methods, because we explicitly consider fairness as part of the policy training process.

The algorithm that we propose, leverages the primal-dual hybrid gradient (PDHG, see Chambolle and Pock 2011). PDHG methods have been widely used in image processing and computer vision applications (e.g., Zhu and Chan 2008, Pock et al. 2009, Esser et al. 2010, and He and Yuan 2012). They are first-order methods, which use gradient information to construct algorithms to find optimal solutions. This class of methods scales very well, and first-order methods have been widely used in many applications, including many machine learning algorithms (Beck 2017). Recent developments have made the algorithm especially suitable for large-scale linear programming problems (see details in Section 4).

Within the PDHG class of methods, the algorithm we use falls within the Primal-Dual Hybrid Gradient for Linear Programming (PDLP) family of methods. These methods are very new, with the theoretical foundation described in Applegate et al. (2023). PDLP is a two-loop algorithm. By initiating a second loop, the algorithm reduces the risk that it moves away from the optimal solution before converging.

Applegate et al. (2023) provides theoretical guarantees for both optimality and computation speed. Implementation of the algorithm at scale requires several additional steps, which are described in Applegate et al. (2021). The research teams that authored these papers include highly skilled engineers and researchers at Google, who developed an efficient C++ implementation of the algorithm within the Google OR-Tools suite.³³3https://developers.google.com/optimization/lp.

As we discuss in the Introduction, we adapt the PDLP algorithm to accommodate the specific characteristics of targeting problems. Our theoretical findings include non-trivial extensions of the guarantees on convergence and optimality to accommodate these characteristics. Moreover, we provide a new theoretical result, comparing the computation requirements of the method with simplex and barrier methods. Finally, we provide the first documented empirical application of this general class of algorithms in the marketing domain.

In the next section, we discuss how to incorporate different types of constraints into personalization problems.

We assume there are $I$ considered customers and $J$ available marketing actions, where the set of marketing actions could include a "no action" or null treatment.⁴⁴4Examples of marketing actions include direct mail advertisements offering a ”free trial” or a discount. Each customer belongs to one of $K$ customer segments, where $K\geq 1$ (if $K$ = 1 then all customers belong to the same segment). We assume that customer segments are defined using observable contextual variables (such as gender, race, geographic locations, or past purchasing).

We formulate the firm’s problem as follows:

The decision variable, $x_{i}^{j}\in[0,1]$, represents the probability a given customer $i$ receives marketing action $j$. While $x_{i}^{j}$ will normally take the value zero or one, a policy could be stochastic (rather than deterministic).

Problem (1) is a linear program, thus it is a convex problem. Furthermore, the targeting and feasibility constraints guarantee that the problem has a bounded and compact feasible region. Therefore, it must have a finite and unique optimal objective value. It is possible to have multiple optimal solutions with the same optimal objective value.

For ease of exposition, we will refer to Problem (1) as the “Individual Personalization with Constraints” problem, and will use the abbreviation “IPwC” throughout the rest of the paper. Notice that in the IPwC problem, the firm chooses marketing actions separately at the individual customer level. In contrast, the volume and similarity constraints are defined at the segment level.

Defining constraints at the segment level is a natural interpretation for volume constraints, which by their nature, require aggregation across customers. For similarity constraints, the firm could in principle design constraints that compare marketing actions between individual customers. However, this is generally not what we observe in practice. Firms face a practical challenge when using similarity constraints to protect a disadvantaged class: the firm may not know which individual customers fall into the disadvantaged class. Few firms document individual characteristics such as race, color, religious creed, national origin, sexual orientation, or disability, which are often used to define protected classes under federal and state laws. In the absence of individual level data, firms can use zip code-level census information to design similarity constraints. For example, suppose a firm wants to impose the similarity constraint that African American households receive a similar number of discounts as other households. Rather than designing a constraint at the individual household level, it can require that zip codes with many African American households receive a similar proportion of discounts as other zip codes. Defining similarity constraints at the segment-level provides a natural solution when customer-level data is unavailable.

We make two further remarks about choosing marketing actions at the individual customer level, while constraints are defined at the segment level. First, if we define each customer as a separate segment, this is equivalent to defining constraints at the individual customer level. The problem generalizes to include this special case. Second, in Section 6, we consider an alternative formulation in which marketing actions are chosen at the segment level, instead of the individual-level (we label this the “SPwC” problem, or “Segment Personalization with Constraints”). This is a simpler problem, and we will show that it can be solved by existing methods. We will interpret the difference in the profit earned from the IPwC and SPwC problems as a measure of the value contributed by the proposed algorithm.

The firm’s objective in (1) is to maximize the incremental profit it earns across all customers and all marketing actions. We denote the incremental profit that the firm earns from customer $i$ if it receives marketing action $j$ as $p_{i}^{j}$. Estimating the incremental response to marketing actions ($p_{i}^{j}$) has been the primary goal of many marketing studies, including many of the recent personalization papers listed in Table 1. We focus on how the firm uses these estimated incremental responses to identify an optimal personalization policy.⁵⁵5We discuss how we predict $p_{i}^{j}$ in our empirical application in Section 5.1. We do note that we stay in the predict-then-optimize paradigm; the firm first predicts $p_{i}^{j}$, and then uses the predicted outcomes to generate optimized decision variables. It is interesting, but beyond the scope of our paper, to explore how to reconcile the misaligned objectives in prediction and optimization (e.g., Elmachtoub and Grigas 2022).

The incremental profit is calculated as the difference between: (a) the profit earned from customer $i$ if the customer receives marketing action $j$, and (b) the profit earned from customer $i$ if no action is taken. Alternatively, we could treat the null action as a separate action in itself, but we would then adjust how we measure outcomes. If we treated the null action as an action in itself, we would measure profits as the profit earned from each action, rather than the difference in profit compared to the null action.

Without changing the model, we can alternatively redefine $p_{i}^{j}$ to measure increments of revenue, units sold, or some other managerially relevant observable outcome. We interpret a no action or null marketing action as a decision not to implement any of the $J$ actions ("business as usual"). The same logic applies to all constraints. To simplify the exposition, we will drop the "incremental" element in our explanation of the constraints.

The first set of constraints $a_{k}^{j}\leq\sum_{i\in S_{k}}x_{i}^{j}\leq b_{k}^{j}$ (Volume I) represent volume constraints on each marketing action. Here, $S_{k}$ is the set of customers in segment $k$, $a_{k}^{j}$ is the lower bound for the total number of customers given marketing action $j$ in segment $k$, and $b_{k}^{j}$ is the upper bound for the total number of customers given marketing action $j$ in customer segment $k$. Volume constraints can include both a minimum or maximum requirement. For example, we earlier cited the example of the Neiman Marcus holiday catalog, where budget constraints impose an upper limit on how many customers receive the catalog, and agreements with suppliers (who fund the catalog) impose a minimum number of recipients. Notice that the framework also allows the minimum and maximum volume constraints to vary by customer segment ($k$) and marketing action ($j$); $a_{k}^{j}$ and $b_{k}^{j}$ can vary across $k$ and $j$.

The second set of constraints $L_{k}\leq\sum_{i\in S_{k}}\sum_{j=1}^{J}c^{j}_{i}x_{i}^{j}\leq U_{k}$ (Volume II) are volume constraints across all marketing actions. Here, $L_{k}$ denotes the lower bound for a combination of all marketing actions in customer segment $k$, and $U_{k}$ denotes the upper bound for a combination of all marketing actions in customer segment $k$. The combination of the marketing actions is determined by parameter $c_{i}^{j}$. We allow the combination to differ across different customers. This is consistent with charities “laddering” their proposed donations, by setting customer-specific donation guidelines. We can also re-interpret this second set of constraints as constraints on marketing outcomes (e.g. the number of customers that respond), rather than constraints on marketing actions. The formulation of the constraints are unchanged under this alternative interpretation.

Volume constraints include several common constraints discussed in the literature. For example, a budget constraint often takes this form. In a budget constraint, $c_{i}^{j}$ denotes the costs for marketing action $j$ to customer $i$, $L_{k}$ is zero, and $U_{k}$ denotes the total budget number for customer segment $k$. It is possible that $c_{i}^{j}$ takes the same value across different customers $i$. Performance constraints may also take this form. Performance constraints impose requirements on a measurable outcome of the targeting policy. For example, although a firm’s objective may be to maximize profits (including the cost of the marketing actions), a manager’s goals might include a requirement that this year’s revenue is no lower than last year (Oyer 1998). In this case, $c_{i}^{j}$ denotes the revenue if we give the customer $i$ marketing action $j$, $L_{k}$ is the performance requirement number for customer segment $k$, and $U_{k}$ is equal to infinity.

The third set of constraints $\sum_{i\in S_{k_{1}}}x_{i}^{j}/n_{k_{1}}\leq\lambda_{j}^{k_{1}k_{2}}\sum_{i\in S_{k_{2}}}x_{i}^{j}/n_{k_{2}}+g_{j}^{k_{1}k_{2}}$ (Similarity I) model the similarity constraints for each marketing action. These similarity constraints restrict the difference in the actions taken with different customer segments, and will often be motivated by concerns about fairness (see for example, Castelnovo et al. 2021, Mehrabi et al. 2021). The total number of customers in segment $k$ is denoted by $n_{k}$, and $\lambda_{j}^{k_{1}k_{2}}$ and $g_{j}^{k_{1}k_{2}}$ restrict the difference between customer segments $k_{1}$ and $k_{2}$. Our framework can capture both subtraction and division differences. When $g_{j}^{k_{1}k_{2}}=0$, the constraint specifies that the division difference in the proportion of customers receiving a given marketing action between two customer segments cannot be larger than $\lambda_{j}^{k_{1}k_{2}}$. When $\lambda_{j}^{k_{1}k_{2}}=1$, the constraint specifies that the subtraction difference in the proportion of customers receiving a given marketing action between two customer segments cannot be larger than $g_{j}^{k_{1}k_{2}}$.

Recall our earlier example, in which a firm wants to impose a similarity constraint that African American households receive a similar number of discounts as non-African American households. We recognized that defining segments using zip codes, and then using census data to characterize the segments, provides a natural solution when customer-level data is unavailable. For illustration, assume a firm uses census data to identify zip codes with at least $X\%$ African American households. We can treat households in these zip codes as segment $k_{1}$, and the remaining households as segment $k_{2}$. The firm might require that the proportion of households that receive a discount cannot vary by more than 5% between the two segments. We can then formulate this constraint as $(\sum_{i\in S_{k_{1}}}x_{i}^{j}/n_{k_{1}})/(\sum_{i\in S_{k_{2}}}x_{i}^{j}/n_{k_{2}})\leq 1.05$ and $(\sum_{i\in S_{k_{2}}}x_{i}^{j}/n_{k_{2}})/(\sum_{i\in S_{k_{1}}}x_{i}^{j}/n_{k_{1}})\leq 1.05$. Alternatively, we could define each zip code as a separate segment, and require that the proportion of households receiving discounts in zip codes with many African Americans does not vary by more than 5% from any zip code with few African Americans.

We can easily include restrictions in which there is a minimum (instead of maximum) difference in the proportion of customers receiving a given marketing action. The setup also allows a firm to restrict the difference in the number of customers who receive a marketing action in different marketing segments (instead of the proportion).⁶⁶6For example, we might require that at least twice as many disadvantaged customers receive discounts as customers who are not disadvantaged. In this case, we can treat customers who are not disadvantaged as customer segment $k_{1}$, and disadvantaged customers as customer segment $k_{2}$. The formulation of this example is $\sum_{i\in S_{k_{1}}}x_{i}^{j}/\sum_{i\in S_{k_{2}}}x_{i}^{j}\leq 1/2$ with $\lambda_{j}^{k_{1}k_{2}}=n_{k_{1}}/2n_{k_{2}}$ and $g_{j}^{k_{1}k_{2}}=0$.

The fourth set of constraints $\sum_{i\in S_{k_{1}}}\sum_{j=1}^{J}d_{i}^{j}x_{i}^{j}/n_{k_{1}}\leq\gamma^{k_{1}k_{2}}\sum_{i\in S_{k_{2}}}\sum_{j=1}^{J}d_{i}^{j}x_{i}^{j}/n_{k_{2}}+h^{k_{1}k_{2}}$ (Similarity II) impose similarity constraints on all marketing actions (or marketing outcomes). The difference between customer segments $k_{1}$ and $k_{2}$ is restricted by $\gamma^{k_{1}k_{2}}$ and $h^{k_{1}k_{2}}$, and $d_{i}^{j}$ is the weighting factor to determine the combination of all marketing actions. For example, the firm might want to require that the budget allocated to disadvantaged customers is at least twice the budget allocated to customers who are not disadvantaged. In this example, we can again treat customers who are not disadvantaged as customer segment $k_{1}$, disadvantaged customers as customer segment $k_{2}$, and $d_{i}^{j}$ as the costs for marketing action $j$ to customer $i$ to derive the formulation.

The last two constraints $\sum_{j=1}^{J}x_{i}^{j}\leq M_{i}$ (Targeting) and $0\leq x_{i}^{j}\leq 1$ (Feasibility) restrict the firm’s action space and represent the key characteristics of a personalization problem. Here, $M_{i}\in(0,J]$ denotes the maximum marketing actions that can be taken for customer $i$. We take a generous perspective, by recognizing that firms may want to send multiple marketing actions to the same customer.⁷⁷7When $M_{i}>1$, our framework implicitly assumes that the profit that the firm earns from customer $i$ if it receives marketing action $j$ is independent across different $j$, which might not hold in reality. In Appendix A.1, we show that a personalization problem with constraints can still be modeled as a linear programming problem even if we remove the independence assumption across different marketing actions. The algorithms and theoretical guarantees provided still hold. Notice that marketing actions can cause negative treatment effects ($p_{i}^{j}$ < 0), but it is not possible to take the negative of a marketing action. As we will show in Section 4, this restriction on the firm’s action space plays a key role in our adaptation of existing theoretical guarantees to personalization problems with constraints.

With the IPwC problem formulated in Problem (1), the number of constraints is potentially large. However, in practice, some but not all of the constraints may be relevant. By specifying several different types of constraints, we aim to provide a menu of options for firms (and researchers) wanting to incorporate constraints into personalization policies.

In Table LABEL:table:constraints_summary, we provide an example of each type of constraint. We also include a calculation of the number of individual constraints required for a single set of each type of constraint, where the set encompasses every combination of customers and segments (where applicable). In our application in Section 5, we use a total of $J=5$ marketing actions, $I=2,065,758$ customers, and up to $K=229$ segments (zip codes). In Table LABEL:table:constraints_summary, we calculate the number of individual constraints required both in general terms, and for this application.

A complete set of constraints requires a total of $2,381,778$ individual constraints ($2JK+2K+K(K-1)J+K(K-1)+I$), comprised of: $2,290$ Volume I constraints ($2JK$), $458$ Volume II constraints ($2K$), $261,060$ Similarity I constraints ($K(K-1)J$), $52,212$ Similarity II constraints ($K(K-1)$), and $2,065,758$ Targeting constraints ($I$). However, even this is not an upper bound on the number of constraints, as the firm might choose to use multiple versions of a constraint (e.g. Similarity II constraints on both race and gender). In our empirical application (Section 5), we show that the number of constraints can pose a challenge for benchmark methods, while our proposed algorithm scales well. We also investigate which types of constraints are particularly challenging.

Before describing these findings, we first formally present the optimization algorithm, and provide guarantees on feasibility, performance and computation speed.

The data was provided by a large American retailer. The retailer operates membership wholesale club stores selling a broad range of products, including electronics, furniture, outdoor, toys, jewelry, clothing, and grocery items. The retailer uses promotions to attract new members, and has implemented large-scale experiments to help it personalize which promotions it should send to different prospective customers. Customers must register for club membership in order to purchase, and the retailer matches the name and address provided at registration to track which customers responded to each promotional offer.

The data describes a large field experiment conducted by the firm in 2015.¹³¹³13Data from this experiment has been used in several previous studies, including: Simester et al. (2020a) and Simester et al. (2020b). The experiment’s goal was to compare how prospective customers responded to five different direct mail promotions, and a no-action control (a total of six experimental conditions). The firm wanted to use this information to design a targeting policy that recommends which marketing action to choose for each customer. A customer represents a separate prospective household, and the customers were randomly assigned to the six experimental conditions. In total, the experiment included approximately 2.4 million unique customers (households).

The profit earned from each customer was measured over the twelve months after the date the promotions were mailed. The profit measure included mailing costs, membership revenue, and profits earned from purchases in the store (if any). The different direct mail promotions included in the experiment were expected to impact these profit components in different ways. For example, some of the promotions offered free trial memberships of different lengths. Longer trials tend to increase adoption, but yield less membership revenue, and attract customers who spend less in the stores. The experimental conditions also included a discounted membership offer. Compared to free trials, discounted memberships tend to convert fewer prospective customers into members, but they generate more membership revenue, and tend to attract customers who spend more in the stores.

Low response rates are particularly common when prospecting for new customers. As a result, only a relatively small number of customers responded in each experimental condition, and so across the 2.4 million customers, the profit was negative for most customers in the five promotion conditions (due to mailing costs), and zero for most customers in the no-action control (there were no mailing costs in the no-action control condition). However, for the customers who did respond, the twelve-month profit measure was positive and large. This distribution of outcomes is typical of many marketing actions. Overall, averaging across customers within a treatment condition, four of the five marketing actions generated positive average profits compared to the “no action” control.¹⁴¹⁴14Specifically, for a given action, the uniform policy in which every customer receives that action yields higher average profits than a uniform policy in which every customer receives the ‘no action” control.

The volume and similarity constraints in Problem (1) require customer segmentation. We group individual customers into segments in this application using zip codes, which are available for all prospective customers. This offers three benefits. First, as we discussed in Section 3, defining segments using zip codes provides a practical solution to the absence of data about which individual customers fall within a protected class. Second, in the prospecting application that we study, firms do not have past purchasing histories for individual customers. For this reason, segmentation based upon zip codes is particularly common when prospecting for new customers, because census data provides detailed no-cost demographic measures (see for example Simester et al., 2020b).¹⁵¹⁵15In contrast, when targeting existing customers, segmentation is often based upon past purchasing measures, such as the recency, frequency and monetary value of past purchases (Sahni et al., 2017). Alternatively, segments could be defined at the store level. A retailer might require that predicted store sales are at least as high as last year, or that the average number of promotions received by customers neighboring each store is similar for each store.

Using zip codes to segment customers also helps to address a primary objective of our empirical analysis; observing how well different methods perform when varying the number of constraints. Recall that the number of constraints is a function of the number of customer segments $K$. The hierarchical nature of zip codes provides a convenient way to vary the number of segments. In particular, a four-digit zip code is identified by the first four digits of a five-digit zip code, and contains all of the five-digit zip codes that share those first four digits. As a result, the assignment of five-digit zip codes to four-digit zip codes is mutually exclusive and collectively exhaustive. The same properties apply when we consider three-digit zip codes (or even two-digit and one-digit zip codes). In this application, we define the customer segments using either three-digit zip codes, four-digit zip codes or five-digit zip codes.

For some five-digit zip codes, the number of prospective customers available in that zip code is small. With similarity constraints, trivial optimal solutions are obtained. Thus, in our validation exercise, we focus on five-digit zip codes with at least 4,000 customers in our data. This leaves us $I=2,065,758$ customers in our validation exercise.¹⁶¹⁶16Recall that our focus is on optimization, rather than minimizing or accounting for estimation errors. Therefore, in our validation exercise, we identify the optimal policy using the same data that we use to predict the response functions (see the discussion in Appendix A.4). In practice, firms may want to minimize over-fitting by designing the optimal policy using a different group of customers than the sample used for estimation. Our final sample has $K=229$ when we use five-digit zip codes to define customer segments, $K=87$ when we use four-digit zip codes, and $K=18$ when we use three-digit zip codes. When we compare how the different methods perform when we vary the number of customers, we select 25%, 50%, and 75% customers from each customer segment to keep the number of customer segments fixed.

To solve Problem (1), we also need to choose exogenous parameters for all of the constraints. We summarize the choice of parameters used in our empirical analyses in Appendix A.7. With these parameter choices, the number of constraints in our implementation is $2JK+K+K(K-1)J/2+K(K-1)/2+I$. For example, when we define the customer segments using a five-digit zip code ($K=229$) and consider all customers ($I=2,065,758$), the number of constraints is $2,224,913$.

The randomized assignment of customers in this training data makes it straightforward to use this data to estimate causal treatment effects for each marketing action. In particular, 27 covariates were available to describe each prospective household. This information was purchased by the firm from a third-party commercial data supplier. We use Lasso with a full set of interactions to predict the profit associated with each marketing action for each customer (in this application, a household is equivalent to a customer). In particular, we estimate Lasso six times, representing a separate model for each marketing action (including the no-action control). Although there are many alternative estimators available, Lasso has been shown to be effective in this type of application.¹⁷¹⁷17See for example Yoganarasimhan (2020) and Simester et al. (2020b), who compare the performance of different estimators. Notably, Simester et al. (2020b) uses a subset of the same data that we use in this study.

We use these estimates to calculate the incremental predicted profit for each customer and marketing action, by subtracting the predicted profit in the control from the predicted profit associated with that action. In Appendix A.4, we provide additional details, including definitions and summary statistics for the covariates.

We consider three benchmark methods: primal simplex, dual simplex, and the barrier method. These are considered state-of-the-art solvers for linear programming problems. We implement each method using Gurobi, which is a commercial software package explicitly designed to solve optimization problems, such as linear programming problems. Data engineers at Gurobi have spent years fine-tuning their implementations of these benchmark methods, and the Gurobi implementations are generally considered amongst the most powerful implementations available.

Different firms have access to different hardware resources. To compare how this affects the performance of the different methods, we compare their performance using three different hardware combinations:

• •

  H1: 8-core CPU and 64GB memory;

• •

  H2: 16-core CPU and 128GB memory;

• •

  H3: 32-core CPU and 256GB memory.

The first hardware option is likely to be feasible and affordable for essentially any firm, because it is representative of the hardware in a standard laptop. The other two specifications include more powerful CPUs and more memory. These hardware configurations recognize that medium and larger firms, and smaller firms with sophisticated technology capabilities, have access to workstations or server-level resources. We implement all hardware options using Google Cloud Computing Services.

We compare the different methods using two performance measures. We first measure feasibility, by asking whether a given method and hardware combination converges to an optimal solution within four days. The second measure focuses on computation time, and measures the total time used to solve the problem (from the set of problems that are actually solved). We use these two measures to show that our method can solve larger IPwC problems, and can consistently solve them faster (given the same hardware specification).

As we point out in Section 3, Problem (1) is a convex problem, and Theorem 2 guarantees the convergence of our method. Therefore, any method that can solve the IPwC problem will deliver the same optimal profit. For this reason, we omit the discussion of the optimal profit in this section. However, we turn attention to the optimal profit in Section 6, when we illustrate the economic implications of solving larger problems.

Table LABEL:table:varyI reports the results when we vary the number of customers $I$ using hardware $H_{3}$ and five-digit zip codes to define customer segments. Recall that we randomly select 25%, 50%, and 75% customers from each customer segment to investigate how the number of customers influences the performance of different methods. In this setup, the number of customer segments is fixed at $K=229$. The table reports the total number of seconds required to solve each IPwC problem. If the method cannot solve an instance of the problem, the table reports either “-” indicating it ran out of memory, or “*” indicating it ran out of time.

We see that Algorithm 1 solves all of the IPwC problem instances proposed in Table LABEL:table:varyI. In contrast, primal simplex and dual simplex can only solve the problems with the smallest number of customers (25% of the sample), while the barrier method is unable to solve any of the problems. When primal simplex and dual simplex can solve the problem, they require a lot more computation time than Algorithm 1. Recall that in Table 1, we summarized eight recent marketing papers that studied personalization problems. In four of these papers, the number of customers exceeded 1 million. It is notable that none of the three benchmark methods were able to solve the IPwC problems proposed in Table LABEL:table:varyI when the number of customers exceed 1 million.

Recall that the findings in Table LABEL:table:varyI were obtained using hardware $H_{3}$. In Appendix A.5, we report additional findings when using hardwares $H_{1}$ and $H_{2}$. With fewer hardware resources, larger versions of the IPwC problem become unsolvable even with our proposed method.

With increases in the number of customers, both the number of decision variables and the number of constraints increase. In Table LABEL:table:varyK, we investigate the impact of varying the number of segments ($K$). We use all customers ($I=2,065,758$) and hardware option $H_{3}$ in all scenarios. Results using hardware configurations $H_{1}$ and $H_{2}$ are reported in Appendix A.6.

In this comparison, Algorithm 1 again solves all of the problems, while the benchmark methods only obtain solutions when the segmentation is relatively coarse (using 3-digit zip codes, for which $K=18$). In this scenario, we again see that our proposed method has a much faster computation time. More generally, when the number of segments decreases, the computation time for Algorithm 1 decreases very quickly.

In our next set of comparisons, we investigate what kind of constraints are most challenging for the different methods. In particular, we investigate how well the different methods perform when the IPwC problem contains: (a) only Volume I and II constraints, (b) only Similarity I and II constraints, or (c) the combination of all of these constraints. All scenarios use hardware option $H_{3}$, all of the customers ($I=2,065,758$), and five-digit zip codes to define customer segments ($K=229$).

The findings in Table LABEL:table:constraint reveal that similarity constraints appear to introduce a more formidable challenge to IPwC problems than volume constraints. If a firm only wants to impose volume constraints, then even with many customers and many segments, the benchmark methods can solve the problem in a reasonable amount of time (3,233 seconds is just less than one hour). However, if the firm wants to incorporate similarity constraints, perhaps due to fairness concerns, then the problem becomes too difficult for these methods. It is these settings in which our proposed algorithm will be particularly useful.

Together, the empirical application described in this section reveals that our proposed method can extend the scale of IPwC problems that can be solved. This includes expanding the number of customers and customer segments that can be considered, and enabling the inclusion of similarity constraints, rather than just volume constraints. In the next section, we measure the implications for firms, by comparing how adjusting the problem to make it solvable with the benchmark methods affects the profitability of the resulting policy.

In Section 5, we showed that Algorithm 1 can solve the IPwC problem in our empirical application using the complete set of customers, a large number of segments (constructed at the 5-digit zip code level), and the complete set of volume and similarity constraints. In contrast, this problem could not be solved by any of the three benchmark methods.

If a firm did not have access to Algorithm 1, and instead was forced to use one of the benchmark methods, it would have to adjust the problem. One solution would be to reduce the number of number of customers, number of segments, or number of constraints. However, this fundamentally changes the firm’s problem. If the firm wants to impose similarity constraints on the full set of customers and segments, then taking any of these steps to make the problem solvable would mean that the solution is not guaranteed to be an optimal or even feasible solution to the problem the firm actually wants to solve.

An alternative way to make the problem solvable is to reduce the number of decision variables, by requiring that some customers receive the same marketing actions. In particular, the firm could choose a different marketing action for each customer segment, but require that all customers within a segment receive the same action. We can formulate this segment-level policy as follows:

We will describe this as the “Segment Personalization with Constraints” problem, or “SPwC”. Notice that in this problem, customers are segmented in two different ways. We use $k$ to denote the segmentation used in the volume and similarity constraints, and $k^{*}$ to denote the segmentation used for grouping customers when assigning marketing actions. Specifically, a customer is assigned to both a $k$ segment and separately to a $k^{*}$ segment. These two segmentations could be identical, but they could also vary. For example, a firm might want to use zip codes to construct segments for the similarity constraints (see earlier discussion), but when assigning marketing actions, segment customers so they align with the firm’s production systems (e.g. sales person territories).

Compared to the IPwC, the decision variables in this problem change to $x_{k^{*}}^{j}\in[0,1]$ to represent the probability that customers in segment $k^{*}$ receive marketing action $j$. The formulation allows boundary solutions, in which all customers in segment $k^{*}$ receive treatment $j$ ($x_{k^{*}}^{j}=1)$, or none of the customers in segment $k^{*}$ receive treatment $j$ ($x_{k^{*}}^{j}=0)$. More generally, $x_{k^{*}}^{j}$ represents the proportion of customers in segment $k^{*}$ who will receive marketing action $j$.

The $p_{k^{*}}^{j}$ term denotes the incremental profit that the firm earns from customer segment $k^{*}$ if it receives marketing action $j$. This is calculated as the sum of $p_{i}^{j}$ for all customers $i$ in segment $k^{*}$. The constraints in (6) are otherwise the same as the constraints in (1). The only difference between the two problems is that (1) designs an individual-level targeting policy ($x_{i}^{j}$), while (6) designs a segment-level targeting policy ($x_{k^{*}}^{j}$).

We implemented three separate versions of both problems (IPwC and SPwC), using the complete dataset ($I=2,065,758)$, and the complete set of volume and similarity constraints. The three versions vary in the $k$-level segmentation used to define the volume and similarity constraints. Consistent with the analysis in Table LABEL:table:varyK, we defined these segments using zip codes identified at the 5-digit level ($K=229$), 4-digit level ($K=87$), or 3-digit level ($K=18$). For all three problems, the $k^{*}$-level segmentation used to segment the marketing actions in the SPwC problem was defined at the 5-digit zip code level.

As we previously discussed, the problem is convex, and so any method that can solve a specific version of a problem, obtains the same optimal profit. However, the optimal profit varies within the pairs of IPwC and SPwC problems, and we summarize these profit differences in Table 6. In the first row, we report the profit difference as an average per 100 customers. In the second row we calculate the difference in the computation cost when solving an IPwC problem using Algorithm 1 versus solving the associated SPwC problem using the barrier or simplex methods. The computation costs were calculated using Google Cloud computing expenses, and are reported per 100 customers.¹⁸¹⁸18When solving the IPwC problem using Algorithm 1, we divide the total computation cost by the total number of customers, and then multiple by 100. All of the SPwC problem can be solved using the barrier or simplex methods in one or two seconds, and so we treat this computation cost as zero.

There are several findings of interest. First, the optimal profit difference is positive, indicating that the optimal profit is higher for the IPwC problem than for the corresponding SPwC problem. This is what we would expect, because the two problems have identical sets of constraints, but the IPwC problem has more degrees of freedom. Any solution to the SPwC problem is also a feasible solution to the IPwC problem. As a result, the optimal solution to the IPwC problem is guaranteed to be (weakly) larger than the optimal solution to the SPwC problem.

Second, the optimal profit difference grows with the complexity of the constraints. When customers are segmented using 3-digit zip codes for the volume and similarity constraints, the optimal profit difference (between the IPwC and SPwC problems) is $16.064, which grows to $23.302 when segmenting at the 5-digit zip code level. The additional degrees of freedom in the IPwC problem provide it with more opportunities to find a solution that satisfies the additional complexity in the constraints. We caution that while this finding is perhaps intuitive, we have not established that it will generalize to all applications.

Third, we see that the computation cost difference is negative for all three pairs of problems. This indicates that the computation cost is higher when solving the IPwC problem using Algorithm 1, than when solving the SPwC problem using the simplex or barrier methods. Notably, the computation cost differences are trivial compared to the optimal profit differences. This suggests that if a firm was restricted to using the simplex or barrier methods, it may be profitable to invest in additional computation time, in order to solve versions of the SPwC problem with less coarse segmentation of the marketing actions. The tradeoff between optimal profit and computation time appears to strongly favor investing in additional computation time.

This last result introduces a new question: if the (IPwC - Algorithm 1) and (SPwC - barrier or simplex) problems used an equivalent amount of computation, what would the optimal profit difference be? We address this question next.

In this analysis, we use 3-digit zip codes to define the $k$-level segmentation for the volume and similarity constraints, so that these constraints are identical in both the IPwC and SPwC problems. Recall from Table LABEL:table:varyK, that the computation time required by Algorithm 1 to solve this IPwC problem is 706 seconds. In the SPwC problem, we vary the $k^{*}$-level segmentation used to group customers when assigning actions, so that solving the SPwC problem also requires 706 seconds (using the dual simplex method).

More specifically, when each customer is in its own $k^{*}$ segment, so that actions are chosen separately for each customer, then the SPwC and IPwC problems are equivalent. We know that with this level of $k^{*}$ segmentation, the dual simplex method requires 1,034 seconds to solve the SPwC problem (Table LABEL:table:varyK). In contrast, if the $k^{*}$ segmentation is at the 5-digit zip code level, then the dual simplex method requires just seconds to solve the problem (Footnote 18). Therefore, we seek an intermediate level of $k^{*}$ segmentation, between individual customers and 5-digit zip codes, in which the dual simplex method requires approximately 706 seconds to solve the SPwC problem. We can then compare the optimal profit from the (IPwC - Algorithm 1) and (SPwC - dual simplex) solutions, where the two solutions are each obtained using the same amount of computation.

To vary the coarseness of the $k^{*}$ segmentation in the SPwC problem, we randomly select some 5-digit zip codes in which we segment at the zip code level, and in the remaining 5-digit zip codes, we segment at the individual customer level. Where we segment at the zip code level, all households within that zip code are assigned the same action. Where we segment at the customer level, actions are assigned separately to individual customers. The larger the proportion of 5-digit zip codes that we assign actions at the zip code level, the more coarse the $k^{*}$ segmentation, and the fewer the degrees of freedom available to the SPwC problem. The optimal profit from the SPwC problem will (weakly) decrease, and the required computation time will also decrease.

We illustrate the findings in Figure 2, where each data point represents an average across 30 iterations of the SPwC problem (with different random draws of zip codes in each iteration). The X-axis varies the proportion of randomly selected zip codes in which the SPwC problem assigns actions at the zip code level (in the remaining segments actions are assigned at the customer level). The black line reports the average computation time for the SPwC problem (using dual simplex). The columns report the average profit difference per 100 customers between the (IPwC - Algorithm 1) and (SPwC - dual simplex) solutions.

As expected, the IPwC problem is always more profitable than the SPwC problem (the profit difference is positive). Moreover, increasing the proportion of segments in which all customers receive the same marketing action, both decreases the computation time for the SPwC problem (black line), and increases the profit advantage for the IPwC problem over the SPwC problem (columns). Recall that the computation time required to solve the IPwC problem using Algorithm 1 is 706 seconds. When the SPwC assigns actions at the zip code level in 21% of the zip codes, dual simplex requires a nearly identical amount of time (689 seconds) to solve the SPwC problem. At this level of segmentation, the IPwC problem earns $3.01 more profit per 100 customers.

The findings in Table 6 illustrate that the additional degrees of freedom that Algorithm 1 can exploit, may result in substantial profit increases. We caution that the optimal profit differences between the SPwC and IPwC problems are specific to the constraints and parameters that we used. However, we expect that the key implications from Table 6 will generalize: (a) the SPwC problem yields lower optimal profits than the IPwC problem, and (b) Algorithm 1 can solve larger versions of the IPwC problem than the benchmark methods. We conclude that the algorithm has the potential to contribute to economically important increases in the profitability of firms’ personalization policies.