CS Talk
Yiding Feng, Postdoctoral Principal Researcher
University of Chicago Booth School of Business
Host: Yang Cai
Title: Strategic Budget Selection in a Competitive Autobidding World
Abstract: We study a game played between advertisers in an online ad platform. The platform sells ad impressions by first-price auction and provides autobidding algorithms that optimize bids on each advertiser’s behalf, subject to advertiser constraints such as budgets. Crucially, these constraints are strategically chosen by the advertisers. The chosen constraints define an “inner” budget-pacing game for the autobidders. Advertiser payoffs in the constraint-choosing “metagame” are determined by the equilibrium reached by the autobidders.
Advertiser preferences can be more general than what is implied by their constraints: we assume only that they have weakly decreasing marginal value for clicks and weakly increasing marginal disutility for spending money. Nevertheless, we show that at any pure Nash equilibrium of the metagame, the resulting allocation obtains at least half of the liquid welfare of any allocation and this bound is tight. We also obtain a 4-approximation for any mixed Nash equilibrium or Bayes-Nash equilibria. These results rely on the power to declare budgets: if advertisers can specify only a (linear) value per click or an ROI target but not a budget constraint, the approximation factor at equilibrium can be as bad as linear in the number of advertisers.
This is a joint work with Brendan Lucier and Aleksandrs Slivkins from Microsoft Research. A preliminary conference version was accepted at STOC 2024.
Bio:
Yiding Feng is a postdoctoral principal researcher at the University of Chicago Booth School of Business. Previously, he worked as a postdoctoral researcher at Microsoft Research New England from 2021 to 2023. He received his Ph.D. from the Department of Computer Science, Northwestern University in 2021. His primary research focuses on theoretical computer science, economics & computation, and operations research. In August 2024, Yiding will be joining HKUST as an assistant professor.