升舱由商家掏钱

参数定义

参数	含义
$\tau_{ij}$	采用折扣 $j$ 时冒泡 $i$ （包含该冒泡的本身特征）的发单率增量
$ecr(j)$	采用折扣 $j$ 时冒泡发单率（忽略冒泡 $i$ 下标）（ $j=0$ 时不补贴）
$cr_{i}$	冒泡 $i$ 的发单完单率
$\tau_{j}^{r}(x_{i})$	折扣 $j$ 给冒泡 $i$ 带来的 $gmv$ 增量
$\tau_{j}^{c}(x_{i})$	折扣 $j$ 给冒泡 $i$ 带来的 $cost$ 增量
$B$	补贴预算

优化模型

\begin{aligned} minf(Z)=-\sum_{i=0}^{N-1}\sum_{j=0}^{M}\tau_{j}^{r}(x_{i})\cdot z_{ij} \\ s.t \sum_{i=0}^{N-1}\sum_{j=0}^{M}\tau_{j}^{c}(x_{i})\cdot z_{ij} \leq B \end{aligned}

\begin{aligned} minL(Z,\lambda)=-[\sum_{i=0}^{N-1}\sum_{j=0}^{M}(\tau_{j}^{r}(x_{i})-\lambda \tau_{j}^{c}(x_{i}))\cdot z_{ij}]-\lambda \cdot B \end{aligned}

原问题目标函数和约束都为凸函数，满足强对偶条件，转为求解

\max_{\lambda \geq 0}\min_{Z \in D}L(Z,\lambda)

其中 $D$ 为原问题决策变量的定义域

当 $\lambda$ 和 $B$ 固定时，该问题实际上为一个连续背包问题，此时：

\begin{aligned} z_{ij}^{*}=\underset{z_{ij}}{\arg\max}\sum_{j=0}^{M}(\tau_{j}^{r}(x_{i})-\lambda \tau_{j}^{c}(x_{i}))\cdot z_{ij} \\ j^{*}_{i}=\underset{j}{\arg\max}(\tau_{j}^{r}(x_{i})-\lambda \tau_{j}^{c}(x_{i})) \end{aligned}

其中：

\begin{aligned} \tau_{j}^{r}(x_{i})-\lambda \tau_{j}^{c}(x_{i}) \end{aligned}

即为连续背包问题中的 $\frac{value_{j}}{weight_{j}}$ ，补贴策略选择 $\tau_{j}^{r}(x_{i})-\lambda \tau_{j}^{c}(x_{i})$ 最大的即可

因此，我们要对该问题求解，应该分成两步：

不同的补贴率对应不同的预算 $B$ ，对每个补贴率求出最优的 $\lambda$ ，作为字典供线上使用对于每种补贴率下的预算 $B$ ，它和gmv相关，在补贴率确定的情况下，通过某种算法确定gmv，固定gmv就等同于固定了 $B$ ，此时通过三分法求解 $\lambda^{*}$

$\lambda$ 的实际意义是边界ROI， $B$ 越少的情况下， $\lambda$ 越大， $B$ 越多的情况下， $\lambda$ 越小