IAS

发表于 2025-01-27 分类于 research

Optimally Integrating Ad Auction into E-Commerce Platforms

IAS（Integrated Ad System）模型即集成广告系统模型，用于描述电商平台上广告与有机搜索结果混合排列的情况。该模型的目标函数和约束条件设计紧密围绕电商平台关注的核心指标，旨在平衡广告收入与用户体验。

目标函数
- 收入（Revenue）：$Revenue =\int_{V} \sum_{i \in A} p_{i}(v) w_{i} x_{i}(v) f(v) dv$，此公式表示收入是对所有广告商品的支付价格、质量因子、分配情况以及概率分布进行积分求和。其中，$p_{i}(v)$是广告商品$i$的支付价格，$w_{i}$为其质量因子，$x_{i}(v)$代表分配规则，$f(v)$是概率分布函数。通过这一函数计算，反映出平台从广告投放中获取的即时收入。
- 商品交易总量（GMV）：$GMV=\int_{V}\left[\sum_{i \in A} g_{i} w_{i} x_{i}(v)+\sum_{i \in O} g_{i} w_{i} x_{i}(v)\right] f(v) dv$，该公式计算的是平台的商品交易总量，考虑了广告商品和有机商品的预估交易量、质量因子和分配情况。其中，$g_{i}$为商品$i$的预估交易量，对广告商品和有机商品分别求和再积分，体现了平台业务的整体交易规模，是衡量用户体验和平台长期收益的重要指标。
- 无约束问题（Unconstrained Problem）：$UCST (\alpha)$给定加权系数$\alpha \in[0,1]$，通过线性凸组合收入和GMV来构建目标函数，即$max _{x \in \mathcal{X}} \alpha \cdot Revenue +(1-\alpha) \cdot GMV$。该目标函数旨在在不同权重下，同时考虑收入和GMV，寻找能使两者综合效益最大化的机制。例如，当$\alpha$接近1时，更注重收入；当$\alpha$接近0时，则更倾向于GMV。
  Unconstrained Problem $UCST (\alpha)$ ) Given the weighted coefficient $\alpha \in[0,1]$ ,the unconstrained problem $UCST (\alpha)$ ) can be written as
  $max _{x \in \mathcal{X}} \alpha \cdot Revenue +(1-\alpha) \cdot Volume. (4)$
- 约束问题（Constrained Problem）：$CST(V_{0})$给定GMV阈值$V_{0}$，以优化收入为目标，即$max Revenue$，同时需满足$GMV \geq V_{0}$和$x \in \mathcal{X}$的约束。此目标函数强调在保证一定GMV水平的前提下，最大化广告收入，体现了平台在平衡用户体验和短期收益时的考量。
  Constrained Problem $CST(V_{0})$ ) Given a threshold $V_{0}$ , the constrained problem $CST(V_{0})$ ) can be written as
  $$max Revenue \quad (P1)$$
  $$s.t. Volume \geq V_{0} \quad(C 1.1)$$
  $$x \in \mathcal{X} \quad(C 1.2)$$
约束条件
- 分配规则约束：对于分配规则$x_{ik}(b)$需满足$\sum_{k} x_{ik}(b) \leq 1, \forall i \in A \cup O$，确保每个商品最多被分配到一个展示位；$\sum_{i \in A} x_{ik}(b)+\sum_{i \in O} x_{ik}(b)=1, \forall k$，保证每个展示位都有且仅有一个商品；$x_{ik}(b) \in{0,1}, \forall i, k$，表示商品是否被分配到展示位只能是0或1的二元选择。这些约束保证了分配的合理性和唯一性。
- 个体理性（Individual Rationality）：$U_{i}(x, p, b_{i}) \geq 0, \forall b_{i} \in[0, u_{i}], \forall i \in A$，此约束确保广告商参与拍卖的期望效用非负，即广告商在平台的广告投放行为能获得至少为零的收益，这是吸引广告商参与的基本条件。
- 贝叶斯激励兼容（Bayesian Incentive Compatibility）：$U_{i}(x, p, v_{i}) \geq U_{i}(x, p, b_{i}), \forall b_{i} \in[0, u_{i}], \forall i \in A$，该约束保证广告商如实报告自身价值是最优策略，避免广告商虚假报价，维护拍卖机制的公平性和有效性。

