Abstract
Title: Autobidding and Auctions
: Over the past few years, more and more Internet advertisers have started using automated bidding for optimizing their advertising campaigns. Advertisers using automated bidding have an optimization goal (e.g. to maximize conversions), and some constraints (e.g. a budget or an upper bound on average cost per conversion), and the automated bidding system optimizes their auction bids on their behalf. In this talk, we discuss several fundamental questions around autobidding and auctions. How should an autobidder bid to optimize their goals? Do optimal bidding algorithms depend on the underlying auction? What happens when all advertisers adopt optimal autobidding? Does an equilibrium exist, and is it efficient? How do we define efficiency in the presence of autobidding? What happens to the equilibrium when the auctioneer uses reserve prices to optimize its revenue? We will attempt to answer some of these questions in this talk. In particular, we will present a practical algorithm for autobidding that is optimal if and only if the underlying auction is truthful. We will show that an equilibrium always exists under certain smoothness conditions and that the price of anarchy is no more than 2. We will also show that the use of reserve prices can increase the price of anarchy, and bound the resulting increase.
This is based on joint work with Ashwinkumar Badanidiyuru, Aranyak Mehta, Andres Perlroth and Junyao Zhao.
Bio: Gagan Aggarwal is a Research Scientist at Google, where she co-leads the Market Algorithms research team. Her research interests are in Algorithmic Game Theory and Approximation Algorithms, as well as their application to online marketplaces. She received her PhD in Computer Science in 2005 from Stanford University, and her BTech in Computer Science in 2000 from IIT Delhi.
Title: Fast and Fair Lock-Free Locks
: Locks are frequently used in concurrent systems to simplify code and ensure safe access to contended parts of memory. However, they are also known to cause bottlenecks in concurrent code, leading practitioners and theoreticians to sometimes opt for more intricate lock-free implementations. In this talk, I’ll show that, despite the seeming contradiction, it is possible to design practically and theoretically efficient lock-free locks. I’ll discuss how we model and reason about concurrent systems theoretically, and present a lock-free lock algorithm with good bounds on running time and fairness.
Bio: Naama Ben-David is a postdoctoral researcher at VMware. Her primary research interests are in the intersection of theory and practice in distributed and concurrent computing. More specifically, Naama strives to theoretically explain phenomena seen in modern machines, and to use obtained insights to design and analyze practical algorithms for multiprocessor settings. Naama’s work has been recognized with several awards, including an honorable mention for the CMU School of Computer Science Dissertation Award, a PPoPP 2022 best paper award, an NSERC postgraduate scholarship and a Microsoft Research PhD Fellowship. After her postdoc at VMware, she will be joining the Technion as an Assistant Professor.
Title: Simple Mechanisms for Rich Advertising Auctions
Abstract: The study of internet advertising auctions has fueled a lot of growth in the area of Algorithmic Game Theory. The traditional model of sponsored Search Auctions is well studied, but more recently we face a more challenging problem of Rich Advertising Auctions, where advertisers provide multiple ads of different sizes and a bid per click. This gives rise to a challenging computational problem of finding the optimal set of ads to fit within a fixed amount of space and a more challenging auction design problem of soliciting true preferences from the advertisers. In this talk, I will describe our recent result that provides a truthful auction that obtains a 3-approximation to the optimal allocation. I will also discuss an extension where with a non-truthful mechanism we prove a 6-approximation in the worst Nash equilibrium.
Bio: Kshipra Bhawalkar is a Research Scientist at Google Research in Mountain View, CA. Her research interest is in Algorithmic Game Theory with applications to online ad auctions and related optimization questions. Kshipra obtained her PhD from Stanford University in 2013 and obtained her bachelors from Duke University.