拍卖与博弈:计算广告中的底价问题

2024-09-03 18:38

本文主要是介绍拍卖与博弈:计算广告中的底价问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

流量变现和RTB

现代计算广告中,最广泛的流量交易模式为实时竞价模式,即Real-Time-Bidding(RTB)。实时竞价顾名思义,就是在流量到达时被放到交易市场进行公开的,实时的竞拍,参与竞拍的广告主赢得竞拍后,即可获得对这个流量的投放权,整个流程如图示。
RTB
以新浪微博的信息流广告为例,当我们刷微博时,微博的信息流(或者timeline)中会夹杂着广告,假设微博将信息流的第4和第10位作为广告位,那么每次你刷新微博后,list中的第4和第10条微博总会是推广(广告)微博。于是当用户A进入微博的信息流界面时,除了从服务器请求微博内容之外,还会同时向RTB请求广告内容,这个请求称之为曝光请求。RTB接受到该曝光请求后,将此次曝光放入流量市场进行实时拍卖,诸多广告主的投放系统(DSP)接到拍卖的事件后,立即对该曝光请求进行出价,一般来说根据曝光质量和属性不同,各个广告主对其出价也不尽相同。例如信息流第4位的曝光出价就比信息流第10位出价高,因为排在前面的广告更能引起用户注意,再如篮球鞋销售商对男性微博用户的曝光请求出价要比女性微博用户的曝光出价要高,因为篮球鞋的受众群体主要是男性。在广告主出价完成后,RTB则向出价最高的广告主请求广告内容,并且将此内容返回到微博客户端,于是用户在刷微博时就看到了这个广告,完成了一次广告曝光。这整个请求、竞价、返回广告的过程会在毫秒级别内完成。

第二高价和底价问题