无约束问题$UCST(\alpha)$

目标函数：$max {x \in \mathcal{X}} \alpha \cdot Revenue+(1 - \alpha)\cdot GMV(4)$。这里的$\alpha\in[0,1]$是加权系数，用于平衡对收入和GMV的侧重程度。
转化为引理 2:要最大化目标函数（4），机制需要最大化目标
$$\int{V} \sum_{i \in I}\left(\alpha \phi_{i}\left(v_{i}\right)+(1-\alpha) g_{i}\right) w_{i} x_{i}(v) f(v) d v-\alpha \sum_{i \in I} U_{i}(x, p, 0) . (5)$$
修正虚拟价值排序：机制$M$涉及到定义修正虚拟价值$\psi_{i}(v_{i})=(\alpha \phi_{i}(v_{i})+(1 - \alpha)g_{i})w_{i}=(1 - \alpha)g_{i}w_{i}$。其中$\phi_{i}(v_{i})$是广告商品$i$的虚拟价值，$g_{i}$是商品$i$的预估交易量，$w_{i}$是商品$i$的质量因子。按照这个修正虚拟价值对所有商品（包括广告商品和有机商品）进行排序。
定价规则(迈尔森)：有机商品的支付为0，广告商品的支付价格是根据其在排序中的位置和相关价值计算得出的，以保证个体理性（广告商参与拍卖的期望效用非负）和贝叶斯激励兼容（广告商如实报告自身价值是最优策略）。
给定分配规则和支付规则，广告项目 i 的出价为$b_{i}$时的预期效用可以表示为：$$U_{i}\left(x, p, b_{i}\right)=\int_{V_{-i}}\left(v_{i}-p_{i}\left(b_{i}, v_{-i}\right)\right) w_{i} x_{i}\left(b_{i}, v_{-i}\right) f_{-i}\left(v_{-i}\right) d v_{-i}$$
因为$p(b)$只出现在$U_{i}(x,p,0)$中，并且我们需要保证（IR）的性质，根据引理 1，如果我们选择$p_{i}(v)=v_{i}-\frac{\int_{0}^{v_{i}} x_{i}(s_{i},v_{-i})ds_{i}}{x_{i}(v)}$作为支付规则，那么$U_{i}(x,p,0)$将为 0，并且我们只需要考虑选择合适的$x(b)$来最大化式（5）的第一部分。
分配规则：将广告商品插入有机商品序列进行分配。对于分配规则$x_{ik}(b)$，要满足$\sum_{k}x_{ik}(b)\leq1,\forall i\in A\cup O$（每个商品最多被分配到一个展示位）、$\sum_{i\in A}x_{ik}(b)+\sum_{i\in O}x_{ik}(b) = 1,\forall k$（每个展示位都有且仅有一个商品）和$x_{ik}(b)\in{0,1},\forall i,k$（商品是否被分配到展示位是二元选择）等条件。
对于分配规则，我们将 $\psi_{i}(v_{i}) \stackrel{ def }{=}(\alpha \phi_{i}(v_{i})+(1-\alpha) g_{i}) w_{i}$ 定义为物品 $i$ 的修正虚拟价值。不难验证，以下分配规则可以最大化公式（5）的第一部分。
$x_{i k}(v)= \begin{cases}1 & 如果\psi_{i}\left(v_{i}\right)是第 k 高的修正虚拟价值，k\in{1,2,\ldots,K}。\0&否则。\end{cases}$

约束问题$CST(V_{0})$ -商业化率约束

可通过对偶转为无约束问题

