Yuan Deng

Yuan Deng

Yuan Deng is a Research Scientist at Google Research New York City. His research is broadly situated at the interface between economics and computer science (aka. algorithmic game theory), mainly including dynamic mechanism design (how to design auctions for online advertisement markets) and learning in economic environments (e.g. online pricing for strategic agents and/or learning agents).
Authored Publications
Sort By
  • Title
  • Title, descending
  • Year
  • Year, descending
    Individual Welfare Guarantees in the Autobidding World with Machine-learned Advice
    Negin Golrezaei
    Patrick Jaillet
    Jason Cheuk Nam Liang
    Proceedings of the ACM on Web Conference 2024, 267–275
    Preview abstract Online advertising channels commonly focus on maximizing total advertiser welfare to enhance channel health, and previous literature has studied augmenting ad auctions with machine learning predictions on advertiser values (also known asmachine-learned advice ) to improve total welfare. Yet, such improvements could come at the cost of individual bidders' welfare and do not shed light on how particular advertiser bidding strategies impact welfare. Motivated by this, we present an analysis on an individual bidder's welfare loss in the autobidding world for auctions with and without machine-learned advice, and also uncover how advertiser strategies relate to such losses. In particular, we demonstrate how ad platforms can utilize ML advice to improve welfare guarantee on the aggregate and individual bidder level by setting ML advice as personalized reserve prices when the platform consists ofautobidders who maximize value while respecting a return on ad spend (ROAS) constraint. Under parallel VCG auctions with such ML advice-based reserves, we present a worst-case welfare lower-bound guarantee for an individual autobidder, and show that the lower-bound guarantee is positively correlated with ML advice quality as well as the scale of bids induced by the autobidder's bidding strategies. Further, we show that no truthful, and possibly randomized mechanism with anonymous allocations can achieve universally better individual welfare guarantees than VCG, in the presence of personalized reserves based on ML-advice of equal quality. Moreover, we extend our individual welfare guarantee results to generalized first price (GFP) and generalized second price (GSP) auctions. Finally, we present numerical studies using semi-synthetic data derived from ad auction logs of a search ad platform to showcase improvements in individual welfare when setting personalized reserve prices with ML-advice. View details
    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
    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
    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 Pricing Schemes for an Impatient Buyer
    Kangning Wang
    Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms(2023), pp. 382-398
    Preview abstract A patient seller aims to sell a good to an impatient buyer (i.e., one who discounts utility over time).The buyer will remain in the market for a period of time T , and her private value is drawn from a publicly known distribution. What is the revenue-optimal pricing-curve (sequence of (price, time) pairs) for the seller? Is randomization of help here? Is the revenue-optimal pricing-curve computable in polynomial time? We answer these questions in this paper. We give an efficient algorithm for computing the revenue-optimal pricing curve. We show that pricing curves, that post a price at each point of time and let the buyer pick her utility maximizing time to buy, are revenue-optimal among a much broader class of sequential lottery mechanisms: namely, mechanisms that allow the seller to post a menu of lotteries at each point of time cannot get any higher revenue than pricing curves. We also show that the even broader class of mechanisms that allow the menu of lotteries to be adaptively set, can earn strictly higher revenue than that of pricing curves, and the revenue gap can be as big as the support size of the buyer’s value distribution. View details
    Multi-channel Autobidding with Budget and ROI Constraints
    Negin Golrezaei
    Patrick Jaillet
    Jason Cheuk Nam Liang
    Proceedings of the 40th International Conference on Machine Learning(2023), 7617–7644
    Preview abstract In digital online advertising, advertisers procure ad impressions simultaneously on multiple platforms, or so-called channels, such as Google Ads, Meta Ads Manager, etc., each of which consists of numerous ad auctions. We study how an advertiser maximizes total conversion (e.g. ad clicks) while satisfying aggregate return-on-investment (ROI) and budget constraints across all channels. In practice, an advertiser does not have control over, and thus cannot globally optimize, which individual ad auctions she participates in for each channel, and instead authorizes a channel to procure impressions on her behalf: the advertiser can only utilize two levers on each channel, namely setting a per-channel budget and per-channel target ROI. In this work, we first analyze the effectiveness of each of these levers for solving the advertiser's global multi-channel problem. We show that when an advertiser only optimizes over per-channel ROIs, her total conversion can be arbitrarily worse than what she could have obtained in the global problem. Further, we show that the advertiser can achieve the global optimal conversion when she only optimizes over per-channel budgets. In light of this finding, under a bandit feedback setting that mimics real-world scenarios where advertisers have limited information on ad auctions in each channels and how channels procure ads, we present an efficient learning algorithm that produces per-channel budgets whose resulting conversion approximates that of the global optimal problem. Finally, we argue that all our results hold for both single-item and multi-item auctions from which channels procure impressions on advertisers' behalf. View details
    Approximately Efficient Bilateral Trade
    Kangning Wang
    Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing(2022), 718–721
    Preview abstract We study bilateral trade between two strategic agents. The celebrated result of Myerson and Satterthwaite states that in general, no incentive-compatible, individually rational and weakly budget balanced mechanism can be efficient. I.e., no mechanism with these properties can guarantee a trade whenever buyer value exceeds seller cost. Given this, a natural question is whether there exists a mechanism with these properties that guarantees a constant fraction of the first-best gains-from-trade, namely a constant fraction of the gains-from-trade attainable whenever buyer’s value weakly exceeds seller’s cost. In this work, we positively resolve this long-standing open question on constant-factor approximation, mentioned in several previous works, using a simple mechanism that obtains a 1/8.23 ≈ 0.121 fraction of the first-best. View details
    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
    Preview abstract We study posted price auctions and dynamic prior-independent mechanisms for (ROI-constrained) value maximizers. In contrast to classic (quasi-linear) utility maximizers, these agents aim to maximize their total value subject to a minimum ratio of value per unit of payment made. When personalized posted prices are allowed, posted price auctions for value maximizers can be reduced to posted price auctions for utility maximizers. However, for anonymous posted prices, the well-known 1/2 approximation for utility maximizers is impossible for value maximizers and we provide a posted price mechanism with 1/2 * (1 - 1/e) approximation. Moreover, we demonstrate how to apply our results to design prior-independent mechanisms in a dynamic environment; and to the best of our knowledge, this gives the first constant revenue approximation with multiple value maximizers. Finally, we provide an extension to combinatorial auctions with submodular / XOS agents. View details
    Welfare-maximizing Guaranteed Dashboard Mechanisms
    Jason Hartline
    Proceedings of the 22nd ACM Conference on Economics and Computation(2021), pp. 370
    Preview abstract Bidding dashboards are used in online marketplaces to aid a bidder in computing good bidding strategies, particularly when the auction used by the marketplace is constrained to have the winners-pay-bid payment format. A dashboard predicts the outcome a bidder can expect to get at each possible bid. To convince a bidder to best respond to the information published in a dashboard, a dashboard mechanism should ensure either (a) that best responding maximizes the bidder's utility (a weaker requirement) or (b) that the mechanism implements the outcome published in the dashboard (a stronger requirement that subsumes (a)). Recent work by Hartline et al. EC'19 formalized the notion of dashboard mechanisms and designed winners-pay-bid mechanisms that guaranteed epsilon-optimal utility (an epsilon-approximate version of (a)), but not (b). I.e., the mechanism could end up implementing arbitrarily different outcomes from what was promised. While this guarantee is sufficient from a purely technical perspective, it is far from enough in the real world: it is hard to convince bidders to best respond to information which could be arbitrarily inaccurate, regardless of the theoretical promise of near-optimality. In this paper we study guaranteed dashboard mechanisms, namely, ones that are guaranteed to implement what they publish, and obtain good welfare. We study this question in a repeated auction setting for general single-dimensional valuations and give tight characterizations of the loss in welfare as a function of natural parameters upper bounding the difference in valuation profile across the rounds. In particular, we give three different characterizations, bounding the loss in welfare in terms of the 0 norm, 1 norm and infinite norm of difference in valuation profile across rounds. All the characterizations generalize at least up to matroid feasibility constraints, and the infinite norm characterization extends to general downward-closed feasibility constraints. We bring to bear different techniques for each of these characterizations, including connections to differential privacy and online convex optimizations. View details