Source-linked AI summary
E-Commerce Promotions Personalization via Online Multiple-Choice Knapsack with Uplift Modeling
Javier Albert, Dmitri Goldenberg
TL;DR
Promotion personalization must balance customer-specific purchase effects against a global budget for incremental revenue loss. The paper formulates the task as online multiple-choice knapsack and combines uplift estimates with constrained optimization that handles negative values and weights. It reports more than 99.7% of possible optimal promotional impact and describes the approach as applicable to real-time e-commerce.
Problem
Method
The paper combines customer-level uplift estimation with online multiple-choice knapsack optimization, extending the formulation to negative values and weights.
Source: §1 · p. 2Results
Above 99.7% of the possible optimal promotional impact is achieved by the adaptive method.
Source: §6 · p. 9Takeaways & Limitations
The authors report that the adaptive method is applicable to decision mechanisms in real-time e-commerce setups.
Source: §6 · p. 9The authors identify an online comparison study as future work for validating the holistic framework.
Source: §6 · p. 9
Abstract
from arXiv · showhide
Promotions and discounts are essential components of modern e-commerce platforms, where they are often used to incentivize customers towards purchase completion. Promotions also affect revenue and may incur a monetary loss that is often limited by a dedicated promotional budget. We study the Online Constrained Multiple-Choice Promotions Personalization Problem, where the optimization goal is to select for each customer which promotion to present in order to maximize purchase completions, while also complying with global budget limitations. Our work formalizes the problem as an Online Multiple Choice Knapsack Problem and extends the existent literature by addressing cases with negative weights and values. We provide a real-time adaptive method that guarantees budget constraints compliance and achieves above 99.7% of the optimal promotional impact on various datasets. Our method is evaluated on a large-scale experimental study at one of the leading online travel platforms in the world.
1 INTRODUCTION
The introduction frames promotion selection as an online, budget-constrained decision that must account for customer-specific purchase effects and revenue loss. It presents an uplift-estimation and constrained-optimization approach, extending Online-MCKP to negative values and weights.
1 INTRODUCTION
- Promotions may increase purchase probability while incurring incremental net revenue loss, which dedicated budgets constrain.The campaign is sustainable when overall incremental net revenue loss stays within budget.Source: §1 · p. 1
- Promotion effects on purchase probability and expected revenue loss vary by customer, motivating individual-level uplift estimates.Uplift modeling estimates conditional treatment effects, commonly using data from randomized controlled trials.Source: §1 · p. 1
- Existing online approaches may limit incremental Return on Investment measurement and fail to account for negative effects on value or weight.The problem also requires selecting among multiple promotions under up-to-date budget constraints.Source: §1 · p. 2
- Online-MCKP selects one promotion at each customer visit using value and weight, supporting dynamic strategy adaptation.The paper frames this as a potential two-step estimation and optimization approach.Source: §1 · p. 2
- The study compares its online solution with benchmarks in a large-scale experimental study on Booking.com.The introduction identifies the study's real-life setting but does not report its results here.Source: §1 · p. 2
- The paper formulates the problem as Online-MCKP and proposes a two-step uplift-estimation and constrained-optimization solution that extends the method to negative values and weights.The study uses real promotions on the Booking.com platform.Source: §1 · p. 2
2 PROBLEM FORMULATION
The problem assigns at most one promotion to each customer to maximize incremental purchases while keeping total incremental net revenue loss within a global budget. It represents customer-level promotion effects as value and weight in an online multiple-choice knapsack formulation that permits negative quantities.
2 PROBLEM FORMULATION
- The objective is to maximize incremental purchase completions by assigning each customer at most one eligible promotion under a global budget on incremental net revenue loss.No promotion is an available option.Source: §2 · p. 2
2.1 Treatment Effect Estimation
- CATE_Y and CATE_R describe customer-specific incremental effects on purchase probability and expected net revenue, respectively.The framework uses potential outcomes for promotion and no-promotion conditions.Source: §2.1 · p. 2
- Uplift modeling on randomized-trial data estimates each customer's treatment effects; the no-promotion base has zero value and weight.For each customer and possible promotion, the method estimates purchase and net-revenue-loss effects.Source: §2.1 · p. 2
2.2 Multiple-Choice Knapsack Problem
- The optimization selects one option per customer to maximize the sum of selected values while keeping total weight within budget C.The displayed formulation introduces the constrained multiple-choice assignment problem.Source: §2.1 · pp. 2–3, §2.2 · p. 3
- The formulation uses a binary assignment variable, with promotion value equal to CATE_Y and weight equal to CATE_L, and permits negative values and weights.Customers arrive one by one in the online version.Source: §2.2 · p. 3
2.3 Problem Toy Example
- The toy example plots four customers' promotion options by value and weight, with options appearing in all four positive and negative quadrants.The example uses a zero budget, so selected options' total weight must not be positive.Source: §2.3 · p. 3, Figure 2 · p. 3
- The local solution selects each customer's highest-value non-positive-weight option, while the global optimum can combine positive-weight choices with negative-weight choices to obtain higher total value.The global selection uses the shared budget across customers rather than deciding independently for each one.Source: §2.3 · p. 3
3 SOLUTION FRAMEWORK
The framework estimates customer-level promotion effects, then solves an online multiple-choice knapsack problem to select promotions under capacity constraints. Its approximation handles negative values and weights through incremental quantities, efficiency angles, and a threshold updated from observed customers.
3.1 CATE Estimation
- Uplift modeling estimates purchase and net-revenue effects for each customer-promotion pair, supplying the item sets for optimization.Two-models, transformed-outcome, and X-learner estimators are evaluated using Qini curves and Qini Score.Source: §3.1 · p. 3
3.2 MCKP Approximation Solution
- The four-step approximation eliminates dominated items, computes incremental values and weights, converts them to efficiency angles, and selects an item using a capacity-oriented threshold.It extends an earlier MCKP approximation to negative values, negative weights, and potentially negative budget constraints.Source: §3.2 · pp. 3–4
3.2.1 Dominant items.
- Dominant items are those not dominated or LP-dominated, forming the upper-left convex hull and excluding options not expected in an optimal solution.The dominant set can be found in O(|K_i| · log|K_i|) time.Source: §3.2.1 · p. 4
3.2.2 Incremental value and weight.
- Incremental quantities measure the extra value and weight of choosing each dominant item rather than the preceding item in increasing-weight order.With negative values and weights, incremental efficiency need not be monotone between the first two items, breaking Zhou and Naroditskiy’s algorithm [36] and motivating the efficiency angle adaptation.Source: §3.2.2 · p. 4
- The efficiency angle function maps an angle to the expected weight of encountered dominant items above it, using their sorted, cumulative-average weights to guide future choices.The threshold is chosen so expected future dominant-item weights fit the remaining capacity.Source: §3.2.4 · p. 4
3.2.4 Efficiency angle threshold.
- The threshold selects the smallest angle above it among a customer’s dominant items, aiming for the best value within capacity.The update uses the total customer count, current iteration, and average number of dominant items per customer estimated from observations.Source: §3.2.4 · p. 4
3.3 Algorithm Complexity
- Per-customer evaluation takes O(|K_i| · log|K_i|) time without threshold updates; function updates can run separately, often in batches.With the sorted dominant-item list maintained, a threshold update takes O(|U|).Source: §3.3 · p. 5
3.4 Solution Toy Example
- In the toy example, nine promotion items are shown, with promotions 1 to 5 dominant and forming an upper-left convex hull; items 6, 7, and 9 are dominated, while item 8 is LP-dominated.Item 1 has the greatest efficiency angle, while item 5 has the smallest.Source: §3.4 · p. 5
4.1 Randomized Controlled Trial
A randomized online multi-variant trial on Booking.com traffic measured purchase completion and revenue effects for three discount levels. All three increased purchases but caused net revenue loss, motivating personalization under a zero-budget goal.
4.1 Randomized Controlled Trial
- All three discount treatments had a conclusively positive effect on purchases but a conclusive net revenue loss.The trial compared treatment groups receiving three discount levels with a no-promotion control over several weeks on Booking.com traffic.Source: §4.1 · p. 5
- The trial’s multi-variant A/B/N design randomized real website traffic among three discount groups and a no-promotion control.Purchase completion, promotion cost, and incremental revenue were aggregated and compared across groups.Source: §4.1 · p. 5
- Because the discounts incurred net revenue loss, the study targets personalization that could sustain a promotional campaign at zero budget over the long term.Source: §4.1 · p. 5
4.2 Uplift Modeling on Experimental Data
Uplift models were trained on randomized-trial data and tested on a disjoint portion to estimate purchase and net-revenue effects. On the test set, the models ranked customers by predicted effects for both outcomes.
4.2 Uplift Modeling on Experimental Data
- The randomized-trial dataset contains more than 20 million entries, split into training and disjoint prediction portions.Each entry includes purchase completion Y, total net revenue R including promotional costs, and customer covariates X.Source: §4.2 · p. 6
- The test-set Qini curves show that the models successfully rank customers by predicted CATE for both purchase completion Y and net revenue R.The reported Qini curves compare three discount types on normalized axes.Source: §4.2 · p. 6
- For each discount type, treating the full population has a clear effect, and stronger positive effects on Y accompany stronger negative effects on R.Source: §4.2 · p. 6
4.3 Datasets
The evaluation uses experimental discounts, simulated campaigns, and a public email-campaign dataset. These datasets provide different customer populations and value-weight settings for testing the method.
4.3 Datasets
- The evaluation includes experimental, synthetic, and publicly available datasets, with dataset properties summarized in Table 1.Source: §4.3 · p. 6, Table 1 · p. 6
4.3.1 Experimental data.
- The experimental discounts dataset subsamples 200,000 customers and assigns four options per customer: three discount levels and no discount.Estimated value and weight distributions span all four quadrants, though most items have positive value and positive weight.Source: §4.3.1 · p. 6
4.3.2 Synthetic data.
- The synthetic campaign varies population size from 5,000 to 100,000 and simulates nine discount levels; its fitted conversion-uplift model assumes diminishing marginal effects as discounts increase.Higher discounts have higher average values and weights, with greater variance in both; simulated net revenue loss can be negative because conversion uplift affects revenue.Source: §4.3.2 · pp. 6–7
4.3.3 Public data.
- The Hillstrom public dataset covers 64,000 customers randomly assigned to men’s merchandise, women’s merchandise, or no-treatment email campaigns over two weeks.Unlike discounts, email campaigns have no direct cost factor, and their offline channel permits assignment optimization to be precomputed.Source: §4.3.3 · p. 7
4.4 Assignment Optimization Methods
The study compares online and offline promotion-assignment methods under a zero-budget constraint. They range from independent customer-level choices to adaptive online optimization and offline upper-bound solutions.
4.4 Assignment Optimization Methods
- Global selects one budget-feasible treatment for all customers, or no promotion if none meets the budget.It chooses the treatment with the highest total value.Source: §4.4.1 · p. 7
4.4.1 Global Selection (Global).
- Local independently selects each customer's highest-value promotion with non-positive weight, without sharing information across decisions.This customer-level solution can be applied online.Source: §4.4.2 · p. 7
4.4.2 Local Solution (Local).
- Greedy picks each customer's highest-value promotion within current capacity, allowing positive-weight choices when earlier picks free capacity.Source: §4.4.2 · p. 7
- Online MCKP adapts each arrival's promotion decision to remaining budget and an updated efficiency-angle function, without prior knowledge of value and weight distributions.Source: §4.4.4 · p. 7
4.4.4 Online MCKP (On-MCKP).
- Offline MCKP uses the same selection algorithm with items supplied in advance, fitting the efficiency-angle function once and then holding it fixed.Source: §4.4.5 · p. 7
4.4.6 Integer Linear Programming (ILP).
- ILP supplies an offline optimal upper bound; with budget C=0, the solver had a three-hour limit and missed optimality in only one instance.That instance still yielded a feasible solution with an infinitesimal optimality gap.Source: §4.4.6 · pp. 7–8
5 RESULTS
The suggested MCKP methods outperform the Global, Local, and Greedy benchmarks, with large gains on the real discounts dataset. Results also characterize selected promotions and show how online weights and thresholds evolve over time.
5.1 Optimization results
- Global achieves 16–26% on simulated instances and no feasible real-discounts solution; Local delivers about 51%, while Greedy reaches 65%-80%.Source: §5.1 · p. 8
- Suggested MCKP solutions widely outperform Global, Local, and Greedy; on real discounts, improvements are +170% versus Local and +51% versus Greedy.Source: Table 2 · p. 8, Figure 7 · p. 8, §5.1 · p. 8
- Off-MCKP's optimality gap is at most 7.4×10−5, while On-MCKP's maximal gap is 0.245% on real discounts.Source: Table 2 · p. 8, Figure 7 · p. 8, §5.1 · p. 8
5.3 Online Dynamics
- On the 5K simulation, cumulative weight fluctuates around target capacity, sometimes exceeding it before recovering to the zero target.Source: Figure 8 · p. 9, §5.3 · p. 9
5.2 Solution Properties
- Selected solutions form a linear value–weight separation in Sim10K and a tradeoff in Discounts, while Hillstrom selections are scattered because capacity does not bind.Source: §5.2 · p. 9
- No selected item has negative value and positive weight because the default dominates that quadrant; no-promotion is selected in Discounts and Hillstrom, but not in simulation.Source: §5.2 · p. 9
5.3 Online Dynamics
- The efficiency-angle threshold fluctuates early, converges near θ=−0.085, then changes sharply in final rounds and returns near zero when no more users are expected.The authors note that this end-of-horizon behavior is not expected in real self-sponsored campaigns, which are expected to run indefinitely.Source: §5.3 · p. 9
6 CONCLUSION
The paper formulates promotions personalization as an online constrained multiple-choice knapsack problem and reports an adaptive method with budget compliance and near-optimal promotional impact. It also identifies extensions and online validation as future work.
6 CONCLUSION
- Above 99.7% of possible optimal promotional impact, the adaptive method complies with budget constraints by responding to offsets from past decisions.The authors report this result for their experimental study.Source: §6 · p. 9
- The framework combines causal uplift estimation with online constrained optimization and extends multiple-choice knapsack to negative values and weights.The authors note these cases are common in causal estimations and especially useful with a zero-budget constraint.Source: §6 · p. 9
- In the promotional business case, personalization transformed an insufficient-budget campaign into an effective, long-term, self-sponsored application.Source: §6 · p. 9
- The framework can extend to different numbers and types of promotions per customer and applications beyond e-commerce, including industrial production, traffic solutions, and trading algorithms.The authors also anticipate potential improvement from an end-to-end tailored learner and call for online comparison and testing on additional use-cases.Source: §6 · p. 9