放宽约束条件：由于可行域是离散的，即$x_{i k}(v)$不是关于出价$v$的连续函数，因此很难直接优化目标。我们首先将约束$x_{i k}(v)∈{0,1}$在（C1.2）中放宽为$x_{i k}(v)∈[0,1]$，并将放宽后的可行域记为$\bar{x}$。放宽后的约束问题为：
最大化$$R(x)\stackrel{ def }{=}\int_{V}\sum_{i\in I}w_{i}p_{i}(v)x_{i}(v)f(v)dv（P2）$$
约束条件为$$V(x)\stackrel{ def }{=}\int_{V}\sum_{i\in I}g_{i}w_{i}x_{i}(v)f(v)dv\geq V_{0}（C2.1）$$
$$x\in\overline{\mathcal{X}}（C2.2）$$
对偶问题：对于可访问的$V_{o}$，强对偶性成立意味着
$$\begin{aligned}&\underbrace{\max_{x:x\in\mathcal{X},V(x)\geq V_{0}}R(x)}{\text{原始问题}}=\underbrace{\min{\lambda\geq0}\max_{x\in\mathcal{X}}\left(R(x)+\lambda\left(V(x)-V_{0}\right)\right)}{\text{对偶问题}}\&=\min{\lambda\geq0}\max_{x\in\mathcal{X}}\left[\int_{V}\sum_{i\in I}\left(p_{i}\left(b_{i}\right)+\lambda g_{i}\right)w_{i}x_{i}(b)f(b)db-\lambda V_{0}\right]。\end{aligned}$$
分配规则：当给定一个$\lambda$时，它是一个具有松弛可行域$\bar{x}$的无约束问题。由于$\bar{x}$的系数矩阵是完全单模矩阵([22])，内部问题的最优解是整数形式，即 0-1 形式。因此，内部问题的最优解可以通过机制 M 以$\alpha = 1/(\lambda + 1)$获得，即
$$ x_{i k}^{\lambda}(v)=\begin{cases}1&\text{如果}\psi_{i}^{\lambda}\left(v_{i}\right)\text{是第}k\text{高的，}k\in{1,2,\ldots,K},\0&\text{否则，}\end{cases}$$
其中$\psi_{i}^{\lambda}(v_{i})\stackrel{def}{=}[(\phi_{i}(v_{i})+\lambda g_{i})w_{i}]/(\lambda + 1)$。
定价规则：$p_{i}^{\lambda}(v)$可以通过在(7)中将$x_{i k}(v)$替换为$x_{i k}^{\lambda}(v)$得到。
$\lambda$计算：二分
定理 2：具有阈值$V_0$的约束问题等价于一个具有系数$\alpha^{}$的无约束问题，其中$\alpha^{}=1/(\lambda^{}+1)$，并且$\lambda^{}$是约束问题中的最优拉格朗日乘子。

广告数量约束

问题设定：在集成广告系统中引入对广告商品总数的限制，要求广告商品数量不超过 $c$ ，即 $\sum_{i \in A} \sum_{k} x_{ik}(v) \leq c$，将此约束加入原有的约束条件集 $x$ 后得到新的可行域 $x’$。
无约束问题的最优机制：基于此前无约束问题的结论，商品按修正虚拟价值 $\psi_{i}(v_{i})$ 排序。在新约束下，为保证广告商品数量符合预算，在排序时仅考虑排名前 $c$ 的广告商品。由此得到扩展机制 $M’(c)$，具体步骤为：
- 将所有广告商品按 $\psi_{i}(v_{i})$ 降序排列，保留前 $c$ 个广告商品，删除其余广告商品；
- 针对剩余的广告商品和所有有机商品，运行系数为 $\alpha$ 的原无约束问题机制 $M$。
- 由于原机制 $M$ 的最优性以及对广告商品数量的有效控制，$M’(c)$ 是当前设定下无约束问题的最优机制。
约束问题的求解：对于约束问题，其求解逻辑与前文类似，但由于新可行域 $x’$ 的系数矩阵不再是全幺模矩阵，导致求解难度增加。通过将其转化为最小费用最大流问题（证明见附录 Lemma 6），可证明松弛问题仍具有0 - 1形式的最优解。基于此，约束问题仍能通过选择合适参数转化为无约束问题求解，从而将此前针对无约束和约束问题关系的结论（Theorem 2）扩展到存在广告数量预算约束的场景。

