Title: Data-driven Optimization of Online Advertising Auctions
Abstract: Over 300 billion dollars have been spent in online advertising markets during 2019, and this number is expected to grow to almost a trillion by 2025. Auctions are the standard method of selling ads in these markets; thus, optimizing them has ever-increasing importance. In this talk, I discuss my work on improving the performance of one of the most widely used auctions in these markets, the second price auction with reserve prices. This work focuses on optimizing personalized reserve prices with the goal of maximizing revenue. (The reserve price of each buyer is the minimum amount they should bid to be considered in the auction.) To optimize these reserve prices, I take a data-driven approach. That is, given a dataset of buyer’s submitted bids to a set of auctions, the goal is to find a single vector of reserve prices that maximizes the total revenue if used over all these auctions. This is indeed the approach taken by prominent advertising platforms, which generate a massive dataset of auctions daily. They then use this data to optimize the reserve prices for future auctions.
The particular problem studied in this work is shown to be NP-hard, and the best-known approximation factor for that was 0.5 prior to our work. I present a polynomial-time algorithm with a significantly improved approximation factor of 0.68. I also discuss a more general algorithm that works for multi-unit auctions and obtains a 0.63-approximation. Both algorithms are based on novel LP-formulations and rounding procedures, which might be of independent interest.
Bio: Mahsa is a fifth-year Ph.D. candidate in Computer Science at the University of Maryland, advised by MohammdTaghi Hajiaghayi. During her Ph.D. Mahsa has spent a year as an intern at Google and Microsoft Research, and two semesters as a visiting student and Simons Institute for the theory of computing at UC Berkeley. Her main area of research is algorithmic mechanism design with a special focus on designing models and algorithms for online platforms such as online advertising markets, online matching markets, and online retail markets. She is also interested in the design and analysis of big-data algorithms, particularly in distributed and dynamic settings. Mahsa’s research is supported by the Ann G. Wylie Dissertation Fellowship and the 2020 Google Ph.D. Fellowship for Algorithms, Optimizations, and Markets.