Learning in Repeated Auctions with Budgets: Regret Minimization and Equilibrium
Learning in Repeated Auctions with Budgets: Regret Minimization and Equilibrium
复制标题
在预算重复拍卖中学习：遗憾最小化和均衡
DOI：
10.2139/ssrn.2921446
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Andrey Fradkin
中科院分区：
文献类型：
--
作者：
Andrey Fradkin
在在线广告市场中，广告商通常基于实现的观众信息通过在重复拍卖中的投标来购买广告位置。我们研究了当未来的投标机会以及竞争对手的异质性偏好和预算存在不确定性时，受约束的广告客户如何在竞争中投标。我们将这个问题表述为不完全信息的序列博弈，投标人既不知道自己的估值分布，也不知道竞争对手的预算和估值分布。我们介绍了一个家庭的动态投标策略，我们称之为“自适应起搏”的策略，广告客户调整他们的出价在整个活动中根据观察到的支出的样本路径。我们分析了这类策略在不同假设下的竞争对手的行为。在任意竞争者的出价下，我们通过匹配上下界建立了这类策略随着拍卖次数增加的渐近最优性。当所有投标人都采用时，动态收敛到一个易于处理和有意义的稳定状态。此外，我们表明，这些策略构成了一个近似的纳什均衡动态策略：单方面偏离到其他策略，包括访问完整的信息，变得可以忽略不计的拍卖和竞争对手的数量越来越大的好处。这就建立了遗憾最小化和市场稳定性之间的联系，通过这种联系，广告商可以基本上遵循均衡投标策略，这些策略也可以确保在非均衡状态下的最佳表现。
In online advertising markets, advertisers often purchase ad placements through bidding in repeated auctions based on realized viewer information. We study how budget-constrained advertisers may bid in the presence of competition, when there is uncertainty about future bidding opportunities as well as competitors' heterogenous preferences and budgets. We formulate this problem as a sequential game of incomplete information, where bidders know neither their own valuation distribution, nor the budgets and valuation distributions of their competitors. We introduce a family of dynamic bidding strategies we refer to as "adaptive pacing" strategies, in which advertisers adjust their bids throughout the campaign according to the sample path of observed expenditures. We analyze the performance of this class of strategies under different assumptions on competitors' behavior. Under arbitrary competitors' bids, we establish through matching lower and upper bounds the asymptotic optimality of this class of strategies as the number of auctions grows large. When adopted by all the bidders, the dynamics converge to a tractable and meaningful steady state. Moreover, we show that these strategies constitute an approximate Nash equilibrium in dynamic strategies: The benefit of unilaterally deviating to other strategies, including ones with access to complete information, becomes negligible as the number of auctions and competitors grows large. This establishes a connection between regret minimization and market stability, by which advertisers can essentially follow equilibrium bidding strategies that also ensure the best performance that can be guaranteed off-equilibrium.