广告间隔约束

用广告数量约束的机制，分别运行局部的无约束问题

PC端

页面划分：当我们在电子商务平台上通过个人电脑搜索产品时，搜索结果通常显示为几行，每行包含几个项目。受这种布局的启发，我们希望限制每行中的广告数量以让用户感到舒适。鉴于此，我们将一个搜索结果页面分成多行，每行包含连续的 l 个槽位。然后，我们要求在这 l 个槽位中显示的广告项目最多为 c 个。我们将这个模型称为稀疏集成广告系统——行（SIASR）。
约束条件：$$\sum_{i \in A} \sum_{k = ml + 1}^{(m + 1)l} x_{ik}(v)≤c，m = 0,1,\ldots,|K/l|$$
$$\sum_{i \in A} \sum_{k=\lfloor K / l] l+1}^{K} x_{i k}(v) ≤c$$。将它们添加到$x$中并表示新的约束条件。
无约束问题的最优机制：基于上述分析，我们可以对每个部分运行机制(M’(c))来为稀疏集成广告系统（SIASR）生成一个可行的广告排列方案。这是因为机制(M’(c))本身具有最优性，所以每个部分都能实现最优的广告商品分配，进而使得整个页面所有展示位都能达到全局最优的分配效果。由此，我们得到了在这种设定下的最优机制，记为(\tilde{M}(c, l))。
- 第一步：运行机制(M’(c))，对所有商品（包括广告商品和自然商品）分配前(l)个展示位。机制(M’(c))会根据商品的相关价值对商品进行排序，并依据广告商品数量预算(c)，从所有商品中选择合适的商品分配到这(l)个展示位上。
- 第二步：运行机制(M’(c))，对剩余的所有商品分配接下来的(l)个展示位。在完成第一步分配后，剩余商品的集合发生了变化，再次运行机制(M’(c))，从这些剩余商品中选择合适的商品填充接下来的(l)个展示位。
- 第三步：重复第二步，直到所有展示位都分配完毕。需要注意的是，在最后一轮分配时，展示位的数量可能会小于(l)。这是因为前面按照每(l)个展示位一轮进行分配，到最后可能会剩下不足(l)个展示位，此时依然按照机制(M’(c))对剩余商品进行分配，以完成整个搜索结果页面的广告与自然商品的分配。
约束问题：我们通过引理 7（在附录中显示）克服了这个问题。到目前为止，我们解决了 SIASR 的受约束问题，并将定理 2 扩展到了这种情况。
引理 7.对于 SIASR，约束问题的松弛内问题可以构造为最小费用最大流问题，并且具有 0-1 形式的最优解。

移动端

页面划分：一般来说，输入一个关键字后，搜索结果在一列中显示（与个人电脑终端的布局不同）。如果我们仍然想限制广告的稀疏性，我们需要在任何连续的 l 个位置上添加约束，即任何连续的 l 个位置上最多显示 c 个广告项。
约束条件：$\sum_{i∈A}\sum_{k = m + 1}^{m + l}x_{ik}(v)\leq c$，$m = 0,1,\ldots,K - l$，并将新的可行区域表示为$\hat{x}$。我们将这个模型称为稀疏集成广告系统——列（SIASC）。
无约束问题的最优机制：

运行机制$M’(c)$以在所有物品上分配前$l$个时段。
运行机制$M’(c - a)$，为所有剩余物品分配下一个时段，其中$a$是最后$l - 1$个时段中的广告物品数量。
重复步骤 2，直到所有槽位都被分配。

约束问题：对于约束问题，我们可以将 SIASR 中使用的方法扩展到这种设置。唯一的区别是，在这种设置下，连续的 l 个槽有更多的约束。然而，最终它并不影响难度。我们只需要稍微修改一下图 6 的结构：添加一定数量的节点$k_{i}$来代表更多的组，并连接弧$s_{j}^{\prime\prime}k_{i}$，其中$j\in{i,i + 1,\cdots,i + l - 1}$，以及弧$k_{i}t$。其他分析是相似的。这样，我们将定理 2 推广到 SIASC 的情况。