BSD：Auction with ROI constraints

作者: shudaxu | 来源:发表于2021-05-17 18:25 被阅读0次

之前关于BSD的讨论：https://www.jianshu.com/p/5edf15c787ed [1]

问题建模Modeling：

类似[1]中的方案，此处为以无偏winning rate建模的方式最优化期望收益）
当然，这种modeling的一大问题是，真实的成功率与无偏随机数据是有差距的，因为我们出价与市场价并不互相独立。 $OurBid \not\perp Others'Bid$
形式化：
$u(r)$ 为utility， $g(r)$ 为预估的用以计算roi的收益。
$\max_{b(r)} \int_r u(r) w(b(r)) p(r) dr$
s.t.1： $\int_r b(r) w(b(r)) p(r) dr \leq B$
s.t.2： $\frac {\int_r g(r) w(b(r)) p(r)dr } {\int_r b(r) w(b(r)) p(r) dr} \geq ROI$
得到：
$L(b(r),\lambda_1,\lambda_2) = \int_{r}^{} \left[ -u(r) w(b(r)) + \lambda_1b(r)w(b(r)) + \lambda_2 ROI w(b(r)) b(r) - \lambda_2 w(b(r)) g(r) \right]p(r) dr - \lambda_1 B$

Solution:

KKT condition：

对 $b(r)$ 偏导为0：
$-u(r) \frac{\partial w(b(r))} {\partial b(r)} + (\lambda_1 + \lambda_2ROI)\left[ \frac{\partial w(b(r))} {\partial b(r)} b(r) + w(b(r)) \right] - \lambda_2 \frac{\partial w(b(r))} {\partial b(r)}g(r) = 0$ （1）
给定win函数:
$w(b) = \frac {b} {l + c*b}$ （2）
其中 $l,c$ 为拟合成功率的常数
求导可得：
$\frac{\partial w(b(r))} {\partial b(r)} = \frac {l}{(l + c*b)^2}$ （3）
将（2）（3）带入（1）化简可得：
$b^2 + \frac {2l} {c} *b - \frac {lu + \lambda_2lg }{c(\lambda_1 + \lambda_2ROI)} = 0$
解得： $b = \sqrt {\frac {l^2}{c^2} + \frac {lu + \lambda_2lg }{c(\lambda_1 + \lambda_2ROI)}} - \frac {l}{c}$
原约束与系数约束：
$\lambda_1,\lambda_2 \geq 0$
$\int_r b(r) w(b(r)) p(r) dr \leq B$
$\frac {\int_r g(r) w(b(r)) p(r)dr } {\int_r b(r) w(b(r)) p(r) dr} \geq ROI$
budegt互补松弛条件：
$\lambda_1 [\int_r b(r)w(b(r))p(r) dr - B ]=0$
roi互补松弛条件：
$\lambda_2 [ROI\int_r b(r) w(b(r)) p(r) dr -\int_r g(r) w(b(r)) p(r)dr ] = 0$

参数解法：

Qualification-LICQ：因为 $b(r) \in R^1$ ，所以当且仅当在其解 $x^*$ 处，激活条件对 $x$ （此处即 $b(r)$ ）梯度向量 $\triangledown g \neq 0$ 时满足LICQ。
很显然
1、在只有一个限制条件激活时，只要极值处限制条件对 $b(r)$ 的导数不为0，则这个条件就是满足的。
2、在多个限制条件激活时，肯定是不满足的。
Qualification-SC：对于多条件激活。判定是否满足SC，即优化目标 $f$ 与限制函数 $g$ ，是否都是convex的。判断方式需要求其二阶变分 $\delta ^2 L \geq 0$ 则满足SC。
为了简化问题，我们可以将当前假设的解带入，即在当前假设下，是否满足SC。
带入式子（2）得到如下：
$\frac{\partial^2 {w(b(r))} } {\partial {b(r)^2} } = \frac {-2lc} {(l+cb)^3}$ （4），根据成功率函数的图像，是恒小于0的。