在RTB的流量竞拍中是按照第二高价来计费的,这意味着如果第 t t t次曝光n个广告主对其出价分别为 b 1 ( t ) , b 2 ( t ) , b 3 ( t ) , . . . , b n ( t ) b_1(t),b_2(t),b_3(t),...,b_n(t) b1(t),b2(t),b3(t),...,bn(t),且有 b 1 ( t ) > b 2 ( t ) > b 3 ( t ) > . . . > b n ( t ) b_1(t)>b_2(t)>b_3(t)>...>b_n(t) b1(t)>b2(t)>b3(t)>...>bn(t),那么广告主1竞价胜出,但是媒体方只会向广告主1收费 b 2 b_2 b2元。这种计费方式主要可以让广告主失去调价的动力,否则在广告主竞价胜出之后,会立即调低出价,以期望使用更低的价格拿到曝光,从而提高自身收益。但是从媒体方的角度来说,第二高价的机制存在着 δ = b 1 ( t ) − b 2 ( t ) \delta = b_1(t)-b_2(t) δ=b1(t)b2(t)的利润空间没有充分利用,于是引出了底价机制。底价机制指的是RTB在竞价拍卖的过程中,设置一个最低价格 α \alpha α, 称之为底价。当 b 1 ( t ) < α b_1(t)<\alpha b1(t)<α时则RTB则拒绝售卖该流量,或者将流量导入其它交易市场售卖。当 b 1 ( t ) ≥ α > b 2 ( t ) b_1(t) \ge \alpha>b_2(t) b1(t)α>b2(t)时,按照 α \alpha α向胜出的广告主收费,当 b 2 ( t ) ≥ α b_2(t) \ge \alpha b2(t)α时,则按照 b 2 ( t ) b_2(t) b2(t)向胜出的广告主收费。总结起来,在第 t t t次竞价中,向竞价胜出的广告主收费 r ( t ) r(t) r(t)如式(1)所示。
r ( t ) = { α , b 1 ( t ) ≥ α > b 2 ( t ) b 2 ( t ) , b 2 ( t ) ≥ α 0 , α > b 1 ( t ) (1) r(t)=\left\{\begin{array}{ll}{\alpha,} & {b_{1}(t) \geq \alpha>b_{2}(t)} \\ {b_{2}(t),} & {b_{2}(t) \geq \alpha} \\ {0,} & {\alpha>b_{1}(t)}\end{array}\right. \tag{1} r(t)=α,b2(t),0,b1(t)α>b2(t)b2(t)αα>b1(t)(1)
r ( t ) r(t) r(t)的表达式中可以看到,当满足 b 1 ( t ) ≥ α > b 2 ( t ) b_1(t) \ge \alpha > b_2(t) b1(t)α>b2(t)时,媒体放可以比原来的纯二价计费方式多赚 β ( t ) = α − b 2 ( t ) \beta(t)=\alpha-b_2(t) β(t)=αb2(t),但也要注意到当 α > b 1 ( t ) \alpha > b_1(t) α>b1(t)时也存在损失 b 2 ( t ) b_2(t) b2(t)的风险。于是一个很自然的想法就是:

α \alpha α能自动调整,让 α \alpha α b 1 ( t ) b_1(t) b1(t)较大时, α \alpha α也能随之增大,反之则减小。 – 原则[1]

这就是动态底价的概念,我们重新把这个可以变化的底价定义为 α ( t ) \alpha(t) α(t),表示在第 t t t次竞价中的底价。式子(1)重新表述为式(2)。
r ′ ( t ) = { α ( t ) , b 1 ( t ) ≥ α ( t ) > b 2 ( t ) b 2 ( t ) , b 2 ( t ) ≥ α ( t ) 0 , α ( t ) > b 1 ( t ) (2) r^{\prime}(t)=\left\{\begin{array}{ll}{\alpha(t),} & {b_{1}(t) \geq \alpha(t)>b_{2}(t)} \\ {b_{2}(t),} & {b_{2}(t) \geq \alpha(t)} \\ {0,} & {\alpha(t)>b_{1}(t)}\end{array}\right. \tag{2} r(t)=α(t),b2(t),0,b1(t)α(t)>b2(t)b2(t)α(t)α(t)>b1(t)(2)
目前动态底价的算法主要有三种:

  1. 基于贝叶斯推断的底价估计算法
  2. 基于均值统计的底价估计算法
  3. 基于经验的One-Shot底价调整算法

下面逐一介绍这三个算法。

基于贝叶斯推断的底价估计算法

该算法首先假设在一次RTB竞价的过程中,最高出价 B 1 B_1 B1为满足对数高斯分布的随机变量,并且假设其方差已知(可以当成超参数来调),而其均值的先验分布为高斯分布,即:
B 1 ∼ lognorm ⁡ ( μ , σ 2 ) μ ( t ) ∼ N ( θ ( t ) , δ 2 ( t ) ) (3) \begin{aligned} B_{1} & \sim \operatorname{lognorm}\left(\mu, \sigma^{2}\right) \\ \mu(t) & \sim \mathcal{N}\left(\theta(t), \delta^{2}(t)\right) \end{aligned} \tag{3} B1μ(t)lognorm(μ,σ2)N(θ(t),δ2(t))(3)
假设 μ ( t ) \mu(t) μ(t)的分布在系统上线前已经由历史时刻 [ 0 , t ] [0,t] [0,t]的数据拟合得到了 θ ( t ) \theta(t) θ(t) δ 2 ( t ) \delta^2(t) δ2(t),当系统在线运行时, t + 1 t+1 t+1竞拍结束后得到一个最高出价的样本 b 1 ( t + 1 ) b_1(t+1) b1(t+1),这样由于对数高斯分布和高斯分布为共轭分布,可以直接后验分布
p ( θ ( t ) ∣ b 1 ( t + 1 ) ) = N ( θ ( t + 1 ) ∣ θ ( t ) , δ 2 ( t ) ) (4) \begin{aligned} p(\theta(t) | b_1(t+1))=\mathcal{N}\left(\theta(t+1) | \theta(t), \delta^{2}(t)\right) \end{aligned} \tag{4} p(θ(t)b1(t+1))=N(θ(t+1)θ(t),δ2(t))(4)
其中
θ ( t + 1 ) = θ ( t ) δ 2 ( t ) + σ 2 b 1 ( t + 1 ) σ 2 + δ 2 ( t ) δ 2 ( t + 1 ) = δ 2 ( t ) σ 2 σ 2 + δ 2 ( t ) (5) \begin{aligned} \theta(t+1) &=\frac{\theta(t) \delta^{2}(t)+\sigma^{2} b_{1}(t+1)}{\sigma^{2}+\delta^{2}(t)} \\ \delta^{2}(t+1) &=\frac{\delta^{2}(t) \sigma^{2}}{\sigma^{2}+\delta^{2}(t)} \end{aligned} \tag{5} θ(t+1)δ2(t+1)=σ2+δ2(t)θ(t)δ2(t)+σ2b1(t+1)=σ2+δ2(t)δ2(t)σ2(5)
这样根据最大后验估计的原则,我们可以使用 θ ( t ) \theta(t) θ(t)来作为 μ \mu μ的估计,并且根据式(3)可知,可以将 l o g ( θ ( t ) ) log(\theta(t)) log(θ(t))作为对 B 1 B_1 B1的估计。根据原则[1], 只要简单地设置:
α ( t + 1 ) = l o g ( θ ( t + 1 ) ) (6) \alpha(t+1) = log(\theta(t+1)) \tag{6} α(t+1)=log(θ(t+1))(6)
可以看到基于贝叶斯推断的方法首先估计了 b 1 ( t + 1 ) b_1(t+1) b1(t+1),然后通过设置 α ( t + 1 ) \alpha(t+1) α(t+1)逼近 b 1 ( t + 1 ) b_1(t+1) b1(t+1)的方式来最大化本次曝光的收益。

基于均值统计的底价估计算法

均值估计的想法其实十分朴素:本次曝光的收益应当不低于历史平均收益。于是很直接的,使用 t − 1 t-1 t1时刻的历史平均收益来作为 α ( t ) \alpha(t) α(t)的估计:
α ( t ) = 1 M ∑ i = t − M t − 1 r ( i ) (7) \alpha(t)=\frac{1}{M} \sum_{i=t-M}^{t-1} r(i) \tag{7} α(t)=M1i=tMt1r(i)(7)
当然,线上系统的运行环境是会发生改变的,比如说流量分布,竞争环境,等等。所以收益分布应当也不是一个静态的分布,并且当样本越靠近当前时刻,则越有可能采样于当前的收益分布,所以计算平均收益时,应当使用加权平均的方式来进行,并且设置离当前时刻越近的数据,权重就越高:
α ( t ) = 1 M ∑ i = t − M t − 1 w ( i , t ) r ( i ) (8) \alpha(t)=\frac{1}{M} \sum_{i=t-M}^{t-1} w(i, t) r(i) \tag{8} α(t)=M1i=tMt1w(i,t)r(i)(8)
其中 w ( i , t ) w(i,t) w(i,t)的选择可以多种多样,只要满足当前时刻越近的数据,权重就越高的原则即可。

ONE-SHOT底价调整算法

ONE-SHOT其实是一个调整算法而不是一个估计算法。其工作的流程是:

  1. 给定一个初始底价 α ( t ) \alpha(t) α(t)
  2. 根据一定规则在 α ( t ) \alpha(t) α(t)的基础上调整得到 α ( t + 1 ) \alpha(t+1) α(t+1)

初始底价可以根据经验直接指定,也可以通过式子(7)对历史数据统计给出。而调整的原则在于:

当底价低于 b 1 b_1 b1时,则应当缓慢提高底价,当底价高于 b 1 b_1 b1时应当迅速降低底价 --原则[2]

原则[2]提出的基本思想是:当底价低于 b 1 b_1 b1时,虽然此时收益并非是最大化的,但毕竟有 b 2 b_2 b2作为保证,收益不会太低,所以底价上涨探索最优的收费不必太过于急切,但如果底价高于 b 1 b1 b1时,收益将会直接变为0,所以需要快速降低底价,让 b 2 b_2 b2来保证收益。

根据原则[2],当然可以设置固定的小步伐 s u s_u su和大步伐 s l s_l sl来调整底价。但是为了平滑和鲁棒性,可以根据式(9)来执行调整过程。
{ α ( t + 1 ) = ( 1 − ϵ t λ h ) a ( t ) if  α ( t ) > b 1 ( t ) α ( t + 1 ) = ( 1 + ϵ t λ e ) a ( t ) if  b 1 ( t ) ≥ α ( t ) ≥ b 2 ( t ) α ( t + 1 ) = ( 1 + ϵ t λ l ) α ( t ) if  b 2 ( t ) > α ( t ) (9) \left\{\begin{array}{ll}{\alpha(t+1)=\left(1-\epsilon^{t} \lambda_{h}\right) a(t)} & {\text { if } \alpha(t)>b_{1}(t)} \\ {\alpha(t+1)=\left(1+\epsilon^{t} \lambda_{e}\right) a(t)} & {\text { if } b_{1}(t) \geq \alpha(t) \geq b_{2}(t)} \\ {\alpha(t+1)=\left(1+\epsilon^{t} \lambda_{l}\right) \alpha(t)} & {\text { if } b_{2}(t)>\alpha(t)}\end{array}\right. \tag{9} α(t+1)=(1ϵtλh)a(t)α(t+1)=(1+ϵtλe)a(t)α(t+1)=(1+ϵtλl)α(t) if α(t)>b1(t) if b1(t)α(t)b2(t) if b2(t)>α(t)(9)
其中 ϵ ∈ ( 0 , 1 ] \epsilon \in (0, 1] ϵ(0,1] λ h , λ e , λ l ∈ [ 0 , 1 ] \lambda_h, \lambda_e, \lambda_l \in [0, 1] λh,λe,λl[0,1], ϵ \epsilon ϵ是一个时间衰减系数,如果RTB只希望在启动后个某个时间段调整底价,并且最终收敛,则可以通过这个参数来调整。而 λ h \lambda_h λh则用于调整当 α ( t ) > b 1 ( t ) \alpha(t) > b_1(t) α(t)>b1(t)时底价的降低速度。而同理 λ l \lambda_l λl用来调整当 α ( t ) < b 2 ( t ) \alpha(t) < b_2(t) α(t)<b2(t)时底价的提升速度。 λ e \lambda_e λe则用于调整探索最优收益的速度。从业务上来说,往往会设置 λ h > λ l > λ e \lambda_h>\lambda_l>\lambda_e λh>λl>λe,即当前收益越高,调整速度越慢,这与原则[2]的基本思想是一致的。

其他讨论

上述三种底价算法里,基于贝叶斯推断的算法的数学理论是最完备的,但必须要考虑到这种算法存在最高出价符合对数高斯分布这个假设前提的。这个假设并非放之四海而皆准的,各个广告系统的业务不一样,符合的分布也不一样,需要选择合适的分布,才能做出好的效果。并且需要注意的是,该算法优化的是单次曝光收益,并没有从全局的视角来考虑底价问题,不一定在整体收益上是最高的。

基于统计均值的算法是最朴素的,也是最容易实现的,不失为一个短平快的解决方案,它应当作为任何动态底价第一版本的最好选择,至少你能有一个Baseline去观察你的系统,判断动态底价对于你的广告系统来说是否是必要的,是否真的能提升收入。

而ONE-SHOT算法虽然没有数学理论支撑,但它作为一种博弈思维的产物,有从业务和全局的视角去考虑底价问题,从直觉上来看是最值得尝试的一种。当然,我想ONE-SHOT算法应当还有许多改进的空间,比如 λ h , λ e , λ l \lambda_h, \lambda_e,\lambda_l λh,λe,λl参数的值可以跟贝叶斯推断来动态调整的值,也可以通过反馈控制的方法来动态调整。

但最终,无论如何,这里都没办法给哪一种算法的优劣性下一个断论,毕竟业务多种多样,只能认真做好A/B Test,好好调参,根据实际业务表现来选择算法了。

这篇关于拍卖与博弈:计算广告中的底价问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1133728

相关文章

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

poj2505(典型博弈)

题意:n = 1,输入一个k,每一次n可以乘以[2,9]中的任何一个数字,两个玩家轮流操作,谁先使得n >= k就胜出 这道题目感觉还不错,自己做了好久都没做出来,然后看了解题才理解的。 解题思路:能进入必败态的状态时必胜态,只能到达胜态的状态为必败态,当n >= K是必败态,[ceil(k/9.0),k-1]是必胜态, [ceil(ceil(k/9.0)/2.0),ceil(k/9.

hdu3389(阶梯博弈变形)

题意:有n个盒子,编号1----n,每个盒子内有一些小球(可以为空),选择一个盒子A,将A中的若干个球移到B中,满足条件B  < A;(A+B)%2=1;(A+B)%3=0 这是阶梯博弈的变形。 先介绍下阶梯博弈: 在一个阶梯有若干层,每层上放着一些小球,两名选手轮流选择一层上的若干(不能为0)小球从上往下移动,最后一次移动的胜出(最终状态小球都在地面上) 如上图所示,小球数目依次为

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监

缓存雪崩问题

缓存雪崩是缓存中大量key失效后当高并发到来时导致大量请求到数据库,瞬间耗尽数据库资源,导致数据库无法使用。 解决方案: 1、使用锁进行控制 2、对同一类型信息的key设置不同的过期时间 3、缓存预热 1. 什么是缓存雪崩 缓存雪崩是指在短时间内,大量缓存数据同时失效,导致所有请求直接涌向数据库,瞬间增加数据库的负载压力,可能导致数据库性能下降甚至崩溃。这种情况往往发生在缓存中大量 k

poj 1113 凸包+简单几何计算

题意: 给N个平面上的点,现在要在离点外L米处建城墙,使得城墙把所有点都包含进去且城墙的长度最短。 解析: 韬哥出的某次训练赛上A出的第一道计算几何,算是大水题吧。 用convexhull算法把凸包求出来,然后加加减减就A了。 计算见下图: 好久没玩画图了啊好开心。 代码: #include <iostream>#include <cstdio>#inclu

uva 1342 欧拉定理(计算几何模板)

题意: 给几个点,把这几个点用直线连起来,求这些直线把平面分成了几个。 解析: 欧拉定理: 顶点数 + 面数 - 边数= 2。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#inc

uva 11178 计算集合模板题

题意: 求三角形行三个角三等分点射线交出的内三角形坐标。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)