移动应用广告刷新的优化

Track: Web Economics, Monetisation, and Online MarketsWWW 2018, April 23-27, 2018, Lyon, France13990优化移动应用广告中的广告刷新0Florin Constantin，Christopher Harris，Samuel Ieong，Aranyak Mehta，Xi Tan GoogleMountain View，CA，USA florin，ckharris，sieong，aranyak，xit@google.com0摘要0应用内广告是一个价值数十亿美元的复杂市场，然而与传统的网络展示广告相比，它的研究要少得多。在本文中，我们研究了移动应用中广告的一个重要但经常被忽视的特性（在传统网络广告中几乎不存在），即广告刷新：用户在应用程序会话期间显示一系列横幅广告，其中每个广告在广告位上显示一定的时间（刷新速率）之后，广告位刷新到下一个广告。对于我们的大规模实验进行的数据分析显示了一个令人惊讶的结果，这个结果不能用现有的用户点击模型来解释：变化的广告刷新几乎保持了总点击次数。我们为这种情况提出了一个新的、自然的“两阶段”点击模型，解释了这种独立性，以及我们对点击率随印象停留时间和广告重复次数变化的测量结果。新的点击模型为整个用户会话的拍卖问题提供了清晰的表述，即在线确定获胜广告的顺序以及显示每个广告的时间量。我们通过实施一个实时流量实验来补充理论拍卖设计的结果。我们的实验和分析为AdMob的“Google优化刷新率”功能提供了理论基础，该功能被许多移动应用程序用于更好地货币化向数百万用户展示的广告。0ACM参考格式：Florin Constantin，Christopher Harris，SamuelIeong，Aranyak Mehta，XiTan。2018。优化移动应用广告中的广告刷新。在2018年网络会议上，2018年4月23日至27日，法国里昂。ACM，纽约，美国，10页。https://doi.org/10.1145/3178876.318604501 引言0在过去几年中，移动应用生态系统已经发展到相当大的规模，因此应用程序的货币化变得越来越重要。虽然一些应用通过收费安装或应用内购买来实现货币化，但大部分应用使用广告作为主要的货币化策略。0本文根据知识共享署名-非商业性使用-禁止演绎 4.0国际许可发布。作者保留在个人和公司网站上传播作品的权利，并附上适当的归属。WWW2018，2018年4月23日至27日，法国里昂©2018IW3C2（国际万维网会议委员会），根据知识共享CC BY-NC-ND 4.0许可发布。ACM ISBN978-1-4503-5639-8/18/04.. https://doi.org/10.1145/3178876.318604501.1 移动应用中的广告背景0应用中的广告与网络上的传统展示广告类似，但也存在一些关键差异。在本文中，我们解决了一个在应用领域中非常重要的维度，这在大多数情况下是独特的：广告在屏幕上的持续时间。应用通常通过广告SDK（例如Google的AdMobSDK）获取广告，该SDK通过向广告服务器发送HTTP请求并解析响应来显示广告。我们的重点是横幅广告，它们占据屏幕的一小部分，例如底部的320x50像素的带状区域，而不会中断应用的主要流程。一旦SDK获取到横幅广告请求的响应，它会在屏幕上显示广告一段特定的时间间隔，称为刷新速率（由移动应用发布者指定，或设置为默认值，通常为60秒），在此期间结束时，它会发送下一个广告请求以切换到新的横幅广告。有时，连续几次展示可能会显示相同的广告，导致用户感知到的广告持续时间大于刷新速率。广告商提交一个每点击成本的估计值（BidCostPerClick），这是他们每次点击的价值估计（互联网广告商通常只支付点击费用）。广告主对印象的估计值是 ������  ×  ���� ，其中 ����是点击率（CTR）的预测，即给定广告印象的点击概率0主要见解：传统的（基于网络广告的）拍卖会根据广告请求选择价值最高的广告，并按照次高价值的广告定价。然而，在应用程序中出现了一些新的情况：当用户使用应用程序时，他们会看到一系列广告，即一系列广告，每个广告在屏幕上显示一段时间。我们的主要见解是，在这种情况下，应该销售的正确商品是有效的屏幕停留时间。在本文中，我们测量和建模广告停留时间和广告顺序对用户对广告的反应的影响，以及这如何影响整个会话的最佳拍卖。本文结构如下：0第2节：时间会话分析。在第2.2节和第2.3节中，我们根据实时流量测量了典型广告的点击率，该点击率是广告在屏幕上停留时间和其先前展示次数的函数。第2.4节描述了我们进行的一组实验的一个非常令人惊讶的结果，这些实验显著改变了刷新率：会话中的总点击次数保持不变。01 http://firebase.google.com/docs/admob/ios/download2这是应用程序中显示的最常见的广告类型（按总流量计算）。其他应用内广告类型包括插页式（全屏）广告和原生广告。3我们的结果适用于优化并出价于点击后事件（如安装或应用内购买）的广告商，这是一个快速增长的人群。14000在实验组中基本保持不变。这不能用传统的基于展示的点击模型来解释。第3节：一种新的点击模型。为了支持我们的实证数据，我们引入了一种新的用户点击模型，将注意力与兴趣分开，即用户注意到广告与点击广告。第4节：会话拍卖。然后我们询问观察结果和新模型应如何指导拍卖设计。我们提供了一个“会话拍卖”问题的清晰表述，即以在线方式为整个用户会话找到福利最优的分配和定价。第5节：具有紧密竞争比的在线算法。我们描述了一种在线分配算法，限制了其竞争比，并提供了一个紧密的例子。第6节：实验结果。我们最后提供了一个新的时间感知拍卖的实现的实时流量数据。我们的结果为AdMob的“谷歌优化刷新率”功能提供了理论基础，该功能被许多移动应用程序用于更好地实现向数百万用户展示的广告的货币化。01.3 相关工作0行业中的刷新率。根据已发布的行业实践，刷新率显然是一个重要的参数，将其设置为最佳状态并不是一项微不足道的任务：AdMob（谷歌）建议设置为60秒或更长5，Facebook AudienceNetwork建议设置为30秒或更长6，而MoPub允许应用程序对刷新率进行实验7。行业标准组织——互动广告局制定了移动应用内广告的指南8，强调了自动刷新广告、应用程序会话（作为替代的测量窗口）以及平均广告曝光时间（用于报告）的重要性。应用程序刷新率文献。最近有几篇论文研究了应用程序的刷新率。与我们最接近的论文是[10]，该论文认为应用程序中广告性能的正确指标是每小时点击次数，而不是典型的每次展示的点击次数（CTR）。它进一步显示，对于一组特定的应用程序，随着广告持续时间缩短，总点击次数增加，这实际上与我们的发现相反（详见第3.2节——我们的模型确定了影响点击次数变化的特征）。此外，[11]和[5]研究了如果减缓广告刷新速度可以节省电池/资源使用情况；两篇论文都没有考虑点击行为。屏幕上的时间。第二篇与之密切相关的论文[4]研究了网络上显示广告的曝光时间（即屏幕上的时间）对广告的影响；据我们所知，这是第一篇研究这一特征的论文。该论文描述了增加曝光时间（尽管只针对两个广告之一）或以不同顺序播放广告的实验。主要指标是品牌认知/广告记忆，这对于某些网络显示广告来说是自然的，而我们则关注基于点击的广告价值，因为我们考虑的是性能广告。我们还进一步研究了这种情况下最佳拍卖设计的问题，基于实证观察和建模。最后，[4]中的实验0请参阅具有此功能的AdMob帐户：http://ibb.co/gzeEkw请参阅http://support.google.com/admob/answer/3245199请参阅http://developers.facebook.com/docs/audience-network请参阅www.mopub.com/wp-content/uploads/2015/02/Pubs-MaximizeRevenuePlaybook.pdf中的“优化横幅广告的刷新率” 请参阅http://tinyurl.com/IAB-app-session。链接访问于2017年10月。0我们使用1000个Amazon MechanicalTurk用户进行了实验，但我们进行了大规模的实时流量AdMob实验。用户点击模型。用户点击模型已经得到了密切研究。位置拍卖的基本模型在[2,3,12]中被定义或隐含。该模型假设广告位置对用户行为有独立的影响。在[1,8]中提出了更丰富的用户模型，如马尔可夫模型或级联模型。这些和其他相关模型都是按印象计算的，而我们的工作的新颖之处在于考虑到了时间的影响，这是流媒体广告设置中独特的维度。最后，[9]回顾了用户点击行为的建模技术。拍卖设计。我们的点击模型将拍卖设计问题简化为一个相当标准的问题，即将可分配的商品分配给具有凹函数效用的一组代理商。这个抽象的设置在文献中已经得到了广泛研究，特别是在网络资源分配的工作中（[6]及其后续结果）。大部分工作都研究了每单位单价的设置，这导致了比例分配拍卖设计。我们的目标是运行一个效率最大化的拍卖；这也在之前的研究中得到了研究[7]。然而，据我们所知，尚未考虑到具有任何非零分配的下限的可分配商品的分配问题。虽然下限似乎是特定于我们的动机问题，但它导致了在线和离线分配值之间的一个有趣的差距。02 点击行为沿会话的变化0我们首先对用户点击行为进行数据分析和实时实验分析，作为时间特征（如刷新时间和广告排序）的函数。我们得出了三个观察结果，这些观察结果推动了一个新的点击行为模型的产生。02.1 数据准备0我们的源数据是从移动广告网络获取的实时流量样本，涵盖游戏、实用工具、新闻和零售等应用程序。所提供的广告包括推广其他应用程序的广告和引导用户访问移动优化网站的广告。我们将连续显示给同一用户的广告定义为一个广告会话，在单个应用程序中，广告会话之间的间隔不超过15分钟。由于我们特别关注刷新率的影响，我们只包括会话中的横幅广告-横幅广告位（通常）会在固定时间间隔自动刷新。所有结果都是在广告展示和点击被清除垃圾之后得出的。我们的研究使用了超过1亿个会话，跨越了几个月的时间。由于保密性，我们无法公开提供数据。点击率的确切值也已被掩盖。我们的分析呈现了点击率的相对差异，这一点在没有确切值的情况下得到了保留。我们承认保密性限制了我们实验的可重复性。尽管如此，我们在整个时间跨度上发现了一致的结果。此外，我们相信可以通过使用来自不同移动广告网络的数据或独立应用程序发布者的类似研究来验证结果。09 其他定义，例如在应用程序之间的使用情况，得出了类似的结果0跟踪：Web经济学，货币化和在线市场WWW 2018年4月23日至27日，法国里昂the effects on CTR of session index and ad repeat count.It plots the (natural logarithm of) CTR on the 𝑦-axis as afunction of session index (𝑥-axis), grouped by ad repeat count.We observe that the drop off in CTR is more significant (theslope is steeper) for repeated ads.To further understand the effects of these factors, we ran alogistic regression (a standard model for CTR prediction [9])of clicks against them. The model coefficients for session indexand ad repeat count are -0.05 and -0.25 respectively, bothsignificant at 𝑝-values of 0.001. Roughly speaking, we see ageometric drop-off along repeat impressions: each subsequentimpression is about 20% less effective than the previous one.14010图1：点击延迟作为点击分布函数的累积分布。时间（点击延迟）在�轴上，上限为�（其确切值已被掩盖以保密）。分布的四分位数约为�/10，�/4和�/2。02.2 点击时间0点击时间，也称为点击延迟，指的是广告首次显示在屏幕上后用户点击广告之前经过的时间。更正式地说，考虑一个横幅广告从某个时间�0开始显示在屏幕上，并打算在时间�内持续显示（在此广告之前和之后可能还有其他广告）。我们首先要问的问题是：在广告的屏幕寿命内，如果发生点击，点击会在多长时间内发生？假设点击在时间��（在�0+�之前）发生。图1显示了所有点击的累积点击延迟（��−�0）的分布，其中�是�的上界。广告展示的观察CTR是其在屏幕上的时间的函数：随着我们将广告在屏幕上持续时间更长，CTR增加，但边际增长率递减。排除前几秒以考虑用户反应时间后，广告CTR分布可以很好地近似为指数累积分布函数。模型系数约为-0.015，�2约为0.93。这适用于同一广告的首次展示和后续展示。02.3 前一次展示对CTR的影响0接下来，我们考虑广告顺序对CTR的影响，主要是当广告在会话中重复时（不一定是连续展示，可能与其他广告交错）。首先，我们观察到后续展示的CTR较低：在我们在会话中多次展示同一广告的情况下，每次重复展示的CTR都低于前一次。仔细观察数据后，我们注意到分析中的一个混淆因素-广告在会话中的索引。我们注意到随着会话的深入，CTR通常会下降，因为长时间的会话通常表示用户对应用程序非常投入。由于重复广告出现在会话的较后阶段（通常要晚得多），我们需要将CTR的下降归因于这两个因素。图2将会话索引和广告重复次数对CTR的影响进行了分解。它将（自然对数的）CTR绘制在�轴上，作为会话索引（�轴）的函数，按广告重复次数分组。我们观察到CTR的下降（斜率更陡）对于重复广告更为显著。为了进一步了解这些因素的影响，我们进行了逻辑回归（CTR预测的标准模型[9]）的点击次数。会话索引和广告重复次数的模型系数分别为-0.05和-0.25，两者的�值都显著为0.001。粗略地说，我们看到重复展示的点击量呈几何级数下降：每个后续展示的效果约比前一个展示减少20%。0图2：CTR随会话索引下降，但对于更高的广告重复次数（在会话中显示的次数）下降更快。图中的每个点聚合了许多广告展示（至少1000次，通常更多），具有相同的会话索引和相同的广告重复次数：例如，广告序列�1，�2，�3，�1，�3中的第二个�3的会话索引=5和广告重复=2。结论来自最佳拟合线，同时显示置信区间。02.4 更改刷新率的影响0在第2.2节中，我们看到广告展示的CTR是其屏幕停留时间的凹函数。在这里，我们提出同样的问题，但在会话级别上：会话中的总点击次数如何取决于广告展示的刷新率。虽然前面的问题是通过对当前刷新率结果的数据分析来研究的，但在这里我们需要进行实时流量实验。实验设置：我们从刷新率为某个固定�>0的广告位（应用程序）中进行采样。然后我们从移动设备集合中进行采样。在处理组中，我们改变刷新率（0.5�、1.5�、2�、2.5�、∞），并测量点击量的变化。请注意，这对每个广告的屏幕停留时间以及广告序列本身都有影响：例如，将刷新时间加倍（到2�）会减少序列中的广告展示次数，因为会话时间是固定的。0跟踪：Web经济学，货币化和在线市场WWW 2018年4月23日至27日，法国里昂14020我们可以尝试使用在赞助搜索文献中广泛使用的标准点击模型来预测实验结果（例如[2, 3, 12]），该模型假设：0总点击次数=∑�0�∈显示的广告UINorm�×�����0其中UINorm�（用户界面标准化器）因子捕捉广告�的突出性。在我们的情况下，UINorm应该捕捉到屏幕停留时间的影响（因为所有位置都是相同的），在第2.2节中已经证明可以很好地近似为指数累积分布函数。因此，在2�实验组中，我们预计会有印象数量的一半之和，每个印象的UINorm增加，尽管远远不会翻倍。因此，经典模型会预测在这个实验组中点击量会大幅下降（类似地，0.5�实验组中的点击量会大幅增加）。令我们惊讶的是，我们发现控制组和治疗组之间的点击次数实际上非常接近。下表描述了在一定范围内更改刷新时间时观察到的点击平均变化，其中刷新率为∞表示我们从不刷新。每个组至少有10000次点击。∆Clicks表示治疗组点击与对照组点击的比率减去1，即∆Clicks = 0％，如果两组的总点击次数相同。0刷新率95％置信区间的∆Clicks00.5� [−2.7％，+0.7％] 1.0�NA（对照组）1.5�[+0.2％，+3.6％] 2.0�[−1.0％，+2.4％] 2.5�[0.0％，+3.4％] ∞[−2.8％，+0.5％]0由于点击变化几乎为零，CTR变化几乎与刷新率的变化成正比。这些结果激励我们重新考虑标准点击模型，我们提出了一个新的点击预测模型，不仅解释了本节中的所有三个观察结果，而且帮助我们更好地理解刷新率变化时影响点击量的因素。03个新的点击行为模型0我们的新会话内点击模型由两个随机过程组成，分别是用户注意力和用户兴趣：0（1）阅读过程：泊松过程，参数为�（取决于应用程序和用户，但不取决于广告和广告持续时间的选择）。这确定了用户在会话中阅读横幅广告块的时间。（2）点击过程：如果用户阅读广告�，则-如果这是会话中对�的第一次阅读，则用户以概率�����点击（这可能取决于广告�，应用程序和用户）。-否则（如果会话中先前已经阅读了�），则不会有点击。0这里的直觉是，在一个会话中，用户根据泊松过程在随机时间查看广告块（“阅读”）0处理10。如果这是他们第一次阅读某个广告�（可能�之前有一些用户没有阅读的印象），那么他们将以概率�����点击该广告。如果相反，用户已经阅读了该广告在会话中的早期印象，则他们不会点击当前的印象。这与用户实际上是否点击该广告的先前印象无关。我们将其称为“非累积效应”假设，以强调我们的模型不包括所谓的品牌效应（多个印象共同导致一种行动）。虽然����通常被定义为给定广告印象的点击概率，但在这里我们将其定义为给定会话中广告的第一次阅读的点击概率。图3讨论了一个具有四次阅读和一次点击的示例用户会话。0图3：用户会话中的示例广告流。顶部行显示了随时间变化的广告序列。泊松阅读过程在广告C、D、B和第二个C上触发四次（在箭头处）。点击过程在每次阅读时启用，并以概率触发广告B的点击（在绿色笑脸处）。请注意，这是用户在会话中第一次阅读广告B。广告C的第一次印象被阅读，但没有被点击，因此第二次阅读C不会得到点击。0而在点击过程中（用户点击广告），拍卖师观察到积极的结果，但整个阅读过程对拍卖师是隐藏的，拍卖师不知道用户是否阅读了广告。因此，对广告的点击缺乏可能是由于用户没有阅读广告，或者用户在阅读后选择不点击广告。我们注意到，之前关于用户模型的相关工作（第1.3节）也实际上将点击模型分为用户界面效果（或阅读过程）和伯努利点击过程。然而，那些模型中的阅读过程是基于展示的（例如，位置归一化），而这里的新颖之处在于阅读过程是一个时间索引的随机过程。让我们展示一下模型如何解释上述的三个发现。03.1 点击时间和广告重复效应0这两个观察结果可以同时解释。固定一个广告，假设我们在用户的会话中展示该广告�次，持续时间分别为�1，�2，...��（与其他广告交错）。令��为广告的第�次展示获得阅读（V表示查看）的事件，��为广告的第�次展示获得点击的事件。在我们的模型中，����010模型还可以进一步扩展，包括一个时变的�（�），以捕捉会话时间轴上用户注意力的变化。0Track: Web Economics, Monetisation, and Online Markets WWW 2018, April  23-27, 2018, Lyon, FranceThe ad’s second impression may be clicked only if the firstimpression had not been read. Since Pr(𝑉2) = 1 − 𝑒−𝜆𝑡2Pr(𝑉1) = 𝑝𝐶𝑇𝑅𝑒−𝜆𝑡1𝐶𝑙𝑖𝑐𝑘𝑠(𝒞) =𝑘𝑖=1 𝑝𝐶𝑇𝑅𝑖1 − 𝑒−𝜆𝑅(𝜇𝑖+𝜈𝑖)(3)𝐶𝑙𝑖𝑐𝑘𝑠(ℰ) =𝑘𝑖=1 𝑝𝐶𝑇𝑅𝑖 1 − 𝑒−𝜆2𝑅𝜇𝑖(4)14030定义为给定广告的第一次阅读的情况下点击的概率。那么，对于广告的第一次展示：0Pr( � 1 ) = 1  −  � − �� 1（阅读过程）0Pr( � 1 | � 1 ) =  ����（点击过程，� 1 是第一次阅读）0�  Pr( � 1 ) = Pr( � 1 | � 1 )  ∙  Pr( � 1 ) =  ����  ∙  (1  −  � − �� 1 )0�  Pr( � 2 ) =  ����  ∙  � − �� 1 ∙ (� 1  −  � − �� 2 )�0一种解释是第二次展示的����随第一次展示的持续时间减少。其他交错广告的时间长度不会影响第二次展示的����。类似地，我们可以证明，对于一般的� ≤ �：0Pr( � � ) =  ����  ∙  � − �  ∑� � − 1 � =1 � � ∙ (� 1  −  � − 0方程（1）显示点击率，等效地，点击时间遵循指数累积分布函数，解释了第2.2节中的观察结果。此外，如果会话中的所有展示都以相同的持续时间�显示，则Pr( � � ) = [ ����  ∙  � − � ( � − 1) � ]  ∙  (1  − )。因此，CTR在会话中重复展示此广告的次数�几何级数下降。这解释了第2.3节中的分析。最后，由于事件��是不相交的，我们得到0Pr(点击广告的某次展示) =0= ∑� � � =1 Pr( � � ) =  ���� (1  −  � − �  ∑� � � =1 � � )0即，交错展示中的任意一次点击概率等于单个长展示的点击概率，其持续时间等于各个时间之和。这是我们点击模型的一个重要结果，极大地简化了进一步的分析，特别是我们的拍卖设计（第4节）。03.2 点击保持不变0标准点击模型还可以解释前两个观察结果（在对时间进行适当的UINorms假设和“硬编码”重复效应的情况下）。但正如我们之前指出的，它无法解释在刷新率独立于的情况下，会话中的总点击数。现在我们展示一下阅读过程如何帮助我们解释这个观察结果。03.2.1直觉。高层次的直觉是点击次数主要取决于会话中的阅读次数。我们假设阅读参数�与提供的广告及其在屏幕上的时间无关。因此，如果我们在实验中改变刷新时间，会话中的阅读次数不会改变。这本身并不能证明点击次数不会改变（即使考虑到任何给定广告的点击过程与刷新率无关），因为阅读现在可能出现在不同的位置。0广告集。如果实验中的读取落在与对照组相同的广告组合上，则总点击量不会改变。读取落在的广告组合又取决于：0（1）读取参数 � 到刷新率 �的大小；（2）会话中显示的广告的多样性，特别是实验组与对照组中显示的不同广告的数量和它们的 ���� 分布。03.2.2 形式化。为了形式化上述直觉，我们从一些符号开始。设 � 1 ，�2 ，...，� � 为唯一的候选广告，���� � 表示 � � 的预测点击率（即第一次读取 � �的概率）。将对照组表示为 Control，刷新时间为 �，实验组表示为experiment，刷新时间为2�（后续分析适用于刷新时间的任何变化）。考虑在对照组中的应用会话，在此期间广告系统（经过一系列复杂的步骤，如检索、预测、评分、预算分配和拍卖）返回广告展示序列 � = ( � 1 , � 2 , ... , � �)（每个展示长度为�，可能有重复广告）。合理地假设实验组将看到序列 � = ( � 1 , � 2 , ... , ��/ 2 )，即 � 的前一半（每个展示长度为 2�）。对于 � = 1，...，�，设 � �表示第一半 � 中广告 � � 的展示次数（称为多重性）。注意，� � 也是 � 中 � �的多重性。设 � � 表示 � 的第二半中广告 � � 的多重性。设 ������ ( � ) 和 ������ ( � )分别表示对照组和实验组的总点击量。� � 在 � 中的总展示时间为 ( � � + � �) �，在 � 中为  � � 2�。根据方程2，我们有：0由于对于序列 �的敏感性，似乎不可能推导出点击量变化的闭式形式或一般性预测，但我们可以评估一些广泛的情况：0∙ 对于 � � = � � ，� � ∈ [1 ..�]的情况，方程3和方程4意味着点击量不会改变。这种情况大致对应于每个广告在应用会话中均匀分布的情况。∙ �� → ∞的情况表示读取速率远快于刷新率（1 /� � �）。然后，(3)、(4)简化为 ������ ( � ) = ∑� � � =1 1 { � � + � � > 0 } ���� �，������ ( � ) = ∑� � � =1 1 { � � > 0 } �����。这立即表明点击量不会增加。此外，如果 �中的每个广告也出现在其前一半，即也出现在 �中，则点击量保持不变。另一方面，考虑偏斜的示例 � 1 = ( � 1 , �1 , ... , � 1 , � 2 , � 3 , � 4 , ... , � � )，其中 � 1 重复 � - 1 次。假设所有的���� 均等于 �。那么 ������ ( � ) → (1 + �)�，而 ������ ( � ) =�，这意味着点击量会急剧下降，因为实验只会显示 � 1。∙最后，考虑所有广告在 � 中都是不同的情况。对于一半的广告，� �= 1 和 � � = 0，对于另一半的广告，� � = 1 和 � � =0。考虑所有广告具有相同 ���� 的子情况。因此，我们得到 ������ ( � ) = �(1 - � - ��) 和 ������ ( � ) =0Track: Web Economics, Monetisation, and Online Markets WWW 2018，2018年4月23日至27日，法国里昂14040子情况中所有广告的 ���� 相同。因此，我们得到 ������ ( � ) 和 ������ ( � ) =02，表明对于任何 ��的值，点击量在实验中都无法增加。现在考虑更现实的情况，即 � 中的广告具有递减的 ���� 值，并且 � 的后半部分的平均 ��比第一半的平均 ���� 低一个因子，假设为 � ∈ [0,1]。那么点击量的比例变为0������(�)��0(1+�)(1−�−��)=1+�−��01+�0在这种情况下，点击次数的变化方向取决于�和�−��中哪个更大。03.2.3结论。在真实的广告系统中，可以预期（a）阅读速率不会过快，刷新次数不会过大（即较小的��值）（b）序列中的广告相对均匀分布（因此更接近假设��=��，��），以及（c）����随广告序列递减，因分基于����选择获胜者。如上所示，这三个因素要么不会改变，要么会增加点击次数。我们的实验证明点击次数没有变化，甚至略有增加，这表明这些因素在我们的系统中可能平均起作用。我们注意到，在相关工作[10]中，有报道称刷新时间的增加导致点击次数的减少。上述分析可能对这些相互矛盾的结果给出了解释。虽然我们的结果是在许多应用上平均得出的，但[10]中的结果是在作者控制的特定应用上得出的，可以推测在该设置中，相关参数之间的平衡导致了点击次数的减少。04会话拍卖问题0在前一节中，我们提出了一个新的点击模型来解释我们的数据和实验观察结果。现在我们提出一个问题，即在这个模型的基础上，我们是否可以改进我们的广告分配和定价；特别是，如何以全局方式拍卖出整个用户会话，而不是按照每次展示的方式。04.1问题定义0对于给定的持续时间为�的用户会话，我们的输入是一组候选广告�，对于每个广告�∈�，其基础点击率预测（�����）和每次点击的出价（���的每次点击价值��对广告商是私有的，对拍卖人是未知的。拍卖人必须选择一系列广告和时间持续值�=((�1,�1),(�2,�2),...,(��,��))，其中∑���中的广告重复）。给定这样的序列，广告根据第3节中定义的模型接收点击。序列�的经济效益（也称为价值）定义为0�(�):=∑���=1���×Pr(点击（��,��）|(�1,�1),...,(��−1,��−1))0目标是确定一个序列�，以最大化总会话价值，并对广告定价以0引导真实出价（即 ������� =��，��）。此外，该问题是在线的，因为拍卖人不知道�，即用户何时退出应用程序并结束会话。因此，实现必须是：在时间0选择（�1，�1）；随后，如果会话延长到�1，则确定（�2，�2），依此类推。最小展示时长：上述�(�)的值是广告主和应用发布者的剩余价值（���减去支付���）的总和，但不考虑用户价值。在我们的背景下，广告的快速刷新会导致糟糕的用户体验，还会增加蜂窝带宽和电池使用量。为了捕捉用户价值的概念，我们通过允许序列�的最小展示时长参数����（通常为30秒）引入了一个约束：��∈[1,�]:��≥����0备注1.虽然问题是在阅读-处理模型的背景下提出的，但我们只使用了模型的两个结果：（1）点击的概率作为时间的函数遵循指数分布，即方程（1），和（2）在广告的两个展示中点击的概率，持续时间分别为�1和�2，与持续时间为�1+�2的一个较长展示上的点击概率相同，即方程（2）。0我们还将假设泊松参数 �是已知的；可以通过将指数CDF拟合到图1中的曲线来从广告点击时间数据中估计它。04.2 离线分配0在本节中，我们研究了当会话长度 �已知时最优离线分配的结构。考虑一个可行的序列 � = (�1, �1), ..., (� �, ��)，其中 ∑�0� � � ≤ �。从等式 (2) 中，我们可以假设无损失地假设广告 �1，...，� �都是不同的：如果不是，则我们可以通过一系列交换操作将两个广告的出现移动到连续位置（并将它们合并为一个更长的展示），而不会丢失点击或价值。因此，离线问题大大简化为以下（相对标准的）拍卖问题（参见，例如，[6]）：我们有 �单位可分割的商品，和一组代理商（广告商）�。如果 � ∈ � 被分配了 � �的商品，那么它的价值是 � � (� �) := ������ � × ���� � (1 − � − ���)。目标是将商品分配给代理商并最大化它们的价值之和。最小展示持续时间约束变为：� �，要么 � � ≥ � ���，要么 � � =0。然后我们可以将VCG定价与最优分配结合使用。考虑构建一个最优序列，并考虑已经分配了时间 � 给广告 �。广告 �的边际值定义为通过展示 �的时间稍微增加所产生的额外价值的速率，即 �(�, �) := ������ � × ���� � × �� −��。通过将代理商的边际值等于某个水平 �进行标准化的等值论证，我们可以证明最优解采取以下形式。将�1，...，� � 分配给时间 �1，...，� �（每个 ≥ � ���），其中 ∑� � � = 1 � � = �，满足 � �使得：0∙ � � ∈ [1, �], �.�. � � > � ���: �(� �, � �) = �,0Track: Web Economics, Monetisation, and Online Markets WWW 2018, April 23-27, 2018, Lyon, France𝑎𝑡 ∈ 𝑎𝑟𝑔𝑚𝑎𝑥𝑎∈𝐴 𝐵𝑖𝑑𝐶𝑝𝐶𝑎 × 𝑝𝐶𝑇𝑅𝑎 × 𝑒−𝜆𝑡𝑎𝑚′ = 𝑚𝑎𝑥𝑎∈𝐴∖{𝑎𝑡} 𝐵𝑖𝑑𝐶𝑝𝐶𝑎 × 𝑝𝐶𝑇𝑅𝑎 × 𝑒−𝜆𝑡𝑎14050- 从时间 � = 0 开始。对于每个广告 �，让 � � 是广告 �在当前会话中到目前为止向用户展示的总时间（在所有展示中）。初始化 � � = 0，� � ∈ �。- 当会话未结束时：在时间 �，(1) 让 是边际值最高的广告0令 � 为 � � 的边际值。（2）令 � ′为下一个最高的边际值：0(3) 将 � � 定义为我们可以显示 � � 直到其边际值等于 � ′的时间量，即0� × � − �� � = � ′ � � � = 10� ln �0（4）展示广告 � � 为 ˆ � � := max{� �, � ���}的时间。（5）更新 � = � + ˆ � �，� � � = � � � + ˆ � �。0图4：在线分配算法（第5节）。0∙ � � ∈ [1, �], �.�. � � = � ���: �(� �, � �) ≤ �，∙ 对于所有其他= 0）：�(� �, 0) ≤ �。0注意，最优分配可能显示边际率严格低于其他显示的广告。这是由于最小持续时间约束造成的，使得我们对最优分配的分析（在下面的章节中）变得相当具有挑战性。特殊情况 � ��� = 0具有简单的结构。对于给定的 � > 0，对于每个 �，将 � � 设置为使得 �(= � 的值，或者如果 �(�, 0) < �，则设置 � � = 0。现在通过二分搜索找�*，使得 ∑�0� � � = �。0例4.1. 离线分配和定价，当 � ��� = 0 时：假设有两个广告，每个广告的 = 1，并且第一个广告的出价为 � > 1，第二个广告的出价为1。然后离线解决方案首先分配时间 �给第一个广告，此时两个广告的边际效用相等，即 �� − �� = 1，即 � =ln(�)/�。如果 � 足够大，使得 � ≥�，则只显示第一个广告。否则，解决方案将剩余的 � − �时间平均分配给两个广告。因此，总体上，第一个广告显示时间为 (�+ �)/2，第二个广告显示时间为 (� −�)/2。第一个广告的VCG价格是其对第二个广告的外部性，即 � − �(� −�)/2 − � − �� = � − ��/2√0�  −  � − �� 。05 在线分配算法0我们现在介绍我们的在线算法，其挑战是以在线方式确定获胜的广告及其持续时间，而不知道会话持续时间  � 。图 4描述了这个自然算法：选择一个边际价值最高的广告，并将其显示为其边际价值降至次高边际价值的持续时间（至少为  � ���时间）。为简单起见，我们假设 11 � ���  >  0。011 如果  � ���  =0，任何在线算法都必须是次优的，因为它自我强加了一个小的最小持续时间以在会话中取得进展。05.1 竞争比05.1.1 与正确的 OPT 比较。为了了解在线算法  ���的性能，我们将其与最优离线分配  ���进行比较，并限制最坏情况下的竞争比。由于  ���可能具有复杂的结构，一种选择是将  ���与没有最小持续时间约束的最优分配  ��� ( � ��� =0)进行比较，后者具有更简单的结构，可能导致更清晰的分析（这是一个有效的比较，因为 ��� ( � ��� =0) ≥  ���）。然而，下面的例子表明，最小持续时间约束本质上使问题更加困难：对于大的  � ��� ， ��� ( � ��� > 0) 可以任意比  ��� ( � ��� =0)更差。符号：为简洁起见，我们将  �  记为  � − �� ��� 。0例子 5.1. 考虑大量的广告，所有广告的价值都相同为  � ，总会话时间为  � ���。任何解决方案都将在整个时间内显示其中一个广告，价值为  � (1  −  � )。无限制的（ � ���