Modern e-commerce platforms make use of promotional ofers, such as discounts and rewards, to encourage customers to complete purchases. As expected, revenue is also afected by promotions, and a dedicated budget usually limits monetary losses. In order to allocate promotions eficiently within budget constraints, a marketer can use causal machine learning based personalization along with constrained optimization tools. In this paper we study four decision levers of promotional campaigns, allowing optimal and personalized ofers allocation within budget constraints. We demonstrate the optimization problems in real-life promotional campaigns and formulate them as variations of the Knapsack problem, allowing us to introduce eficient applied solutions. We demonstrate that such solutions have a significant impact on promotional campaigns at Booking.com - a world leading online travel platform. CCS Concepts: • Information systems → Personalization; Recommender systems; • Applied computing → Multi-criterion optimization and decision-making.
E-commerce applications use promotional campaigns to ofer more value to customers and help grow their customer
base [
Customer purchase prediction and expected net revenue losses may vary from customer to customer, even when
they are shown the same promotion. A number of machine learning techniques have been developed to estimate the
Conditional Average Treatment Efect (CATE) of a specific treatment on an individual [
Marketers have more options than just allocating personalized promotions [
Relying on our previous work, we aim to demonstrate how to use the diferent levers, showing real-life examples of
our approach. The paper is outlined as follows: Section 2 describes campaign eligibility modeling; Section 3 focuses on
multiple-choice promotion recommendation; Section 4 showcases reward conditions optimization; Section 5 presents
campaign persistence optimization and the final section concludes the paper.
In this section, we focus on maximizing the overall number of customers completing a purchase by deciding whether to
ofer a specific promotion, while considering global budget limitations. Note the random variable ∈ {0, 1} representing
the completion of a purchase. Additionally, the random variable , we consider to represent the net monetary revenue
associated with the purchase (including the cost associated with the promotion). We briefly cover the optimization
method and its results, which are fully described in a previous work [
Using the Potential Outcomes framework [11], we express the causal efects of the promotion: for each customer ∈ , we denote (1) as a potential purchase if received the promotion ( = 1), and (1) as the potential revenue (with deducted cost of the promotion). (0) and (0) represent the potential outcomes if the promotion is not ofered. Given customer’s pre-promotion covariates (features such as origin country or search dates) the conditional average treatment efect (CATE) of these variables are: ( ) = E( (1) − (0) | = ) ( ) = E( (1) − (0) | = ) The net revenue loss is defined as L = − (we use positive loss values as a measure for weight in the knapsack problem defined in Equation 1). We aim to model the decision whether to ofer a promotion to a customer with given covariates , in order to maximize the total incremental purchases subject to budget constraints.
Using previously collected data on randomly assigned promotions, we evaluate the optimal re-assignment of the promotions given to customers set , with the following optimization formulation: (1) subject to:
Õ · ( ) Õ ∈
· L ( ) ≤ 0 ∈
Here ∈ {0, 1} is the assignment variable indicating whether customer is ofered the promotion or not. The target function is maximizing the total incremental purchases, and the constraint limits the incremental budget to zero. This formulation resembles the Binary Knapsack Problem with possible negative weights and utility values. In our setting, ≤ 0 =⇒ L ≥ 0, due to the fact that the incremental revenue is generated only by incremental purchases. We apply a transformation on negative values [25] converting our problem into a standard binary Knapsack Problem for customers with > 0 and L > 0. The new budget constraint constant is achieved by Í L for all customers where > 0 and L ≤ 0.
We can approximate our problem to the Fractional Knapsack Problem, and use the greedy algorithm with sorting customers by descending /ℎ . Here, this sorting criteria is calculated by / L . Relying on a decision threshold , the assignment strategy is to provide a promotion to all customers with a ratio above the threshold. The threshold is calibrated on historical data such that the total budget of the customers above the threshold is not exceeding the constraint. In an online setup, the threshold can be further tuned according to new data behaviors and target shifts.
The quantity / L is estimated by modeling and L separately. In [
Experimental Results
We compared the Fractional Approximation and Retrospective Estimation [
= ΔΔ−Δ The stars on each curve represent the best operating points (in terms of total treatment efect) for each method, subject to ≥ 0 constraint (zero-budget).
In terms of unconstrained uplift efect, the Transformed Outcome method achieves the highest Area Under the Uplift Curve ( = 0.912), and the Two-Models method has the maximal potential treatment efect (109%). However, those methods have a limited feasible solutions space ( ≥ 0), resulting in at most 38.6% of the potential efect.
At the same time, the Fractional Approximation method achieves the highest population coverage (38%) at ≥ 0 and reaches 65.8% of the potential treatment efect. The Retrospective Estimation method provides the maximal treatment efect achieving 79.7% of the possible uplift with = 0.805. The solution allows to run a self-sponsored promotional campaign, with zero-budget, while achieving up to 80% of the possible impact. 2.5 2.0 1.5 0.5 0.0 0.5 I 1.0 O R 0 0 20
40 60
Percentage of users treated (%)
MULTIPLE-CHOICE PROMOTIONS RECOMMENDATION In this section, we extend the previously presented problem, such that we can ofer each customer at most one promotion from a finite set of promotions that are eligible. In other words, rather than deciding whether to give or not to give an ofer, the marketer determines which promotion to assign to each user. Similar to the previous section, a global budget constrains the overall incremental net revenue loss generated by the promotions.
A general case like this no longer allows for trivial incremental comparisons. Examining the incremental uplifts,
we question whether the comparison be made with the no-promotion baseline or with the second-best option. Recent
research tackled the multiple-promotion uplift problem using meta-learning, taking conversion and cost into account
[27]. Another promotion recommendation study recommended an ofline-constrained optimization strategy [ 15], based
on a constant promotion cost assumption. However, in our online e-commerce setup, these solutions are not feasible,
since the decision about promotion selection needs to be made in real-time under the current budget constraints. We
proposed a solution method relying on the Online Multiple-Choice Knapsack Problem [29] that is fully described in [
Solution Approach We express the causal efects of the promotions with two variables: () represents the potential purchase if customer is ofered the promotion , while () represents the potential net revenue if customer is ofered the promotion . Likewise, (0) and (0) represent the potential outcomes if no promotion is ofered to customer , an option that is always available for every customer. We define the conditional average treatment efect on and for a customer with pre-promotion covariates as follows:
CATE (, ) = E( () − (0) | = )
CATE (, ) = E( () − (0) | = ) Both quantities CATE (, ) and CATE (, ) can be positive or negative. The CATE on the expected net revenue loss L is:
CATE L (, ) = −CATE (, ) We estimate CATE (, ) and CATE L (, ) per each customer and each promotion ∈ using uplift modeling trained on past treatment data. Item = 0 for which CATE (, 0) = 0 and CATE L (, 0) = 0 represents the base treatment of not giving a promotion, and therefore has no incremental efect. The target of the optimization problem is for every customer picking a single item ∗ ∈ in order to maximize the total incremental impact CATE (, ∗), while the total selected CATE L (, ∗) would not exceed the budget constraint .
This problem is formalized as the Multiple-Choice Knapsack Problem (MCKP) [22] in Equation 2, where, , is a binary assignment variable indicating if a customer should be ofered the item .
Maximize Õ Õ CATE (, ) ·
∈ ∈ subject to:
∈ ∈ 2.
Õ = 1 ∈ 3. ∈ {0, 1} ∀ ∈ , ∈ (2)
In our case, the value of each item (a promotion ofered to a specific customer) is CATE (, ) and the weight of
each item is CATE L (, ). Diferent from the classical setup, we allow the weights and values of the items to be
negative. For practical applications, we investigate the Online-MCKP [28], a variation of the MCKP where customers
arrive one-by-one. Here, we need to decide which promotion to ofer each customer in an online manner.
We address the problem with a two-phased approach: an estimation phase and an optimization phase. The first phase
estimates CATE (, ) and CATE L (, ). In the second phase, we then use these estimations and solve the MCKP and
the Online-MCKP. CATE estimation for both and are achieved using uplift modeling and data from previous
randomized controlled trials. We consider diferent estimators such as two-models [
Similar to the 0-1 knapsack problem, the optimization phase relies on an approximation solution to overcome the
computational limitations and fit for online environments. In [
The outline of the solution is presented in algorithm 1. The proposed algorithm addresses the assignment problem in an online manner, and is able to tune the strategy according the up-to-date remaining budget status. 3.3
Solution Example We demonstrate the optimization flow by illustrating a toy example on Figure 4. In this example, we observe various promotional ofers for four diferent customers (green-squares, red-circles, blue-triangles, and purple-rhombuses) given a budget of zero. Namely, we need to pick one promotion per customer, such that the total weight (expected net revenue loss L) will not be positive and the total value will be the maximal. For each promotion we present its value (a) Available Items (b) Dominant Items (c) Optimal solution V a l u e
V a l u e
V a l u e
Fig. 4. Example of the solution method. (a) all available promotional options of 4 customers (colors and shapes) on value and weight axes; (b) the dominant items per-customer (colored); (c) the optimal assignment given a threshold angle. 10: 11: 12: 13: 14: 15: 16: 17: 18: 19:
2( , ) ← ∪ ( , ) end for Sort by decreasing angle for ∈ do: if p=0: (0) = 0/| | else: ( ) = (−1) + /| | end for Update eficiency threshold ∗:
∗ ← ∈ | ( ) ≤ | | ·( | |−+1)
20: Find dominant item ∗:
21: ∗ ← arg min ∈ { | ≥ ∗}
22: Update capacity:
23: ← − ∗
24: Pick item ∗
25: end for
Algorithm 1 Online MCKP [
Sub-figure (c) presents the optimal solution to the problem. In this case, we also pick promotions with positive weight for the blue and purple customers since their weight is compensated with the negative weight of the selected green and red promotions. We can observe that the total value (overall position of selected options on the y-axis) is higher than any other possible combination within the budget constraints.
(a) Input dataset (b) Optimal Solution An assessment of the potential impact of various uniformly assigned promotions was conducted before we optimized the promotion assignment. The treatment groups in our randomized controlled trial received three diferent levels of discounts on Booking.com products. The target metrics - completion of purchases, promotion costs, and incremental revenues - were aggregated and compared between control and treatment groups, yielding an average treatment efect on net revenue and purchase completion per promotion. Despite conclusively positive treatment efects, each promotion resulted in a loss in net revenue. Ideally, a zero-budget promotional campaign will be able to operate for a long time using a solution including personalized promotions.
More than 20 million entries were generated in the study. For each data point, the binary variable was used to represent the completion of a sale, the continuous variable was used to represent the total net revenue (including the promotional costs), and covariates were used to represent customer characteristics. We selected the best model from a number of uplift modeling techniques to obtain CATE (, ) and CATE L (, ) and picked the best model according to the highest Qini Score on the test set.
Next, for each customer ∈ and each potential promotion we calculated the expected value (CATE (, )) and the expected weight (CATE L (, )) based on the models predictions. This resulted in | | × rows, where the number of treatments per customer is = 4 ∀ ∈ (three promotion levels and a no-discount treatment). Figure 5(a) displays the joint distribution of value and weight across three discount levels (A,B,C) on a normalized scale. We observe items in all four quadrants of the chart, with a vast majority in the first quadrant, meaning that we predict that the promotions have a positive value and a positive weight for most customers.
We evaluated the On-MCKP solution, which simulates the real-world scenario where customers arrive one at a time, and the decision of which promotion to ofer is made live, at each time-step. At the beginning of the process, we have no information about the general weights and values distributions. The method adapts the promotion assignment decision to the remaining budget and the updated eficiency angle function as described in Algorithm 1.
The outcome of the promotions assignment is depicted in Figure 5(b). The solution demonstrates a near-optimal performance with a maximal optimality gap of 0.245% (compared to the optimal Integer Linear programming results) on the real discounts dataset. The suggested solutions widely outperform the greedy benchmarks and play a game-changing role in allowing the promotional campaign to become self-sponsored, with a significant improvement compared to simple Greedy (+51%) solutions. We observe an interesting phenomenon, where the selected promotions follow a linear value/weight trend. This forms a separation bound by excluding the solutions below the line, which is equivalent to the eficiency threshold used by the method. It consists of a blend of all three available promotions, using items from three possible quadrants. 4
Similar to the previous methods, here we aim to maximize incremental sales given budget (or incremental ROI) constraints. However, instead of allocating diferent promotions or deciding whether to reward a promotion to a customer based on its cost-efectiveness, we focus on tuning the reward conditions. More specifically, while the same promotion is ofered on all supply and all customers, the qualification conditions (such as minimal spend requirement) might vary. A good example for such condition is presented in Figure 1, where a customer needs to complete a purchase above a certain amount in order to qualify for the promotion. This method allows the marketer to control for the eficiency of the promotion on the targeted audience, while at the same time maintaining a consistent promotional ofer to all customers. The optimization of the reward condition can be done on various resolutions, ranging from a global decision (uniform minimal spend requirement), through a geography based decision (diferent conditions in diferent cities), to individual product or even customer-level decisions.
Such method relies on a simple assumption that a strict reward condition (such as a very high minimum spend requirement) will afect smaller population but result in cost-efective budget allocation, while loose reward conditions (or no conditions at all) will have a great impact on the sales, but result in a significant budget loss. Therefore, the 2.0 1.5 1.0 IRO 0.5 0.0 0.5 1.0 Measured ROI Fitted Model Target ROI = 0 Current condtion - 10% eligible New condition - 19% eligible 0.0 0.2 0.4
0.6 Eligible population 0.8 1.0
Fig. 6. An example of eligibility criteria tuning, based on ROI-Model optimization method is seeking for an operating point, in terms of reward condition, which maximizes the size of the exposed population, subject to the budget constraints. Moreover, while such decisions can be achieved separately in each sub-segment (for example destination city), a global budget allocation policy can reach higher sales results.
By using empirical data of purchases as a response to diferent reward conditions, we can build an ROI-elasticity curve, mapping between the portion of the exposed population ( ) according to reward condition and the associated ROI. The blue line in Figure 6 represents the empirical ROI-elasticity curve gathered from one of the targeted geographies. As expected, the curve is decreasing with the portion of exposed population, reducing the cost eficiency of the promotion when exposed to a bigger audience. It is important to note that the curve has an intersection with the target ROI value (in our example - = 0), allowing us to update the operating point threshold to the desired value ∗.
However, during an online campaign, the general trafic distribution might difer and therefore the optimal threshold ∗ can shift accordingly. We propose a simple curve fitting technique to address this problem. As presented in the orange curve in Figure 6, we assume a non-linear monotonic relation between the portion of the exposed population and the resulted . We suggest to model this relation as an exponential curve, by learning the parameters , and using the Levenberg-Marquardt least-squares curve fitting algorithm [19] to select a new ∗ such that: d ( ) = +
d ( ∗) = 0
Using this parametric curve fitting method allows incorporating historical and up-to-date data in ROI estimation, by refitting the curve every time-period. The update step ∗−1 → ∗ (moving from the red to green operating thresholds in Figure 6) can be re-evaluated on the new data, allowing to build a new elasticity curve in the next iteration. 5
PROMOTIONAL OFFERS PERSISTENCE
In this section we survey the persistence lever, as described in details in [
Given a wide variety of ofers ∈ A, our personalized solution aims to pick the best treatment ∗ to maximize the expected business impact. As mentioned in previous sections, we can model the conditional treatment efect, or any other desired outcome of a treatment with a learner function L. The context of the input would use customer pre-treatment covariates ˆ at time . Our goal is to pick the best treatment ∗ such that:
However, a customer might interact with our platform multiple times, generating repeated browsing sessions and
additional model calls. The model decision about the optimal treatment may change, due to context change, model
parameters update or even due to an intrinsic exploration strategy within the model [
Theoretically, the optimization model may determine itself whether to persist with the previously selected decision. Previous customer interactions’ data can be fed into the learner model L, by using sequential [18] or reinforcement [23] learning methods such that: ∗ (ˆ , ) = arg max L (, ˆ , , [ − 1])
RETURNING
USER?
NO REQUEST
READ USER DATA
OPTIMIZATION
MODEL
UPDATE USER DATA
RESPONSE Persistent
Storage
In practice, online applications rely on delayed, sparse and biased feedback [16]. Therefore, learning L (, ˆ , , [ −1]) is challenging, and while a holistic optimization method can achieve a global optimal strategy, it still might harm the experience consistency of individuals.
Using an explicit persistency mechanism will ensure consistent model behavior and allow more control and clarify about the assignment of the ofers. At the same time, to allow flexibility, setting the right expectations with the customer such as "This ofer is valid for the next three days " is crucial. Therefore, while the persistence challenge might sound purely technical, it is important to involve user experience, copywriting, and business stakeholders in the process. ∗ (ˆ , ) = arg max L (, ˆ , )
We suggest implementing a flexible storage-based system, to ensure a consistent user journey while continuously learning and optimizing ofers allocation. A distributed key-value database will be used to keep track of the personalized recommendations. At each point of customer-system interaction, the system decides whether to stick with the previously ofered treatment or recalculate a new up-to-date ofer (as shown in Figure 7). The mechanism is specified by two hyper-parameters: • Persistence Key - a set of attributes defining the persistence.
• Persistence Timeout - treatment persistence time span.
The Persistence Key defines the set of context properties that require to stick to the same treatment. To guarantee the same treatment, the key can be constructed from customer and session characteristics (for example, stick for the same decisions give the same user identifiers and search destination). The Persistence Timeout defines how long the decision remains valid. Parameters for the key, as well as conditions for timeouts, are often defined based on business use cases. Examples include session length, coupon expiration time, and customer expectations. Parameters can be tuned to achieve optimal performance.
In our previous work [
CONCLUSION In this paper we showcased four levers that can be adjusted for the purpose of maximizing promotion allocation while remaining within budget constraints. In addition to modifying one of these levers per campaign, one can also try multiple combinations of diferent levers. For example, combining campaign eligibility modeling with promotion reward conditions optimization. Of course, the more complex the campaign will be, the harder it will be to accurately measure and optimize. To enable such multi-dimensional decision making, there needs to be a robust pipeline or system in place where all these decisions can be made. This system will take in a campaign with all its viable possibilities dictated by the business, and outputs the optimized campaign with the right benefit, reward condition, and persistence setting on the instance level.
It is important to note that even while all these levers could be optimized, the success of a campaign is still strongly dependent on the overall customer experience. This includes the customer-facing design and copywriting, and how clear and attractive the benefit is communicated to the customer or how explainable the campaign is for customer support to answer related incoming inquiries Further, one can achieve optimal campaign configuration with the benefit ofered per customer, the right reward condition, and the right persistence threshold, but the campaign will fail due to poor customer-facing user interface. Moreover, such promotions tend to have long term efects on customer loyalty, and given a dynamic business environment, the optimisation decisions need to be re-calibrated periodically. Introducing advanced methods such as exploration via bandits and cross-campaign learning may help with fast iterations and dynamic updates, but at the same time create an additional level of complexity and evaluation challenges. We look forward to investigating the diferent usages of the levers discussed, and validating this approach as a one-stop-shop for personalized promotions.
We thank Thomas Bosman, Nerie Ohana and Itsik Adiv for their help in editing this paper; to Booking.com Value Research Group for fruitful ideation and discussions; and to Igor Spivak, Amir Tzur and Ola Czajkowska for making these concepts work in real-life systems. [11] Guido W Imbens and Donald B Rubin. 2010. Rubin causal model. In Microeconometrics. Springer, 229–241. [12] Sören R Künzel, Jasjeet S Sekhon, Peter J Bickel, and Bin Yu. 2019. Metalearners for estimating heterogeneous treatment efects using machine learning. Proceedings of the national academy of sciences 116, 10 (2019), 4156–4165. [13] Ying-Chun Lin, Chi-Hsuan Huang, Chu-Cheng Hsieh, Yu-Chen Shu, and Kun-Ta Chuang. 2017. Monetary discount strategies for real-time promotion campaign. In Proceedings of the 26th International Conference on World Wide Web. 1123–1132. [14] George S Lueker. 1998. Average-case analysis of of-line and on-line knapsack problems. Journal of Algorithms 29, 2 (1998), 277–305. [15] Rahul Makhijani, Shreya Chakrabarti, Dale Struble, and Yi Liu. 2019. LORE: a large-scale ofer recommendation engine with eligibility and capacity constraints. In Proceedings of the 13th ACM Conference on Recommender Systems. 160–168. [16] Themis Mavridis, Soraya Hausl, Andrew Mende, and Roberto Pagano. 2020. Beyond algorithms: Ranking at scale at Booking. com. In Proceedings of the Fourth Workshop on Recommendation in Complex Scenarios. CEUR-WS. [17] Alex Miller and Kartik Hosanagar. 2020. Personalized discount targeting with causal machine learning. (2020). [18] Sarai Mizrachi and Pavel Levin. 2019. Combining Context Features in Sequence-Aware Recommender Systems.. In RecSys (Late-Breaking Results).
11–15. [19] Jorge J Moré. 1978. The Levenberg-Marquardt algorithm: implementation and theory. In Numerical analysis. Springer, 105–116. [20] Diego Olaya, Wouter Verbeke, Jente Van Belle, and Marie-Anne Guerry. 2021. To do or not to do: cost-sensitive causal decision-making. arXiv preprint arXiv:2101.01407 (2021). [21] Alon Sela, Erez Shmueli, Dima Goldenberg, and Irad Ben-Gal. 2016. Why spending more might get you less, dynamic selection of influencers in social networks. In 2016 IEEE International Conference on the Science of Electrical Engineering (ICSEE). IEEE, 1–4. [22] Prabhakant Sinha and Andris A Zoltners. 1979. The multiple-choice knapsack problem. Operations Research 27, 3 (1979), 503–515. [23] Csaba Szepesvári. 2010. Algorithms for reinforcement learning. Synthesis lectures on artificial intelligence and machine learning 4, 1 (2010), 1–103. [24] Irene Teinemaa, Javier Albert, and Dmitri Goldenberg. 2021. Uplift Modeling: from Causal Inference to Personalization. (2021). [25] Paolo Toth and Silvano Martello. 1990. Knapsack problems: Algorithms and computer implementations. Wiley. 14–15 pages. [26] Kui Zhao, Junhao Hua, Ling Yan, Qi Zhang, Huan Xu, and Cheng Yang. 2019. A Unified Framework for Marketing Budget Allocation. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 1820–1830. [27] Zhenyu Zhao and Totte Harinen. 2019. Uplift modeling for multiple treatments with cost optimization. In 2019 IEEE International Conference on
Data Science and Advanced Analytics (DSAA). IEEE, 422–431. [28] Yunhong Zhou, Deeparnab Chakrabarty, and Rajan Lukose. 2008. Budget constrained bidding in keyword auctions and online knapsack problems.
In International Workshop on Internet and Network Economics. Springer, 566–576. [29] Yunhong Zhou and Victor Naroditskiy. 2008. Algorithm for stochastic multiple-choice knapsack problem and application to keywords bidding. In Proceedings of the 17th international conference on world wide web. 1175–1176.