E-Commerce Promotions Personalization via Online Multiple-Choice Knapsack with Uplift Modeling

问题背景

促销在电子商务平台的营销工作中起着关键作用。他们通过为客户提供更多的价值，从而显著提升了销售额。向客户提供优惠(如图1所示)会产生完成预订的动机，并推动业务增长。在增加购买可能性的同时，如果促销活动时的销售净收入小于不提供促销活动时的净收入，促销活动也可能招致增量货币损失。通常，会制定专门的预算来弥补这一增加的净收入损失，以确保可持续的竞选活动。

预算约束营销最近越来越受欢迎，尤其是在促销分配方面。许多解决方案考虑一个恒定的成本因素[18]。然而，在存在因果增量估计的情况下，晋升的货币影响可能导致不同的、积极的或消极的结果。现有的解决方案主要依赖于基于意图的模型，不能适应因果模型的负值，因此不适用于此类问题。

本文利用提升模型(uplift modeling)的因果估计，形式化了预算约束下的多选择晋升分配问题。我们提出了一种新的在线选择背包设置中负值和权重的解决方案。我们在最大的在线旅游平台之一Booking.com上展示了该方法的部署，并在现实生活的实验研究中对其进行了各种基准测试。

我们的主要贡献有:

1. 将预算约束下的促销个性化问题表述为具有因果估计的在线mckp。
2. 基于因果隆起模型估计和多项选择背包优化的两步求解方法。
3. Online-MCKP解的新颖扩展，以适应负值和权值。
4. 在Booking.com平台进行大规模的真实促销活动实验研究。

解决方法

符号定义

𝑌𝑖 - a binary random variable representing a completion of a purchase

​ 一个二进制随机变量，表示购买完成

𝑅𝑖 - a continuous random variable representing the net monetary revenue associated with the purchase (sum of all revenues minus all promotional costs)

​ 表示与购买相关的净货币收入的连续随机变量（所有收入的总和减去所有促销成本）

𝑌𝑖 (𝑘): potential purchase 对于客户𝑖 和促销𝑘如果客户𝑖 获得促销𝑘

𝑅𝑖 (𝑘): potential net revenue表示如果客户𝑖 获得促销𝑘.

k=0, no promotion
$$
CATE_{𝑌} (𝑖, 𝑘) = E(𝑌_{𝑖} (𝑘) − 𝑌_{𝑖} (0) | 𝑋 = 𝑥𝑖 )
$$

表示如果促销k，则对客户i的预期购买概率的增量影响

$$
CATE_{𝑅} (𝑖, 𝑘) = E(𝑅_{𝑖}(𝑘) − 𝑅_{𝑖}(0) | 𝑋 = 𝑥𝑖 )
$$

ppt66-68

CATEL (𝑖, 𝑘) = −CATE𝑅 (𝑖, 𝑘)

𝑣𝑖𝑘 is CATE𝑌 (𝑖, 𝑘)and 𝑤𝑖𝑘 is CATEL (𝑖, 𝑘)

MCKP：给你N组物品，然后每一组你至多选择一个物品,每个物品都有自己的体积和价值，现在给你一个容里为M的背包，让你用这个背包装物品，使得物品价值总和最大

这里一个人是一组，K1,K2….

每个人可能收到的优惠券k∈Ki,k=0表示这个用户没有优惠

解决方案框架

先调了公共的UpliftML package，Optimization部分

Dominant items

删除Dominant和 LP-Dominant，和The Multiple-Choice Knapsack Problem这篇一样

Incremental value and weight

感觉和mckp那篇也差不多

此外，the incremental efficiency 𝑣𝑖𝑑/𝑤𝑖𝑑 is monotonically decreasing with 𝑑，除了d=0到d=1，可能w和v是负的，看图3。

Efficiency angle

Efficiency angle threshold

1: Input:

• Set of past dominant items 𝑃

• Knapsack capacity 𝐶

• Current customer index 𝑖

• Expected number of customers |𝑈 |

2: Sort 𝑃 by decreasing angle 𝜃𝑝

3: for 𝑝 ∈ 𝑃 do:

4: if p=0:
$$
𝑓 ((𝜃_{0}) ) = w_{0}/|𝑃 |
$$

5: else:
$$
𝑓 ((𝜃_{p}) ) = 𝑓 (𝜃_{p} −1 ) + 𝑤_{p} /|𝑃 |
$$

6: end for

7: Return efficiency threshold 𝜃^{*}:
$$
𝜃^{ * } ← 𝑚𝑖𝑛_{𝑝∈𝑃} ({ 𝜃_{p} | 𝑓 (𝜃_{p} ) ≤ 𝐶/(|𝑃 |/𝑖 · (|𝑈 |−𝑖+1) )})
$$
// TODO：这个就不知道咋想出来的，问问去

总的：O (|𝐾𝑖 | · 𝑙𝑜𝑔|𝐾𝑖 |)，𝜃更新具有O(|𝑈 |) 复杂性

系统架构

比较了好几种optimization，global，local， Greedy，下面几个

1. Online MCKP (On-MCKP):
   • 情境描述：该方法对应于真实世界中的情景，其中顾客逐一到达，每次决策都必须在特定时间步骤中做出，即每到一个新顾客就需要做出促销活动的决策。
   • 信息限制：在开始时，没有有关一般权重和价值分布的信息。
   • 决策过程：方法会根据剩余预算和更新的效率角度函数（Algorithm 2描述）来调整促销活动的分配决策。
2. Offline MCKP (Off-MCKP):
   • 情境描述：与Online MCKP相比，这种方法不同的是提前知道所有物品，即所有的顾客和可能的促销活动。
   • 信息利用：因为提前知道所有物品，可以在分配决策之前仅适应一次效率角度函数（Algorithm 1描述）。
   • 决策过程：在知道所有顾客和促销活动之后，算法会决定为每个顾客提供哪种促销活动，而不需要更新效率角度函数。

在这两种方法中，主要的区别在于信息利用和决策时机。Online MCKP需要在每个时间步骤中动态地做出决策，而Offline MCKP可以提前知道所有信息，然后在不需要动态更新的情况下做出决策。

1. Integer Linear Programming (ILP)
   • 解决方法：ILP求解器用于在离线设置中寻找最优的上界解决方案。
   • 线性规划：MCKP问题可以被表示为一个线性规划，并且采用了论文中所描述的线性方程（Equation 1）来解决。
   • 预算常数：预算常数 C被设置为零（C=0）。
   • 工具和求解器：研究使用了 Python PuLP 软件包和 CBC（Coinor branch and cut）求解器。整体求解器运行时间被限制在3小时内。
   • 性能说明：尽管对于背包问题有更合适的求解器，研究中仅遇到了一个实例，即在有限的运行时间内无法达到最优解。不过，它达到了一个可行解，且具有微小的最优性差距。

ILP方法利用了数学规划中的整数线性规划来解决MCKP问题。在离线设置下，ILP被用来找到一个最优的上界解决方案，其依赖于线性规划的建模，并使用了特定的求解器和工具来解决问题。

结论

这部分感觉看原文，比较了这几个方法比ILP垃圾多少（不是），然后是看online-mckp自己的一个性质：bound，然后three flat-discount levels 看ROI，最后是一个净利润和阈值的浮动（？