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. Finally, we compare the equilibrium outcomes of throttling to those of multiplicative pacing, which is the other most popular and well-studied method of budget management.
翻译:刺激是在线拍卖的一种流行的预算管理方法, 平台在其中调整广告商的参与概率, 以便顺利地在多个拍卖中花费预算。 在这项工作中, 我们调查所有广告商同时使用节拍来管理其预算的场合, 我们这样做是为了第一价格和第二价格拍卖。 我们分析由此产生的平衡的结构和计算特性。 在第一价格拍卖中, 我们显示一个独特的平衡始终存在, 良好地管理, 并且可以通过调和式分散式的动态来有效计算。 相反, 在第二价格拍卖中, 我们证明,即使始终存在一种平衡, 找到平衡的问题仍然是PPAD- 完全的, 也可能存在多重平衡, 并且很难找到收入最大化的平衡。 最后, 我们比较了节拍的平衡结果和倍增速的平衡结果, 这是另一个最受欢迎和研究良好的预算管理方法。