Throttling is a popular method of budget management for online ad auctions in which the platform modulates the participation probability of an advertiser in order to smoothly spend her budget across many auctions. In this work, we investigate the setting in which all of the advertisers simultaneously employ throttling to manage their budgets, and we do so for both first-price and second-price auctions. We analyze the structural and computational properties of the resulting equilibria. For first-price auctions, we show that a unique equilibrium always exists, is well-behaved and can be computed efficiently via tatonnement-style decentralized dynamics. In contrast, for second-price auctions, we prove that even though an equilibrium always exists, the problem of finding an equilibrium is PPAD-complete, there can be multiple equilibria, and it is NP-hard to find the revenue maximizing one. We also compare the equilibrium outcomes of throttling to those of multiplicative pacing, which is the other most popular and well-studied method of budget management. Finally, we characterize the Price of Anarchy of these equilibria for liquid welfare by showing that it is at most 2 for both first-price and second-price auctions, and demonstrating that our bound is tight.
翻译:在网上拍卖中,我们调查了所有广告商同时使用节拍来管理其预算的场合,我们这样做是为了第一价格和第二价格拍卖。我们分析了由此产生的平衡的结构性和计算性能。在第一价格拍卖中,我们发现一个独特的平衡始终存在,是稳妥的,可以通过调和式的分散式预算动态来有效计算。相比之下,在第二次价格拍卖中,我们证明,尽管始终存在一种平衡,但找到平衡的问题仍然是PPAAD-完整的,但可能存在多重平衡,而且很难找到收入最大化的平衡。我们还将调和的平衡结果与倍增速度的平衡结果相比较,这是另一个最受欢迎和最受研究的预算管理方法。最后,我们把ANASG-价格的第二高价格和最受约束的拍卖价格展示了这种价格。