The Parity Ray Regularizer for Pacing in Auction Markets
The Parity Ray Regularizer for Pacing in Auction Markets
复制标题
用于拍卖市场节奏的 Parity Ray 正则化器
DOI：
10.1145/3485447.3512061
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Eric Sodomka
中科院分区：
文献类型：
--
作者：
A. Celli;Riccardo Colini;Christian Kroer;Eric Sodomka
预算管理系统是现代拍卖市场的关键组成部分之一。互联网广告平台通常为广告商提供通过预算节奏机制调整预算耗尽速度的可能性。我们专注于在线环境中的倍增节奏机制，其中投标人反复面临一系列广告机会。收集出价后，每件物品都会通过单件第二价格拍卖进行分配。如果没有预算限制，如实出价对于广告主来说将是最佳选择。然而，由于他们的预算有限，广告商可能希望降低出价，以便为未来的机会保留预算，并随着时间的推移平均分配支出。有关在线节奏问题的文献主要关注投标人优化可加性可分离目标的设置，例如总点击率或分配收入。然而，在许多情况下，投标人也可能关心其他目标，这些目标通常是不可分割的。我们研究了一种常见的情况，其中（代理）投标人的效用取决于从他们分配的项目中获得的奖励，以及实现的印象分布与目标分布的距离。我们引入了一种新颖的正则化器，它可以描述这些分布偏好，同时保持问题的易于处理。我们证明，该正则化器可以通过较小的修改集成到现有的在线镜像下降方案中，与从未知分布独立提取输入时事后的最佳分配相比，获得亚线性后悔的最佳顺序。此外，我们表明我们的方法可以很容易地融入到标准的现有起搏系统中，而这些系统通常不是为此目的而构建的。我们的算法在互联网广告应用中的有效性已通过现实世界数据的数值实验得到证实。
Budget-management systems are one of the key components of modern auction markets. Internet advertising platforms typically offer advertisers the possibility to pace the rate at which their budget is depleted, through budget-pacing mechanisms. We focus on multiplicative pacing mechanisms in an online setting in which a bidder is repeatedly confronted with a series of advertising opportunities. After collecting bids, each item is then allocated through a single-item, second-price auction. If there were no budgetary constraints, bidding truthfully would be an optimal choice for the advertiser. However, since their budget is limited, the advertiser may want to shade their bid downwards in order to preserve their budget for future opportunities, and to spread expenditures evenly over time. The literature on online pacing problems mostly focuses on the setting in which the bidder optimizes an additive separable objective, such as the total click-through rate or the revenue of the allocation. In many settings, however, bidders may also care about other objectives which oftentimes are non-separable. We study the frequent case in which the utility of a (proxy) bidder depends on the rewards obtained from items they are allocated, and on the distance of the realized distribution of impressions from a target distribution. We introduce a novel regularizer which can describe those distributional preferences, while keeping the problem tractable. We show that this regularizer can be integrated into an existing online mirror descent scheme with minor modifications, attaining the optimal order of sub-linear regret compared to the optimal allocation in hindsight when inputs are drawn independently, from an unknown distribution. Moreover, we show that our approach can easily be incorporated in standard existing pacing systems that are not usually built for this objective. The effectiveness of our algorithm in internet advertising applications is confirmed by numerical experiments on real-world data.