Convexity of functional：[1]
a、目标函数的二阶变分：
$\delta^2 f = \int [u(r) \frac {2lc} {(l+cb)^3}]p(r)dr$
带入拟合出来的常数 $l,c$ ，在实际区间上积分大于等于0
b、预算限制的二阶变分：
$\delta^2 g_1 = \int [\frac {2l}{(l + c*b)^2} + \frac {-2lcb} {(l+cb)^3}]p(r)dr$
$= \int [\frac {2l^2}{(l + c*b)^3}]p(r)dr$
带入拟合出来的常数 $l,c$ ，其积分显然大于等于0
c、ROI限制的二阶变分：
$\delta^2 g_2 =\frac {\delta^2 \int [ROI*b(r) - g(r) ]w(b(r)) p(r)dr} {\delta b(r)^2}$
$= \int [\frac {2l^2ROI+2lcg(r)}{(l+cb)^3}]p(r)dr$
带入拟合出来的常数 $l,c$ ，其积分也显然大于等于0
所以，由此可以得出，当前问题在两个约束都生效时，满足SC

情况0： $\lambda_1=0, \lambda_2=0$
则 $b(r) \rightarrow inf$ ，明显不满足条件。
情况1： $\lambda_2 = 0$
这种情况下，等价于只有budget预算限制。
所以将 $b(r)$ 的解带入（将 $\lambda_2=0$ 带入，其中仅包含 $\lambda_1$ ），解如下问题即可：
$\int_r b(r)w(b(r))p(r) dr - B =0$
观察 $b(r)$ 解的形式与 $w(b)$ 的形式，可轻易得出 $\lambda_1$ 与预算消耗成反比 $b(r) \propto \frac {u}{\lambda_1}$
在这个问题中，由于无论 $\lambda_1$ 如何变化，排序是不变的。所以可以直接将数据带入，求方程的数值解即可。
当然，由于本身也是单调的，通过二分搜索也可以较容易地获得数值解。

情况2： $\lambda_1 = 0$
类似地，将 $b(r)$ 的解带入，求解ROI刚好满足的状态即可。
$ROI\int_r b(r) w(b(r)) p(r) dr -\int_r g(r) w(b(r)) p(r)dr = 0$
得到 $b(r) \propto (\frac {u}{\lambda_2} + g)$ ，可以看出 $\lambda_2$ 就是u的反向权重。 $\lambda_2$ 越大，越倾向于用g（收益）来排序，即参与竞价的ad的 $g(r)$ 越大，且总体出价越低（成本低），则ROI越大。
所以ROI对 $\lambda_2$ 单调递增，可以通过二分搜索以获得数值解。
（这种情况下，由于 $\lambda_2$ 的变化会影响排序，所以无法将数值全部带入直接求其数值解，当然，改写整个方程，将排序过程加入也是可以的，但是求解速度也并不一定会很快）
情况3： $\lambda_1 \neq 0,\lambda_2 \neq 0$
条件：如果上述两种方式求解出来分别的ROI，Budget不满足边界条件的（即都超出边界）。
此时两个KKT乘子都不为0，
即最优解在ROI刚好满足，Budget也刚好满足的边界上，KKT multiplier等价于Lagrangine multiplier。
将 $w(b(r))$ 带入松弛条件（同拉格朗日，等式约束，即偏导为0），求解如下方程组：
$\lambda_1,\lambda_2\begin{cases} \int_r b(r)w(b(r))p(r) dr - B =0 \\ ROI\int_r b(r) w(b(r)) p(r) dr -\int_r g(r) w(b(r)) p(r)dr = 0 \end{cases}$
化简后无特殊形式，不易求出解析解可由数值解法解出。
当然，这个方程组求解的最大问题同样在于，由于 $\lambda_1,\lambda_2$ 会影响排序，所以很难直接用传统的数值优化的方程组解法得到解。（TODO）