Research Areas
Authored Publications
Sort By
Efficiency of the Generalized Second-Price Auction for Value Maximizers
Hanrui Zhang
Proceedings of the ACM on Web Conference 2024, 46–56
Preview abstract
We study the price of anarchy of the generalized second-price auction where bidders are value maximizers (i.e., autobidders). We show that in general the price of anarchy can be as bad as 0. For comparison, the price of anarchy of running VCG is 1/2 in the autobidding world. We further show a fined-grained price of anarchy with respect to the discount factors (i.e., the ratios of click probabilities between lower slots and the highest slot in each auction) in the generalized second-price auction, which highlights the qualitative relation between the smoothness of the discount factors and the efficiency of the generalized second-price auction.
View details
Mechanism Design for Large Language Models
Paul Duetting
Haifeng Xu
Proceedings of the ACM on Web Conference 2024, Association for Computing Machinery, New York, NY, USA, 144–155
Preview abstract
We investigate auction mechanisms for AI-generated content, focusing on applications like ad creative generation. In our model, agents' preferences over stochastically generated content are encoded as large language models (LLMs). We propose an auction format that operates on a token-by-token basis, and allows LLM agents to influence content creation through single dimensional bids. We formulate two desirable incentive properties and prove their equivalence to a monotonicity condition on output aggregation. This equivalence enables a second-price rule design, even absent explicit agent valuation functions. Our design is supported by demonstrations on a publicly available LLM.
View details
Non-uniform Bid-scaling and Equilibria for Different Auctions: An Empirical Study
Proceedings of the ACM on Web Conference 2024, 256–266
Preview abstract
In recent years, the growing adoption of autobidding has motivated the study of auction design with value-maximizing auto-bidders. It is known that under mild assumptions, uniform bid-scaling is an optimal bidding strategy in truthful auctions, e.g., Vickrey-Clarke-Groves auction (VCG), and the price of anarchy for VCG is 2. However, for other auction formats like First-Price Auction (FPA) and Generalized Second-Price auction (GSP), uniform bid-scaling may not be an optimal bidding strategy, and bidders have incentives to deviate to adopt strategies with non-uniform bid-scaling. Moreover, FPA can achieve optimal welfare if restricted to uniform bid-scaling, while its price of anarchy becomes 2 when non-uniform bid-scaling strategies are allowed.
All these price of anarchy results have been focused on welfare approximation in the worst-case scenarios. To complement theoretical understandings, we empirically study how different auction formats (FPA, GSP, VCG) with different levels of non-uniform bid-scaling perform in an autobidding world with a synthetic dataset for auctions. Our empirical findings include: * For both uniform bid-scaling and non-uniform bid-scaling, FPA is better than GSP and GSP is better than VCG in terms of both welfare and profit; * A higher level of non-uniform bid-scaling leads to lower welfare performance in both FPA and GSP, while different levels of non-uniform bid-scaling have no effect in VCG. Our methodology of synthetic data generation may be of independent interest.
View details
Autobidding Auctions in the Presence of User Costs
Hanrui Zhang
Proceedings of the ACM Web Conference 2023, pp. 3428-3435
Preview abstract
Although costs are prevalent in ad auctions, not many auction theory works study auction design in the presence of cost in the classic settings. One reason is that most auctions design in the setting without cost directly generalize to the setting with cost when the bidders maximizing quasi-linear utility.
However, as auto-bidding becomes a major choice of advertisers in online advertising, the distinction from the underlying behavior model often leads to different solutions of many well-studied auctions. In the context of ad auctions with cost, VCG achieves optimal welfare with quasi-linear utility maximizing bidders, while has 0 welfare approximation guarantee with value maximizing bidders who follow the optimization behind common auto-bidding algorithms.
In this paper, we prove that the approximation welfare guarantee of VCG auction can be significantly improved by a minimal change --- introducing cost multipliers. We note that one can use either one multiplier per auction or one multiplier per bidder, but one global multiplier across all auctions and bidders does not work. Finally, to echo with our theoretical results, we conduct empirical evaluations using semi-synthetic data derived from real auction data of a major advertising platform.
View details
Optimal Mechanisms for Value Maximizers with Budget Constraints via Target Clipping
Proceedings of the 23rd ACM Conference on Economics and Computation(2022), pp. 475
Preview abstract
We study the design of revenue-maximizing mechanisms for value-maximizing agents with budget constraints. Agents have return-on-spend constraints requiring a minimum amount of value per unit of payment made and budget constraints limiting their total payments. The agents' only private information are the minimum admissible ratios on the return-on-spend constraint, referred to as the target ratios.
Our work is motivated by internet advertising platforms, where automated bidders are increasingly being adopted by advertisers to purchase advertising opportunities on their behalf. Instead of specifying bids for each keyword, advertiser set high-level goals, such as maximizing clicks, and targets on cost-per-clicks or return-on-spend, and the platform automatically purchases opportunities by bidding in different auctions. We present a model that abstracts away the complexities of the auto-bidding procurement process that is general enough to accommodate many allocation mechanisms such as auctions, matchings, etc.
We reduce the mechanism design problem when agents have private target ratios to a challenging non-linear optimization problem with monotonicity constraints. We provide a novel decomposition approach to tackle this problem that yields insights into the structure of optimal mechanisms and show that surprising features stem from the interaction on budget and return-on-spend constraints. Our optimal mechanism, which we dub the target-clipping mechanism, has an appealing structure: it sets a threshold on the target ratio of each agent, targets above the threshold are allocated efficiently, and targets below are clipped to the threshold.
View details
Calibrated Click-Through Auctions
Dirk Bergemann
Paul Duetting
Proceedings of the ACM Web Conference 2022, pp. 47-57
Preview abstract
We analyze the optimal information design in a click-through auction with stochastic click-through rates and known valuations per click. The auctioneer takes as given the auction rule of the click-through auction, namely the generalized second-price auction. Yet, the auctioneer can design the information flow regarding the click-through rates among the bidders. We require that the information structure to be calibrated in the learning sense. With this constraint, the auction needs to rank the ads by a product of the value and a calibrated prediction of the click-through rates. The task of designing an optimal information structure is thus reduced to the task of designing an optimal calibrated prediction.
We show that in a symmetric setting with uncertainty about the click-through rates, the optimal information structure attains both social efficiency and surplus extraction. The optimal information structure requires private (rather than public) signals to the bidders. It also requires correlated (rather than independent) signals, even when the underlying uncertainty regarding the click-through rates is independent. Beyond symmetric settings, we show that the optimal information structure requires partial information disclosure, and achieves only partial surplus extraction.
View details
Revenue-Incentive Tradeoffs in Dynamic Reserve Pricing
International Conference on Machine Learning(2021), pp. 2601-2610
Preview abstract
Online advertisements are primarily sold via repeated auctions with reserve prices. In this paper, we study how to set reserves to boost revenue based on the historical bids of strategic buyers, while controlling the impact of such a policy on the incentive compatibility of the repeated auctions. Adopting an incentive compatibility metric which quantifies the incentives to shade bids, we propose a novel class of reserve pricing policies and provide analytical tradeoffs between their revenue performance and bid-shading incentives. The policies are inspired by the exponential mechanism from the literature on differential privacy, but our study uncovers mechanisms with significantly better revenue-incentive tradeoffs than the exponential mechanism in practice. We further empirically evaluate the tradeoffs on synthetic data as well as ad auction data from a major ad exchange to verify and support our theoretical findings.
View details
The Landscape of Autobidding Auctions: Value versus Utility Maximization
Proceedings of the 22nd ACM Conference on Economics and Computation(2021), pp. 132-133
Preview abstract
Internet advertisers are increasingly adopting automated bidders to buy advertising opportunities. Automated bidders simplify the procurement process by allowing advertisers to specify their goals and then bidding on their behalf in the auctions that are used to sell advertising slots. One popular goal adopted by advertisers is to maximize their clicks (or conversions) subject to a return on spend (RoS) constraint, which imposes that the ratio of total value to total spend is greater than a target ratio specified by the advertisers. The emergence of automated bidders brings into question whether the standard mechanisms used to sold ads are still effective in this new landscape. Thus motivated, in this paper we study the problem of characterizing optimal mechanisms for selling an item to one of multiple agents with return on spend constraints when either the values or target ratios are private. We consider two objectives for the agents: value maximization, which is becoming the prevalent objective in advertising markets, and utility maximization, which is the de facto paradigm in economic theory. Our goal is to understand the impact of the agents' private information and their objectives on the seller's revenue, and determine whether the first-best revenue, which is the optimal revenue without private information, is achievable.
View details
Non-Clairvoyant Dynamic Mechanism Design with Budget Constraints and Beyond
Proceedings of the 22nd ACM Conference on Economics and Computation(2021), pp. 369
Preview abstract
We provide a general design framework for dynamic mechanisms under complex environments, coined Lossless History Compression mechanisms. Lossless history compression mechanisms compress the history into a state carrying the least historical information without losing any generality in terms of either revenue or welfare. In particular, the characterization works for almost arbitrary constraints on the outcomes, and any objective function defined on the historical reports, allocations, and the cumulative payments. We then apply our framework to design a non-clairvoyant dynamic mechanism under budget and ex-post individual rationality constraints that is dynamic incentive-compatible and achieves non-trivial revenue performance, even without any knowledge about the future. In particular, our dynamic mechanism obtains a constant approximation to the optimal dynamic mechanism having access to all information in advance. To the best of our knowledge, this is the first dynamic mechanism that achieves a constant approximation and strictly respects dynamic incentive-compatibility and budget constraints without relying on any forecasts of the future.
View details
Preview abstract
Auto-bidding has become one of the main options for bidding in online advertisements, in which advertisers only need to specify high-level objectives and leave the complex task of bidding to auto-bidders. In this paper, we propose a family of auctions with boosts to improve welfare for auto-bidders with both return on ad spend constraints and budget constraints. Our empirical results validate our theoretical findings and show that both the welfare and revenue can be improved by selecting the weight of the boosts properly.
View details
