Budget Management in Auctions: Bidding Algorithms and Equilibrium Analysis.

다국어 초록 (Multilingual Abstract)

Advertising is the economic engine of the internet. It allows online platforms to fund services that are free at the point of use, while providing businesses the opportunity to target their ads at relevant users. The mechanism of choice for selling these advertising opportunities is real-time auctions: whenever a user visits the platform, an auction is run among interested advertisers, and the winner gets to display their ad to the user. The entire process runs in milliseconds and is implemented via automated algorithms which bid on behalf of the advertisers in every auction. These automated bidders take as input the high-level objectives of the advertiser like value-per-click and budget, and then participate in the auctions with the goal of maximizing the utility of the advertiser subject to budget constraints. Thus motivated, this thesis develops a theory of bidding in auctions under budget constraints, with the goal of informing the design of automated bidding algorithms and analyzing the market-level outcomes that emerge from their simultaneous use.First, we take the perspective of an individual advertiser and tackle algorithm-design questions. How should one bid in repeated second-price auctions subject to a global budget constraint? What is the optimal way to incorporate data into bidding decisions? Can data be incorporated in a way that is robust to common forms of variability in the market? As we analyze these questions, we go beyond the problem of bidding under budget constraints and develop algorithms for more general online resource allocation problems. In Chapter 2, we study a non-stationary stochastic model of sequential auctions, which despite immense practical importance has received little attention, and propose a natural algorithm for it. With access to just one historical sample per auction/distribution, we show that our algorithm attains (nearly) the same performance as that possible under full knowledge of the distributions, while also being robust to distribution shifts which typically occur between the sampling and true distributions. Chapter 3 investigates the impact of uncertainty about the total number of auctions on the performance of bidding algorithms. We prove upper bounds on the best-possible performance that can be achieved in the face of such uncertainty, and propose an algorithm that (nearly) achieves this optimal performance guarantee. We also provide a fast method for incorporating predictions about the total number of auctions into our algorithm. All of our proposed algorithms implement some version of FTRL/Mirror-Descent in the dual space, making them ideal for large-scale low-latency markets like online advertising.Next, we look at the market as a whole and analyze the equilibria which emerge from the simultaneous use of automated bidding algorithms. For example, we address questions like: Does an equilibrium always exist? How does the auction format (first-price vs second-price) impact the structure of the equilibria? Do automated bidding algorithms always efficiently converge to some equilibrium? What are the social welfare properties of these equilibrium outcomes? We systematically examine such questions using a variety of tools, ranging from infinite-dimensional fixed-point arguments for proving existence of structured equilibria, to computational complexity results about finding them. In Chapter 4, we start by establishing the existence of equilibria based on pacing-a practically-popular and theoretically-optimal budget management strategy-for all standard auctions, including first-price and second-price auctions. We then leverage its structure to establish a revenue equivalence result and bound the price of anarchy of liquid welfare. Chapter 5 looks at the market from a computational lens and investigates the complexity of finding pacing-based equilibria. We show that the problem is PPAD complete, which in turn implies the impossibility of polynomial-time convergence of any pacing-based automated bidding algorithms (under standard complexity-theoretic assumptions). Finally, in Chapter 6, we move beyond pacing-based strategies and investigate throttling, which is another popular method for managing budgets in practice. Here, we describe a simple tatonnement-style algorithm which efficiently converges to an equilibrium in first-price auctions, and show that no such algorithm exists for second-price auctions (under standard complexity-theoretic assumptions). Furthermore, we prove tight bounds on the price of anarchy for liquid welfare, and compare platform revenue under throttling and pacing.